TY - JOUR

T1 - Staccato: Shared-memory work-stealing task scheduler with cache-aware memory management

AU - Kuchumov, Ruslan

AU - Sokolov, Andrey

AU - Korkhov, Vladimir

PY - 2019/1/1

Y1 - 2019/1/1

N2 - 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.

AB - 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.

KW - Cache locality

KW - Fork-join parallelism

KW - Lock-free data structures

KW - Work-stealing deques

KW - Work-stealing scheduler

UR - http://www.scopus.com/inward/record.url?scp=85074111740&partnerID=8YFLogxK

U2 - 10.1504/IJWGS.2019.103233

DO - 10.1504/IJWGS.2019.103233

M3 - Article

AN - SCOPUS:85074111740

VL - 15

SP - 394

EP - 407

JO - International Journal of Web and Grid Services

JF - International Journal of Web and Grid Services

SN - 1741-1106

IS - 4

ER -