Hyperqueues: Design and Implementation of Deterministic Concurrent Queues

Research output: Contribution to journalArticlepeer-review

39 Downloads (Pure)

Abstract

The hyperqueue is a programming abstraction for queues that results in deterministic and scale-free 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 provide a shared view on a queue data structure. Hereby, hyperqueues guarantee determinism for programs using concurrent queues. We define the programming API and semantics of two instances of the hyperqueue concept. These hyperqueues differ in their API and the degree of concurrency that is extracted. We describe the implementation of the hyperqueues in a work-stealing scheduler and demonstrate scalable performance on pipeline-parallel benchmarks from PARSEC and StreamIt.
Original languageEnglish
Article number23
Number of pages35
JournalACM Transactions on Parallel Computing (TOPC)
Volume6
Issue number4
DOIs
Publication statusPublished - 20 Nov 2019

Fingerprint Dive into the research topics of 'Hyperqueues: Design and Implementation of Deterministic Concurrent Queues'. Together they form a unique fingerprint.

Cite this