Hyperqueues: Design and Implementation of Deterministic Concurrent Queues

Hans Vandierendonck; Dimitrios S. Nikolopoulos

doi:10.1145/3365660

Hyperqueues: Design and Implementation of Deterministic Concurrent Queues

Hans Vandierendonck, Dimitrios S. Nikolopoulos

School of Electronics, Electrical Engineering and Computer Science

Research output: Contribution to journal › Article › peer-review

237 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 language	English
Article number	23
Number of pages	35
Journal	ACM Transactions on Parallel Computing (TOPC)
Volume	6
Issue number	4
DOIs	https://doi.org/10.1145/3365660
Publication status	Published - 20 Nov 2019

Access to Document

10.1145/3365660Licence: Unspecified

Hyperqueues: Design and Implementation of Deterministic Concurrent Queues
© 2019 Copyright held by the owner/author(s). Publication rights licensed to ACM. This work is made available online in accordance with the publisher’s policies. Please refer to any applicable terms of use of the publisher.
Accepted author manuscript, 836 KBLicence: Unspecified

R6394CSC: Software management of hybrid DRAM/NVRAM memory systems
Nikolopoulos, D. (PI) & Vandierendonck, H. (CoI)
01/08/2012 → …
Project: Research

Cite this

@article{1e487c3df5684466bf007a7c0561c046,

title = "Hyperqueues: Design and Implementation of Deterministic Concurrent Queues",

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.",

author = "Hans Vandierendonck and Nikolopoulos, {Dimitrios S.}",

year = "2019",

month = nov,

day = "20",

doi = "10.1145/3365660",

language = "English",

volume = "6",

journal = "ACM Transactions on Parallel Computing (TOPC)",

issn = "2329-4949",

publisher = "Association for Computing Machinery",

number = "4",

}

TY - JOUR

T1 - Hyperqueues: Design and Implementation of Deterministic Concurrent Queues

AU - Vandierendonck, Hans

AU - Nikolopoulos, Dimitrios S.

PY - 2019/11/20

Y1 - 2019/11/20

N2 - 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.

AB - 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.

U2 - 10.1145/3365660

DO - 10.1145/3365660

M3 - Article

SN - 2329-4949

VL - 6

JO - ACM Transactions on Parallel Computing (TOPC)

JF - ACM Transactions on Parallel Computing (TOPC)

IS - 4

M1 - 23

ER -

Hyperqueues: Design and Implementation of Deterministic Concurrent Queues

Abstract

Access to Document

Fingerprint

Projects

R6394CSC: Software management of hybrid DRAM/NVRAM memory systems

Cite this