Title: Staccato: shared-memory work-stealing task scheduler with cache-aware memory management

Authors: Ruslan Kuchumov; Andrey Sokolov; Vladimir Korkhov

Addresses: Saint Petersburg State University, 7/9 Universitetskaya Nab., St. Petersburg, 199034, Russia ' Institute of Applied Mathematical Research, Karelian Research Centre RAS, Petrozavodsk, Russia ' Saint Petersburg State University, 7/9 Universitetskaya Nab., St. Petersburg, 199034, Russia

Abstract: Work-stealing is one of the popular ways to schedule near-optimal task distribution across multiple CPU cores with low overheads on time, memory and inter-thread synchronisations. In the work-stealing strategy, workers that run out of tasks for execution start claiming tasks from other workers' queues. Double ended queues (deques) based on circular arrays proved to be an effective solution for such scenario. In this paper we investigate ways to improve performance of work-stealing schedulers based on deques by enhancing internal data handling mechanisms. Traditionally, deques are designed with an assumption that task pointers are stored within these data structures, while task objects reside in the heap memory. By modifying task queues so that they can hold task objects instead of pointers we managed to increase the performance more than 2.5 times on CPU-bound applications and decrease last-level cache misses up to 30% compared to Intel TBB and Intel/MIT Cilk work-stealing schedulers.

Keywords: work-stealing scheduler; work-stealing deques; lock-free data structures; cache locality; fork-join parallelism.

DOI: 10.1504/IJWGS.2019.103233

International Journal of Web and Grid Services, 2019 Vol.15 No.4, pp.394 - 407

Received: 09 Jan 2019
Accepted: 18 Jul 2019
Published online: 22 Oct 2019 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article