Skip to Main content Skip to Navigation
Journal articles

Reordering Strategy for Blocking Optimization in Sparse Linear Solvers

Grégoire Pichon 1 Mathieu Faverge 1, 2 Pierre Ramet 1 Jean Roman 1 
1 HiePACS - High-End Parallel Algorithms for Challenging Numerical Simulations
LaBRI - Laboratoire Bordelais de Recherche en Informatique, Inria Bordeaux - Sud-Ouest
Abstract : Solving sparse linear systems is a problem that arises in many scientific applications, and sparse direct solvers are a time consuming and key kernel for those applications and for more advanced solvers such as hybrid direct-iterative solvers. For this reason, optimizing their performance on modern architectures is critical. The preprocessing steps of sparse direct solvers, ordering and block-symbolic factorization, are two major steps that lead to a reduced amount of computation and memory and to a better task granularity to reach a good level of performance when using BLAS kernels. With the advent of GPUs, the granularity of the block computation became more important than ever. In this paper, we present a reordering strategy that increases this block granularity. This strategy relies on the block-symbolic factorization to refine the ordering produced by tools such as Metis or Scotch, but it does not impact the number of operations required to solve the problem. We integrate this algorithm in the PaStiX solver and show an important reduction of the number of off-diagonal blocks on a large spectrum of matrices. This improvement leads to an increase in efficiency of up to 20% on GPUs.
Complete list of metadata

Cited literature [28 references]  Display  Hide  Download
Contributor : Mathieu Faverge Connect in order to contact the contributor
Submitted on : Wednesday, March 8, 2017 - 10:28:34 PM
Last modification on : Wednesday, March 2, 2022 - 4:10:01 PM
Long-term archiving on: : Friday, June 9, 2017 - 2:22:04 PM


Files produced by the author(s)


  • HAL Id : hal-01485507, version 1


Grégoire Pichon, Mathieu Faverge, Pierre Ramet, Jean Roman. Reordering Strategy for Blocking Optimization in Sparse Linear Solvers. SIAM Journal on Matrix Analysis and Applications, Society for Industrial and Applied Mathematics, 2017. ⟨hal-01485507v1⟩



Record views


Files downloads