Staccato: Cache-aware work-stealing task scheduler for shared-memory systems

Research output

1 Citation (Scopus)

Abstract

Parallel tasks work-stealing schedulers yield near-optimal tasks distribution (i.e. all CPU cores are loaded equally) and have low time, memory and inter-thread synchronizations. The key idea of work-stealing strategy is that when scheduler worker runs out of tasks for execution, it start stealing tasks from the queues of other workers. It’s been shown that double ended queues based on circular arrays are effective in this scenario. They are designed with an assumption that tasks pointer are stored in these data structures, while tasks object reside in heap memory. By modifying tasks queues so that they can hold task objects instead pointers we managed to increase the performance above 2.5 times on CPU bound applications and decrease last-level cache misses 30% compared to Intel TBB and Intel/MIT Cilk work-stealing schedulers.

Original languageEnglish
Pages (from-to)91-102
Number of pages12
JournalLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume10963
DOIs
Publication statusPublished - 4 Jul 2018
Event18th International Conference on Computational Science and Its Applications, ICCSA 2018 - Melbourne
Duration: 2 Jul 20185 Jul 2018

Fingerprint

Shared Memory
Scheduler
Cache
Program processors
Queue
Data storage equipment
Data structures
Synchronization
Heap
Thread
Data Structures
Decrease
Scenarios
Object

Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Cite this

@article{b9fb68944a36466faf1ece3ac7bcbb6a,
title = "Staccato: Cache-aware work-stealing task scheduler for shared-memory systems",
abstract = "Parallel tasks work-stealing schedulers yield near-optimal tasks distribution (i.e. all CPU cores are loaded equally) and have low time, memory and inter-thread synchronizations. The key idea of work-stealing strategy is that when scheduler worker runs out of tasks for execution, it start stealing tasks from the queues of other workers. It’s been shown that double ended queues based on circular arrays are effective in this scenario. They are designed with an assumption that tasks pointer are stored in these data structures, while tasks object reside in heap memory. By modifying tasks queues so that they can hold task objects instead pointers we managed to increase the performance above 2.5 times on CPU bound applications and decrease last-level cache misses 30{\%} compared to Intel TBB and Intel/MIT Cilk work-stealing schedulers.",
keywords = "Data structures, Work-stealing deques, Work-stealing scheduler",
author = "Ruslan Kuchumov and Andrey Sokolov and Vladimir Korkhov",
year = "2018",
month = "7",
day = "4",
doi = "10.1007/978-3-319-95171-3_8",
language = "English",
volume = "10963",
pages = "91--102",
journal = "Lecture Notes in Computer Science",
issn = "0302-9743",
publisher = "Springer",

}

TY - JOUR

T1 - Staccato: Cache-aware work-stealing task scheduler for shared-memory systems

AU - Kuchumov, Ruslan

AU - Sokolov, Andrey

AU - Korkhov, Vladimir

PY - 2018/7/4

Y1 - 2018/7/4

N2 - Parallel tasks work-stealing schedulers yield near-optimal tasks distribution (i.e. all CPU cores are loaded equally) and have low time, memory and inter-thread synchronizations. The key idea of work-stealing strategy is that when scheduler worker runs out of tasks for execution, it start stealing tasks from the queues of other workers. It’s been shown that double ended queues based on circular arrays are effective in this scenario. They are designed with an assumption that tasks pointer are stored in these data structures, while tasks object reside in heap memory. By modifying tasks queues so that they can hold task objects instead pointers we managed to increase the performance above 2.5 times on CPU bound applications and decrease last-level cache misses 30% compared to Intel TBB and Intel/MIT Cilk work-stealing schedulers.

AB - Parallel tasks work-stealing schedulers yield near-optimal tasks distribution (i.e. all CPU cores are loaded equally) and have low time, memory and inter-thread synchronizations. The key idea of work-stealing strategy is that when scheduler worker runs out of tasks for execution, it start stealing tasks from the queues of other workers. It’s been shown that double ended queues based on circular arrays are effective in this scenario. They are designed with an assumption that tasks pointer are stored in these data structures, while tasks object reside in heap memory. By modifying tasks queues so that they can hold task objects instead pointers we managed to increase the performance above 2.5 times on CPU bound applications and decrease last-level cache misses 30% compared to Intel TBB and Intel/MIT Cilk work-stealing schedulers.

KW - Data structures

KW - Work-stealing deques

KW - Work-stealing scheduler

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

U2 - 10.1007/978-3-319-95171-3_8

DO - 10.1007/978-3-319-95171-3_8

M3 - Article

AN - SCOPUS:85049974554

VL - 10963

SP - 91

EP - 102

JO - Lecture Notes in Computer Science

JF - Lecture Notes in Computer Science

SN - 0302-9743

ER -