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

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年第10-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

来源：评论

学校读者我要写书评

暂无评论

PFACC: An OpenACC-like programming model for irregular nested parallelism

引用

SOFTWARE-PRACTICE & EXPERIENCE 2020年第10期50卷 1877-1904页

作者： Huang, Ming Hsiang Yang, Wuu Natl Chiao Tung Univ Dept Comp Sci Hsinchu Taiwan

OpenACC is a directive-based programming model which allows programmers to write graphic processing unit (GPU) programs by simply annotating parallel loops. However, OpenACC has poor support for irregular nested parallel loops, which are natural choices to express nested parallelism. We propose PFACC, a programming model similar to OpenACC. PFACC directives can be used to annotate parallel loops and to guide data movement between different levels of memory hierarchy. Parallel loops can be arbitrarily nested or be placed inside functions that would be (possibly recursively) called in other parallel loops. The PFACC translator translates C programs with PFACC directives into CUDA programs by inserting runtime iteration-sharing and memory allocation routines. The PFACC runtime iteration-sharing routine is a two-level mechanism. Thread blocks dynamically organize loop iterations intobatchesand execute the batches in a depth-first order. Different thread blocks share iterations among one another with an iteration-stealing mechanism. PFACC generates CUDA programs with reasonable memory usage because of the depth-first execution order. The two-level iteration-sharing mechanism is implemented purely in software and fits well with the CUDA thread hierarchy. Experiments show that PFACC outperforms CUDA dynamic parallelism in terms of performance and code size on most benchmarks.

关键词： dynamic scheduling GPGPU irregular parallelism nested parallelism OpenACC parallel programming model PFACC

来源：评论

学校读者我要写书评

暂无评论

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 Verification of First Tangled Races to Occur in Programs with nested parallelism

Efficient Verification of First Tangled Races to Occur in Pr...

引用

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

作者： Kang, Mun-Hye Jun, Young-Kee Gyeongsang Natl Univ Dept Informat Jinju 660701 South Korea

ISBN: (纸本)9783642272066;9783642272073

Since data races result in unintended nondeterministic executions of the programs, detecting the races is important for debugging shared memory programs with nested parallelism. Particularly, the first races to occur in an execution of a program must be detected, because they can potentially affect other races that occur later. Previous on-the-fly techniques are inefficient or can not guarantee to verify the existence of the first tangle of data races to occur. This paper presents an efficient two-pass on-the-fly technique in such a kind of programs. This technique is still efficient with regard to the execution time and memory space by keeping a constant number of accesses involved in the first races for each shared variable during the execution. We empirically compare our technique with previous techniques using a set of synthetic programs with OpenMP directives.

关键词： shared memory programs nested parallelism data races first races to occur first tangle verification on-the-fly race detection efficiency

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：