Steal tree: Low-overhead tracing of work stealing schedulers

Jonathan Lifflander, Sriram Krishnamoorthy, Laxmikant V. Kale

Research output: Contribution to journalArticlepeer-review


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)
Pages (from-to)507-518
Number of pages12
JournalACM SIGPLAN Notices
Issue number6
StatePublished - Jun 2013


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

ASJC Scopus subject areas

  • Computer Science(all)


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

Cite this