检索结果-内蒙古大学图书馆

nested parallelism with Algorithmic Skeletons 1

31st International Workshop on Languages and Compilers for Parallel Computing (LCPC)

作者： Majidi, Alireza Thomas, Nathan Smith, Timmie Amato, Nancy Rauchwerger, Lawrence Texas A&M Univ College Stn TX 77840 USA

ISBN: (数字)9783030346270

ISBN: (纸本)9783030346270;9783030346263

nested parallelism is a natural way to express programs for hierarchical systems. It enables a compositional programming approach that can then be mapped onto the system hierarchy. In this paper, we present nested algorithm composition in the STAPL Skeleton Library (SSL) which uses a nested dataflow model as its internal representation. We show how a high level program specification using SSL allows for asynchronous computation and improved locality. We study both the specification and performance of the stapl implementation of Kripke, a mini-app developed by Lawrence Livermore National Laboratory. Kripke has multiple levels of parallelism and a number of data layouts, making it an excellent test bed to exercise the effectiveness of a nested parallel programming approach. Performance results are provided for six different nesting orders of the benchmark demonstrating the flexibility and performance of nested algorithmic skeleton composition in stapl.

关键词： Algorithmic skeletons nested parallelism Dataflow Kripke mini-app Sweep algorithm

来源：评论

学校读者我要写书评

暂无评论

A compiler for exploiting nested parallelism in OpenMP programs

引用

PARALLEL COMPUTING 2005年第1-12期31卷 960-983页

作者： Tian, XM Hoeflinger, JP Haab, G Chen, YK Girkar, M Shah, S Intel Corp Intel Compiler Labs Software & Solut Grp Santa Clara CA 95052 USA Intel Corp Appl Res Lab Core Technol Grp Santa Clara CA 95052 USA Intel Corp Parallel & Distributed Solut Div Software & Solut Grp Champaign IL 61820 USA

This paper presents the design and implementation of a parallelization framework and OpenMP runtime support in Intel (R) C++ & Fortran compilers for exploiting nested parallelism in applications using OpenMP pragmas or directives. We conduct the performance evaluation of two multimedia applications parallelized with OpenMP pragmas and compiled with the Intel C++ compiler on Hyper-Threading Technology (HT) enabled multiprocessor systems. The performance results show that the multithreaded code generated by the Intel compiler achieved a speedup up to 4.69 on 4 processors with HT enabled for five different input video sequences for the H.264 encoder workload, and a 1.28 speedup on an HT enabled single-CPU system and 1.99 speedup on an HT-enabled dual-CPU system for the audio visual speech recognition workload. The performance gain due to exploiting nested parallelism for leveraging Hyper-Threading Technology is up to 70% for two multimedia workloads under different multiprocessor system configurations. These results demonstrate that hyper-threading benefits can be achieved by exploiting nested parallelism through Intel compiler and runtime system support for OpenMP programs, (c) 2005 Elsevier B.V. All rights reserved.

关键词： compiler parallelization nested parallelism OpenMP hyper-threading performance

来源：评论

学校读者我要写书评

暂无评论

NestStep:: nested parallelism and virtual shared memory for the BSP model

引用

JOURNAL OF SUPERCOMPUTING 2000年第3期17卷 245-262页

作者： Kessler, CW Univ Trier FB Informat 4 D-54286 Trier Germany

NestStep is a parallel programming language for the BSP (bulk-synchronous-parallel) model of parallel computation. Extending the classical BSP model, NestStep supports dynamically nested parallelism by nesting of supersteps and a hierarchical processor group concept. Furthermore, NestStep adds a virtual shared memory realization in software, where memory consistency is relaxed to superstep boundaries. Distribution of shared arrays is also supported. A prototype for a subset of NestStep has been implemented based on Java as sequential basis language. The prototype implementation is targeted to a set of Java Virtual Machines coupled by Java socket communication to a virtual parallel computer.

关键词： BSP model of parallel computation nested parallelism virtual shared memory message combining distributed arrays parallel Java extension

来源：评论

学校读者我要写书评

暂无评论

Space-efficient scheduling of nested parallelism

引用

ACM TRANSACTIONS ON PROGRAMMING LANGUAGES AND SYSTEMS 1999年第1期21卷 138-173页

作者： Narlikar, GJ Blelloch, GE Carnegie Mellon Univ Dept Comp Sci Pittsburgh PA 15213 USA

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.

关键词： algorithms languages performance dynamic scheduling multithreading nested parallelism parallel language implementation space efficiency

来源：评论

学校读者我要写书评

暂无评论

nested parallelism with Algorithmic Skeletons

Nested Parallelism with Algorithmic Skeletons

引用

作者： Majidi, Alireza Texas A&M University

学位级别：硕士

New trend in design of computer architectures, from memory hierarchy design to grouping computing units in different hierarchical levels in CPUs, pushes developers toward algorithms that can exploit these hierarchical designs. This trend makes support of nested-parallelism an important feature for parallel programming models. It enables implementation of parallel programs that can then be mapped onto the system hierarchy. However, supporting nested-parallelism is not a trivial task due to complexity in spawning nested sections, destructing them and more importantly communication between these nested parallel sections. Structured parallel programming models are proven to be a good choice since while they hide the parallel programming complexities from the programmers, they allow programmers to customize the algorithm execution without going through radical changes to the other parts of the program. In this thesis, nested algorithm composition in the STAPL Skeleton Library (SSL) is presented, which uses a nested dataflow model as its internal representation. We show how a high level program specification using SSL allows for asynchronous computation and improved locality. We study both the specification and performance of the STAPL implementation of Kripke, a mini-app developed by Lawrence Livermore National Laboratory. Kripke has multiple levels of parallelism and a number of data layouts, making it an excellent test bed to exercise the effectiveness of a nested parallel programming approach. Performance results are provided for six different nesting orders of the benchmark under different degrees of nested-parallelism, demonstrating the flexibility and performance of nested algorithmic skeleton composition in STAPL .

关键词： Algorithmic Skeletons nested parallelism Parallel Computing Thesis

来源：评论

学校读者我要写书评

暂无评论

Controlling NUMA effects in embedded manycore applications with lightweight nested parallelism support

引用

PARALLEL COMPUTING 2016年 59卷 24-42页

作者： Marongiu, Andrea Capotondi, Alessandro Benini, Luca Swiss Fed Inst Technol Zurich ETHZ D ITET Gloriastr 35 CH-8092 Zurich Switzerland Univ Bologna DEI Wale Risorgimento 2 I-40136 Bologna Italy

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 x speedup versus flat parallelism. (C) 2016 Elsevier B.V. All rights reserved.

关键词： Manycores nested parallelism OpenMP

来源：评论

学校读者我要写书评

暂无评论

Contention in Structured Concurrency: Provably Efficient Dynamic Non-Zero Indicators for nested parallelism 17

Contention in Structured Concurrency: Provably Efficient Dyn...

引用

22nd ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming (PPoPP)

作者： Acar, Umut A. Ben-David, Naama Rainey, Mike Carnegie Mellon Univ Pittsburgh PA 15213 USA INRIA Rocquencourt France

ISBN: (纸本)9781450344937

Over the past two decades, many concurrent data structures have been designed and implemented. Nearly all such work analyzes concurrent data structures empirically, omitting asymptotic bounds on their efficiency, partly because of the complexity of the analysis needed, and partly because of the difficulty of obtaining relevant asymptotic bounds: when the analysis takes into account important practical factors, such as contention, it is difficult or even impossible to prove desirable bounds. In this paper, we show that considering structured concurrency or relaxed concurrency models can enable establishing strong bounds, also for contention. To this end, we first present a dynamic relaxed counter data structure that indicates the non-zero status of the counter. Our data structure extends a recently proposed data structure, called SNZI, allowing our structure to grow dynamically in response to the increasing degree of concurrency in the system. Using the dynamic SNZI data structure, we then present a concurrent data structure for series-parallel directed acyclic graphs (sp-dags), a key data structure widely used in the implementation of modern parallel programming languages. The key component of sp-dags is an in-counter data structure that is an instance of our dynamic SNZI. We analyze the efficiency of our concurrent sp-dags and in -counter data structures under nested-parallel computing paradigm. This paradigm offers a structured model for concurrency. Under this model, we prove that our data structures require amortized O(1) shared memory steps, including contention. We present an implementation and an experimental evaluation that suggests that the sp-dags data structure is practical and can perform well in practice.

关键词： analytical bounds contention concurrent data structures series-parallel dags indicators contention bounds snzi non-blocking data structures structured concurrency nested parallelism concurrency

来源：评论

学校读者我要写书评

暂无评论

Efficient Thread Labeling for On-the-fly Race Detection of Programs with nested parallelism

Efficient Thread Labeling for On-the-fly Race Detection of P...

引用

International Conference on Advanced Software Engineering and Its Applications (ASEA 2011)

作者： Ha, Ok-Kyoon Jun, Yong-Kee Gyeongsang Natl Univ Dept Informat Jinju 660701 South Korea

ISBN: (纸本)9783642272066;9783642272073

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.

关键词： Fork-join programs nested parallelism data races on-the-fly detection thread labeling efficiency

来源：评论

学校读者我要写书评

暂无评论

Enabling Scalable and Fine-Grained nested parallelism on Embedded Many-Cores 9

Enabling Scalable and Fine-Grained Nested Parallelism on Emb...

引用

9th IEEE International Symposium on Embedded Multicore/Manycore Systems-on-Chip (MCSoC)

作者： Capotondi, Alessandro Marongiu, Andrea Benini, Luca Univ Bologna DEI I-40126 Bologna Italy Univ Bologna IIS I-40126 Bologna Italy Swiss Fed Inst Technol Zurich ETHZ Zurich Switzerland

ISBN: (纸本)9781479986705

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%.

关键词： cache storage embedded systems multiprocessing systems parallel programming system-on-chip PMCA STMicroelectronics STHORM many-core SoC distributed memory with nonuniform access embedded many-cores fine-grained parallelism heterogeneous systems-on-chip nested parallelism parallel team configuration parallel thread creation overhead programmable manycore accelerator programming abstraction software cache mechanism Fabrics Instruction sets Message systems Parallel processing Programming Recruitment Embedded Many-Core Architectures OpenMP Parallel Programming Models Embedded systems Computer based information systems Parallel programming instruction sets system-on-chip Multiprocessing systems cache storage PARALLEL PROCESSING (COMPUTERS) Programming Textile fabrics parallelism fabric Synclitism THREADS Parallel Lines

来源：评论

学校读者我要写书评

暂无评论

Efficiency of e-NR Labeling for On-the-fly Race Detection of Programs with nested parallelism

引用

2nd International Conference on Ubiquitous Computing and Multimedia Applications

作者： Kim, Sun-Sook Ha, Ok-Kyoon Jun, Yong-Kee Gyeongsang Natl Univ Dept Informat Jinju 660701 South Korea Gyeongsang Natl Univ Specialized Grad Sch Aerosp Engn Jinju 660701 South Korea

ISBN: (纸本)9783642209970

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.

关键词： Empirical comparison thread labeling race detection nested parallelism e-NR labeling

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：