Steal tree: Low-overhead tracing of work stealing schedulers

Jonathan Lifflander, Sriram Krishnamoorthy, Laxmikant V Kale

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

Abstract

Work stealing is a popular approach to scheduling task-parallel programs. The flexibility inherent in work stealing when dealing with load imbalance results in seemingly irregular computation structures, complicating the study of its runtime behavior. In this paper, we present an approach to efficiently trace async-finish parallel programs scheduled using work stealing. We identify key properties that allow us to trace the execution of tasks with low time and space overheads. We also study the usefulness of the proposed schemes in supporting algorithms for data-race detection and retentive stealing presented in the literature. We demonstrate that the perturbation due to tracing is within the variation in the execution time with 99% confidence and the traces are concise, amounting to a few tens of kilobytes per thread in most cases. We also demonstrate that the traces enable significant reductions in the cost of detecting data races and result in low, stable space overheads in supporting retentive stealing for async-finish programs.

Original languageEnglish (US)
Title of host publicationPLDI 2013 - Proceedings of the 2013 ACM SIGPLAN Conference on Programming Language Design and Implementation
Pages507-518
Number of pages12
DOIs
StatePublished - Sep 2 2013
Event34th ACM SIGPLAN Conference on Programming Language Design and Implementation, PLDI 2013 - Seattle, WA, United States
Duration: Jun 16 2013Jun 19 2013

Publication series

NameProceedings of the ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI)

Other

Other34th ACM SIGPLAN Conference on Programming Language Design and Implementation, PLDI 2013
CountryUnited States
CitySeattle, WA
Period6/16/136/19/13

Keywords

  • Async-finish parallelism
  • Tracing
  • Work-stealing schedulers

ASJC Scopus subject areas

  • Software

Fingerprint Dive into the research topics of 'Steal tree: Low-overhead tracing of work stealing schedulers'. Together they form a unique fingerprint.

  • Cite this

    Lifflander, J., Krishnamoorthy, S., & Kale, L. V. (2013). Steal tree: Low-overhead tracing of work stealing schedulers. In PLDI 2013 - Proceedings of the 2013 ACM SIGPLAN Conference on Programming Language Design and Implementation (pp. 507-518). (Proceedings of the ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI)). https://doi.org/10.1145/2462156.2462193