Basker: A Threaded Sparse LU Factorization Utilizing Hierarchical Parallelism and Data Layouts

Citations Over TimeTop 17% of 2016 papers

Abstract

Scalable sparse LU factorization is critical for efficient numerical simulation of circuits and electrical power grids. In this work, we present a new scalable sparse direct solver called Basker. Basker introduces a new algorithm to parallelize the Gilbert-Peierls algorithm for sparse LU factorization. As architectures evolve, there exists a need for algorithms that are hierarchical in nature to match the hierarchy in thread teams, individual threads, and vector level parallelism. Basker is designed to map well to this hierarchy in architectures. There is also a need for data layouts to match multiple levels of hierarchy in memory. Basker uses a two-dimensional hierarchical structure of sparse matrices that maps to the hierarchy in the memory architectures and to the hierarchy in parallelism. We present performance evaluations of Basker on the Intel SandyBridge and Xeon Phi platforms using circuit and power grid matrices taken from the University of Florida sparse matrix collection and from Xyce circuit simulations. Basker achieves a geometric mean speedup of 5.91× on CPU (16 cores) and 7.4× on Xeon Phi (32 cores) relative to KLU. Basker outperforms Intel MKL Pardiso (PMKL) by as much as 30× on CPU (16 cores) and 7.5× on Xeon Phi (32 cores) for low fill-in circuit matrices. Furthermore, Basker provides 5.4× speedup on a challenging matrix sequence taken from an actual Xyce simulation.

Related Papers

• → Optimizing the PCIT algorithm on stampede's Xeon and Xeon Phi processors for faster discovery of biological networks(2013)18 cited
• → Training Large Scale Deep Neural Networks on the Intel Xeon Phi Many-Core Coprocessor(2014)22 cited
• → Mapping of option pricing algorithms onto heterogeneous many-core architectures(2017)5 cited
• → Performance Aspects of Collocated and Staggered Grids for Particle-in-Cell Plasma Simulation(2017)1 cited
• → Accelerating Pattern Matching on Intel Xeon Phi Processors(2020)