Standard

Staccato: Cache-aware work-stealing task scheduler for shared-memory systems. / Kuchumov, Ruslan; Sokolov, Andrey; Korkhov, Vladimir.

In: Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), Vol. 10963, 04.07.2018, p. 91-102.

Research output: Contribution to journal › Article › peer-review

Harvard

Kuchumov, R, Sokolov, A & Korkhov, V 2018, 'Staccato: Cache-aware work-stealing task scheduler for shared-memory systems', Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 10963, pp. 91-102. https://doi.org/10.1007/978-3-319-95171-3_8

APA

Kuchumov, R., Sokolov, A., & Korkhov, V. (2018). Staccato: Cache-aware work-stealing task scheduler for shared-memory systems. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 10963, 91-102. https://doi.org/10.1007/978-3-319-95171-3_8

Vancouver

Kuchumov R, Sokolov A, Korkhov V. Staccato: Cache-aware work-stealing task scheduler for shared-memory systems. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 2018 Jul 4;10963:91-102. https://doi.org/10.1007/978-3-319-95171-3_8

Author

Kuchumov, Ruslan ; Sokolov, Andrey ; Korkhov, Vladimir. / Staccato: Cache-aware work-stealing task scheduler for shared-memory systems. In: Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 2018 ; Vol. 10963. pp. 91-102.

BibTeX

@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{\textquoteright}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 = jul,
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 Nature",
note = "18th International Conference on Computational Science and Its Applications, ICCSA 2018 ; Conference date: 02-07-2018 Through 05-07-2018",

}

RIS

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

T2 - 18th International Conference on Computational Science and Its Applications, ICCSA 2018

Y2 - 2 July 2018 through 5 July 2018

ER -

ID: 35284195