Scholarlink

<p>Finite element analysis solves sparse linear systems via sparse LU decomposition. Supernodal and multifrontal techniques accelerate this process by grouping structurally identical or similar columns (or rows) into dense blocks to leverage highly optimized GEMM routines. However, their efficiency critically depends on the matrix structure – performance drops sharply if repeating patterns are scarce. Although the PanguLU algorithm improves on this by introducing a two-dimensional block-cyclic method, there is still room for improvement in its CPU performance. In our two-dimensional block-cyclic algorithm, we manually unrolled loops for sparse blocks, yielding a 23% speedup over the compiler’s automatic unrolling. We also introduced a dense-row detection algorithm since accessing dense rows is faster, which delivered an 11% improvement in sparse-block performance. In addition, we implemented a dense-block check: because dense operators far outperform sparse ones, applying dense operators to dense blocks further accelerates computation. Furthermore, PanguLU employs a static scheduling algorithm for load balancing, which is ill-suited for single-machine (shared-memory) systems. We adapted it to leverage OpenMP’s dynamic multithreading scheduling, utilizing the depend clause to manage dependencies between blocks. This approach dynamically dispatches tasks based on the actual runtime of blocks, offering significantly greater flexibility. Experimental results show that, compared to PanguLU, our method achieves average speedups of 1.67<InlineEquation ID="IEq1"> <EquationSource Format="TEX">\(\times \)</EquationSource> </InlineEquation> on the Kunpeng chips and 1.71<InlineEquation ID="IEq2"> <EquationSource Format="TEX">\(\times \)</EquationSource> </InlineEquation> on the intel chips. Our implementation is available at <a href="https://github.com/mainfun/QKLU">https://github.com/mainfun/QKLU</a>.</p>

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

Qklu: a two-dimensional block-cyclic sparse direct solver

  • 期刊论文

  • 发表日期：

    2025年11月28日

查看全文
  • Renqian Wan,
  • Jianqiang Huang,
  • Haodong Bian

摘要

Finite element analysis solves sparse linear systems via sparse LU decomposition. Supernodal and multifrontal techniques accelerate this process by grouping structurally identical or similar columns (or rows) into dense blocks to leverage highly optimized GEMM routines. However, their efficiency critically depends on the matrix structure – performance drops sharply if repeating patterns are scarce. Although the PanguLU algorithm improves on this by introducing a two-dimensional block-cyclic method, there is still room for improvement in its CPU performance. In our two-dimensional block-cyclic algorithm, we manually unrolled loops for sparse blocks, yielding a 23% speedup over the compiler’s automatic unrolling. We also introduced a dense-row detection algorithm since accessing dense rows is faster, which delivered an 11% improvement in sparse-block performance. In addition, we implemented a dense-block check: because dense operators far outperform sparse ones, applying dense operators to dense blocks further accelerates computation. Furthermore, PanguLU employs a static scheduling algorithm for load balancing, which is ill-suited for single-machine (shared-memory) systems. We adapted it to leverage OpenMP’s dynamic multithreading scheduling, utilizing the depend clause to manage dependencies between blocks. This approach dynamically dispatches tasks based on the actual runtime of blocks, offering significantly greater flexibility. Experimental results show that, compared to PanguLU, our method achieves average speedups of 1.67 \(\times \) on the Kunpeng chips and 1.71 \(\times \) on the intel chips. Our implementation is available at https://github.com/mainfun/QKLU.