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.
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: 21 Oct 2019 *