Tsung‐Wei Huang, Leslie K Hwang · 2022
Task graph programming model (TGPM) has become central to a wide range of scientific computing applications because it enables top-down optimization of parallelism that governs the macro-scale performance. Existing TGPMs focus on expressing tasks and dependencies of a workload and leave the scheduling details to a library runtime. While maximizing the task concurrency is a typical scheduling goal, many applications require task parallelism to be constrained during the graph execution. Examples are limiting the number of worker threads in a subgraph or relating a conflict between two tasks. However, mainstream TGPMs have largely ignored this important feature of constrained parallelism in a task graph. Users have no choice but to implement a separate and often sophisticated scheduling solution that is neither generalizable nor scalable. In this paper, we propose a semaphore programming model and a scheduling method both of which can be easily integrated into an existing TGPM to support constrained parallelism. We have demonstrated the effectiveness and efficiency of our approach in real applications. As an example, our semaphore model speeds up an industrial circuit placement workload up to 28%.
Cited by 14
Sanjay Chatterjee, Sağnak Taşırlar, Zoran Budimlić et al. · 2013
Effective combination of inter-node and intra-node parallelism is recognized to be a major challenge for future extreme-scale systems. Many researchers have demonstrated the potential benefits of combining both levels of parallelism, including increased communication-computation overlap, improved memory utilization, and effective use of accelerators. However, current “hybrid programming” approaches often require significant rewrites of application code and assume a high level of programmer expertise. Dynamic task parallelism has been widely regarded as a programming model that combines the best of performance and programmability for shared-memory programs. For distributed-memory programs, most users rely on efficient implementations of MPI. In this paper, we propose HCMPI (Habanero-C MPI), an integration of the Habanero-C dynamic task-parallel programming model with the widely used MPI message-passing interface. All MPI calls are treated as asynchronous tasks in this model, thereby enabling unified handling of messages and tasking constructs. For programmers unfamiliar with MPI, we introduce distributed data-driven futures (DDDFs), a new data-flow programming model that seamlessly integrates intra-node and inter-node data-flow parallelism without requiring any knowledge of MPI. Our novel runtime design for HCMPI and DDDFs uses a combination of dedicated communication and computation specific worker threads. We evaluate our approach on a set of micro-benchmarks as well as larger applications and demonstrate better scalability compared to the most efficient MPI implementations, while offering a unified programming model to integrate asynchronous task parallelism with distributed-memory parallelism.
Cited by 82
Tarek Abdelrahman And, Tarek S. Abdelrahman, Sum Huynh · 1996
This paper presents pTask--- a system that allows users to automatically exploit dynamic task-level parallelism in sequential array-based C programs. The system employs compiler analysis to extract data usage information from the program, then uses this information at run-time to dynamically exploit concurrency and to enforce data-dependences. Experimental results using a prototype of the system show scaling performance and low overhead on a 32-processor KSR1 multiprocessor for a number of applications.
Cited by 0
Ian Foster · Lecture notes in computer science · 1996
Cited by 2
Sheri Mickelson · 2016
Cited by 0
Jisheng Zhao, Roberto Lublinerman, Swarat Chaudhuri et al. · 2015
Isolation—the property that a task can access shared data without interference from other tasks—is one of the most basic concerns in parallel programming. While there is a large body of past work on isolated task-parallelism, the in-tegration of isolation, task-parallelism, and nesting of tasks has been a difficult and unresolved challenge. In this pa-per, we present a programming and execution model called Otello where isolation is extended to arbitrarily nested par-allel tasks with irregular accesses to heap data. At the same time, no additional burden is imposed on the programmer, who only exposes parallelism by creating and synchroniz-ing parallel tasks, leaving the job of ensuring isolation to the underlying compiler and runtime system. Otello extends our past work on Aida execution model
Cited by 0
Dragoş Sbîrlea · Rice Digital Scholarship Archive (Rice University) · 2012
As multicore computing becomes the norm, exploiting parallelism in applications becomes a requirement for all software. Many applications exhibit different kinds of parallelism, but most parallel programming languages are biased towards a specific paradigm, of which two common ones are task and streaming parallelism. This results in a dilemma for programmers who would prefer to use the same language to exploit different paradigms for different applications. Our thesis is an integration of stream-parallel and task-parallel paradigms can be achieved in a single language with high programmability and high resource efficiency, when a general dataflow programming model is used as the foundation. The dataflow model used in this thesis is Intel's Concurrent Collections (CnC). While CnC is general enough to express both task-parallel and stream-parallel paradigms, all current implementations of CnC use task-based runtime systems that do not deliver the resource efficiency expected from stream-parallel programs. For streaming programs, this use of a task-based runtime system is wasteful of computing cycles and makes memory management more difficult than it needs to be. We propose Streaming Concurrent Collections (SCnC), a streaming system that can execute a subset of applications supported by Concurrent Collections, a general macro data-flow coordination language. Integration of streaming and task models allows application developers to benefit from the efficiency of stream parallelism as well as the generality of task parallelism, all in the context of an easy-to-use and general dataflow programming model. To achieve this integration, we formally define streaming access patterns that, if respected, allow CnC task based applications to be executed using the streaming model. We specify conditions under which an application can run safely, meaning with identical result and without deadlocks using the streaming runtime. A static analysis that verifies if an application respects these patterns is proposed and we describe algorithmic transformations to bring a larger set of CnC applications to a form that can be run using the streaming runtime. To take advantage of dynamic parallelism opportunities inside streaming applications, we propose a simple tuning annotation for streaming applications, that have traditionally been considered with fixed parallelism. Our dynamic parallelism construct, the dynamic splitter, which allows fission of stateful filters with little guidance from the programmer is based on the idea of different places where computations are distributed. Finally, performance results show that transitioning from the task parallel runtime to streaming runtime leads to a throughput increase of up to 40×. In summary, this thesis shows that stream-parallel and task-parallel paradigms can be integrated in a single language when a dataflow model is used as the foundation, and that this integration can be achieved with high programmability and high resource efficiency. Integration of these models allows application developers to benefit from the efficiency of stream parallelism as well as the generality of task parallelism, all in the context of an easy-to-use dataflow programming model.
Cited by 0Open access
Pimentel, A.D., Terpstra, F., Polstra, S. et al. · UvA-DARE (University of Amsterdam) · 2002
The Sesame environment provides modeling and simulation methods and tools for the efficient design space exploration of heterogeneous embedded multimedia systems. It specifically targets the performance evaluation of embedded systems architectures in which task-level parallelism is available.
Cited by 2
Éric Maisonnave · SPIRE - Sciences Po Institutional REpository · 2020
Cited by 0Open access
田浦健次朗, Kenjiro Taura, 中島 潤 et al. · Tokyo Tech Research Repository (Tokyo Institute of Technology) · 2016
Cited by 0
Marisabel Guevara, Chris Gregg, Kim Hazelwood et al. · 2009
General purpose computing on graphics processing units (GPUs) introduces the challenge of scheduling independent tasks on devices designed for data parallel or SPMD applications. This paper proposes an issue queue that merges workloads that would underutilize GPU processing resources such that they can be run concurrently on an NVIDIA GPU. Using kernels from microbenchmarks and two applications we show that throughput is increased in all cases where the GPU would have been underused by a single kernel. An exception is the case of memory-bound kernels, seen in a Nearest Neighbor application, for which the execution time still outperforms the same kernels executed serially by 12-20%. It can also be beneficial to choose a merged kernel that over-extends the GPU resources, as we show the worst case to be bounded by executing the kernels serially. This paper also provides an analysis of the latency penalty that can occur when two kernels with varying completion times are merged. 1.
Cited by 0
Steven J. Deitz · 2003
This paper suggests that data parallelism is more general than previously thought and that integrating support for task parallelism into a data parallel programming language is a mistake. With several proposed improvements, the data parallel programming language ZPL is surprisingly versatile. The language and its power are illustrated by the solution to several traditionally task parallel problems. In addition, limitations are discussed.
Cited by 0
Ryan Newton, Eric Holk, Trevor L. McDonell · 2014
Cited by 0
Jens Gustedt, Maxime Moge · HAL (Le Centre pour la Communication Scientifique Directe) · 2019
We present a paradigm and implementation of a parallel control flow model for algorithmic patterns of two nested loops; an outer iteration loop and an inner data traversal loop. It is centered around memory access patterns. Other than dataflow programming it emphasizes on upholding the sequential modification order of each data object. As a consequence the visible side effects on any object can be guaranteed to be identical to a sequential execution. Thus the set of optimizations that are performed are compatible with C's abstract state machine and compilers could perform them, in principle, automatically and unobserved. We present two separate implementations of this model. The first in C++ uses overloading of the operator[] to instrument the memory accesses. The second in Modular C uses annotations and code transformations for the two nested loops. Thereby the code inside the loops may stay as close as possible to the original code such that optimization of that code is not impacted unnecessarily. These implementations show promising results for appropriate benchmarks from polybench and rodinia.
Cited by 0Open access
Alan Heirich, Elliott Slaughter, Manolis Papadakis et al. · 2017
This short paper describes an experimental prototype of in situ visualization in a task-based parallel programming framework. A set of reusable visualization tasks were composed with an existing simulation. The visualization tasks include a local OpenGL renderer, a parallel image compositor, and a display task. These tasks were added to an existing fluid-particle-radiation simulation and weak scaling tests were run on up to 512 nodes of the Piz Daint supercomputer. Benchmarks showed that the visualization components scaled and did not reduce the simulation throughput. The compositor latency increased logarithmically with increasing node count.
Cited by 7
Patrick R Atkinson · Bristol Research (University of Bristol)
Cited by 0
A. Duran, Julita Corbalán, Eduard Ayguadé · 2008
In task parallel languages, an important factor for achieving a good performance is the use of a cut-off technique to reduce the number of tasks created. Using a cut-off to avoid an excessive number of tasks helps the runtime system to reduce the total overhead associated with task creation, particularlt if the tasks are fine grain. Unfortunately, the best cut-off technique its usually dependent on the application structure or even the input data of the application. We propose a new cut-off technique that, using information from the application collected at runtime, decides which tasks should be pruned to improve the performance of the application. This technique does not rely on the programmer to determine the cut-off technique that is best suited for the application. We have implemented this cut-off in the context of the new OpenMP tasking model. Our evaluation, with a variety of applications, shows that our adaptive cut-off is able to make good decisions and most of the time matches the optimal cut-off that could be set by hand by a programmer.
Cited by 57
Richard H. Littin, J. A. David McWha, Murray W. Pearson et al. · 1998
Cited by 0
Nawal Copty, Ro Duran, Jay Hoeflinger et al. · 2008
Abstract. This paper presents a novel proposal to define task paral-lelism in OpenMP. Task parallelism has been lacking in the OpenMP language for a number of years already. As we show, this makes cer-tain kinds of applications difficult to parallelize, inefficient or both. A subcommittee of the OpenMP language committee, with representatives from a number of organizations, prepared this proposal to give OpenMP a way to handle unstructured parallelism. While defining the proposal we had three design goals: simplicity of use, simplicity of specification and consistency with the rest of OpenMP. Unfortunately, these goals were in conflict many times during our discussions. The paper describes the pro-posal, some of the problems we faced, the different alternatives, and the rationale for our choices. We show how to use the proposal to parallelize some of the classical examples of task parallelism, like pointer chasing and recursive functions. 1
Cited by 0
Shahawy, Mohamed Mahfouz · Zenodo (CERN European Organization for Nuclear Research) · 2024
This is the code to reproduce experimental results for "HardCilk: Cilk-Like Task Parallelism for FPGAs" published in FCCM'24
Cited by 0Open access