1 引用

Gao, Xiangyu , et al. "Switch Code Generation Using Program Synthesis." SIGCOMM '20: Annual conference of the ACM Special Interest Group on Data Communication on the Applications, technologies, architectures, and protocols for computer communication ACM, 2020.

2 摘要

为可编程交换机管道编写数据包处理程序是一件具有挑战性的任务，因为这类数据包处理程序通常具有“全有”或“全无”的性质，即：当程序能够满足管道所需资源时，程序就可以以线速运行；反之，则程序根本无法运行。编译器负责使程序满足管道资源的限制。但是，使用重写规则生成交换机机器代码的交换机编译器通常会拒绝程序，因为这些规则无法将程序转换为可以映射到管道有限资源的形式，即：使该映射实际上存在。

本文介绍了一个名为 Chipmunk 的编译器，它将代码生成转换为一类程序合成问题。Chipmunk 使用程序综合引擎 SKETCH 向下转换高级程序以切换为机器代码。但是，单纯将代码生成公式化为一类程序合成问题通常会导致编译时间较长。因此，本文开发了一种新的应用于特定领域的程序合成技术，即应用切片，将编译时间平均减少了 51 倍。

使用交换机硬件模拟器，我们证明 Chipmunk 可以编译许多被以前的基于规则的编译器——Domino 无法处理的程序。此外，Chipmunk 还产生比 Domino 更少的管道阶段的机器代码。应用 Chipmunk 后端的 Tofino 可编程交换机的表现证明，程序合成可以生成用于高速交换机的机器代码。

3 背景介绍

3.1 数据包处理编程语言

现在存在几种用于数据包处理的语言，例如 P4-14，P4-16，POF 和 Domino。本文使用 Domino 作为程序员指定输入程序的语言。Domino 非常适合表达具有算法风格的数据包处理，例如实现 RCP 协议。图 1 展示了一个 Domino 程序的例子，该程序对通过管道的第 11 个数据包进行采样。Domino 提供了事务语义：Domino 程序中的操作从头到尾原子地执行，就像目标一次只处理一个数据包一样；这使程序员不必处理并发问题，可将其委托给编译器。

图 1 Domino 示例程序

3.2 数据包处理管道结构

可编程交换机包括：用于解析分组报头的可编程解析器，用于操纵报头的一个或多个可编程匹配动作入口管道，一个分组调度器以及用于其他报头操纵的一个或多个可编程匹配动作出口管道。本文专注于管道，因为这是数据包操纵发生的主要位置。本文考虑基于 RMT 和 Banzai 的用于包处理的管道体系结构，该体系结构通过状态计算扩展了 RMT。这种架构现在通常被称为协议独立交换架构（PISA），并且在许多高速网络中都可以看到。

在 PISA 中，传入的数据包首先进入解析器。解析之后，解析的分组报头被存储在分组报头向量（PHV）中：容器的向量，每个容器存储单个报头字段（例如，IP TTL），该 PHV 通过入口和出口管道传递。每个管道阶段都包含多个在 PHV 容器上同时运行的匹配动作表。每个动作匹配表使用匹配单元（例如，可以使用指定 TCP 端口 22 的规则来匹配 SSH 数据包）来标识当前数据包的关注规则，并使用操作单元（例如，将 1 添加到数据包字段）来修改数据包与该规则相关。管线可以维持少量的动作单元的本地状态以执行动作，例如，维持所有 SSH 分组的计数。

这里假设 PISA 管道是前馈的：数据包只能从较早的阶段流向较晚的阶段，而不能反向流动。这意味着后期的计算可以取决于早期的计算，反之则不然。特别是，存储在管道阶段中的一条状态在数据包通过管道时只能被一次读取，修改和写入。交换机可以将数据包重新循环到管道中以实现反向流，但是重新循环极大地降低了数据包处理的吞吐量，因此本文在此不予考虑。

3.3 管道编译器

管道的编译器（例如 Domino）采用以高级语言编写的数据包处理程序，并将其转换为代表管道配置的低级机器代码，例如 ALU 操作码，将分组字段分配给 PHV 容器和多路复用器的配置（图 1）。

将程序编译到管道是“全有”或“全无”：成功编译的程序可以以管道的线速运行，但是被编译器拒绝的程序根本无法运行。可以拒绝程序有两个原因。第一个原因是违反资源限制：由编译器生成的机器代码可能会消耗比可用资源更多的资源。第二个原因是违反了计算限制：即就算使用无限的 ALU，编译器也可能找不到将程序中的计算映射到硬件 ALU 的方法。

这代表编译器负有重大责任，理想情况下，编译器应能够找到与给定高级程序相对应的某些机器代码——前提是该程序在管道的资源和计算限制之内：程序的计算属于有限空间使用单次通过管道的 ALU 即可进行计算，而无需再循环。作为超出这些限制的程序的示例，如果管道仅支持状态的增量操作（但不支持乘法），并且该程序需要在排队延迟上使用指数加权的移动平均滤波器，则无法使用管道运行该程序。

当前的管道处理程序编译器经常错误地拒绝程序，即相同程序的语义等价版本不被相同的编译器接受，这个问题在商业和学术编译器中都存在。

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

图 2 Domino 编译器虚假拒绝

虽然上述特定情况可以由编译器开发人员通过添加规则来修复，但是类似的情况将在未来继续出现。事实上，基于规则的编译器和程序可以被认为是军备竞赛的两个方面，随着时间的推移，编译器变得越来越复杂，以纳入更多的重写规则来简化更复杂的程序模式。相比之下，正如本文提出的基于程序合成的交换机编译器的思想，通过彻底搜索机器代码空间，程序合成有可能提供一种更简单、更经得起未来考验的编译器设计。

4 Chipmunk

Chipmunk 将以下内容作为输入:(1)数据包事务和(2)管道能力的规范，如图 3 所示；它可以消耗少量资源来为该流水线产生机器代码。下面将从 Chipmunk 的各个模块来进行介绍。

图 3 Chipmunk 工作流

4.1 程序合成引擎 SKETCH

SKETCH、是本文中使用的程序合成引擎。 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 切片技术

虽然基于包的合成比基于轨迹的合成简单，但在几个基准集上的实现结果仍然太慢。为了进一步加速合成，我们开发了一种叫做切片的技术。我们从切片的简化版本开始，它只适用于无状态和确定性的数据包事务。然后我们对其进行改进，以处理状态和随机性。

为在基于包的合成中，需要规范和实现在整个更新状态+包向量上达成一致，而不需要对整个向量达成一致，而是将需求分解成更简单的需求或片段的集合。每个切片是一个更简单的合成问题，其合成管道实现，使得实现和规范仅在更新的状态+分组向量的单个向量维度上一致。一旦成功合成每个切片，通过将最终的管道实现堆叠在彼此之上来合并切片实现，便可以形成最终的硬件实现。

与基于数据包的合成相比，切片有两个主要优势。首先，每个切片可以并行合成，因为每个切片实现运行在管道的独立子网格上，子网格之间没有重叠。第二，因为每个切片的实现只满足规范的一个子集，即一维而不是状态+分组向量的所有维度，可以使用比原始规范所需尺寸更小的子网格来合成。更小的网格需要更少的孔来合成，相对于原始规范，减少了任何一个切片的合成时间。

5 结论

本文介绍了 Chipmunk，一个基于程序合成的交换机编译器。Chipmunk 将程序放入有限的交换机管道资源中，否则这些程序可能会被基于规则的编译器拒绝。为此，它利用特定领域的合成技术来加速编译，并使用管道描述语言来定位多个后端。本文所展示的技术和结果有望促进在设计程序综合算法方面的后续研究，这些算法能够以更少的计算资源更快地编译程序，并以更低的交换机资源消耗产生机器代码。本文作者还认为，本文中的思想更普遍地适用于现场可编程门阵列和基于专用集成电路的智能网卡管道。

致谢

本文由南京大学软件学院2019级硕士研究生李紫欣翻译转述