Improving Cache Utilization of Nested Parallel Programs by Almost Deterministic Work Stealing
Improving Cache Utilization of Nested Parallel Programs by Almost Deterministic Work Stealing
复制标题
DOI：
10.1109/tpds.2022.3196192
复制
发表时间：
2022-12
影响因子：
5.3
通讯作者：
Shumpei Shiina;K. Taura
中科院分区：
文献类型：
--
作者：
Shumpei Shiina;K. Taura
嵌套（fork-join）并行性通过支持并行性的高级表达式并将并行任务和硬件之间的映射留给运行时调度器来简化并行编程。嵌套并行动态调度的一个挑战是如何利用数据局部性，这在具有大量内核的现代处理器的深度缓存层次结构中变得更加苛刻。本文介绍了几乎确定性的工作窃取（ADWS），它通过确定性地规划一个缓存层次感知的调度来有效地利用数据局部性，同时允许少量的调度变化以促进动态负载平衡。此外，我们建议扩展我们之前在ADWS上的工作，以实现更好的共享缓存利用率。调度器的改进版本称为多级ADWS。其思想是，只有工作集大小小到足以放入共享缓存的部分计算才由ADWS在缓存内递归地调度，从而避免过多的容量丢失。我们对并行决策树构建的基准评估表明，多级ADWS比Cilk Plus的传统随机工作窃取性能高出61%，比以前的ADWS设计性能提高了40%。
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.