基于E-Graph反统一化的可复用指令发现：ISAMORE框架学术研究报告

一、 作者、机构与发表信息

本研究报告的核心内容基于Youwei Xiao、Chenyun Yin、Yitian Sun、Yuyang Zou和Yun Liang（通讯作者）共同完成的研究工作。所有作者均来自北京大学，其中Youwei Xiao和Yun Liang来自北京大学集成电路学院，Chenyun Yin、Yitian Sun和Yuyang Zou来自北京大学。该研究成果以论文形式发表，论文标题为“Finding Reusable Instructions via E-Graph Anti-Unification”，发表于2026年3月22日至26日在美国匹兹堡举行的第31届ACM编程语言与操作系统架构支持国际会议（ASPLOS ’26）的会议论文集。该论文已获得ACM ISBN编号，并遵循知识共享署名4.0国际许可协议。

二、 学术背景与研究动机

本研究属于计算机体系结构、硬件/软件协同设计以及编译器技术交叉领域，具体聚焦于应用特定指令集处理器（Application-Specific Instruction-set Processor, ASIP）的自动化设计。随着数字信号处理、人工智能等计算密集型领域的快速发展，通用处理器的性能提升已难以满足特定应用对计算能力和能效的严苛要求，尤其是在物联网、边缘设备等资源受限的场景下。定制指令（Custom Instructions, CIs）结合专用硬件单元或加速器，成为一种强大的解决方案。RISC-V等开放、可扩展指令集架构的兴起，进一步推动了这一趋势。

然而，为特定应用领域设计高效且可复用的定制指令面临巨大挑战。现有自动化方法主要存在两大局限：1) 可复用性差：现有方法大多基于程序热点（hotspots）的语法分析，仅能识别或合并语法结构相似的指令序列，而忽略了语义上等效的模式。这导致生成的定制指令过度特化，仅能被应用程序中的少数代码片段使用，硬件面积利用率低下。2) 并行性发掘有限：现有方法主要关注标量指令序列，未能有效发掘数据级并行性（Data-Level Parallelism, DLP）以生成向量化的定制指令。

本研究的目标是提出一种新颖的方法论，能够从领域应用中自动发现语义上等效、高度可复用且能发掘数据并行性的定制指令模式，从而克服现有方法的局限性，充分释放定制指令的潜力，实现性能与硬件开销的最佳平衡。

三、 研究方法与详细工作流程

本研究提出了一个名为ISAMORE的端到端框架，其核心是可复用指令识别（Reusable Instruction Identification, RII） 方法论。RII利用E-Graph（等价图）数据结构和反统一化（Anti-Unification, AU）技术来识别跨不同应用程序的语义等效公共模式。整个工作流程包含多个精密设计的步骤，旨在解决将E-Graph AU应用于实际指令定制所面临的三大挑战：通用程序表示、算法可扩展性以及性能最优模式选择。

1. 结构化领域特定语言（DSL）与E-Graph编码 * 研究目标与对象：为了将具有复杂控制流（如条件分支、循环）的真实世界程序表示为E-Graph中的项（terms），研究团队设计了一种结构化的DSL。该DSL不仅包含算术、逻辑、内存访问等数据流操作，还专门引入了if和loop操作来结构化地表示条件执行和循环语义。此外，DSL还包含向量操作以及用于模式应用的特殊构造。 * 方法与处理：ISAMORE的前端包含LLVM编译流程。首先，通过自定义的LLVM Pass将应用程序的LLVM中间表示（IR）转换为此结构化DSL。然后，将DSL程序直接编码为E-Graph：DSL中的每个表达式对应一个E-Node（操作符为构造器，子节点为包含其参数的E-Class）。重复的表达式会被吸收到同一个E-Class中，实现紧凑表示。同时，一个强类型系统被集成到E-Graph分析中，用于推断每个E-Class的结果类型，这对后续的高效模式匹配至关重要。

2. 面向阶段的迭代式RII流程 * 核心算法：RII采用一种分阶段的迭代算法（如图7所示），而非一次性应用所有重写规则。流程始于初始化的E-Graph和一个空的帕累托前沿（用于存储权衡性能与面积的解决方案集合）。 * 迭代过程：在每一轮迭代中，调度器根据当前解决方案状态，选择一个特定的重写规则子集（R≡）。迭代过程首先将上一轮已识别的模式作为重写规则应用于当前E-Graph（κ(P_pre)），然后应用选定的规则子集进行等式饱和（Equality Saturation, EqSat）。EqSat过程会穷举应用重写规则，发现并合并语义等价的表达式，从而扩展E-Graph的表示空间。 * 创新性与优势：这种分阶段策略有两大好处：a) 控制规模：避免一次性应用所有规则导致的E-Graph规模爆炸式增长，使其能够处理真实应用（通常超过2000个E-Class）。b) 渐进式发现：允许在后续阶段识别先前已发现模式的公共子结构，从而发现更具复用性的高层次模式。例如，先发现模式(x+y)*2，后续可能进一步泛化为(x+y)*z。

3. 智能反统一化（Smart AU）识别 * 挑战：在饱和的E-Graph上直接进行AU（如LLMT算法）需要枚举所有E-Class对并遍历其结构，导致候选模式数量呈指数增长，对于大规模程序不可行。 * 创新方法：RII引入了“智能AU”技术来提升可扩展性。 * 基于相似性的E-Class配对：并非比较所有E-Class对，RII利用E-Class分析为每个E-Class计算一个64位的结构哈希值。该哈希值通过其构造器和子节点的哈希递归计算，并对字面值、参数等统一处理以聚焦结构匹配。仅当两个E-Class的结果类型一致且其结构哈希值的Jaccard距离超过预设阈值时，才对其进行AU计算，大幅减少了需要处理的配对数量。 * 启发式模式采样：对于需要AU的E-Class对，RII不再枚举所有可能的反统一化模式，而是采用启发式采样策略来获取代表性模式子集。论文提出了两种策略：边界策略仅保留特征值（综合考虑延迟和面积）最小和最大的极端模式；KD-Tree策略则在特征向量空间中使用KD-Tree数据结构进行分区，从每个分区中均匀采样。这有效控制了候选模式集合的大小。

4. 基于AU的模式向量化 * 目标：发掘标量程序中的数据级并行性，生成向量化定制指令。 * 流程： * 种子打包：首先通过智能AU找到在E-Graph中多次出现的标量模式（种子）。将这些种子实例的根节点（位于同一基本块内）通过vec操作符合并，形成向量项。 * 包扩展：应用“提升”重写规则，将标量操作符的vec组合替换为对应的向量化操作符（如vecadd），并在向量与标量数据流之间插入get操作进行耦合，构建混合标量-向量的E-Graph。 * 无环剪枝：为了解决向量-标量耦合引入的循环和组合爆炸问题，RII采用一种贪婪的提取器，优先选择具有高DLP潜力的向量构造器，将特定的向量化方案融合回原始标量E-Graph中，从而得到一个轻量级、无环的混合E-Graph，用于后续的向量化模式识别与选择。

5. 硬件感知的成本模型与多目标选择/提取 * 成本模型：RII引入了一个基于性能剖析和高级综合（HLS）的硬件感知成本模型来评估每个候选模式的收益。对于模式p，其总延迟节省δL(p)计算为其所有使用实例的软件执行周期（通过Gem5模拟器插桩剖析获得）之和，减去该模式作为硬件加速器（通过轻量级HLS引擎进行ASAP调度得到）的预计执行周期。整体加速比S(P)和面积开销A(P)则基于所选模式集合P计算。 * 多目标选择：利用E-Class分析，为每个E-Class和E-Node关联一个帕累托前沿（包含多个模式集合解决方案）。通过传播规则（对于非app节点，计算其子节点前沿的笛卡尔积；对于app节点，则将模式加入集合），最终在根E-Class处得到一组帕累托最优解，代表了加速比与面积开销之间的不同权衡。 * 提取与精炼：对于每个选中的非支配解（模式集合），RII使用配置了最大化延迟节省成本函数的提取器，从应用了这些模式重写规则的E-Graph中提取最终程序。随后进行保真度精炼，基于提取后的程序重新精确计算成本模型，并更新全局解决方案集。

四、 主要实验结果与分析

研究团队通过广泛的评估来验证ISAMORE的有效性、性能优势及可扩展性。

1. 与基线方法的性能对比 * 实验设置：在9个基准测试内核（来自计算机视觉、信号处理、密码学等领域）和一个复合基准上，将ISAMORE与三种基线方法对比：ENUM（基于[22,29]的细粒度枚举方法）、NOVIA[60]（基于语法合并的粗粒度方法）和NoEqSat（禁用EqSat的ISAMORE默认模式，即不考虑语义等价）。 * 结果与分析：如图10所示，ISAMORE在适中的面积开销下， consistently实现了比基线方法更高的加速比。NOVIA由于卸载整个基本块，硬件面积大且可能包含在更高频率处理器上运行更快的指令序列，导致性能不理想，尤其在qrdecomp和all基准上。ISAMORE的最大加速比解决方案平均比NOVIA高1.52倍（范围1.12-1.94倍）。ENUM需要更多面积才能达到与ISAMORE相似的加速比，因为它生成了大量差异微小的重复指令，证明了可复用性引导的重要性。与NoEqSat相比，ISAMORE平均加速比高1.12倍，而平均面积仅为后者的84.9%，这直接证明了利用语义等价能发现更高效的加速模式。例如在deriche基准上，ISAMORE实现了2.02倍加速比，高于NoEqSat的1.51倍，同时节省了46.7%的面积。

2. RII技术有效性与不同模式对比 * 与原始E-Graph AU (LLMT)对比：如表2所示，在禁用RII功能（即运行原始LLMT）时，由于候选模式爆炸（高达633K）导致内存溢出（>30GB），所有测试均无法完成。启用RII的默认模式（使用边界采样策略）后，峰值E-Graph规模减少了6-39倍，所有测试均在145秒内完成，内存使用不超过799MB，证明了RII技术使E-Graph AU变得可行。 * 不同ISAMORE模式对比：如图11和表3所示，astsize模式（使用硬件无关的项大小作为优化目标）性能最差，凸显了硬件感知成本模型的重要性。kdsample模式（KD-Tree采样）在部分基准上优于默认模式，因为它能采样到更代表性的模式，可能识别出更大的模式，但代价是更长的探索时间和更高的内存使用。vector模式（启用向量化）在10个基准中的8个上优于默认模式，在matmul、matchain和qrdecomp上提升显著。尽管由于宽松的I/O约束允许DLP操作出现在宽标量指令中，导致提升幅度有限（最高1.68倍），但ISAMORE相对于NOVIA和ENUM的平均优势分别扩大到1.76倍和1.46倍，证明了模式向量化的有效性。

3. 真实世界案例研究 * 领域特定库分析：在三个开源库（Liquid-DSP, CImg, PCL）上评估ISAMORE。如图12所示，ISAMORE在大多数模块上取得了比NOVIA和ENUM更高的加速比。特别地，在CImg库上，NOVIA生成了一个庞大的定制硬件单元（大小167），仅被8个点使用；而ISAMORE识别出8个定制指令，平均复用次数达93次，以仅9.5%的面积实现了1.18倍加速比（NOVIA仅为1.01倍），面积节省达90.5%。这充分展示了语义感知方法在提升指令复用性和硬件效率方面的巨大优势。 * 量化大语言模型（BitNet b1.58）推理：ISAMORE从BitLinear层的实现中识别出一个用于计算打包低比特点积的向量化模式，并生成了相应的ROCC加速器。RTL仿真显示，该定制指令为BitLinear带来了2.15倍的加速比。物理设计显示面积开销为4.81%，频率无下降。 * 后量子密码学（CRYSTALS-Kyber）：ISAMORE识别出在正向和逆向NTT中复用的蝴蝶操作作为定制指令。实现的ROCC加速器带来了5.15倍的加速比，面积开销为17.67%（主要源于硬件乘法器），频率略有下降（2.58%）。该案例证明了ISAMORE在快速演进的软件领域进行自动化硬件定制的潜力。

五、 研究结论与价值

本研究成功提出了ISAMORE框架及其核心的可复用指令识别（RII）方法论，首次实现了通过可扩展的E-Graph反统一化技术，从真实世界应用中自动化、语义感知地发现高度可复用且支持并行的定制指令。

• 科学价值：该研究创新性地将程序语义等价性（通过E-Graph和EqSat）与模式泛化（通过AU）引入到指令定制领域，突破了传统方法依赖语法相似性的局限，为硬件/软件协同设计提供了新的理论基础和方法论。提出的分阶段迭代、智能AU、模式向量化等技术，有效解决了将形式化方法应用于大规模、复杂程序实践中的可扩展性问题。
• 应用价值：ISAMORE是一个开源的端到端框架，能够显著降低为特定领域（如DSP、AI、密码学）设计高效ASIP的门槛。实验表明，其生成的定制指令在多个基准和真实应用上能带来显著的性能提升（最高达2.69倍），同时通过高复用性大幅节约硬件面积。这有助于在RISC-V等开放生态中快速部署针对特定工作负载优化的高性能、高能效处理器。

六、 研究亮点

1. 首创性方法论：首次提出并实现了基于E-Graph反统一化的可复用指令识别（RII）方法论，将指令发现从语法层面提升至语义层面。
2. 解决关键挑战：通过结构化DSL、面向阶段的迭代流程、智能AU（相似性配对与启发式采样）等一系列创新技术，系统性解决了将E-Graph AU应用于真实世界指令定制任务的可扩展性难题。
3. 发掘数据并行性：创新性地提出基于AU的模式向量化技术，能够从标量程序中自动发掘并合成向量化定制指令，充分利用数据级并行性。
4. 硬件感知的帕累托优化：集成基于剖析的性能模型和HLS面积估算，实现多目标帕累托最优模式选择，在性能增益与硬件开销之间提供最佳权衡。
5. 端到端实践验证：不仅提出了理论方法，还构建了完整的开源工具链，并通过丰富的基准测试和涵盖DSP、图像处理、点云处理、LLM、PQC的案例研究，全面验证了其有效性、性能优势和实践潜力。

七、 其他有价值内容

论文还详细比较了ISAMORE与现有指令定制工作的差异（如表1所示），突出了其在自动化、复用合并策略（语义级）、支持粒度（包括控制流）和向量化支持方面的全面优势。此外，论文对相关领域工作进行了梳理，包括早期的细粒度/粗粒度自动化方法、基于E-Graph的编译优化与逻辑合成等，明确了本工作的定位与贡献。