Track papers across labs, topics, and trends.
Search papers, labs, and topics across Lattice.
This paper introduces a reinforcement learning (RL) framework to automate graph transformations for optimizing sparse triangular solve (SpTRSV) performance, moving beyond manual heuristics. By treating graph transformation as a sequential decision-making problem, an RL agent learns matrix-dependent policies to reduce parallelism bottlenecks. Experiments show significant reductions in SpTRSV levels and level cost variance, with minimal matrix modifications, and demonstrate policy transferability via curriculum learning.
An RL agent learns to optimize SpTRSV parallelism by intelligently rewriting sparse matrix dependency graphs, achieving substantial performance gains with minimal structural changes.
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.