Abstract
The sTiles framework introduces a novel approach to the Cholesky factorization of structured sparse matrices, specifically "block arrowhead" matrices common in Bayesian inference. By integrating dense tile-based algorithms with a tree-reduction scheduling strategy, sTiles achieves significant performance improvements over traditional sparse and dense solvers, with speedups reaching up to 11x against industry-standard libraries.
Introduction
In scientific computing, particularly within spatial and spatiotemporal statistical modeling (such as the INLA framework), researchers frequently encounter block arrowhead matrices. These matrices feature dense clusters of non-zero elements along the diagonal and the final rows and columns, while remaining largely sparse elsewhere.
Existing linear algebra libraries often struggle with this specific geometry. Sparse solvers fail to exploit the local density of the blocks, resulting in poor hardware utilization. Conversely, dense solvers waste computational cycles and memory on zero elements. Furthermore, the arrowhead structure typically results in a thin dependency graph, creating a sequential bottleneck that limits the effectiveness of multi-core CPU scaling.
The sTiles Methodology
sTiles addresses these challenges by treating structured sparse matrices as a collection of dense tiles. This hybrid approach allows for high arithmetic intensity while maintaining the memory efficiency of sparse representations.
Algorithmic Innovations
- Compressed Tile Storage: The matrix is partitioned into fixed-size dense blocks ("tiles"). Empty tiles are bypassed, while dense tiles are processed using optimized kernels.
- Structure-Aware Permutation: The framework utilizes an adaptable Nested Dissection (ND) method to reorder matrices. This preserves the essential arrowhead shape while exposing independent sub-blocks for parallel execution.
- Tree Reduction for Parallelism: To overcome the sequential constraints of the arrowhead dependency graph,
sTilesimplements a tree-reduction technique for matrix updates. By restructuring updates into a binary tree, the framework enables multiple processing units to aggregate results concurrently.
GPU Acceleration
The heavy computational load of dense tile operations is offloaded to NVIDIA GPUs. sTiles utilizes cuBLAS and cuSOLVER kernels, managed by a static scheduler to maximize throughput on architectures like the NVIDIA A100.
Performance Evaluation
The authors evaluated sTiles using 20 synthetic matrices (ranging from 10k to 1M rows) designed to replicate the computational demands of the INLA framework.
Comparative Results
On CPU platforms, sTiles significantly outperformed established libraries, achieving speedups of:
- 8.41x over CHOLMOD
- 9.34x over SymPACK
- 5.07x over MUMPS
- 11.08x over PARDISO
The tree-reduction technique alone provided a 20x speedup for update accumulations. When accelerated by an NVIDIA A100 GPU, sTiles delivered a 5x speedup over a 32-core AMD EPYC CPU for 50k-sized matrices and a 2.7x speedup for 1M-sized matrices.
Conclusion
sTiles demonstrates that a "structure-aware" hybrid approach is essential for efficiently factorizing large-scale structured sparse matrices. By combining tile-based processing with hierarchical task scheduling, the framework effectively breaks the parallelization barriers inherent in arrowhead matrices. Future developments will focus on out-of-core memory management and multi-GPU support to further scale these capabilities.
Summary updated