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 即可进行计算，而无需再循环 。作为超出这些限制的程序的示例，如果管道仅支持状态的增量操作（但不支持乘法），并且该程序需要在排队延迟上使用指数加权的移动平均滤波器，则无法使用管道运行该程序 。
推荐阅读
- 详解 gcc 编译、链接原理—揭开应用程序运行背后的奥秘
- 随机数大家都会用，但是你知道生成随机数算法吗？
- 分库分表的 9种分布式主键ID 生成方案，挺全乎的
- 刺客羁绊用金铲铲和什么怎么合成 新版本金铲子合成羁绊
- 适用于任何设备的屏幕共享应用程序–Mirroring360
- 认识小程序生成平台：用法、优劣、成本
- 什么是整切牛排 整切牛排和合成牛排有什么区别
- 大学生|“理想男友”职业排名，程序员第三，“聪明绝顶”的医生成榜首
- python随机生成100道100以内的加法试卷
- 500个文件生成不到10秒，Python生成合同不要太方便