Analysis of Work-Stealing and Parallel Cache Complexity
Analysis of Work-Stealing and Parallel Cache Complexity
复制标题
DOI：
10.1137/1.9781611977059.4
复制
发表时间：
2021-11
期刊：
影响因子：
--
通讯作者：
Yan Gu;Zachary Napier;Yihan Sun
中科院分区：
文献类型：
--
作者：
Yan Gu;Zachary Napier;Yihan Sun
在过去十年中，并行性变得极其流行，并且出现了许多新的并行算法和软件。随机工作窃取（RWS）调度器在这个生态系统中起着至关重要的作用。在本文中，我们研究了与随机工作窃取调度器相关的两个重要主题。我们的第一个贡献是一个简化的、适合课堂教学的RWS调度器分析版本。RWS调度器的理论效率已在多种设置下进行了分析，但其中大多数都相当复杂。在本文中，我们展示了一种新的分析方法，我们认为它易于理解，并且在教育方面特别有用。我们在分析中避免使用势函数，并假设一个高度异步的设置，这对于当今的并行机器来说更符合实际。我们的第二个也是主要的贡献是针对使用RWS调度器的算法的一些新的并行缓存复杂度。尽管在过去几十年中顺序I/O模型已经得到了充分的研究，但到目前为止，很少有结果将其扩展到并行设置。许多现有算法的并行缓存界限受到跨度的多项式的影响，这对高跨度算法造成了显著的开销。我们的新分析将跨度与并行缓存复杂度的分析解耦。这使我们能够为一系列经典算法展示新的并行缓存界限。我们的结果与下限仅相差一个多项对数因子，并显著改进了先前的结果。
Parallelism has become extremely popular over the past decade, and there have been a lot of new parallel algorithms and software. The randomized work-stealing (RWS) scheduler plays a crucial role in this ecosystem. In this paper, we study two important topics related to the randomized work-stealing scheduler. Our first contribution is a simplified, classroom-ready version of analysis for the RWS scheduler. The theoretical efficiency of the RWS scheduler has been analyzed for a variety of settings, but most of them are quite complicated. In this paper, we show a new analysis, which we believe is easy to understand, and can be especially useful in education. We avoid using the potential function in the analysis, and we assume a highly asynchronous setting, which is more realistic for today's parallel machines. Our second and main contribution is some new parallel cache complexity for algorithms using the RWS scheduler. Although the sequential I/O model has been well-studied over the past decades, so far very few results have extended it to the parallel setting. The parallel cache bounds of many existing algorithms are affected by a polynomial of the span, which causes a significant overhead for high-span algorithms. Our new analysis decouples the span from the analysis of the parallel cache complexity. This allows us to show new parallel cache bounds for a list of classic algorithms. Our results are only a polylogarithmic factor off the lower bounds, and significantly improve previous results.