A communication-avoiding 3D algorithm for sparse LU factorization on heterogeneous systems

摘要

We propose a new algorithm to improve the strong scalability of right-looking sparse LU factorization on distributed memory systems. Our 3D algorithm for sparse LU uses a three-dimensional MPI process grid, exploits elimination tree parallelism, and trades off increased memory for reduced per-process communication. We also analyze the asymptotic improvements for planar graphs (e.g., those arising from 2D grid or mesh discretizations) and certain non-planar graphs (specifically for 3D grids and meshes). For a planar graph with n vertices, our algorithm reduces communication volume asymptotically in n by a factor of 0 (root log n) and latency by a factor of 0 (log n). For non planar cases, our algorithm can reduce the per-process communication volume by 3x and latency by o (n(1/3)) times. In all cases, the memory needed to achieve these gains is a constant factor. We implemented our algorithm by extending the 2D data structure used in SuPERLU_DIST. Our new 3D code achieves empirical speedups up to 27x for planar graphs and up to 3.3x for non-planar graphs over the baseline 2D SuPERLU_DIST when run on 24,000 cores of a Cray XC30. We extend the 3D algorithm for heterogeneous architectures by adding the Highly Asynchronous Lazy Offload (HALO) algorithm for co-processor offload [44]. On 4096 nodes of a Cray XK7 with 32,768 CPU cores and 4096 Nvidia K20x GPUs, the 3D algorithm achieves empirical speedups up to 24x for planar graphs and 3.5x for non-planar graphs over the baseline 2D SuPERLU_DIST with co-processor acceleration. (C) 2019 Elsevier Inc. All rights reserved.