Multicore acceleration of priority-based schedulers for concurrency bug detection

Santosh Nagarakatte, Sebastian Burckhardt, Milo M.K. Martin, Madanlal Musuvathi

Research output: Contribution to journalArticlepeer-review

5 Scopus citations


Testing multithreaded programs is difficult as threads can interleave in a nondeterministic fashion. Untested interleavings can cause failures, but testing all interleavings is infeasible. Many interleaving exploration strategies for bug detection have been proposed, but their relative effectiveness and performance remains unclear as they often lack publicly available implementations and have not been evaluated using common benchmarks. We describe NeedlePoint, an open-source framework that allows selection and comparison of a wide range of interleaving exploration policies for bug detection proposed by prior work. Our experience with NeedlePoint indicates that priority-based probabilistic concurrency testing (the PCT algorithm) finds bugs quickly, but it runs only one thread at a time, which destroys parallelism by serializing executions. To address this problem we propose a parallel version of the PCT algorithm (PPCT).We show that the new algorithm outperforms the original by a factor of 5+ when testing parallel programs on an eight-core machine. We formally prove that parallel PCT provides the same probabilistic coverage guarantees as PCT. Moreover, PPCT is the first algorithm that runs multiple threads while providing coverage guarantees.

Original languageEnglish (US)
Pages (from-to)543-554
Number of pages12
JournalACM SIGPLAN Notices
Issue number6
StatePublished - Aug 2012
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Computer Science(all)


  • Concurrency
  • Multithreading
  • Parallel testing
  • Priority-based scheduling
  • Probabilistic concurrency testing


Dive into the research topics of 'Multicore acceleration of priority-based schedulers for concurrency bug detection'. Together they form a unique fingerprint.

Cite this