Huawei Computing Systems Lab

Abstract

We introduce stale synchronous parallel as a mode of execution in parallel sparse triangular linear system solve and present a general directed-acyclic-graph scheduler capable of producing such schedules. Stale-synchronous-parallel schedules allow the overlap of synchronisation and compute which results in a geometric-mean speed-up of 7-30% of our scheduler, ElasticDivide, over state-of-the-art synchronous scheduler GrowLocal on an ARM machine using 48 cores. On an x86 machine using 48 cores, we report geometric-mean speed-ups of 19-60% over SpMP.

Abstract on arXiv

DOI arXiv PDF

Cite this work

@misc{elasticityinparallelsparsetriangularsolve,
  title = {Elasticity in Parallel Sparse Triangular Solve},
  author = {Raphael Sebastian Steiner and Christos Konstantinos Matzoros and Pál András Papp and Toni Boehnlein and Albert-Jan N. Yzelman},
  year = {2026},
  note = {ICPP},
  url = {https://doi.org/10.1145/3832810.3832901}
}

Download