ACM通信
研究突出了
随机程序优化
来源:iStockPhoto.com
无环、定点汇编代码序列的短序列优化是高性能计算中的一个重要问题。然而，转换正确性和性能改进这两个相互竞争的约束常常迫使特殊目的的编译器生成次优代码。我们证明，通过将这些约束编码为成本函数中的项，并使用马尔可夫链蒙特卡罗采样器快速探索所有可能的代码序列的空间，我们能够生成给定目标代码序列的激进优化版本。从11vm O0编译的二进制代码开始，我们能够生成可证明正确的代码序列，这些代码序列要么与qcc O3、icc O3生成的代码匹配，要么优于qcc O3、icc O3生成的代码，在某些情况下，还有专家手写汇编。
1.简介
对于许多应用程序域来说，尽可能生成性能最好的代码具有相当大的价值。然而，编译器优化阶段的传统结构并不适合这一任务。将优化问题分解为一组可以独立解决的小子问题，尽管这些子问题适合于生成持续良好的编解码器，但会导致次优结果。在许多情况下，最好的代码只能通过同时考虑相互依赖的问题，如指令选择、寄存器分配和目标相关的优化。
以前解决这个问题的方法都集中在探索一些有限的代码序列类中的所有可能性。与使用性能约束来驱动单个序列生成的传统编译器不同，这些系统考虑多个序列，并选择最能满足这些约束的序列。这种方法的一个吸引人的特性是完整性:如果存在满足所需约束的代码序列，就保证能找到它。然而，完整性也对可以考虑的代码类型施加了实际的限制。这些技术要么局限于比发生许多有趣优化的阈值短的序列，要么局限于用简化语言编写的代码。
我们通过使用不完全搜索来克服这一限制:正确性和性能改进的竞争性要求被编码为成本函数的项，该成本函数定义在所有无循环的x86_64指令序列的空间上，优化任务被表述为成本最小化问题。虽然搜索空间是高度不规则的，不适合精确优化技术，但我们表明，使用马尔可夫链蒙特卡罗(MCMC)采样器来探索函数并产生低成本样本的常用方法足以产生高质量的代码。
尽管这种技术牺牲了完整性，但却显著提高了结果代码的质量。图1显示了OpenSSL RSA加密库使用的蒙哥马利乘法内核的两个版本。从编译的代码开始llvm O0(116行，没有显示)，我们的原型随机优化器STOKE生成的代码(右)比由gcc o3(左)，甚至比OpenSSL存储库中包含的专家手写程序集还要稍微快一些。
2.相关工作
尽管保持完整性的技术在某些领域是有效的，但它们的普遍适用性仍然有限。中所示的代码序列的上下文中最好地突出了缺点图1．
该代码执行以下操作:两个32位的值，连成一片而且edx，并与64位值相乘肢体重复性劳损症生产128位的产品。中的64位值rdi而且r8都被添加到该产品中，而结果存储在r8而且rdi．由gcc o3(左)将128位乘法实现为4个64位乘法和结果的和。相比之下，由STOKE生产的版本(右)使用了一种硬件特性，它要求输入进行排列并移动到不同的寄存器位置，以便在单个步骤中完成乘法运算。第4行(右)上看起来奇怪的移动产生了不明显但必要的副作用，即将的上32位归零黑索今．
Massalin的superoptimizer12显式枚举长度不断增加的代码序列，并选择在一组测试用例中表现与输入序列相同的第一个代码序列。Massalin报告优化了长度为12的指令序列，但前提是将可枚举操作码集限制在10到15之间。相比之下，斯托克使用了近400个x86_64操作码的一个大子集，其中一些操作码有超过20个变体，以生成如图所示的11个指令内核图1．Massalin的方法不太可能扩展到这么大的指令集。
德纳里峰9与平等饱和,17通过只考虑与输入序列等价的代码序列，实现改进的可伸缩性;通过连续应用保等变换来探索候选变量。因为这两种技术都是目标导向的，它们极大地提高了基本指令的数量和在实践中可以考虑的序列的长度。然而，两者都严重依赖专业知识。尚不清楚专家是否知道如何编码中所示的乘法转换图1或者一组专家规则是否能够涵盖所有可能的有趣优化。
邦萨尔的窥视孔superoptimizer2自动枚举32位x86优化，并将结果存储在数据库中以备以后使用。通过利用等价于寄存器重命名的代码序列之间的对称性，Bansal能够将这种方法扩展到优化，将长度不超过6的代码序列映射到长度不超过3的序列。该方法具有双重好处，即通过离线一次性执行搜索来隐藏超级优化的高成本，并消除对专家知识的依赖。在某种程度上，数据库的使用还允许系统通过沿着滑动代码窗口重复应用优化器来克服指令长度的低上限。无论如何，内核显示在图1是否存在许多真实代码序列所共有的属性，即任何局部优化序列都不会对生成的代码进行转换gcc o3转换成STOKE生产的代码。
最后,素描16和梵天7解决密切相关的基于组件的序列合成问题。这些系统依赖于声明性规范或用户指定的部分序列，并在简化位向量微积分中的语句上操作，而不是直接在硬件指令上操作。梁等。10仅仅从测试用例中考虑学习代码序列的任务，但是在同样高的抽象级别上。尽管这些系统对合成重要的代码很有用，但它们使用的内部表示方式使它们无法对所生成的代码的低级性能属性进行推理。
3.成本最小化
在描述我们的x86_64优化方法之前，我们将抽象地讨论优化作为成本最小化。首先，我们定义一个成本函数，它的术语平衡竞争约束转换的正确性(eq(·)),性能改进(性能(·))。我们将输入序列称为目标（T)和候选编译作为重写（R)，并说一个函数f（X；Y)输入X它的定义是Y
eq(·)项度量两个代码序列的相似性，当且仅当它们相等时返回零。就我们的目的而言，代码序列被视为寄存器和内存内容的函数，如果对于所有赞同目标定义的实时输入的机器状态，两个代码序列对目标定义的实时输出产生相同的副作用，我们就说它们是相等的。因为优化对于不良形式的代码序列是未定义的，所以没有必要为产生异常行为的目标或重写定义eq(·)。然而，没有什么可以阻止我们这样做，定义eq(·)来保存异常行为也会很简单。
相比之下，perf(·)项量化了重写的性能改进;较小的值表示较大的改进。关键是，这个术语的准确程度直接影响结果代码的质量。
使用这种表示法，与优化的联系就很简单了。我们说，优化是一组重写，其中perf(·)项得到改进，而eq(·)项为零
发现这些优化需要使用成本最小化过程。然而，通常我们认为这种形式的成本函数是高度不规则的，不适合精确的优化技术。解决这个问题的方法是使用MCMC采样器的通用策略。尽管对该技术的完整讨论超出了本文的范围，但我们在此总结其主要思想。
MCMC抽样是一种从概率密度函数中提取元素的技术，它与概率密度函数的值成正比:概率高的区域比概率低的区域更常被抽样。当应用到成本最小化时，它有两个吸引人的特性。在极限情况下，从函数的最小(最优)值中选取的样本最多。在实践中，早在这种行为被观察到之前，它就作为一种智能爬坡方法，对具有密集局部极小值的不规则函数具有鲁棒性。
一个常见的方法6将任意函数(如成本(·))转换为概率密度函数如下所示，其中为常数和Z是一个将结果分布规格化的配分函数:尽管计算Z通常是难以处理的，MetropolisHastings算法被设计用来探索密度函数，如p(·)无需计算Z直接8
基本的想法很简单。算法保持当前重写R并提议修改重写R*。的建议R *然后要么接受，要么拒绝。如果被接受，R*成为当前的重写。否则另一个建议基于R是生成的。算法迭代，直到耗尽计算预算，只要提案被耗尽遍历性(足以通过一些应用程序序列将任何代码序列转换为任何其他代码序列)，算法将在极限下产生一个按其成本比例分布的样本序列。
这个全局属性取决于提案的本地接受标准RR*，由如下所示的大都会黑斯廷斯接受概率决定。我们用这个符号问（R * |)来表示一个新的重写的建议分布R*为当前重写的采样，R．这种分布是算法成功应用的关键。从经验上讲，最好的结果是一个分布，它既提出局部建议，又对R以及引发重大变化的全球性建议
验收标准的重要属性如下:如果R比……好(概率高/成本低)R，建议总是被接受的。如果R比……更糟糕(概率更低/成本更高)R，该建议仍可被接受，其概率随两者之比的函数而减小R*和R．这个属性可以防止搜索陷入局部极小值，同时保持不太可能接受比可用替代方案差得多的移动。如果提案分布是对称的，q(R*|R) = q(R|R*)时，可将接收概率简化为更简单的Metropolis比率，该比率由成本(·)直接计算:
4.X86_64优化
现在我们讨论将成本最小化应用于x86_64优化的实际细节。由于x86_64可以说是CISC体系结构中最复杂的实例，我们希望本文的讨论能够很好地推广到其他体系结构。实现eq(·)项的自然选择是使用A象征性的验证器(瓦尔(·)),4和一个二元指标函数（1(·))，如果参数为真，则返回1，否则返回0
但是，使用当前的符号验证器技术每秒可以执行的调用总数相当低。即使是中等大小的代码序列，它也远低于1000。因为MCMC抽样只有在能够探索足够多的建议时才有效，重复计算式(6)将使该数字远远低于有用的阈值。
这一观察激发了对eq(·)项的近似定义，它基于测试用例（)．直观地说，我们执行这个建议R*，并通过计算实时输出之间的差异(即汉明距离)来衡量输出与目标的“接近程度”。除了比使用定理证明程序快得多之外，这种等价近似还有一个额外的优势，即产生比符号等价测试的0/1输出更流畅的场景;它提供了一个“近乎正确”的有用概念，可以帮助指导搜索
式(7)中，用reg(·)比较副作用(eval(·))上生成的住寄存器输出（)由目标定义。这些输出可以包括通用、SSE和条件寄存器。Reg(·)计算结果不同的位数人口统计函数(pop(·))，它返回整数的64位表示形式中1位的个数
为了简洁起见，我们省略了类似的mem(·)的定义。剩下的术语err(·)用于区分表现出未定义行为的代码序列，方法是计算并惩罚在执行重写过程中发生的段错误、浮点异常和从未定义内存或寄存器读取的数量。我们注意到sigsegv(·)的定义是T，它决定了可以通过对特定测试用例的重写成功解引用的地址集。重写必须在沙箱中运行，以确保在运行时可以安全地检测到此行为。扩展到其他类型的异常非常简单
eq’(·)的求值可以通过JIT编译实现，也可以使用硬件模拟器实现。在我们的实验(第8节)中，我们选择了前者，并展示了以每秒100万到1000万的速度分派测试用例评估的能力。利用这个实现，我们定义了一个计算eq(·)的优化方法，它实现了足够的吞吐量，对MCMC采样有用
除了改进性能外，式(10)还有两个可取的性质。首先，eq(·)的失败计算将产生一个反例测试用例4可以用来提炼．尽管这样做改变了由成本(·)定义的搜索空间，但在实践中，产生精确预测正确性的健壮测试用例集所需的失败验证的数量是相当低的。第二，如前所述，它通过在正确和错误的代码序列之间平滑地插入来提高搜索空间。
类似的考虑也适用于perf(·)术语的实现。尽管JIT编译目标和重写并比较运行时似乎很自然，但为了消除瞬变影响而多次执行代码序列所需的时间是非常昂贵的。为了解释这一点，我们定义了一个简单的启发式逼近运行时，它是基于静态逼近平均延迟(lat(·))的指令
图2为典型的代码序列语料库展示了这种启发式和实际运行时之间的合理相关性。异常值的特征要么是在微操作级别上不成比例的高指令级别并行，要么是不一致的内存访问时间。现代CISC处理器引入的更高阶性能效应的更精确模型是可行的，如果构建起来很繁琐，而且对于更复杂的代码序列可能是必要的。
无论如何，这种近似对于我们考虑的基准已经足够了(第8节)。通过使用JIT编译方法作为后处理步骤，通过重新计算perf(·)来解决这种方法产生的错误。在搜索过程中，我们记录nMCMC采样生成的成本最低的程序，根据它们的实际运行时重新排序，并返回最佳结果。
最后，实现了对x86_64优化的MCMC采样。重写被表示为无循环的长度指令序列l，其中使用区分令牌(UNUSED)表示未使用的指令槽。这种对有界长度序列的简化是至关重要的，因为它在结果搜索空间的维度上放置了一个恒定的值。1建议分布q(·)从四种可能的移动中选择:前两个小调和后两个大调:
- 码。一个指令是随机选择的，它的操作码被一个随机操作码替换。
- 操作数。一条指令是随机选择的，它的一个操作数被一个随机操作数替换。
- 交换。两行代码是随机选择和交换的。
- 指令。一条指令被随机选择并替换为一条随机指令或UNUSED令牌。提出UNUSED对应于删除一条指令，用一条指令替换UNUSED对应于插入一条指令。
这些移动满足第3节中描述的遍历性:任何代码序列都可以通过重复应用指令移动转换为任何其他代码序列。这些移动也满足对称性属性，并允许使用(5)式。要了解原因，请注意执行所有四种移动的概率等于使用相同类型的移动撤消它们产生的转换的概率:操作码和操作数移动在接受之前和之后被约束从相同的等价类采样，交换和指令移动在任何方向上都不受约束。
5.搜索策略
上面描述的实现的早期版本能够进行转换llvm O0代码的等效gcc O3代码，但无法产生与专家手写代码竞争的结果。原因是由图3，抽象地描述了蒙哥马利乘法基准的搜索空间，如图1．对于无循环的代码序列，llvm O0而且gcc O3主要是在堆栈使用和指令选择方面的不同，但在其他方面产生的算法结果相似。编译器通常被设计成组成许多小的局部转换:死代码消除删除一条指令，常量传播将一个寄存器更改为即时寄存器，强度折减用加法替换乘法。这样的局部优化序列对应于等价代码序列的区域，这些区域由非常短的移动序列(通常只有一个)密集连接，很容易被局部搜索方法遍历。开始从llvm O0代码中，MCMC采样将迅速地一个接一个地改善局部效率低下的情况，并逐步达到与之相当的水平gcc O3代码。
斯托克发现的代码占据了搜索空间的一个完全不同的区域。如前所述，它代表了在程序集级别实现内核的一种完全不同的算法。本地搜索过程从编译器生成的代码生成这种形式的代码的唯一方法是遍历极低概率的路径，在原始代码旁边构建代码(始终增加其成本)，只是在最后删除原始代码。
尽管MCMC采样可以保证在极限范围内遍历这条路径，但在任何合理的时间内遍历这条路径的可能性都非常低，以致于在实践中毫无用处。这一观察促使我们将成本最小化分为两个阶段:
- 一个合成Phase只关注正确性，它试图定位与目标所占区域不同的等价代码序列区域。
- 一个优化Phase专注于性能，它在每个区域中搜索最快的序列。
这些阶段具有相同的实现，只是起点和接受功能不同。综合从一个随机代码序列开始，而优化从一个已知与目标等价的代码序列开始。综合忽略了性能(·)项，并使用(10)式作为其代价函数，而优化使用了这两个项，这允许它提高性能，同时也尝试了(暂时)违反正确性的“捷径”。
合成应该能够在可控制的时间内从如此巨大的搜索空间生成正确的重写，这也许是不直观的。根据我们的经验，当可以逐步发现正确重写的部分内容时，而不是一次性发现全部内容时，综合是有效的。图4比较开销随时间的变化与蒙哥马利乘法基准的最终重写中出现的指令的百分比。随着合成的进行，正确代码的百分比与成本函数的值成反比增加。
虽然这是令人鼓舞的，而且有许多代码序列可以分段合成，但也有许多不能。幸运的是，即使合成失败，优化仍然是可能的。它必须仅仅从目标所占领的区域作为起点着手。
6.搜索优化
式(10)对于MCMC采样来说已经足够快了，但是它的性能还可以进一步提高。如前所述，eq*(·)项是通过在测试用例上执行一个建议来计算的，注意到总成本与当前重写的比率，然后抽样一个随机变量来决定是否接受该建议。然而，通过第一次抽样p，然后计算算法将为该值接受的最大比例，一旦超过该界限，且建议肯定会被拒绝，就有可能终止测试用例的评估
图5显示了在蒙哥马利乘法基准的综合过程中应用该优化的结果。随着成本函数的值下降，在早期终止之前必须评估的测试用例的平均数量也在下降。这导致每秒评估的提案数量大幅增加，峰值时在10万至100万之间。
一个更重要的改进来自于观察到(8)式中reg(·)的定义过于严格。一个例子显示在图6对于一个寄存器al被活出的目标。在al中产生与期望值相反的重写会被分配最大可能的代价，尽管它产生了正确的值，只是在不正确的位置:dl。我们可以通过奖励在不正确的位置产生正确(或接近正确)值的重写来改进这个术语。下面所示的宽松定义检查了所有等价寄存器位宽(bw(·))，选择与目标寄存器的值最接近的值，并分配一个小的错位的点球（w米)，如果所选寄存器与原寄存器不同。使用这个定义，重写的代价为w米
虽然可以类似地放宽内存相等的定义，但计算这一项所需的时间与目标内存占用的大小成二次增长。尽管这种方法对于我们的实验已经足够了，但是对于更复杂的代码序列，需要更有效的实现。
图7显示了在蒙哥马利乘法基准的合成过程中使用这些改进定义的结果。在松弛代价函数收敛所需的时间量上，原始严格版本获得的最小代价仅略优于纯随机搜索。这种显著的改进可以解释为搜索过程的隐式并行化。在任意位置接受正确的值允许重写程序同时探索尽可能多的可选计算，只要适合一个长度的代码序列l．
7.斯托克城
STOKE是上述思想的一个原型实现。一个STOKE运行由标准编译器创建的二进制文件(在我们的实验中，llvm o0)，为感兴趣的无循环目标生成测试用例，并将目标和测试用例广播给一组合成线程。经过一段固定的时间后，这些线程返回一组经过验证的重写，并使用一组新的优化线程改进这些重写。在结果中，性能最高的前20%将根据实际运行时重新排名，并将最好的返回给用户。STOKE为每个目标生成32个测试用例，合成和优化在8核3.5 GHz Intel i74770K上并行执行，计算预算为15分钟。
STOKE使用Intel的PinTool生成测试用例。11它执行用户提供的二进制文件，每次调用目标时都记录初始寄存器状态和从内存中解引用的值集。对于每个测试用例，目标解引用的地址集用于定义执行候选重写的沙盒。无效地址的解引用被捕获，并被产生恒定零值的指令所取代;从未定义位置读取和浮点异常的处理方式类似。
STOKE使用一个健全的过程来验证无循环代码序列的相等性。2在Z3所使用的位向量算法的无量词理论中，将目标和重写转化为SMT公式，5产生一个查询，询问从相同的初始机器状态执行时，两个序列是否对实时输出产生相同的副作用。根据类型的不同，寄存器被建模为8位到256位的向量，而内存被建模为两个向量:一个64位地址和一个8位值(x86_64是可字节寻址的)。
斯托克断言约束，两个序列一致的初始机器状态有关的活动输入由目标定义。对于目标中的每条指令，它还断言一个约束，该约束对它在机器状态上表示的转换进行编码，并将这些转换链接在一起，以生成一个约束，该约束描述由目标定义的实时输出的状态。对于重写和地址处的所有内存访问对，断言了一组类似的约束addr1而且addr2，斯托克增加了一个与他们的价值相关的附加约束:addr1＝addr2瓦尔1＝瓦尔2．
使用这些约束，STOKE询问Z3是否存在导致两个序列产生不同结果的初始机器状态。如果答案是“否”，则确定序列相等。如果答案是“是”，那么Z3生成一个证人，该证人被转换为一个新的测试用例。
为了保持运行时的可处理性，STOKE做了两个简化的假设。它假定堆栈地址仅表示为rsp的常数偏移量。这允许在llvm O0代码中将堆栈位置作为命名变量处理，这将显示大量的堆栈流量。此外，它将64位的乘法和除法视为未解释的函数，这些函数受到一小组特殊目的公理的约束。尽管Z3在推理两个或更多这样的操作时发散，但我们的基准测试在每个序列中最多包含四个。
8.评价
除了Montgomery乘法内核之外，我们还根据来自文献和高性能代码的基准来评估STOKE。性能改进和运行时总结在图8．从使用llvm O0编译的二进制代码开始，STOKE一致地生成与所生成代码的性能匹配的重写海湾合作委员会而且国际刑事法庭(两个编译器产生的结果基本上相同)。在某些情况下，重写的性能与手写程序集相当。
Gulwani et al。7确定黑客的喜悦18一种将复杂算法编码为小的无循环代码序列的技术集合，作为程序合成和优化的基准(p01p25)的来源。为了简单起见，我们只关注一个内核，该内核的STOKE发现了算法上不同的重写。图9显示了“循环3个值”基准测试，它接受输入x并将其转换为序列a、b、c中的下一个值。该函数最自然的实现是条件赋值序列，但对于没有必要的内在特性的isa，所示的实现比使用分支的实现更便宜。对于具有条件移动intrinsic的x86_64，这是一个过早优化的实例。虽然STOKE能够重新发现最优的实现，海湾合作委员会而且国际刑事法庭按照所写的方式抄写代码。
单精度Alpha X + Y (SAXPY)是基本线性代数子系统库中的一级向量运算。3.它大量使用了堆访问，并提供了使用vector intrinsic的机会。要公开此属性，我们的整数实现手动展开了四次，如图10．尽管注释表明x而且y对齐且不别名，则两个生产编译器都无法生成向量化代码。另一方面，斯托克能够发现理想的实现。
最后，我们注意到斯托克并非没有局限性。图11显示了Bansal和Aiken的链表遍历基准。2该代码遍历整数列表并对每个元素进行加倍。因为斯托克只能推理无循环代码，最近的工作已经探索了这个问题的解决方案15它不能在每次迭代开始时消除堆栈移动。STOKE也无法合成三个Hacker’s Delight基准的重写。尽管如此，仅使用优化阶段，它能够发现执行与生产编译器代码相当的重写。
9.结论
提出了一种基于随机搜索的程序优化新方法。与传统编译器将优化分解为一系列独立可解决的小子问题相比，我们的方法使用了成本最小化，同时考虑了转换正确性和性能改进的竞争约束。尽管该方法牺牲了完整性，但它与生产编译器相比具有竞争力，并且已被证明能够生成性能优于专家手写汇编的代码。
本文基于最初发表于2013年的工作。从那以后，斯托克城经历了实质性的改进;这里出现的更新结果是使用当前实现生成的，并在原来的基础上改进了一个数量级。有兴趣的读者可以参考原文随机Superoptimization13以及之后的那些。
数据驱动的等价性检查15描述了对STOKE的扩展，使代码序列具有非平凡控制流的优化。它定义了一个可靠的方法，以确保由STOKE产生的优化对于所有可能的输入都是正确的，即使在存在循环的情况下也是如此。该方法基于一个数据驱动的算法，该算法观察测试用例的执行，并自动推断不变量以产生归纳等价证明。原型实现是第一个用x86_64程序集编写的循环的声音等价检查器。
可调精度浮点程序的随机优化14描述支持优化浮点代码序列的对STOKE的扩展。通过修改eq(·)术语的定义，以考虑到浮点等式的宽松约束，STOKE能够生成英特尔手写C数值库的低精度实现，其速度比原始库快6倍，并在高性能应用程序上实现超过30%的端到端加速，这些应用程序可以容忍精度的损失，但仍然保持正确。由于这些优化大多不符合使用当前技术状态的形式验证，本文描述了一种描述最大误差的搜索技术。
参考文献
1.Andrieu, C. de Freitas, N. Doucet, A. Jordan, M.I.机器学习MCMC介绍。机器学习,12(2003), 543。
2.Bansal, S, Aiken, A.使用窥视孔超级优化器的二进制翻译。在第八届操作系统设计与实现USENIX研讨会论文集，OSDI 2008。r·德维斯和r·范·瑞内斯，编。(2008年12月810日，美国加利福尼亚州圣地亚哥)。USENIX协会,177192。
3.l.s. Blackford, Demmel, J.， Dongarra, J.， Duff, I.， Hammarling, S.， Henry, G.， Heroux, M.， Kaufman, L.， Lumsdaine, A.， Petitet, A.， Pozo, R.， Remington, K.， Whaley, R.C.一组更新的基本线性代数子程序(BLAS)。ACM反式。数学。Softw。28日2(2002), 135151。
4.Cadar, C, Dunbar, D, Engler, D.R. Klee:为复杂系统程序自动生成高覆盖率测试。在第八届操作系统设计与实现USENIX研讨会论文集，OSDI 2008。r·德维斯和r·范·瑞内斯，编。(2008年12月810日，美国加利福尼亚州圣地亚哥)。USENIX协会,209224。
5.位向量和数组的决策过程。在第十九届计算机辅助验证国际会议论文集（骑兵）2007.达姆和赫曼斯编。成交量为4590计算机科学课堂讲稿(德国柏林，2007年7月37日)，施普林格，519531。
6.Gilks,得到马尔可夫链蒙特卡洛的实践。查普曼和霍尔/CRC, 1999年。
7.Gulwani, S.， Jha, S.， Tiwari, A.， Venkatesan, R.无循环程序的合成。在第32届ACM SIGPLAN编程语言设计与实现会议论文集（PLDI2011年)。M. W.霍尔和D. A.帕多瓦编。(2011年6月48日，美国加利福尼亚州圣何塞)。ACM, 6273年。
8.使用马尔可夫链的蒙特卡罗抽样方法及其应用。生物统计学57岁1(1970), 97109。
9.Joshi, R, Nelson, G, Randall, K.H. Denali:目标导向的超级优化者。在ACM SIGPLAN 2002编程语言设计与实现会议论文集中(柏林,德国,2002)。ACM，美国纽约，纽约，304314。
10.梁，P，乔丹，m.i.，克莱因，D.学习程序:一个层次贝叶斯方法。在第27届国际机器学习会议论文集（ICML-10）．J. Fürnkranz和T.约阿希姆斯，编。(2010年6月2124日，以色列海法)。Omnipress, 639646年。
11.陆,C.-K。， Cohn, r.s.， Muth, R.， Patil, H.， Klauser, A.， Lowney, p.g.， Wallace, S.， Reddi, v.j.， Hazelwood, K.M.。Pin:用动态仪器构建定制的程序分析工具。在2005年ACM SIGPLAN编程语言设计与实现会议论文集(芝加哥，伊利诺伊州，美国，2005)。ACM，纽约，纽约，美国，190200。
12.Massalin, H. Superoptimizer A看看最小的程序。在第二届编程语言和操作系统体系结构支持国际会议论文集（ASPLOS二世)．R. H. Katz，主编(美国加利福尼亚州帕洛阿尔托，1987年10月58日)。ACM出版社,122126年。
13.Schkufza, E, Sharma, R, Aiken, A.随机超级优化。在编程语言和操作系统的体系结构支持，ASPLOS'13。V.萨卡尔和R. Bodík，编。(2013年3月1620日，美国德克萨斯州休斯顿)。ACM, 305316年。
14.Schkufza, Sharma, R, Aiken, A.具有可调精度的浮点程序的随机优化。在ACM SIGPLAN编程语言设计与实现会议，PLDI'14．M. F. P. O'Boyle和K. Pingali主编。(2014年6月0911，英国爱丁堡)。ACM。
15.R. Sharma, Schkufza, E. Churchill, b.r.， Aiken, A.数据驱动的等价检验。在2013 ACM SIGPLAN面向对象编程系统语言与应用国际会议论文集，OOPSLA 2013, SPLASH 2013的一部分。霍斯金。尤斯特和C. V.洛佩斯，编。(2013年10月2631日，美国印第安纳波利斯)。ACM, 391406年。
16.Solar-Lezama, A.， Tancau, L.， Bodík, R.， Seshia, S.A.， Saraswat, va .有限程序的组合草图。在第12届编程语言和操作系统体系结构支持国际会议论文集，ASPLOS 2006。沈建平、马尔托诺西主编。(圣何塞，加利福尼亚州，美国，2006年10月2125)。ACM, 404415年。
17.泰特，斯坦普，M，塔特洛克，Z.，勒纳，S.平等饱和:一种优化的新方法。第一版的逻辑方法。Sci。7,1(2011)。
数据
图1。来自OpenSSL RSA库的Montgomery乘法内核。gcc O3(左)和随机优化器(右)的编译。
图2。所选代码序列的预测运行时和观察运行时。异常值的特征是指令级并行和内存效应。
图3。蒙哥马利乘法基准的搜索空间:O0和O3代码紧密相连，而专家代码只能通过极低概率的路径到达。
图4。成本随时间的变化与蒙哥马利乘法合成基准的最终零成本重写中出现的指令的百分比相比。
图5。对于Montgomery乘法合成基准，每秒评估的建议与在早期终止之前评估的测试用例相比。成本函数显示供参考。
图6。目标的严格和松弛的等式函数，其中ax是活出来的，正确的结果出现在错误的位置。
图7。蒙哥马利乘法综合基准的严格与松弛代价函数。随机搜索结果显示供参考。
©2016 0001 - 0782/16/02 ACM
允许为个人或课堂使用部分或全部作品制作数字或硬拷贝，但不得为盈利或商业利益而复制或分发，且副本在首页上附有本通知和完整的引用。除ACM外，本作品的其他组件的版权必须受到尊重。允许有信用的文摘。以其他方式复制、重新发布、在服务器上发布或重新分发到列表，都需要事先获得特定的许可和/或费用。请求发布的权限permissions@acm.org传真(212)869-0481。
数字图书馆是由计算机协会出版的。版权所有©2016 ACM, Inc.
没有发现记录