2024.12.30-2025.01.05 学习内容

超级优化（Superoptimizer）是一种计算机程序，它能够为给定的指令集找到计算函数的最短程序。本博客是对几篇论文的阅读总结。

Superoptimizer – A Look at the Smallest Program

相关信息

发表时间：1987

发表会议：ASPLOS（CCF A）

目标场景

给定一个特定的指令集，在汇编指令的级别上进行优化。可以应用于编译器的窥孔优化阶段。

优化目标：最短的程序，而非运行最快。

现有方法

无。

本文方法

核心是概率测试和修剪搜索树。

• 快速概率测试，用于确定两个程序的等价性。使用一些输入集运行被测试程序的机器代码几次，并检查输出是否与源程序的输出相匹配。这里的想法是，大多数程序都无法通过这个简单的测试，而完整的程序验证测试只会针对这个测试未能捕获的少数程序进行。
• 修剪搜索空间，同时保持最优性的保证。过滤掉已知不会出现在任何最佳程序中的指令序列。

实验结果

可以生成比源程序短的指令。

评价

• 作为编译器窥孔优化的一部分比较有用。
• 局限很大：针对小程序片段、搜索效率低下、指令集受限。
• 竟然是按照1、2、3….这样的指令长度进行依次生成的。

Faster sorting algorithms discovered using deep reinforcement learning

相关信息

发表时间：2022

发表会议：Nature

目标场景

对汇编指令级的代码，特别是排序算法做优化。重点关注固定排序和可变排序，也就是对序列长度固定和可变的数组进行的排序方式。

现有方法

之前都是枚举搜索技术或者完全随机的搜索。

本文方法

将发现新的、高效的排序算法的问题设计成一个单人游戏——AssemblyGame。

引入了 AlphaDev，这是一个经过训练可以搜索正确和有效算法的agent。agent由两个核心组件组成， 学习算法和表示函数。

• 学习算法是AlphaZero33的扩展，并使用深度神经网络指导蒙特卡洛树搜索 (MCTS) 规划程序。该神经网络的输入是状态 St，输出是策略和价值预测。策略预测是动作的分布，价值函数是agent应该从当前状态 St 获得的累积回报 R 的预测。在游戏过程中，agent接收当前状态 St 作为输入。然后，代理执行 MCTS 程序并使用它来选择要采取的下一个动作。然后使用生成的游戏来更新网络的参数，使agent能够学习。
• 表示函数是可互换的，并捕获汇编程序的底层结构。该表示函数是基于transformer的。该网络由两个组件组成，即 (1) 一个transformer encoder，为代理提供算法结构的表示；(2) CPU 状态编码器网络，帮助代理预测算法如何影响内存和寄存器的动态。

此游戏中的每个状态都定义为向量 St = ⟨Pt, Zt⟩，其中 Pt 是游戏中迄今为止生成的算法的表示，Zt 表示在对一组预定义输入执行当前算法后内存和寄存器的状态。

在时间步 t，玩家接收当前状态 St 并执行操作 at。这涉及将合法的汇编指令（例如，mov<A,B>）附加到迄今为止生成的当前算法。收到的奖励 rt 包括算法正确性和延迟的度量。

算法正确性涉及将一组 N 个测试序列输入当前算法 Pt 以生成 N 个输出。然后将这些输出与预期输出进行比较，并计算正确性奖励 rt。

也就是在超级优化项目中使用的办法

延迟奖励可以通过以下方式生成：(1) 惩罚代理增加算法的长度（当长度和延迟高度相关时），我们将其称为算法长度奖励；或 (2) 测量算法的实际延迟。

游戏执行有限步数，之后游戏终止。赢得游戏相当于使用汇编指令生成正确的低延迟算法。输掉游戏相当于生成不正确的算法或正确但效率低下的算法。

实验结果

发现了一系列手工无法优化的结构。

评价

• 模型比较复杂。
• 功能较为强大。与更容易陷入局部最优的广度优先随机搜索程序相比，AlphaDev 能够更好地探索算法空间

对于RL for SuperOptimize的看法

优点

• AlphaDev证明了基本可行
• 有AlphaDev的伪代码可以参考
• 相比于LLM，算力资源要求很低

缺点

• 做的人较少，目前可参考代码不多
• RL对数学要求较高，需要一段时间入门

总体评价

目前看来比较有希望能做出来一些较好的优化，需要加速努力。

规划

• 利用4周左右的时间快速入门RL
• 利用2周左右的时间阅读alphadev等的代码
• 利用n周左右的时间完成代码