Reinforcement learning improves parallel processing of sparse matrices
Reinforcement Learning-Guided Graph Transformations for SpTRSV Optimization
Distributed, Parallel, and Cluster ComputingMachine Learning
Summary
Sparse triangular solve (SpTRSV) is a task important in many scientific fields but is hard to speed up because parts depend on others. The authors use reinforcement learning (RL) to find better ways to change the problem’s structure for faster parallel computing. Their RL method reduces the steps and balances the work, improving efficiency compared to traditional hand-crafted rules. It also adapts to new cases with some training, although it doesn’t always work perfectly on very different problems.
What this means in practice
- •For high performance computing teams: Optimize algorithms that solve sparse triangular systems for faster simulation and scientific computations by applying learned graph transformation policies.
- •For data engineers: Improve the efficiency of workflows involving sparse matrix computations by reducing imbalance in task workloads through adaptive graph modifications.
Authors
Buse Yılmaz
Abstract
Sparse triangular solve (SpTRSV) is a fundamental kernel in numerous scientific and engineering applications. However, the data dependencies inherent in sparse triangular matrices significantly limit the available parallelism and make efficient workload distribution challenging. Recent graph transformation techniques address these limitations by modifying the dependency graph of the input matrix to improve parallel execution. Existing graph transformation strategies, however, rely on manually designed heuristics, making their development and adaptation to different optimization objectives challenging. This work proposes a reinforcement learning-guided graph transformation framework for SpTRSV, in which graph transformation is formulated as a sequential decision-making problem and an RL agent learns matrix-dependent transformation policies. Experimental results on real-world sparse matrices demonstrate level reductions of up to 94% and reductions of up to 80% in the coefficient of variation of level costs, while modifying only 1.50% of the rows in the highest case. On average, the RL- guided graph transformation achieves a 23% reduction in the number of levels and a 29% reduction in the coefficient of variation of level costs while rewriting only 0.82% of the matrix rows. Although the heuristic strategies generally achieve more aggressive level reduction(between 31% and 46%), the RL-based approach achieves the largest average reduction in the coefficient of variation of level costs, demonstrating its ability to balance competing graph transformation objectives. The results further show that the learned policies can be transferred to previously unseen matrices through curriculum learning and fine-tuning, while zero-shot experiments provide insights into the limitations of generalizing graph transformation policies across different sparsity patterns.