The Experts below are selected from a list of 9507 Experts worldwide ranked by ideXlab platform
Kunle Olukotun - One of the best experts on this subject based on the ideXlab platform.
-
Chip Multiprocessor architecture techniques to improve throughput and latency
2007Co-Authors: Kunle OlukotunAbstract:Chip Multiprocessors - also called multi-core microprocessors or CMPs for short - are now the only way to build high-performance microprocessors, for a variety of reasons. Large uniprocessors are no longer scaling in performance, because it is only possible to extract a limited amount of parallelism from a typical instruction stream using conventional superscalar instruction issue techniques. In addition, one cannot simply ratchet up the clock speed on today's processors, or the power dissipation will become prohibitive in all but water-cooled systems. Compounding these problems is the simple fact that with the immense numbers of transistors available on today's microprocessor Chips, it is too costly to design and debug ever-larger processors every year or two. CMPs avoid these problems by filling up a processor die with multiple, relatively simpler processor cores instead of just one huge core. The exact size of a CMPs cores can vary from very simple pipelines to moderately complex superscalar processors, but once a core has been selected the CMPs performance can easily scale across silicon process generations simply by stamping down more copies of the hard-to-design, high-speed processor core in each successive Chip generation. In addition, parallel code execution, obtained by spreading multiple threads of execution across the various cores, can achieve significantly higher performance than would be possible using only a single core. While parallel threads are already common in many useful workloads, there are still important workloads that are hard to divide into parallel threads. The low inter-processor communication latency between the cores in a CMP helps make a much wider range of applications viable candidates for parallel execution than was possible with conventional, multi-Chip Multiprocessors; nevertheless, limited parallelism in key applications is the main factor limiting acceptance of CMPs in some types of systems.
-
atlas a Chip Multiprocessor with transactional memory support
Design Automation and Test in Europe, 2007Co-Authors: Njuguna Njoroge, C. Kozyrakis, Jared Casper, Sewook Wee, Yuriy Teslyar, Kunle OlukotunAbstract:Chip-Multiprocessors are quickly becoming popular in embedded systems. However, the practical success of CMPs strongly depends on addressing the difficulty of multithreaded application development for such systems. Transactional memory (TM) promises to simplify concurrency management in multithreaded applications by allowing programmers to specify coarse-grain parallel tasks, while achieving performance comparable to fine-grain lock-based applications. This paper presents ATLAS, the first prototype of a CMP with hardware support for transactional memory. ATLAS includes 8 embedded PowerPC cores that access coherent shared memory in a transactional manner. The data cache for each core is modified to support the speculative buffering and conflict detection necessary for transactional execution. The authors have mapped ATLAS to the BEE2 multi-FPGA board to create a full-system prototype that operates at 100MHz, boots Linux, and provides significant performance and ease-of-use benefits for a range of parallel applications. Overall, the ATLAS prototype provides an excellent framework for further research on the software and hardware techniques necessary to deliver on the potential of transactional memory
-
The common case transactional behavior of multithreaded programs
The Twelfth International Symposium on High-Performance Computer Architecture 2006., 2006Co-Authors: J.w. Chung, H. Chafi, C.c. Minh, A. Mcdonald, B. Carlstrom, C. Kozyrakis, Kunle OlukotunAbstract:Transactional memory (TM) provides an easy-to-use and high-performance parallel programming model for the upcoming Chip-Multiprocessor systems. Several researchers have proposed alternative hardware and software TM implementations. However, the lack of transaction-based programs makes it difficult to understand the merits of each proposal and to tune future TM implementations to the common case behavior of real application. This work addresses this problem by analyzing the common case transactional behavior for 35 multithreaded programs from a wide range of application domains. We identify transactions within the source code by mapping existing primitives for parallelism and synchronization management to transaction boundaries. The analysis covers basic characteristics such as transaction length, distribution of read-set and write-set size, and the frequency of nesting and I/O operations. The measured characteristics provide key insights into the design of efficient TM systems for both non-blocking synchronization and speculative parallelization.
-
improving the performance of speculatively parallel applications on the hydra cmp
International Conference on Supercomputing, 1999Co-Authors: Kunle Olukotun, Lance Hammond, Mark WilleyAbstract:Abstract : Hydra is a Chip Multiprocessor (CMP) with integrated support for thread-level speculation. Thread-level speculation provides a way to parallelize sequential programs without the need for data dependence analysis or synchronization. This makes it possible to parallelize applications for which static memory dependence analysis is difficult or impossible. While performance of the baseline Hydra system on applications with significant amounts of medium to large grain parallelism is good, the performance on integer applications with fine-grained parallelism can be poor. In this paper, we describe a collection of software and hardware techniques for improving speculation performance of the Hydra CMP. These techniques focus on reducing the overheads associated with speculation and improving the speculation behavior of the applications using code restructuring. When these techniques are applied to a set of ten integer, multimedia and floating-point bench-marks, significant performance improvements result.
-
data speculation support for a Chip Multiprocessor
Architectural Support for Programming Languages and Operating Systems, 1998Co-Authors: Lance Hammond, Mark Willey, Kunle OlukotunAbstract:Thread-level speculation is a technique that enables parallel execution of sequential applications on a Multiprocessor. This paper describes the complete implementation of the support for threadlevel speculation on the Hydra Chip Multiprocessor (CMP). The support consists of a number of software speculation control handlers and modifications to the shared secondary cache memory system of the CMP This support is evaluated using five representative integer applications. Our results show that the speculative support is only able to improve performance when there is a substantial amount of medium--grained loop-level parallelism in the application. When the granularity of parallelism is too small or there is little inherent parallelism in the application, the overhead of the software handlers overwhelms any potential performance benefits from speculative-thread parallelism. Overall, thread-level speculation still appears to be a promising approach for expanding the class of applications that can be automatically parallelized, but more hardware intensive implementations for managing speculation control are required to achieve performance improvements on a wide class of integer applications.
Yan Solihin - One of the best experts on this subject based on the ideXlab platform.
-
HAQu: Hardware-accelerated queueing for finegrained threading on a Chip Multiprocessor
2011Co-Authors: Sanghoon Lee, Yan Solihin, Devesh Tiwari, James TuckAbstract:Queues are commonly used in multithreaded programs for synchronization and communication. However, because software queues tend to be too expensive to support finegrained parallelism, hardware queues have been proposed to reduce overhead of communication between cores. Hardware queues require modifications to the processor core and need a custom interconnect. They also pose difficulties for the operating system because their state must be preserved across context switches. To solve these problems, we propose a hardware-accelerated queue, or HAQu. HAQu adds hardware to a CMP that accelerates operations on software queues. Our design implements fast queueing through an application’s address space with operations that are compatible with a fully software queue. Our design provides accelerated and OS-transparent performance in three general ways: (1) it provides a single instruction for enqueueing and dequeueing which significantly reduces the overhead when used in fine-grained threading; (2) operations on the queue are designed to leverage low-level details of the coherence protocol; and (3) hardware ensures that the full state of the queue is stored in the application’s address space, thereby ensuring virtualization. We have evaluated our design in the context of application domains: offloading fine-grained checks for improved software reliability, and automatic, fine-grained parallelization using decoupled software pipelining. 1
-
fair cache sharing and partitioning in a Chip Multiprocessor architecture
International Conference on Parallel Architectures and Compilation Techniques, 2004Co-Authors: Seongbeom Kim, Dhruba Chandra, Yan SolihinAbstract:This paper presents a detailed study of fairness in cache sharing between threads in a Chip Multiprocessor (CMP) architecture. Prior work in CMP architectures has only studied throughput optimization techniques for a shared cache. The issue of fairness in cache sharing, and its relation to throughput, has not been studied. Fairness is a critical issue because the operating system (OS) thread scheduler's effectiveness depends on the hardware to provide fair cache sharing to co-scheduled threads. Without such hardware, serious problems, such as thread starvation and priority inversion, can arise and render the OS scheduler ineffective. This paper makes several contributions. First, it proposes and evaluates five cache fairness metrics that measure the degree of fairness in cache sharing, and shows that two of them correlate very strongly with the execution-time fairness. Execution-time fairness is defined as how uniform the execution times of co-scheduled threads are changed, where each change is relative to the execution time of the same thread running alone. Secondly, using the metrics, the paper proposes static and dynamic L2 cache partitioning algorithms that optimize fairness. The dynamic partitioning algorithm is easy to implement, requires little or no profiling, has low overhead, and does not restrict the cache replacement algorithm to LRU. The static algorithm, although requiring the cache to maintain LRU stack information, can help the OS thread scheduler to avoid cache thrashing. Finally, this paper studies the relationship between fairness and throughput in detail. We found that optimizing fairness usually increases throughput, while maximizing throughput does not necessarily improve fairness. Using a set of co-scheduled pairs of benchmarks, on average our algorithms improve fairness by a factor of 4/spl times/, while increasing the throughput by 15%, compared to a nonpartitioned shared cache.
-
fair cache sharing and partitioning in a Chip Multiprocessor architecture
International Conference on Parallel Architectures and Compilation Techniques, 2004Co-Authors: Seongbeom Kim, Dhruba Chandra, Yan SolihinAbstract:This paper presents a detailed study of fairness in cache sharing between threads in a Chip Multiprocessor (CMP) architecture. Prior work in CMP architectures has only studied throughput optimization techniques for a shared cache. The issue of fairness in cache sharing, and its relation to throughput, has not been studied. Fairness is a critical issue because the Operating System (OS) thread scheduler's effectiveness depends on the hardware to provide fair cache sharing to co-scheduled threads. Without such hardware, serious problems, such as thread starvation and priority inversion, can arise and render the OS scheduler ineffective. This paper makes several contributions. First, it proposes and evaluates five cache fairness metrics that measure the degree of fairness in cache sharing, and shows that two of them correlate very strongly with the execution-time fairness. Execution-time fairness is defined as how uniform the execution times of co-scheduled threads are changed, where each change is relative to the execution time of the same thread running alone. Secondly, using the metrics, the paper proposes static and dynamic L2 cache partitioning algorithms that optimize fairness. The dynamic partitioning algorithm is easy to implement, requires little or no profiling, has low overhead, and does not restrict the cache replacement algorithm to LRU. The static algorithm, although requiring the cache to maintain LRU stack information, can help the OS thread scheduler to avoid cache thrashing. Finally, this paper studies the relationship between fairness and throughput in detail. We found that optimizing fairness usually increases throughput, while maximizing throughput does not necessarily improve fairness. Using a set of co-scheduled pairs of benchmarks, on average our algorithms improve fairness by a factor of 4x, while increasing the throughput by 15%, compared to a non-partitioned shared cache.
Athanasios V Vasilakos - One of the best experts on this subject based on the ideXlab platform.
-
loop parallelism maximization for multimedia data processing in mobile vehicular clouds
IEEE Transactions on Cloud Computing, 2019Co-Authors: Meikang Qiu, Wenyun Dai, Athanasios V VasilakosAbstract:Mobile vehicular cloud has become popular with the rapid development of cloud computing and mobile computing. Nested loops are usually the most critical part in multimedia and high performance Digital Signal Processing (DSP) systems which are widely used in vehicular applications and systems. In order to further explore the parallelism in nested loops, we study how to maximize the system performance with considering the energy reduction for applications on Chip Multiprocessor (CMP) architectures. We propose an algorithm Energy-Aware Loop Parallelism Maximization (EALPM) to maximize the system performance with the consideration of energy reduction for applications with multidimensional nested loops. Our experiment shows that using the EALPM algorithm significantly improves both performance and energy consumption on average in comparision to other algorithms.
Seongbeom Kim - One of the best experts on this subject based on the ideXlab platform.
-
fair cache sharing and partitioning in a Chip Multiprocessor architecture
International Conference on Parallel Architectures and Compilation Techniques, 2004Co-Authors: Seongbeom Kim, Dhruba Chandra, Yan SolihinAbstract:This paper presents a detailed study of fairness in cache sharing between threads in a Chip Multiprocessor (CMP) architecture. Prior work in CMP architectures has only studied throughput optimization techniques for a shared cache. The issue of fairness in cache sharing, and its relation to throughput, has not been studied. Fairness is a critical issue because the operating system (OS) thread scheduler's effectiveness depends on the hardware to provide fair cache sharing to co-scheduled threads. Without such hardware, serious problems, such as thread starvation and priority inversion, can arise and render the OS scheduler ineffective. This paper makes several contributions. First, it proposes and evaluates five cache fairness metrics that measure the degree of fairness in cache sharing, and shows that two of them correlate very strongly with the execution-time fairness. Execution-time fairness is defined as how uniform the execution times of co-scheduled threads are changed, where each change is relative to the execution time of the same thread running alone. Secondly, using the metrics, the paper proposes static and dynamic L2 cache partitioning algorithms that optimize fairness. The dynamic partitioning algorithm is easy to implement, requires little or no profiling, has low overhead, and does not restrict the cache replacement algorithm to LRU. The static algorithm, although requiring the cache to maintain LRU stack information, can help the OS thread scheduler to avoid cache thrashing. Finally, this paper studies the relationship between fairness and throughput in detail. We found that optimizing fairness usually increases throughput, while maximizing throughput does not necessarily improve fairness. Using a set of co-scheduled pairs of benchmarks, on average our algorithms improve fairness by a factor of 4/spl times/, while increasing the throughput by 15%, compared to a nonpartitioned shared cache.
-
fair cache sharing and partitioning in a Chip Multiprocessor architecture
International Conference on Parallel Architectures and Compilation Techniques, 2004Co-Authors: Seongbeom Kim, Dhruba Chandra, Yan SolihinAbstract:This paper presents a detailed study of fairness in cache sharing between threads in a Chip Multiprocessor (CMP) architecture. Prior work in CMP architectures has only studied throughput optimization techniques for a shared cache. The issue of fairness in cache sharing, and its relation to throughput, has not been studied. Fairness is a critical issue because the Operating System (OS) thread scheduler's effectiveness depends on the hardware to provide fair cache sharing to co-scheduled threads. Without such hardware, serious problems, such as thread starvation and priority inversion, can arise and render the OS scheduler ineffective. This paper makes several contributions. First, it proposes and evaluates five cache fairness metrics that measure the degree of fairness in cache sharing, and shows that two of them correlate very strongly with the execution-time fairness. Execution-time fairness is defined as how uniform the execution times of co-scheduled threads are changed, where each change is relative to the execution time of the same thread running alone. Secondly, using the metrics, the paper proposes static and dynamic L2 cache partitioning algorithms that optimize fairness. The dynamic partitioning algorithm is easy to implement, requires little or no profiling, has low overhead, and does not restrict the cache replacement algorithm to LRU. The static algorithm, although requiring the cache to maintain LRU stack information, can help the OS thread scheduler to avoid cache thrashing. Finally, this paper studies the relationship between fairness and throughput in detail. We found that optimizing fairness usually increases throughput, while maximizing throughput does not necessarily improve fairness. Using a set of co-scheduled pairs of benchmarks, on average our algorithms improve fairness by a factor of 4x, while increasing the throughput by 15%, compared to a non-partitioned shared cache.
Meikang Qiu - One of the best experts on this subject based on the ideXlab platform.
-
loop parallelism maximization for multimedia data processing in mobile vehicular clouds
IEEE Transactions on Cloud Computing, 2019Co-Authors: Meikang Qiu, Wenyun Dai, Athanasios V VasilakosAbstract:Mobile vehicular cloud has become popular with the rapid development of cloud computing and mobile computing. Nested loops are usually the most critical part in multimedia and high performance Digital Signal Processing (DSP) systems which are widely used in vehicular applications and systems. In order to further explore the parallelism in nested loops, we study how to maximize the system performance with considering the energy reduction for applications on Chip Multiprocessor (CMP) architectures. We propose an algorithm Energy-Aware Loop Parallelism Maximization (EALPM) to maximize the system performance with the consideration of energy reduction for applications with multidimensional nested loops. Our experiment shows that using the EALPM algorithm significantly improves both performance and energy consumption on average in comparision to other algorithms.
-
thermal aware task scheduling in 3d Chip Multiprocessor with real time constrained workloads
ACM Transactions in Embedded Computing Systems, 2013Co-Authors: Meikang Qiu, Jianwei Niu, Laurence T Yang, Yongxin Zhu, Zhong MingAbstract:Chip Multiprocessor (CMP) techniques have been implemented in embedded systems due to tremendous computation requirements. Three-dimension (3D) CMP architecture has been studied recently for integrating more functionalities and providing higher performance. The high temperature on Chip is a critical issue for the 3D architecture. In this article, we propose an online thermal prediction model for 3D Chips. Using this model, we propose novel task scheduling algorithms based on rotation scheduling to reduce the peak temperature on Chip. We consider data dependencies, especially inter-iteration dependencies that are not well considered in most of the current thermal-aware task scheduling algorithms. Our simulation results show that our algorithms can efficiently reduce the peak temperature up to 8.1ˆC.