article · Infoscience (Ecole Polytechnique Fédérale de Lausanne) · 2014

On Lock-Free Work-stealing Iterators for Parallel Data Structures

Aleksandar Prokopec, Dmitry Petrashko, Martin Odersky

Cited by 10Open access

Abstract

With the rise of multicores, there is a trend of supporting data-parallel collection operations in general purpose programming languages. These operations are highly parametric, incurring abstraction performance penalties. Furthermore, data-parallel operations must scale when applied to irregular workloads. Work-stealing is a proven technique for load balancing irregular workloads, but general purpose work-stealing also suffers abstraction penalties. We present a generic data-parallel collections design based on work-stealing for shared-memory architectures that overcomes abstraction penalties through callsite specialization of data-parallel operation instances. Moreover, we introduce \\textit{work-stealing iterators} that allow fine-grained and efficient work-stealing for particular data-structures. By eliminating abstraction penalties and making work-stealing data-structure-aware we achieve up to 60x better performance compared to JVM-based approaches and 3x speedups compared to tools such as Intel TBB.

Cite this paper

APA 7

Prokopec, A., Petrashko, D., & Odersky, M. (2014). On Lock-Free Work-stealing Iterators for Parallel Data Structures. Infoscience (Ecole Polytechnique Fédérale de Lausanne).

MLA 9

Prokopec, Aleksandar, et al. “On Lock-Free Work-stealing Iterators for Parallel Data Structures.” Infoscience (Ecole Polytechnique Fédérale de Lausanne), 2014.

Chicago

Prokopec, Aleksandar, Dmitry Petrashko, and Martin Odersky. 2014. “On Lock-Free Work-stealing Iterators for Parallel Data Structures.” Infoscience (Ecole Polytechnique Fédérale de Lausanne).

Harvard

Prokopec, A., Petrashko, D. and Odersky, M. (2014) ‘On Lock-Free Work-stealing Iterators for Parallel Data Structures’, Infoscience (Ecole Polytechnique Fédérale de Lausanne).

BibTeX

@article{prokopec2014lock,
  title = {{On Lock-Free Work-stealing Iterators for Parallel Data Structures}},
  author = {Prokopec, Aleksandar and Petrashko, Dmitry and Odersky, Martin},
  journal = {Infoscience (Ecole Polytechnique Fédérale de Lausanne)},
  year = {2014}
}

Made from the index record. Check names, capitalisation and page numbers against the paper. Need another style? AI for Research has over 10,000.