Reinforcement Learning-Guided Graph Transformations for SpTRSV Optimization

📄 arXiv: 2609.40159v1 📥 PDF

作者: Buse Yılmaz

分类: cs.DC, cs.LG

发布日期: 2026-09-30

备注: 33 pages, 3 figures, 7 tables. Submitted to The Journal of Supercomputing and currently under review

💡 一句话要点

提出基于强化学习的图变换框架以优化稀疏三角求解

🎯 匹配领域: 支柱二：RL算法与架构 (RL & Architecture)

关键词: 稀疏矩阵 强化学习 图变换 稀疏三角求解 优化算法

📋 核心要点

  1. 现有的图变换策略依赖于手动设计的启发式方法，难以适应不同的优化目标。
  2. 本文提出了一种基于强化学习的图变换框架，将图变换视为序列决策问题，利用RL代理学习变换策略。
  3. 实验显示，RL引导的图变换在层数和层成本变异系数上分别减少了23%和29%，并且修改的行数极少。

📝 摘要（中文）

稀疏三角求解（SpTRSV）是众多科学与工程应用中的基础内核。然而，稀疏三角矩阵固有的数据依赖性显著限制了可用的并行性，并使得高效的工作负载分配变得困难。现有的图变换技术通过修改输入矩阵的依赖图来改善并行执行，但这些方法依赖于手动设计的启发式策略，导致其开发和适应不同优化目标的挑战。本文提出了一种基于强化学习的图变换框架，将图变换形式化为一个序列决策问题，强化学习代理学习与矩阵相关的变换策略。实验结果表明，在真实稀疏矩阵上，平均减少了23%的层数和29%的层成本变异系数，且仅修改了0.82%的矩阵行。

🔬 方法详解

问题定义：本文旨在解决稀疏三角求解中的数据依赖性问题，这限制了并行性和工作负载分配的效率。现有方法依赖于手动设计的启发式策略，难以灵活应对不同的优化需求。

核心思路：提出的框架将图变换视为一个序列决策问题，通过强化学习代理自动学习与矩阵相关的变换策略，以优化稀疏三角求解的性能。

技术框架：整体架构包括数据预处理、图依赖性分析、强化学习训练和策略应用四个主要模块。首先对输入矩阵进行分析，然后通过RL代理进行策略学习，最后将学习到的策略应用于图变换。

关键创新：最重要的创新在于将图变换问题转化为强化学习问题，使得变换策略能够自适应不同的稀疏矩阵，克服了传统启发式方法的局限性。

关键设计：在设计中，采用了特定的奖励函数来引导RL代理学习有效的变换策略，并通过课程学习和微调实现策略的迁移能力。

🖼️ 关键图片

fig_0
fig_1
fig_2

📊 实验亮点

实验结果表明，基于强化学习的图变换方法在层数上平均减少了23%，层成本变异系数减少了29%。尽管启发式策略在层数减少上更为激进，但RL方法在层成本变异系数的平均减少上表现最佳，显示出其在平衡多重优化目标方面的优势。

🎯 应用场景

该研究的潜在应用领域包括高性能计算、科学计算和工程模拟等，能够显著提升稀疏矩阵求解的效率。未来，该框架有望在更广泛的矩阵优化问题中发挥作用，推动相关领域的技术进步。

📄 摘要（原文）

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.