The evolution of processor hardware increasingly supports fine grain parallelism through SIMD (Single Instruction, Multiple Data) vector instruction sets and hardware threading. For instance, the new ARM SVE instruction set allows for hardware implementation of up to 32 double precision SIMD vector sizes per hardware thread. In this work, we focus on vectorization of the triangular solves required in BiCGStab preconditioned with ILU(0) that is particularly numerically effective for IFPEN applications. In our context, expressing some parallelism can be achieved by changing the sparse structure of the matrices through unknown ordering; that can be recast in terms of graph ordering and coloring. We use a graph coloring method named ColorRCM to exhibit fine grain parallelism to feed the SIMD computing units while improving the convergence of the Krylov solver compared to classical greedy graph coloring method. We first evaluate the performance of SIMD-SpTRSV using the permutation provided by ColorRCM and achieve an acceleration between 1.7 and 6 in AVX2 compared to Intel MKL 21.4. Then we examine the impact of ColorRCM ordering on ILU(0)-BiCGStab performance on 201 matrices, including those from the Suite Sparse matrix (The University of Florida Sparse Matrix Collection: https://doi.org/10.1145/2049662.2049663 ) collection and from the IFPEN porous media flow simulations. The solver configuration uses the ColorRCM ordering and vectorized with AVX2 instructions showed the best convergence times in two thirds of the tests.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Sparse Matrix Ordering for Fine Grain Parallel Triangular Solve Using SIMD

  • Aboul-Karim Mohamed El Maarouf,
  • Luc Giraud,
  • Abdou Guermouche,
  • Thomas Guignon

摘要

The evolution of processor hardware increasingly supports fine grain parallelism through SIMD (Single Instruction, Multiple Data) vector instruction sets and hardware threading. For instance, the new ARM SVE instruction set allows for hardware implementation of up to 32 double precision SIMD vector sizes per hardware thread. In this work, we focus on vectorization of the triangular solves required in BiCGStab preconditioned with ILU(0) that is particularly numerically effective for IFPEN applications. In our context, expressing some parallelism can be achieved by changing the sparse structure of the matrices through unknown ordering; that can be recast in terms of graph ordering and coloring. We use a graph coloring method named ColorRCM to exhibit fine grain parallelism to feed the SIMD computing units while improving the convergence of the Krylov solver compared to classical greedy graph coloring method. We first evaluate the performance of SIMD-SpTRSV using the permutation provided by ColorRCM and achieve an acceleration between 1.7 and 6 in AVX2 compared to Intel MKL 21.4. Then we examine the impact of ColorRCM ordering on ILU(0)-BiCGStab performance on 201 matrices, including those from the Suite Sparse matrix (The University of Florida Sparse Matrix Collection: https://doi.org/10.1145/2049662.2049663 ) collection and from the IFPEN porous media flow simulations. The solver configuration uses the ColorRCM ordering and vectorized with AVX2 instructions showed the best convergence times in two thirds of the tests.