pipette
ESEspañol

Accelerating Direct Sparse Solvers with Graph Computing Accelerators

Jiya Su, Fran\c{c}ois-Henry Rouet, Jeff Beisheim, Robert Lucas, Yuqing Wang, Alexander Fell, Chris Mccarthy, David F. Gleich, Andrew A Chien

PreprintBold claims, read criticallyReal-world use

In the authors' words

Solving large sparse linear systems by Gaussian elimination is a challenging computational task due to the introduction of non-zero elements, or fill-in. Practitioners use heuristics such as the nested dissection reordering algorithm to try to reduce fill-in. In practice, reordering codes do not achieve the same parallel scaling as factorization, nor can they exploit AVX instructions or GPUs. Thus, reordering can be the primary runtime bottleneck in large-scale computer-aided engineering applications. We consider the use of a novel accelerator, the UpDown system, to accelerate the METIS multilevel nested dissection reordering algorithm. The UpDown system is designed for a broad class of graph computing and irregular algorithms. We report results for small-scale UpDown systems that will be available commercially in 2027, using validated simulation and FPGA emulation platforms. Our findings indicate that small UpDown systems can speed up METIS by two-orders of magnitude versus a single CPU. Compared to ParMETIS on hundreds of MPI ranks, we anticipate the same small UpDown systems offer speedups of 4 - 7, providing the potential to significantly speed finite element simulations

Main resultLimitation the authors admit

Appeared: Tuesday, November 10. arXiv. Preprint, not yet peer-reviewed.