The Experts below are selected from a list of 606 Experts worldwide ranked by ideXlab platform
Okkyoon Ha - One of the best experts on this subject based on the ideXlab platform.
-
efficient thread labeling for on the fly race detection of programs with Nested Parallelism
International Conference on Advanced Software Engineering and Its Applications, 2011Co-Authors: Okkyoon HaAbstract:It is quite difficult to detect data races in parallel programs, because they may lead to unintended nondeterministic executions of the program. To detect data races during an execution of program that may have Nested Parallelism, it is important to maintain thread information called label which is used to determine the logical concurrency between threads. Unfortunately, the previous schemes of thread labeling introduce a serious amount of overhead that includes serializing bottleneck to access centralized data structure or depends on the maximum Parallelism or the depth of Nested Parallelism. This paper presents an efficient thread labeling, called eNR Labeling, which does not use any centralized data structure and creates thread labels on every thread operation in a constant amount of time and space even in its worst case. Furthermore, this technique allows to determine the logical concurrency between threads in a small amount of time that is proportional only to the depth of Nested Parallelism. Compared with three state-of-the-arts labeling schemes, our empirical results using OpenMP benchmarks show that eNR labeling reduces both time overhead by 10% and space overhead by more than 90% for on-the-fly race detection.
-
FGIT-ASEA/DRBC/EL - Efficient Thread Labeling for On-the-fly Race Detection of Programs with Nested Parallelism
Communications in Computer and Information Science, 2011Co-Authors: Okkyoon HaAbstract:It is quite difficult to detect data races in parallel programs, because they may lead to unintended nondeterministic executions of the program. To detect data races during an execution of program that may have Nested Parallelism, it is important to maintain thread information called label which is used to determine the logical concurrency between threads. Unfortunately, the previous schemes of thread labeling introduce a serious amount of overhead that includes serializing bottleneck to access centralized data structure or depends on the maximum Parallelism or the depth of Nested Parallelism. This paper presents an efficient thread labeling, called eNR Labeling, which does not use any centralized data structure and creates thread labels on every thread operation in a constant amount of time and space even in its worst case. Furthermore, this technique allows to determine the logical concurrency between threads in a small amount of time that is proportional only to the depth of Nested Parallelism. Compared with three state-of-the-arts labeling schemes, our empirical results using OpenMP benchmarks show that eNR labeling reduces both time overhead by 10% and space overhead by more than 90% for on-the-fly race detection.
-
efficiency of e nr labeling for on the fly race detection of programs with Nested Parallelism
Ubiquitous Computing, 2011Co-Authors: Okkyoon HaAbstract:On-the-fly race detector using Lamport’s happened-before relation needs thread labeling scheme for generating unique identifiers which maintain logical concurrency information for the parallel thread. e-NR labeling creates the NR labels by inheriting from the parent thread a pointer to their shared information, so it requires constant amount of time and space overhead on every fork/join operation. Previous work compares e-NR labeling only with OS labeling using a set of synthetic programs to support that e-NR labeling is efficient in detecting races during an execution of programs with Nested Parallelism. This paper compares empirically e-NR labeling with BD labeling that shows the same complexity of space and time with OS labeling. The results using OpenMP benchmarks with Nested Parallelism show that e-NR labeling is more efficient than T-BD labeling by at least 2 times in total monitoring time for race detection, and by at least 3 times in average space for maintaining thread labels.
-
UCMA (2) - Efficiency of e-NR Labeling for On-the-fly Race Detection of Programs with Nested Parallelism
Communications in Computer and Information Science, 2011Co-Authors: Okkyoon HaAbstract:On-the-fly race detector using Lamport’s happened-before relation needs thread labeling scheme for generating unique identifiers which maintain logical concurrency information for the parallel thread. e-NR labeling creates the NR labels by inheriting from the parent thread a pointer to their shared information, so it requires constant amount of time and space overhead on every fork/join operation. Previous work compares e-NR labeling only with OS labeling using a set of synthetic programs to support that e-NR labeling is efficient in detecting races during an execution of programs with Nested Parallelism. This paper compares empirically e-NR labeling with BD labeling that shows the same complexity of space and time with OS labeling. The results using OpenMP benchmarks with Nested Parallelism show that e-NR labeling is more efficient than T-BD labeling by at least 2 times in total monitoring time for race detection, and by at least 3 times in average space for maintaining thread labels.
-
efficient thread labeling for monitoring programs with Nested Parallelism
International Conference on Future Generation Communication and Networking, 2010Co-Authors: Okkyoon HaAbstract:It is difficult and cumbersome to detect data races occurred in an execution of parallel programs. Any on-the-fly race detection techniques using Lamport’s happened-before relation needs a thread labeling scheme for generating unique identifiers which maintain logical concurrency information for the parallel threads. NR labeling is an efficient thread labeling scheme for the fork-join program model with Nested Parallelism, because its efficiency depends only on the nesting depth for every fork and join operation. This paper presents an improved NR labeling, called e-NR labeling, in which every thread generates its label by inheriting the pointer to its ancestor list from the parent threads or by updating the pointer in a constant amount of time and space. This labeling is more efficient than the NR labeling, because its efficiency does not depend on the nesting depth for every fork and join operation. Some experiments were performed with OpenMP programs having nesting depths of three or four and maximum Parallelisms varying from 10,000 to 1,000,000. The results show that e-NR is 5 times faster than NR labeling and 4.3 times faster than OS labeling in the average time for creating and maintaining the thread labels. In average space required for labeling, it is 3.5 times smaller than NR labeling and 3 times smaller than OS labeling.
Guy E. Blelloch - One of the best experts on this subject based on the ideXlab platform.
-
space efficient scheduling of Nested Parallelism
ACM Transactions on Programming Languages and Systems, 1999Co-Authors: Girija J Narlikar, Guy E. BlellochAbstract:Many of today's high-level parallel languages support dynamic, fine-grained Parallelism. These languages allow the user to expose all the Parallelism in the program, which is typically of a much higher degree than the number of processors. Hence an efficient scheduling algorithm is required to assign computations to processors at runtime. Besides having low overheads and good load balancing, it is important for the scheduling algorithm to minimize the space usage of the parallel program. This article presents an on-line scheduling algorithm that is provably space efficient and time efficient for Nested-parallel languages. For a computation with depth D and serial space requirement S 1 , the algorithm generates a schedule that requires at most S 1 + O (K•D•p ) space (including scheduler space) on p processors. Here, K is a user-adjustable runtime parameter specifying the net amount of memory that a thread may allocate before it is preempted by the scheduler. Adjusting the value of K provides a trade-off between the running time and the memory requirement of a parallel computation. To allow the scheduler to scale with the number of processors we also parallelize the scheduler and analyze the space and time bounds of the computation to include scheduling costs. In addition to showing that the scheduling algorithm is space and time efficient in theory, we demonstrate that it is effective in practice. We have implemented a runtime system that uses our algorithm to schedule lightweight parallel threads. The results of executing parallel programs on this system show that our scheduling algorithm significantly reduces memory usage compared to previous techniques, without compromising performance.
-
space efficient implementation of Nested Parallelism
ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, 1997Co-Authors: Girija J Narlikar, Guy E. BlellochAbstract:Many of today's high level parallel languages support dynamic, fine-grained Parallelism. These languages allow the user to expose all the Parallelism in the program, which is typically of a much higher degree than the number of processors. Hence an efficient scheduling algorithm is required to assign computations to processors at runtime. Besides having low overheads and good load balancing, it is important for the scheduling algorithm to minimize the space usage of the parallel program. This paper presents a scheduling algorithm that is provably space-efficient and time-efficient for Nested parallel languages. In addition to proving the space and time bounds of the parallel schedule generated by the algorithm, we demonstrate that it is efficient in practice. We have implemented a runtime system that uses our algorithm to schedule parallel threads. The results of executing parallel programs on this system show that our scheduling algorithm significantly reduces memory usage compared to previous techniques, without compromising performance.
-
PPOPP - Space-efficient implementation of Nested Parallelism
Proceedings of the sixth ACM SIGPLAN symposium on Principles and practice of parallel programming - PPOPP '97, 1997Co-Authors: Girija J Narlikar, Guy E. BlellochAbstract:Many of today's high level parallel languages support dynamic, fine-grained Parallelism. These languages allow the user to expose all the Parallelism in the program, which is typically of a much higher degree than the number of processors. Hence an efficient scheduling algorithm is required to assign computations to processors at runtime. Besides having low overheads and good load balancing, it is important for the scheduling algorithm to minimize the space usage of the parallel program. This paper presents a scheduling algorithm that is provably space-efficient and time-efficient for Nested parallel languages. In addition to proving the space and time bounds of the parallel schedule generated by the algorithm, we demonstrate that it is efficient in practice. We have implemented a runtime system that uses our algorithm to schedule parallel threads. The results of executing parallel programs on this system show that our scheduling algorithm significantly reduces memory usage compared to previous techniques, without compromising performance.
-
Compiling collection-oriented languages onto massively parallel computers
Journal of Parallel and Distributed Computing, 1990Co-Authors: Guy E. Blelloch, Gary W. SabotAbstract:Abstract This paper introduces techniques for compiling the Nested Parallelism of collection-oriented languages onto existing parallel hardware. Programmers of parallel machines encounter Nested Parallelism whenever they write a routine that performs parallel operations, and then want to call that routine itself in parallel. This occurs naturally in many applications. Most parallel systems, however, do not permit the expression of Nested Parallelism. This forces the programmer to exploit only one level of Parallelism or to implement Nested Parallelism themselves. Both of these alternatives tend to produce code that is harder to maintain and less modular than code described at a higher level with Nested parallel constructs. Not permitting the expression of Nested Parallelism is analogous to not permitting Nested loops in serial languages. This paper describes issues and techniques for taking high-level descriptions of Parallelism in the form of operations on Nested collections and automatically translating them into flat, single-level Parallelism. A compiler that translates a subset of a collection-oriented language, Paralation Lisp , into the instruction set of a flat virtual machine is presented. The instructions of the virtual machine are simple instructions on vectors of atomic values, and can be implemented on a broad class of target architectures, including vector machines, single-instruction parallel machines, and multiple-instruction parallel machines. We have implemented the instructions on the Connection Machine computer (CM-2), a massively parallel, single-instruction computer. As an illustration of the compiler techniques, the paper presents a quicksort example. The example has been tested on the CM-2. The speed of the compiled sort is only a factor of 3 slower than that of the fastest CM-2 sort.
David Gregg - One of the best experts on this subject based on the ideXlab platform.
-
PACT - An Efficient Vectorization Approach to Nested Thread-level Parallelism for CUDA GPUs
2015 International Conference on Parallel Architecture and Compilation (PACT), 2015Co-Authors: Shixiong Xu, David GreggAbstract:Nested thread-level Parallelism (TLP) is pervasive in real applications. For example, 75% (14 out of 19) of the applications in the Rodinia benchmark for heterogeneous accelerators contain kernels with Nested thread-level Parallelism. Efficiently mapping the enclosed Nested Parallelism to the GPU threads in the C-to-CUDA compilation (OpenACC in this paper) is becoming more and more important. This mapping problem is two folds: suitable execution models and efficient mapping strategies of the Nested Parallelism.
-
An Efficient Vectorization Approach to Nested Thread-level Parallelism for CUDA GPUs
2015 International Conference on Parallel Architecture and Compilation (PACT), 2015Co-Authors: Shixiong Xu, David GreggAbstract:Nested thread-level Parallelism (TLP) is pervasive in real applications. For example, 75% (14 out of 19) of the applications in the Rodinia benchmark for heterogeneous accelerators contain kernels with Nested thread-level Parallelism. Efficiently mapping the enclosed Nested Parallelism to the GPU threads in the C-to-CUDA compilation (OpenACC in this paper) is becoming more and more important. This mapping problem is two folds: suitable execution models and efficient mapping strategies of the Nested Parallelism.
Daniel Sanchez - One of the best experts on this subject based on the ideXlab platform.
-
fractal an execution model for fine grain Nested speculative Parallelism
International Symposium on Computer Architecture, 2017Co-Authors: Suvinay Subramanian, Mark C Jeffrey, Maleen Abeydeera, Victor A Ying, Joel Emer, Daniel SanchezAbstract:Most systems that support speculative parallelization, like hardware transactional memory (HTM), do not support Nested Parallelism. This sacrifices substantial Parallelism and precludes composing parallel algorithms. And the few HTMs that do support Nested Parallelism focus on parallelizing at the coarsest (shallowest) levels, incurring large overheads that squander most of their potential. We present FRACTAL, a new execution model that supports unordered and timestamp-ordered Nested Parallelism. FRACTAL lets programmers seamlessly compose speculative parallel algorithms, and lets the architecture exploit Parallelism at all levels. FRACTAL can parallelize a broader range of applications than prior speculative execution models. We design a FRACTAL implementation that extends the Swarm architecture and focuses on parallelizing at the finest (deepest) levels. Our approach sidesteps the issues of Nested parallel HTMs and uncovers abundant fine-grain Parallelism. As a result, FRACTAL outperforms prior speculative architectures by up to 88x at 256 cores.
-
ISCA - Fractal: An Execution Model for Fine-Grain Nested Speculative Parallelism
Proceedings of the 44th Annual International Symposium on Computer Architecture, 2017Co-Authors: Suvinay Subramanian, Mark C Jeffrey, Maleen Abeydeera, Victor A Ying, Joel Emer, Daniel SanchezAbstract:Most systems that support speculative parallelization, like hardware transactional memory (HTM), do not support Nested Parallelism. This sacrifices substantial Parallelism and precludes composing parallel algorithms. And the few HTMs that do support Nested Parallelism focus on parallelizing at the coarsest (shallowest) levels, incurring large overheads that squander most of their potential. We present FRACTAL, a new execution model that supports unordered and timestamp-ordered Nested Parallelism. FRACTAL lets programmers seamlessly compose speculative parallel algorithms, and lets the architecture exploit Parallelism at all levels. FRACTAL can parallelize a broader range of applications than prior speculative execution models. We design a FRACTAL implementation that extends the Swarm architecture and focuses on parallelizing at the finest (deepest) levels. Our approach sidesteps the issues of Nested parallel HTMs and uncovers abundant fine-grain Parallelism. As a result, FRACTAL outperforms prior speculative architectures by up to 88x at 256 cores.
Luca Benini - One of the best experts on this subject based on the ideXlab platform.
-
controlling numa effects in embedded manycore applications with lightweight Nested Parallelism support
Parallel Computing, 2016Co-Authors: Andrea Marongiu, Alessandro Capotondi, Luca BeniniAbstract:Lightweight Nested Parallelism support for NUMA embedded many-cores is proposed.SW- and HW-accelerated solutions are explored and integrated in OpenMP.Implementation is provided on a real manycore (STMicroelectronics STHORM).We achieve 28 speedup VS flat Parallelism on several real embedded applications. Embedded manycore architectures are often organized as fabrics of tightly-coupled shared memory clusters. A hierarchical interconnection system is used with a crossbar-like medium inside each cluster and a network-on-chip (NoC) at the global level which make memory operations nonuniform (NUMA). Due to NUMA, regular applications typically employed in the embedded domain (e.g., image processing, computer vision, etc.) ultimately behave as irregular workloads if a flat memory system is assumed at the program level. Nested Parallelism represents a powerful programming abstraction for these architectures, provided that (i) streamlined middleware support is available, whose overhead does not dominate the run-time of fine-grained applications; (ii) a mechanism to control thread binding at the cluster-level is supported. We present a lightweight runtime layer for Nested Parallelism on cluster-based embedded manycores, integrating our primitives in the OpenMP runtime system, and implementing a new directive to control NUMA-aware Nested Parallelism mapping. We explore on a set of real application use cases how NUMA makes regular parallel workloads behave as irregular, and how our approach allows to control such effects and achieve up to 28 speedup versus flat Parallelism.
-
MCSoC - Enabling Scalable and Fine-Grained Nested Parallelism on Embedded Many-cores
2015 IEEE 9th International Symposium on Embedded Multicore Many-core Systems-on-Chip, 2015Co-Authors: Alessandro Capotondi, Andrea Marongiu, Luca BeniniAbstract:Current high-end embedded systems are designed as heterogeneous systems-on-chip (SoCs), where a general-purpose host processor is coupled to a programmable manycore accelerator (PMCA). Such PMCAs typically leverage hierarchical interconnect and distributed memory with non-uniform access (NUMA). Nested Parallelism is a convenient programming abstraction for large-scale cc-NUMA systems, which allows to hierarchically (and dynamically) create multiple levels of fine-grained Parallelism whenever it is available. Available implementations for cc-NUMA systems introduce large overheads for Nested Parallelism management, which cannot be tolerated due to the extremely fine-grained nature of embedded parallel workloads. In particular, creating a team of parallel threads has a cost that increases linearly with the number of threads, which is inherently non scalable. This work presents a software cache mechanism for frequently-used parallel team configurations to speed up parallel thread creation overheads in PMCA systems. When a configuration is found in the cache the cost for parallel team creation has a constant time, providing a scalable mechanism. We evaluated our support on the STMicroelectronics STHORM many-core. Compared to the state-of-the art, our solution shows that: i) the cost for parallel team creation is reduced by up to 67%, ii) the tangible effect on real ultra-fine-grained parallel kernels is a speedup of up to 80%.
-
Enabling Scalable and Fine-Grained Nested Parallelism on Embedded Many-cores
2015 IEEE 9th International Symposium on Embedded Multicore Many-core Systems-on-Chip, 2015Co-Authors: Alessandro Capotondi, Andrea Marongiu, Luca BeniniAbstract:Current high-end embedded systems are designed as heterogeneous systems-on-chip (SoCs), where a general-purpose host processor is coupled to a programmable manycore accelerator (PMCA). Such PMCAs typically leverage hierarchical interconnect and distributed memory with non-uniform access (NUMA). Nested Parallelism is a convenient programming abstraction for large-scale cc-NUMA systems, which allows to hierarchically (and dynamically) create multiple levels of fine-grained Parallelism whenever it is available. Available implementations for cc-NUMA systems introduce large overheads for Nested Parallelism management, which cannot be tolerated due to the extremely fine-grained nature of embedded parallel workloads. In particular, creating a team of parallel threads has a cost that increases linearly with the number of threads, which is inherently non scalable. This work presents a software cache mechanism for frequently-used parallel team configurations to speed up parallel thread creation overheads in PMCA systems. When a configuration is found in the cache the cost for parallel team creation has a constant time, providing a scalable mechanism. We evaluated our support on the STMicroelectronics STHORM many-core. Compared to the state-of-the art, our solution shows that: i) the cost for parallel team creation is reduced by up to 67%, ii) the tangible effect on real ultra-fine-grained parallel kernels is a speedup of up to 80%.
-
Fast and lightweight support for Nested Parallelism on cluster-based embedded many-cores
2012 Design Automation & Test in Europe Conference & Exhibition (DATE), 2012Co-Authors: Andrea Marongiu, Paolo Burgio, Luca BeniniAbstract:Several recent many-core accelerators have been architected as fabrics of tightly-coupled shared memory clusters. A hierarchical interconnection system is used - with a crossbar-like medium inside each cluster and a network-on-chip (NoC) at the global level - which make memory operations non-uniform (NUMA). Nested Parallelism represents a powerful programming abstraction for these architectures, where a first level of Parallelism can be used to distribute coarse-grained tasks to clusters, and additional levels of fine-grained Parallelism can be distributed to processors within a cluster. This paper presents a lightweight and highly optimized support for Nested Parallelism on cluster-based embedded many-cores. We assess the costs to enable multi-level parallelization and demonstrate that our techniques allow to extract high degrees of Parallelism.
-
DATE - Fast and lightweight support for Nested Parallelism on cluster-based embedded many-cores
2012 Design Automation & Test in Europe Conference & Exhibition (DATE), 2012Co-Authors: Andrea Marongiu, Paolo Burgio, Luca BeniniAbstract:Several recent many-core accelerators have been architected as fabrics of tightly-coupled shared memory clusters. A hierarchical interconnection system is used -- with a crossbar-like medium inside each cluster and a network-on-chip (NoC) at the global level -- which make memory operations non-uniform (NUMA). Nested Parallelism represents a powerful programming abstraction for these architectures, where a first level of Parallelism can be used to distribute coarse-grained tasks to clusters, and additional levels of fine-grained Parallelism can be distributed to processors within a cluster. This paper presents a lightweight and highly optimized support for Nested Parallelism on cluster-based embedded many-cores. We assess the costs to enable multi-level parallelization and demonstrate that our techniques allow to extract high degrees of Parallelism.