Telos: A Dataflow Accelerator for Sparse Triangular Solver of Partial Differential Equations

Partial Differential Equations (PDEs) serve as the backbone of numerous scientific problems.Their solutions often rely on numerical methods, which transform these equations into large, sparse systems of linear equations.These systems, solved with iterative methods, exhibit structured sparsity patterns when derived from stencil-based numerical schemes.In preconditioned solvers, the sparse triangular solve procedure, SpTRSV, usually dominates the entire execution due to its loop-carried dependencies.Optimizing SpTRSV requires extracting parallelism from dependent computations.However, prior works have struggled to achieve both high parallelism and data locality, leading to suboptimal performance.We propose Telos, a dataflow accelerator for SpTRSV that exploits structured sparsity patterns in PDE solving.The dataflow execution leverages stencil patterns, efficiently utilizing pipeline parallelism to resolve data dependencies with minimal overhead.We tackle the challenge of complex data dependencies by proposing a plane-parallel pipelining technique that maps computations onto processing elements (PEs) while preserving data locality.A cross-plane communication aggregation technique is developed to streamline data transfers into a systolic manner.Our accelerator features effective pipelining of dependent computations and overlapping of computations with memory accesses.Experiments demonstrate that Telos delivers average speedups of 61×, 8×, and 11× over CPUs, GPUs, state-of-the-art accelerator, respectively.