应用程序合成生成交换机代码( 二 ) _交换机代码

当前的管道处理程序编译器经常错误地拒绝程序，即相同程序的语义等价版本不被相同的编译器接受，这个问题在商业和学术编译器中都存在。
本文用一个简单的例子来说明 Domino 编译器中的虚假程序拒绝问题。。图 2 显示了两个针对 PISA 管道编写的 Domino 程序。这两个程序在语义上是等价的，即给定相同的输入包和相同的初始状态变量，它们都将在运行时产生相同的输出包和状态值。然而，Domino 编译器表现出蝴蝶效应或假阳性编译结果:它成功地编译了第一个程序，但拒绝了第二个程序，尽管它们具有相同的语义。

文章插图

图 2 Domino 编译器虚假拒绝
虽然上述特定情况可以由编译器开发人员通过添加规则来修复，但是类似的情况将在未来继续出现。事实上，基于规则的编译器和程序可以被认为是军备竞赛的两个方面，随着时间的推移，编译器变得越来越复杂，以纳入更多的重写规则来简化更复杂的程序模式。相比之下，正如本文提出的基于程序合成的交换机编译器的思想，通过彻底搜索机器代码空间，程序合成有可能提供一种更简单、更经得起未来考验的编译器设计。
4 ChipmunkChipmunk 将以下内容作为输入:(1)数据包事务和(2)管道能力的规范，如图 3 所示；它可以消耗少量资源来为该流水线产生机器代码。下面将从 Chipmunk 的各个模块来进行介绍。

文章插图

图 3 Chipmunk 工作流
4.1 程序合成引擎 SKETCHSKETCH、是本文中使用的程序合成引擎。SKETCH 接受两个输入：一个规范和一个草图，一个局部程序，其孔代表有限整数范围内的未知值。草图只考虑那些程序，其中每个草图孔都填充有一个属于孔范围的整数，从而限制了合成搜索空间。草图将人的观察编码为合成程序的形式。然后，SKETCH 用整数填充所有孔，以使完整的草图符合规格（假定有可能符合规格），或者说不可能这样做。
代码生成器最终需要选择低级可编程硬件旋钮的正确值，例如，哪个输入连接到每个 ALU（输入复用器），每个输入执行什么操作（ALU 操作码），哪个 PHV 容器是用于输出（输出多路复用器），将哪个数据包字段分配给每个容器等。Chipmunk 的目标是让 SKETCH 做出这些选择。因此，Chipmunk 将这些可编程旋钮编码为 SKETCH 孔。
Chipmunk 用草图表示实现包处理程序时要考虑的有效管道配置的空间。该草图捕获了管道支持的所有可能的计算，这些计算是孔的函数。首先，该草图根据与 ALU 操作码，输入多路复用控件，立即操作数和局部状态变量相对应的孔洞，对每个有状态和无状态 ALU 对 PHV 容器和 ALU 局部状态的影响进行建模。其次，该草图对管道进行了建模：PHV 从一个阶段到另一个阶段的流动，它是与输入/输出多路复用控件和 PHV 分配域对应的孔的函数。实际上，Chipmunk 的管道草图是图 1 中 ALU 的 2D 网格的程序表示。
4.2 数据包事务规范本文使用术语包(状态)向量来指代向量，其每个维度对应于规范中的单个包字段(状态变量)，即图 1 中的数据包事务。本文使用术语状态+包向量来表示状态和包向量的连接，目标是合成一个管道实现，该实现在任意输入包跟踪上遵守包事务规范：在任意包向量序列和任意初始状态向量上，对于规范和实现，包向量和最终状态向量的输出序列必须相同。本文把这个问题叫做基于轨迹的合成。
然而，基于轨迹的合成似乎令人望而生畏，因为包轨迹可以无限长，而 SKETCH 是为有限的输入而设计的。但是可以将基于轨迹的合成简化为一个更简单的有限问题，称之为基于包的合成，其中本文的目标是合成管道实现，使得在任意单个分组向量和任意单个先前状态向量上，处理该分组之后的更新状态+分组向量对于规范和实现必须是相同的。
为了实现这种简化，我们将在 Domino 中作为包事务编写的包处理程序转换成 SKETCH 规范，该规范将一个状态+包向量作为输入，并输出一个更新的状态+包向量。为了将 Domino 程序转换成草图规范，本文向多米诺编译器添加了一个传递程序。这相对简单，因为 Domino 和 SKETCH 都有非常相似的类似 C 的语法。用 P4-16 @atomic 代替 Domino 作为 Chipmunk 的输入语言同样需要 p4c 编译器的传递程序。
4.3 切片技术虽然基于包的合成比基于轨迹的合成简单，但在几个基准集上的实现结果仍然太慢。为了进一步加速合成，我们开发了一种叫做切片的技术。我们从切片的简化版本开始，它只适用于无状态和确定性的数据包事务。然后我们对其进行改进，以处理状态和随机性。