.png){kind=icon}
返回
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}
原文求助.png){kind=icon}
分享.png){kind=icon}
收藏
摘要
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.
Keyword:
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
期刊
IF:
6
论文数:
5.2K
被引数:
1.1W
机构
引用论文
Searching for exotic particles in high-energy physics with deep learning用深度学习寻找高能物理中的奇异粒子.png)
NATURE COMMUNICATIONS
NATURE COMMUNICATIONSIF15.7
PREAI
分享收藏
Polyamine accumulation during lymphocyte transformation and its relation to the synthesis, processing, and accumulation of ribonucleic acidBiochemistry
BiochemistryIF0
PREAI
分享收藏
查看更多内容