Deterministic Scale-Free Pipeline Parallelism with Hyperqueues

Research output: Chapter in Book/Report/Conference proceedingConference contribution

6 Citations (Scopus)
176 Downloads (Pure)

Abstract

Ubiquitous parallel computing aims to make parallel programming accessible to a wide variety of programming areas using deterministic and scale-free programming models built on a task abstraction. However, it remains hard to reconcile these attributes with pipeline parallelism, where the number of pipeline stages is typically hard-coded in the program and defines the degree of parallelism.

This paper introduces hyperqueues, a programming abstraction that enables the construction of deterministic and scale-free pipeline parallel programs. Hyperqueues extend the concept of Cilk++ hyperobjects to provide thread-local views on a shared data structure. While hyperobjects are organized around private local views, hyperqueues require shared concurrent views on the underlying data structure. We define the semantics of hyperqueues and describe their implementation in a work-stealing scheduler. We demonstrate scalable performance on pipeline-parallel PARSEC benchmarks and find that hyperqueues provide comparable or up to 30% better performance than POSIX threads and Intel's Threading Building Blocks. The latter are highly tuned to the number of available processing cores, while programs using hyperqueues are scale-free.
Original languageEnglish
Title of host publicationSC '13 Proceedings of the International Conference on High Performance Computing, Networking, Storage and Analysis
Number of pages12
DOIs
Publication statusPublished - Nov 2013
EventSC13: 25th IEEE/ACM International Conference on High Performance Computing, Networking, Storage and Analysis - CO, Denver, United States
Duration: 17 Nov 201421 Nov 2014

Conference

ConferenceSC13: 25th IEEE/ACM International Conference on High Performance Computing, Networking, Storage and Analysis
Country/TerritoryUnited States
CityDenver
Period17/11/201421/11/2014

Fingerprint

Dive into the research topics of 'Deterministic Scale-Free Pipeline Parallelism with Hyperqueues'. Together they form a unique fingerprint.

Cite this