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”

Integrated Support for Task and Data Parallelism

K. Mani Chandy, Ian Foster, Ken Kennedy et al. · 1994

We present an overview of research at the CRPC designed to provide an efficient, portable programming model for scientific applications possessing both task and data parallelism. Fortran M programs exploit task parallelism by providing language extensions for user-defined process management and typed communication channels. A combination of compiler and run-time system support ensures modularity, safety, portability, and efficiency. Fortran D and High Performance Fortran programs exploit data parallelism by providing language extensions for user-defined data decomposition specifications, parallel loops, and parallel array operations. Compile-time analysis and optimization yield efficient, portable programs. We design an interface for using a task-parallel language to coordinate concurrent data-parallel computations. The interface permits concurrently executing data-parallel computations to interact through messages. A key notion underlying the proposed interface is the integration of Fortran M ...

Cited by 0

A proposal for task parallelism in OpenMP

Ayguadé Parra, Eduard, Nawal, Copty, Duran González, Alejandro et al. · RECERCAT (Consorci de Serveis Universitaris de Catalunya)

This paper presents a novel proposal to define task parallelism in OpenMP. Task parallelism has been lacking in the OpenMP language for a number of years already. As we show, this makes certain 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 proposal, 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.

Cited by 0Open access

Enabling OpenMP task parallelism on Multi-FPGAs

Ramon Nepomuceno · 2021

Os aceleradores de hardware baseados em FPGA têm recebido uma crescente atenção nos últimos anos.Um dos principais motivos para isso é que seus recursos reconfiguráveis facilitam a adaptação do acelerador a diferentes tipos de cargas de trabalho.Em alguns casos, os aceleradores baseados em FPGA fornecem maior desempenho computacional e eficiência energética.Foi relatado que o offload para FPGA alcança um melhor desempenho quando comparado GPUs e CPUs para algumas aplicações, como Fast Fourier Transform.Esse desempenho pode ser ainda maior se conectarmos vários FPGAs criando um cluster Multi-FPGA.No entanto, programar esses sistemas heterogêneos é um empreendimento desafiador que ainda requer esforços de pesquisa e desenvolvimento para torná-lo realmente simples.O modelo de programação baseado em tarefas OpenMP é uma boa escolha para programar sistemas Multi-FPGA Heterogêneos.Isso advém da capacidade deste modelo de expor um grau mais alto de paralelismo que combina: (a) offload de computação para aceleradores; (b) dependências explícitas de dados; e (c) definição das regiões de código para cada dispositivo específico.Com base nisso, o trabalho desta tese estende a infraestrutura LLVM/OpenMP existente, bem como propõe uma plataforma de hardware para ajudar o programador a expressar facilmente o offload e o uso de IP-cores disponíveis em um código binário reconfigurável pré-existente (bitstream).Para isto, foi utilizada uma metodologia de co-design, que implementa a arquitetura de hardware e software em paralelo.No lado do software, duas modificações principais foram feitas na implementação do OpenMP: (a) construir um plugin VC709 na biblioteca libomptarget; e (b) modificar o algoritmo de tempo de execução que gerencia o grafo de tarefas.No lado do hardware, foi criada uma infraestrutura baseada no Target Reference Design (TRD) da placa Xilinx VC709.As principais contribuições desta tese são: (a) um novo plugin Clang/LLVM que entende placas FPGA como dispositivos OpenMP, e usa a diretiva OpenMP declare variant para especificar IPs-cores de hardware; (b) Um mecanismo baseado na dependência de tarefa OpenMP e no modelo de transferência de computação que permite a comunicação transparente de IPs-cores em uma arquitetura Multi-FPGA; (c) Uma arquitetura em hardware, baseada no Target Reference Design da placa VC709, capaz de executar tarefas OpenMP utilizando preexistentes IP-cores; (d) Um modelo de programação baseado em paralelismo de tarefas OpenMP, que torna simples mover dados entre FPGAs, CPUs ou outros dispositivos de aceleração (por exemplo, GPUs), e que permite ao programador usar um único modelo de programação para executar sua aplicação em uma verdadeira arquitetura heterogênea.Resultados experimentais para um conjunto de aplicações de stencil em OpenMP que executaram em uma plataforma Multi-FPGA com 6 placas Xilinx VC709 interconectadas através de links de fibra ótica, mostraram acelerações quase lineares conforme o número de FPGAs e IP-cores por FPGA aumenta.

Cited by 0Open access

A note on task-parallelism upon multiprocessors

Joël Goossens, Shelby Funk, Nathan Fisher et al. · Dépôt institutionnel de l'Université libre de Bruxelles (Université Libre de Bruxelles) · 2010

info:eu-repo/semantics/published

Cited by 1

GPU task parallelism for scalable anomaly detection

Koji Ueno, Toyotaro Suzumura · 2012

Stream computing has emerged as a new processing paradigm that processes incoming data streams from large numbers of sensors in real time. At the same time, many recent efforts have shown the suitability of GPGPU s for batch-typed long-running applications. However, few studies conduct the applicability of GPGPU to stream computing and also our first experiment shows that the performance does not scale as expected if one introduces the GPGPU to stream computing applications. This paper presents the workload characterization of GPGPU-based stream computing. We especially focus on computing SVD (Singular Value Decomposition) with GPGPUs for small-sized matrix since it can be widely applicable to real-time stream-based data mining applications such as real-time anomaly detection. In this paper, we not only show the workload characterization of GPGPU-based stream computing but also propose the optimization approach of SVD for stream computing applications called “GPU task Parallelism” to leverage the sufficient capability of GPGPUs. This optimization offers new levels of scalability for real-time operations with large numbers of sensors. Our experimental results show that GPU task parallelism provides roughly four-fold performance gains against a quad-core CPU for matrixes of 300 × 300 to 500 × 500 data values. We also implemented a stream-based change-point and anomaly detection system based on the optimized SVD and stream computing system called System S. By porting the optimized version of SVD to the distributed stream computing system, it was easy to exploit multiple GPUs on multiple nodes. The performance results showed performance around 7.6 times faster than CPUs. The scalability of our proposed system was tested up to 1,525 sensors, which were simultaneously handled for change-point detection every 5 seconds.

Cited by 0

Modeling of Intra-task Parallelism in Sesame

Andy D. Pimentel, Fokke G. Terpstra, Simon Polstra 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. In this paper, we present techniques that allow Sesame to also model intra-task parallelism exploited at the architecture level. Moreover, we describe a case study using a QR decomposition application to validate our modeling concepts. To this end, we were able to compare the performance estimates of our abstract system models with the results of an actual FPGA implementation. The results are promising in the sense that they show good accuracy with minimal modeling effort.

Cited by 1

HardCilk: Cilk-like Task Parallelism for FPGAs

Mohamed Shahawy, Canberk Sönmez, Cemalettin Cem Belentepe et al. · Infoscience (Ecole Polytechnique Fédérale de Lausanne) · 2024

High-level synthesis (HLS) helps to develop hard-ware accelerators for field-programmable gate arrays (FPGAs) using C/C++ descriptions. HLS is tailored to exploit instruction-level parallelism and, where available, data-level parallelism in applications. Yet, some applications mostly display another type of parallelism known as task-level parallelism (TLP): they may have massive amounts of available parallelism but paralleliz-able execution threads follow starkly different control paths or make completely independent memory accesses. Alas, there is very limited support for TLP in HLS tools (with much of the support being for statically scheduled coarse-grained tasks) whereas TLP is widely supported on conventional CPU platforms via libraries like OpenCilk, Intel Threading Building Blocks, and OpenMP. In this paper, we introduce a framework for supporting software-like TLP on FPGAs. The framework provides a parameterized architectural template that implements all hardware modules needed to support TLP primitives and task management. The emphasis is on providing programmers with a software-like experience: limited hardware resource constraints should only impact performance and never functionality. For this, all queues in the limited BRAMs are virtually extended to larger HBM/DDR FPGA memory and potentially beyond. We provide an open-source Chisel hardware generator that creates a dedicated task management system from a given Cilk-like application description. It is then straightforward to integrate it with HLS-based processing elements to realize full TLP-enabled applications on FPGAs. In the evaluation, we focus on the efficiency and scalability of our hardware task management system and compare it with OpenCilk, a recent software TLP framework. The results show that the architectural building blocks consume a small percentage of resources on modern FPGAs designed for data centres and achieve linear hardware scalability. For a reasonable range of parameters, the system shows near-perfect efficiency and speedup scales linearly when increasing the number of processing elements.

Cited by 4Open access

Automatic Inference of Task Parallelism in Task-Graph-Based Actor Models

Abu Naser Masud, Björn Lisper, Federico Ciccozzi · IEEE Access · 2018

Automatic inference of task level parallelism is fundamental for ensuring many kinds of safety and liveness properties of parallel applications. For example, two tasks running in parallel may be involved in data races when they have conflicting memory accesses, or one is affecting the termination of another by updating shared variables. In this paper, we have considered a task-graph-based actor model, used in signal processing applications (e.g., baseband processing in wireless communication, LTE uplink processing) that are deployed on many-core platforms, in which the actors, task-graphs, and tasks are the active entities running in parallel. The actors invoke task graphs, which in turn invoke tasks, and they communicate through message passing, thus creating different kinds of dependencies and parallelism in the application. We introduce a novel May Happen in Parallel (MHP) analysis for complex parallel applications based on our computational model. The MHP analysis consists of (i) data-flow analysis applicable to parallel control-flow structures inferring MHP facts representing pairs of tasks running in parallel, (ii) identification of all direct and indirect communication by generating a context-free grammar and enumerating valid strings representing parallelism and dependencies among active entities, and (iii) inferring MHP facts when multiple task-graphs communicate. Our analysis is applicable to other computational models (e.g. Cilk or X10) too. We have fully implemented our analysis and evaluated it on signal processing applications consisting of a maximum of 36.57 million lines of code representing 232 different tasks. The analysis took approximately 7 minutes to identify all communication information and 10.5 minutes to identify 12052 executable parallel task-pairs (to analyse for concurrency bugs) proving that our analysis is scalable for industrial-sized code-bases.

Cited by 6Open access

Extracting SIMD Parallelism from Recursive Task-Parallel Programs

Bin Ren, Shruthi Balakrishna, Youngjoon Jo et al. · ACM Transactions on Parallel Computing · 2019

The pursuit of computational efficiency has led to the proliferation of throughput-oriented hardware, from GPUs to increasingly wide vector units on commodity processors and accelerators. This hardware is designed to execute data-parallel computations in a vectorized manner efficiently. However, many algorithms are more naturally expressed as divide-and-conquer, recursive, task-parallel computations. In the absence of data parallelism, it seems that such algorithms are not well suited to throughput-oriented architectures. This article presents a set of novel code transformations that expose the data parallelism latent in recursive, task-parallel programs. These transformations facilitate straightforward vectorization of task-parallel programs on commodity hardware. We also present scheduling policies that maintain high utilization of vector resources while limiting space usage. Across several task-parallel benchmarks, we demonstrate both efficient vector resource utilization and substantial speedup on chips using Intel’s SSE4.2 vector units, as well as accelerators using Intel’s AVX512 units. We then show through rigorous sampling that, in practice, our vectorization techniques are effective for a much larger class of programs.

Cited by 3

CppSs – a C++ Library for Efficient Task Parallelism

Steffen Brinkmann, José Gracia · 2015

We present the C++ library CppSs (C++ superscalar), which provides efficient task-parallelism without the need for special compilers or other software. Any C++ compiler that supports C++11 is sufficient. CppSs features different directionality clauses for defining data dependencies. While the variable argument lists of the taskified functions are evaluated at compile time, the resulting task dependencies are fixed by the runtime value of the arguments and are thus analysed at runtime. With CppSs, we provide task-parallelism using merely native C++. Keywords–high-performance computing; task parallelism; parallel libraries.

Cited by 0

Exploiting Parallelism in Multi-Task Robot Allocation Problems

Branko Miloradović, Baran Çürüklü, Mikael Ekström et al. · 2021

Multi-Agent Systems (MASs) have been widely adopted in robotics, as a means to solve complex missions by subdividing them into smaller tasks. In such a context, Multi-Robot Task Allocation (MRTA) has been a relevant research area, with the main aim of providing formulations and solutions to different mission configurations, in order to optimize the planning and the execution of complex missions utilizing multiple robots. In recent years, robotic systems have become more powerful thanks to the adoption of novel computing platforms, enabling an increased level of parallelism, in terms of sensing, actuation, and computation. As a result, more complex missions can be achieved, at the cost of an increased complexity for the optimization of the mission planning. In this paper, we first introduce the distinction between physical and virtual tasks of the robots, and their relation in terms of parallel execution. Therefore, we propose a mathematical formalization of the mission planning problem for Multi-Task (MT) robots, in the presence of tasks that require only a Single-Robot (SR) to complete, and in the presence of Time-Extended Assignments (TAs). The problem is modeled with a Mixed-Integer Linear Programming (MILP) formulation, with the objective of minimizing the total makespan of the mission, exploiting the potential (physical and virtual) parallelism of the robots. The model is validated over some representative scenarios, and their respective solutions are obtained with the CPLEX optimization tool, showing the generality of the proposed formulation.

Cited by 3

Puppetmaster: a certified hardware architecture for task parallelism

Perez-Lopez, Áron Ricardo · DSpace@MIT (Massachusetts Institute of Technology) · 2021

This thesis presents Puppetmaster, a hardware accelerator for transactional workloads. Existing software and hardware frameworks for transactional memory and online transaction processing are not able to scale to hundreds or thousands of cores unless the rate of conflicts between transactions is very low. Puppetmaster aims to improve upon the scalability of concurrency control by requiring transactions to declare their read and write sets in advance and uses this information to only run transactions concurrently when they are known not to conflict. In this thesis, I present and evaluate the design of Puppetmaster in a high-level model, in cycle-accurate simulations, and on real reconfigurable hardware.

Cited by 1

Dynamic Task Parallelism in FPM and Related Methods

Krogstie, Øystein · Duo Research Archive (University of Oslo) · 2021

Mikroskopi lar oss se detaljer som vanligvis er for små til å se med det blotte øye, men størrelsen på området som avbildes begrenses av forstørrelsesgraden. Innenfor fagfelt som medisinsk bildeforskning og materialvitenskap ønsker man bilder som både er høyoppløste, men som også dekker en stor del av prøven. Å øke både størrelsen og oppløsningen i et konvensjonelt mikroskop krever enten dyrere optiske komponenter, eller store og kompliserte oppsett. I løpet av de siste tiårene har det å bruke datamaskiner til å forbedre bildesystemer, såkalt "computational imaging", blitt stadig mer populært. En ny teknikk innen dette feltet er fourierptychografisk mikroskopi (FPM). I FPM blir en prøve belyst med lys fra ulike vinkler og avbildet i et konvensjonelt lysmikroskop. Resultatbildene blir deretter slått sammen til ett enkelt høyoppløst bilde ved å løse et fasegjenfinningsproblem. Å løse dette fasegjenfinningsproblemet krever imidlertid mye regnekraft, noe som forhindrer FPM-mikroskopet fra å kunne operere i sanntid.\\\\\n\nI denne avhandlingen presenterer vi en modifisert iterativ løser for fasegjenfinning som brukt i FPM som tillater samtidig utførelse av deliterasjoner. Den modifiserte løseren avdekker og utnytter oppgaveparalellitet mellom de ulike deliterasjonene ved hjelp av en prioritetskø som bruker en avhengighetsgraf og en kostnadsfunksjon. Dette reduserer kjøretiden, og eksponerer mer dataparalellitet i FPM-rekonstrussjonsprosessen. Implementasjonen vår kjører ca 5 ganger raskere på en CPU med 16 tråder enn en tilsvarende entrådet versjon av algoritmen, selv uten å utnytte dataparalellitet i problemet, og ved kun en svært liten reduksjon i rekonstruksjonskvalitet. Ettersom mange fasegjenfinningsalgoritmer i både FPM og ptychografi har lignende struktur er det gode muligheter for at denne metoden kan anvendes som et paralelliseringsverktøy på et bredere plan. Forslag til videre arbeid er også inkludert.

Cited by 0Open access

Exploiting task-level parallelism automatically using pTask, M.A.Sc

Sum Huynh · 1996

Existing systems supporting task-level parallelism often involve the process of task synchronization and/or task creation. Task synchronization requires specification of dependencies or dataflow constraints among tasks, or data usage information of tasks. This thesis describes a system called pTask which automatically detects and exploits task-level parallelism in sequential array-based C programs. The system is composed of two components: a compile-time analysis module and a run-time system. The input to the compile-time module is a sequential C program in which the programmer annotates procedures to be asynchronously invoked as tasks. The output is a parallel program containing constructs for the creation and coordination of parallel tasks. pTask utilizes current compile technology to statically extract data usage information of tasks, and uses this information at run-time to dynamically detect and enforce data dependencies among tasks in order to exploit parallelism. A prototype of pTask has been implemented on a KSR1 multiprocessor. Experimental results show the system to be efficient and effective for many applications. iv vAcknowledgments First of all, I would like to express my thankfulness to my supervisor, Professor Tarek Abdelrahman, for having introduced me to task-level parallelism and allowed me to explore and experiment; yet was always ready to offer guidance and advices. I learned so much from him. To the people who helped this research work, I sincerely thank Dennis Gannon and associates from Indiana University for having created Sigma II; and John Ross from University of Toronto for taking care of the KSR machine and having responded (ever so friendly) to my seemingly absurd requests. Financially, I am very grateful for the support from the Natural Sciences and

Cited by 0