Skip to Main content Skip to Navigation
Conference papers

A Makespan Lower Bound for the Scheduling of the Tiled Cholesky Factorization based on ALAP Schedule

Abstract : 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. It is also implemented in mainstream dense linear algebra libraries and is used as a testbed for runtime systems. However, we note that 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. Based on the relative costs of involved kernels, we prove that only two different situations must be considered, typically corresponding to CPUs and GPUs. 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 the number of busy processors at any time (as degree 2 polynomials). We then use this information to find a closed form formula for the minimum time to schedule a tiled Cholesky factorization of size n on P processors. We show that this bound outperforms classical bounds from the literature. We also prove that ALAP(P), an ALAP-based schedule where the number of resources is limited to P , has a makespan extremely close to the lower bound, thus proving both the effectiveness of ALAP(P) schedule and of the lower bound on the makespan.
Complete list of metadata

Cited literature [22 references]  Display  Hide  Download
Contributor : Olivier Beaumont <>
Submitted on : Friday, February 21, 2020 - 11:38:41 PM
Last modification on : Thursday, December 3, 2020 - 2:59:38 PM


Files produced by the author(s)


  • HAL Id : hal-02487920, version 1



Olivier Beaumont, Julien Langou, Willy Quach, Alena Shilova. A Makespan Lower Bound for the Scheduling of the Tiled Cholesky Factorization based on ALAP Schedule. EuroPar 2020 - 26th International European Conference on Parallel and Distributed Computing, Aug 2020, Warsaw / Virtual, Poland. ⟨hal-02487920⟩



Record views


Files downloads