English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Tools annual

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Tools monthly

Global: Zendy Plus monthly

Presents the access of premium content as premium feature

Premium Content

Global: Zendy Plus annual

Global: Zendy Free Plan

Due to the advent of multicore architectures and massive parallelism, thetiled Cholesky factorization algorithm has recently received plenty ofattention and is often referenced by practitioners as a case study. It is alsoimplemented in mainstream dense linear algebra libraries. However, we note thattheoretical study of the parallelism of this algorithm is currently lacking. Inthis paper, we present new theoretical results about the tiled Choleskyfactorization in the context of a parallel homogeneous model withoutcommunication costs. We use standard flop-based weights for the tasks. For a$t$-by-$t$ matrix, we know that the critical path of the tiled Choleskyalgorithm is $9t-10$ and that the weight of all tasks is $t^3$. In thiscontext, we prove that no schedule with less than $0.185 t^2$ processing unitscan finish in a time less than the critical path. In perspective, a naive boundgives $0.11 t^2.$ We then give a schedule which needs less than $0.25t^2+0.16t+3$ processing units to complete in the time of the critical path. Inperspective, a naive schedule gives $0.50 t^2.$ In addition, given a fixednumber of processing units, $p$, we give a lower bound on the execution time asfollows: $$\max( \frac{t^{3}}{p}, \frac{t^{3}}{p} - 3\frac{t^2}{p} + 6\sqrt{2p}- 7 , 9t-10).$$ The interest of the latter formula lies in the middle term. Ourresults stem from the observation that the tiled Cholesky factorization is muchbetter behaved when we schedule it with an ALAP (As Late As Possible) heuristicthan an ASAP (As Soon As Possible) heuristic. We also provide schedulingheuristics which match closely the lower bound on execution time. We believethat our theoretical results will help practical scheduling studies. Indeed,our results enable to better characterize the quality of a practical schedulewith respect to an optimal schedule.

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