A Makespan Lower Bound for the Tiled Cholesky Factorization Based on ALAP Schedule.
A Makespan Lower Bound for the Tiled Cholesky Factorization Based on ALAP Schedule.
复制标题
基于 ALAP 计划的平铺 Cholesky 分解的 Makespan 下界。
DOI：
10.1007/978-3-030-57675-2_9
复制
发表时间：
2020
期刊：
影响因子：
--
通讯作者：
Shilova, Alena
中科院分区：
文献类型：
--
作者：
Beaumont, Olivier;Langou, Julien;Quach, Willy;Shilova, Alena
由于多核架构和大规模并行性的出现，平铺Cholesky分解算法最近受到了广泛的关注，并经常被从业者作为案例研究。然而，我们注意到，该算法的并行性的理论研究是目前缺乏。在本文中，我们提出了新的理论结果的上下文中的一个平行齐次模型没有通信成本的平铺Cholesky分解。通过对无资源限制的阿拉普（As Late As Possible）调度中同时运行的每种类型的任务数的仔细分析，我们能够精确地确定任意时刻忙碌处理器数的上界（作为2次多项式）.然后，我们使用这些信息，找到一个封闭的形式公式的最小时间的下限，以安排一个平铺Cholesky因式分解的sizeonprocessors。我们表明，这个下限优于（大于）经典的下限从文献中。我们还表明，阿拉普（），一个ALAP为基础的时间表的资源数量是有限的，有一个最大完工时间非常接近的下限，从而建立了有效的阿拉普（）计划和我们的新的最大完工时间的下限。
Due to the advent of multicore architectures and massive parallelism, the tiled Cholesky factorization algorithm has recently received plenty of attention and is often referenced by practitioners as a case study. However, we note that a theoretical study of the parallelism of this algorithm is currently lacking. In this paper, we present new theoretical results about the tiled Cholesky factorization in the context of a parallel homogeneous model without communication costs. By a careful analysis on the number of tasks of each type that run simultaneously in the ALAP (As Late As Possible) schedule without resource limitation, we are able to determine precisely an upper bound on the number of busy processors at any time (as degree 2 polynomials). We then use this information to find a closed form formula for a lower bound on the minimum time to schedule a tiled Cholesky factorization of sizeonprocessors. We show that this lower bound outperforms (is larger than) classical lower bounds from the literature. We also demonstrate that ALAP(), an ALAP-based schedule where the number of resources is limited to, has a makespan extremely close to the lower bound, thus establishing both the effectiveness of ALAP() schedule and of our new lower bound on the makespan.