Staccato: shared-memory work-stealing task scheduler with cache-aware memory management Online publication date: Tue, 22-Oct-2019
by Ruslan Kuchumov; Andrey Sokolov; Vladimir Korkhov
International Journal of Web and Grid Services (IJWGS), Vol. 15, No. 4, 2019
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.
Existing subscribers:
Go to Inderscience Online Journals to access the Full Text of this article.
If you are not a subscriber and you just want to read the full contents of this article, buy online access here.Complimentary Subscribers, Editors or Members of the Editorial Board of the International Journal of Web and Grid Services (IJWGS):
Login with your Inderscience username and password:
Want to subscribe?
A subscription gives you complete access to all articles in the current issue, as well as to all articles in the previous three years (where applicable). See our Orders page to subscribe.
If you still need assistance, please email subs@inderscience.com
Our Blog 
Follow us on Twitter 
Visit us on Facebook