Skip to content
Free planNo credit card requiredStart writing
AI for Research home
AI for Research home
Dashboard
Sign inGet started

Search 250 million research papers

Read the abstract, see who wrote it and who cites it, and get the citation in APA, MLA, Chicago or Harvard.

About 4,062 papers for “Task parallelism”

Streaming Task Parallelism

Albert Cohen · HAL (Le Centre pour la Communication Scientifique Directe) · 2015

Keynote presentation

Cited by 0

Generalized Task Parallelism

Kevin Streit, Johannes Doerfert, Clemens Hammacher et al. · ACM Transactions on Architecture and Code Optimization · 2015

Existing approaches to automatic parallelization produce good results in specific domains. Yet, it is unclear how to integrate their individual strengths to match the demands and opportunities of complex software. This lack of integration has both practical reasons, as integrating those largely differing approaches into one compiler would impose an engineering hell, as well as theoretical reasons, as no joint cost model exists that would drive the choice between parallelization methods. By reducing the problem of generating parallel code from a program dependence graph to integer linear programming, <i>generalized task parallelization</i> integrates central aspects of existing parallelization approaches into a single unified framework. Implemented on top of LLVM, the framework seamlessly integrates enabling technologies such as speculation, privatization, and the realization of reductions. Evaluating our implementation on various C programs from different domains, we demonstrate the effectiveness and generality of generalized task parallelization. On a quad-core machine with hyperthreading we achieve speedups of up to 4.6 ×.

Cited by 8Open access

Data and Task Parallelism

Narayan Ganesan, Roger D. Chamberlain, Jeremy Buhler et al. · 2012

Many biologically motivated problems are expressed as dynamic programming recurrences and are difficult to parallelize due to the intrinsic data dependencies in their algorithms. Therefore their solutions have been sped up using task level parallelism only. Emerging platforms such as GPUs are appealing parallel architectures for high-performance; at the same time they are a motivation to rethink the algorithms associated with these problems, to extract finergrained parallelism such as data parallelism. In this paper, we consider the hmmersearch program as a representative of these problems and we re-design its computational algorithm to extract data parallelism for a more efficient execution on emerging platforms, despite the fact that hmmersearch has data dependencies. Our approach outperforms other existing methods when searching a very large database of unsorted sequences on GPUs. 1.

Cited by 0

Task Parallelism in Spar

F. Kuijlman, A. Rădulescu, Arjan J. C. van Gemund et al. · 1998

In this paper we will give a small introduction to Spar, a programming language for semi-automatic parallel programming. Spar, a Java derivative is being developed as part of the Automap project, which aims to create completely automatic mappings for code and data at either compile time or runtime. We will present how Spar supports task-parallel programming and how it interacts with the user or the scheduler to define code mappings. 2 Introduction Issues that are of major importance in the design of parallel programming languages for distributedmemory systems include: ffl parallelizability, the extent to which parallelism can either be expressed by the user or deduced by the compiler such that problem parallelism is adequately captured. ffl programmability, the extent to which the user is relieved from programming the complex synchronizations required between concurrently executing tasks in order to retain correctness. ffl portability, the extent to which the program is machine-inde...

Cited by 0

Kokkos Task-DAG Parallelism.

Harold Edwards · OSTI OAI (U.S. Department of Energy Office of Scientific and Technical Information) · 2019

Abstract not provided.

Cited by 0Open access

Phaser Beams: Integrating Stream Parallelism with Task Parallelism

Jun Shirako, David M. Peixotto · 2011

Current streaming languages place significant restrictions on the structure of parallelism that they support, and usually do not allow for dynamic task parallelism. In contrast, there are a number of task-parallel programming models that support dynamic parallelism but lack the ability to set up efficient streaming communications among dynamically varying sets of tasks. We address this gap by introducing Phaser Beams as a foundation for integrating stream parallelism with task parallelism. Phaser Beams builds on past work on accumulators and point-to-point synchronization in Habanero-Java (HJ) phasers, which in turn was derived from X10 clocks. Phaser Beams introduce three key extensions relative to past work: 1) a bounded phaser that limits the maximum phase difference between a producer and a consumer synchronizing on that phaser and the buffer size needed to support streaming, 2) an extension to accumulators to work in non-barrier mode with bounded phasers for use in streaming, and 3) a dynamic cycle-detection algorithm to phaser registration to detect cyclic structures in a streaming program so as to enable efficient batching optimizations for acyclic structures. These extensions could easily be incorporated in a future version of X10. Our preliminary Java-based implementation of Phaser Beams is restricted to the single node case, and the results obtained on three multicore SMPs are encouraging. As a calibration of the baseline performance of phaser synchronization, the performance of barriers in HJ phasers was found to be significantly faster than Java’s CyclicBarrier and the Java and C++ implementations of X10’s clocks, when measured using the BarrierBench benchmark. To evaluate the effectiveness of streaming with cyclic structures in Phaser Beams, we measured a performance improvement of up to 6.0 for the thread-ring microbenchmark, relative to the original Java version. For the restricted case of static parallelism and acyclic graphs, we compared the performance of our Phaser Beams implementation with the batched C-based StreamIt v2.1.1 implementation that only supports acyclic graphs. Our results on one microbenchmark (Push-Pop) and three StreamIt benchmarks (FilterBank, FMRadio, BeamFormer) show that the scalability of the Phaser Beams implementation relative to serial Java is better than that of StreamIt v2.1.1 relative to serial C, but the difference in ab[Copyright notice will appear here once ’preprint’ option is removed.] solute performance varied depending on the relative performance of the serial Java vs. serial C versions. To evaluate the effectiveness of Phaser Beams to integrate stream and dynamic task parallelism, we measured a performance improvement of up to 37.2 for the FacilityLocation benchmark compared with a pure task-parallel implementation using Intel’s Concurrent Collections (CnC) language, and up to 40.2 speedup relative to sequential implementation for Sieve of Eratosthenes.

Cited by 2

Exploiting Task-Level Parallelism Using

Ptask Tarek Abdelrahman, 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. 1 Introduction Compiling sequential programs into parallel programs has been an active area of research for the past few years. Much of this research has focused on loop-level parallelism and on the efficient execution of data-parallel programs. An alternative model of parallelism is that of a collection of asynchronous cooperating tasks, or task-level parallelism. Such a model is attractive for a number of reasons. Some parallel applications are best expressed as a collection o...

Cited by 0

Integrating Task and Data Parallelism

Berna L. Massingill · CaltechAUTHORS (California Institute of Technology) · 1993

Many models of concurrency and concurrent programming have been proposed; most can be categorized as either task-parallel (based on functional decomposition) or data-parallel (based on data decomposition). Task-parallel models are most effective for expressing irregular computations; data-parallel models are most effective for expressing regular computations. Some computations, however, exhibit both regular and irregular aspects. For such computations, a better programming model is one that integrates task and data parallelism. This report describes one model of integrating task and data parallelism, some problem classes for which it is effective, and a prototype implementation.

Cited by 0Open access

Extending Kokkos with Task Parallelism.

Sunderland, Daniel; Edwards, Harold C.; Trott, Christian Robert · OSTI OAI (U.S. Department of Energy Office of Scientific and Technical Information) · 2019

Abstract not provided.

Cited by 0Open access

Mixed Task and Data Parallelism

Olivier Beaumont, Arnaud Legrand, Yves Robert · HAL (Le Centre pour la Communication Scientifique Directe) · 2002

International audience

Cited by 1

EXTENDING OPENMP FOR TASK PARALLELISM

Ami Marowka · Parallel Processing Letters · 2003

In a wide variety of scientific parallel applications, both task and data parallelism must be exploited to achieve the best possible performance on a multiprocessor machine. These applications induce task-graph parallelism with coarse-grain granularity. Nevertheless, using the available task-graph parallelism and combining it with data parallelism can increase the performance of parallel applications considerably since an additional degree of parallelism is exploited. The OpenMP standard supports data parallelism but does not support task-graph parallelism. In this paper we present an integration of task-graph parallelism in OpenMP by extending the parallel sections constructs to include task-index and precedence-relations matrix clauses. There are many ways in which task-graph parallelism can be supported in a programming environment. A fundamental design decision is whether the programmer has to write programs with explicit precedence relations, or if the responsibility of precedence relations generation is delegated to the compiler. One of the benefits provided by parallel programming models like OpenMP is that they liberate the programmer from dealing with the underlying details of communication and synchronization, which are cumbersome and error-prone tasks. If task-graph parallelism is to find acceptance, writing task-graph parallel programs must be no harder than writing data parallel programs, and therefore, in our design, precedence relations are described through simple programmer annotations, with implementation details handled by the system. This paper concludes with a description of several parallel application kernels that were developed to study the practical aspects of task-graph parallelism in OpenMP. The examples demonstrate that exploiting data and task parallelism in a single framework is the key to achieving good performance in a variety of applications.

Cited by 6

Task parallelism and high-performance languages

Ian Foster · OSTI OAI (U.S. Department of Energy Office of Scientific and Technical Information) · 1996

The definition of High Performance Fortran (HPF) is a significant event in the maturation of parallel computing: it represents the first parallel language that has gained widespread support from vendors and users. The subject of this paper is to incorporate support for task parallelism. The term task parallelism refers to the explicit creation of multiple threads of control, or tasks, which synchronize and communicate under programmer control. Task and data parallelism are complementary rather than competing programming models. While task parallelism is more general and can be used to implement algorithms that are not amenable to data-parallel solutions, many problems can benefit from a mixed approach, with for example a task-parallel coordination layer integrating multiple data-parallel computations. Other problems admit to both data- and task-parallel solutions, with the better solution depending on machine characteristics, compiler performance, or personal taste. For these reasons, we believe that a general-purpose high-performance language should integrate both task- and data-parallel constructs. The challenge is to do so in a way that provides the expressivity needed for applications, while preserving the flexibility and portability of a high-level language. In this paper, we examine and illustrate the considerations that motivate the use of task parallelism. We also describe one particular approach to task parallelism in Fortran, namely the Fortran M extensions. Finally, we contrast Fortran M with other proposed approaches and discuss the implications of this work for task parallelism and high-performance languages.

Cited by 5Open access

Enabling Task Level Parallelism in HandelC

Thamer S. AbuYasin · KU ScholarWorks (The University of Kansas) · 2007

HandelC is a programming language used to target hardware and is similar in syntax to ANSI-C. HandelC offers constructs that allow programmers to express instruction level parallelism. Also, HandelC offers primitives that allow task level parallelism. However, HandelC does not offer any runtime support that enables programmers to express task level parallelism efficiently. This thesis discusses this issue and suggests a support library called HCthreads as a solution. HCthreads offers a subset of Pthreads functionality and interface relevant to the HandelC environment. This study offers means to identify the best configuration of HCthreads to achieve the highest speedups in real systems. This thesis investigates the issue of integrating HandelC within platforms not supported by Celoxica. A support library is implemented to solve this issue by utilizing the high level abstractions offered by Hthreads. This support library abstracts away any HWTI specific synchronization making the coding experience quite close to software. HCthreads is proven effective and generic for various algorithms with different threading behaviors. HCthreads is an adequate method to implement recursive algorithms even if no task level parallelism is warranted. Not only HCthreads offers such versatility, it achieves modest speedups over instruction level parallelism ad-hoc approaches. The Hthreads support library served its intended purpose by allowing HCthreads real system tests to proceed on a third party platform. No major issues were reported while conducting these tests, still additional investigation and verification is required.

Cited by 0Open access

Extending Vienna Fortran with task parallelism

Barbara Chapman, P. Mehrotra, J. Van Rosendale et al. · 2002

Vienna Fortran supports a wide range of data-parallel numerical problems. However, a significant number of scientific and engineering applications are of a multi-disciplinary and heterogeneous nature and thus do not fit well into the data parallel paradigm. In this paper we present new language extensions to fill this gap. Tasks can be spawned as asynchronous activities in a homogeneous or heterogeneous computing environment; they interact by sharing access to Shared Data Abstractions (SDAs). SDAs are an extension of Fortran 90 modules, representing a pool of common data, together with a set of methods for controlled access to these data and a mechanism for providing persistent storage. These extensions support the integration of data and task parallelism and can be used to express task parallel applications in a natural and efficient way.

Cited by 1

Combining Task Parallelism and Multithreaded Concurrency

Pusapaty, Sai Sameer · DSpace@MIT (Massachusetts Institute of Technology) · 2022

In this thesis, I present Multicilk, a threads library based on C11 threads and the OpenCilk runtime for enabling task parallelism within multiple concurrent threads. With Multicilk, a programmer can parallelize threads in a multithreaded application simply by using Cilk independently within each thread. Without Multicilk, doing so violates the semantics that we expect in concurrent thread programming, leading to catastrophic failure of the application. No other existing combination of task-parallel system — including OpenMP, TBB, and TPL, and the various other implementations of Cilk — and threads library — including C11, C++11, Pthreads, and WinAPI threads — can parallelize multithreaded applications transparently and modularly.
\n
\nThe key insight behind Multicilk recognizes that integrating task-parallel systems with multithreaded concurrency requires two layers of thread abstraction that are conflated in previous systems. Service threads implement the workers in the Cilk runtime system. But the Cilk computation itself, called a cilk, though implemented by many service threads, itself provides the abstraction of a single application thread to other threads within the multithreaded application, regardless of whether they are cilks. Multicilk employs a technique called impersonation to individual workers to act on behalf of the entire cilk, providing the same interface to the outside world as it would it were an ordinary thread. This powerful “two-layer-cake” abstraction enables ordinary multithreaded applications to be ported to a Cilk environment and parallelized in a straightforward and modular fashion.
\n
\nMy Multicilk implementation for OpenCilk provides two thread libraries corresponding to the layers in the two-layer cake, as well as some modifications to the OpenCilk runtime system. The service-thread library is the standard glibc. The application-thread library was created by modifying eight glibc functions using 63 lines of source code and writing wrappers for four glibc functions using 115 lines of code, amounting to about half of the 25 functions in the C11 sublibrary of glibc. I wrote 180 lines of utility functions for threading and synchronization. The changes to OpenCilk amounted to 62 lines, also for threading and synchronization. In sum, I added or modified just over 400 lines of source code to implement Multicilk.

Cited by 0