DBSR: An Efficient Storage Format for Vectorizing Sparse Triangular Solvers on Structured Grids

The Sparse Triangular Solver (SPTRSV) plays a critical role in solving structured grid problems. Yet, the commonly used sparse matrix storage formats for structured grid methods do not efficiently support SPTRSV in utilizing the instruction parallelism offered by modern multi-core CPUs. We introduce DBSR, a new sparse storage format to enable SPTRSV to take advantage of the SIMD instructions. DBSR promotes contiguous memory access and vectorized computation, while also optimizing memory usage. We evaluate DBSR by applying it within multigrid algorithms and the zero fill-in incomplete $\mathbf{L U}$ preconditioner. Our evaluation, conducted on four architectures - three ARMv8 systems and one x86 system - demonstrates that DBSR consistently outperforms mainstreamed storage formats across evaluation workloads and platforms.