.png){kind=icon}
Return
Improving Cache Utilization of Nested Parallel Programs by Almost Deterministic Work Stealing
.png){kind=icon}
OA
AI
DOI：10.1109/TPDS.2022.3196192.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
Nested (fork-join) parallelism eases parallel programming by enabling high-level expression of parallelism and leaving the mapping between parallel tasks and hardware to the runtime scheduler. A challenge in dynamic scheduling of nested parallelism is how to exploit data locality, which has become more demanding in the deep cache hierarchies of modern processors with a large number of cores. This paper introduces almost deterministic work stealing (ADWS), which efficiently exploits data locality by deterministically planning a cache-hierarchy-aware schedule, while allowing a little scheduling variety to facilitate dynamic load balancing. Furthermore, we propose an extension of our prior work on ADWS to achieve better shared cache utilization. The improved version of the scheduler is called multi-level ADWS. The idea is that only part of a computation whose working set size is small enough to fit into a shared cache is scheduled by ADWS within the cache recursively, thus avoiding excessive capacity misses. Our evaluation on a benchmark of parallel decision tree construction demonstrated that multi-level ADWS outperformed the conventional random work stealing of Cilk Plus by 61% and it showed a 40% performance improvement over the previous ADWS design.
Keywords:
Task analysis
Parallel processing
Dynamic scheduling
Decision trees
Program processors
Processor scheduling
Runtime
Dynamic load balancing
locality
nested parallelism
task parallelism
task scheduling
work stealing
Journal
IF:
6
Papers:
5.2K
Citations:
1.1W
Organization
Cited Papers
Searching for exotic particles in high-energy physics with deep learning.png)
NATURE COMMUNICATIONS
NATURE COMMUNICATIONSIF15.7
PREAI
ShareSave
ShareSavePolyamine accumulation during lymphocyte transformation and its relation to the synthesis, processing, and accumulation of ribonucleic acidBiochemistry
BiochemistryIF0
PREAI
ShareSave
View more