随着P4语言正逐渐成为可编程交换机事实上的可编程语言标准，越来越多的人希望打造属于自己的支持P4语言的可编程交换机或智能网卡或DPU，因此支持P4语言的编译器的开发至关重要。P4编译器负责如何将逻辑查找表映射到物理表，同时要满足程序中的数据和控制依赖关系，这里面涉及到数学的最优化问题。抛开最优化问题不谈，能否打造一款不是最优的但也能支持P4语言的编译器呢？打造编译器的过程中会遇到什么问题呢？有没有可以参考的开源资源？或许2022年8月26日arvix网站上的一篇文章会告诉你答案。PDF原文下载链接：https://arxiv.org/pdf/2208.12892.pdf。本文将该文的部分内容进行了翻译（跟以往的公众号相关文章一样，翻译质量不高，难免有问题，见谅！），给大家分享一下。另外，笔者所在团队也曾开发过一款支持P4语言的HyperParser，其中就开发出一款支持P4语言的自己的编译器，具体可参考公众号之前文章《【Verilog开源】一种用于智能网卡或可编程交换机的，支持P4语言的高性能开源解析器的设计》。
摘要：P4语言已成为编程基于可重构匹配动作表的可编程交换机的主要选择。V1Model架构是匹配动作架构最广泛可用的实现。P4联盟开发的开源编译器前端可以执行语法分析，并导出使用最新版本的P4（也称为P416）编写的程序的硬件独立表示。但是还需要后端编译器将此硬件表示映射到V1Model交换机的硬件资源。然而，没有开源后端编译器可用于检查P416程序在V1Model交换机上的可实现性。不同硬件供应商提供的专有工具完成上述映射过程。但是，它们是封闭源代码，我们看不到内部的映射机制。这抑制了针对可重构匹配动作表架构的新映射算法和创新指令集的实验。此外，专用后端编译器成本高昂，并附带各种保密协议。这些因素对可编程交换机相关研究提出了严峻挑战。在这项工作中，我们为基于V1Model架构的可编程交换机提供了一个开源P416后端编译器。它使用基于启发式的映射算法将P416程序映射到V1Model交换机的硬件资源上。它允许开发人员快速原型化不同的映射算法。它还提供了P416程序的各种资源使用统计信息，从而能够在多个P416方案之间进行比较。
01
引言
RMT体系结构和P4语言：近年来，基于可重构匹配动作表（RMT）[1]体系结构的可编程交换机越来越流行，并得到了广泛部署。P4语言已经成为对这些交换机进行编程的事实上的标准语言。自引入[2]以来，P4编程语言经历了几次架构变化。其最新版本（版本16[3]，也称为P416）是该语言最初版本（P414[4]）的主要重新设计。它被设计为支持具有不同架构的各种目标交换机（即，软件交换机[5]、smartNIC[6]、eBPF[7]、FPGA[8]、RMT[9]、dRMT[10]等）进行分组处理。
图1:V1Model交换机P4编译器的高级工作流程
基于RMT架构[1]的交换机被设计为多级流水线，其中包含可重新配置的解析器、多个匹配动作阶段、逆解析器和一些其他固定模块（例如，数据包复制引擎和流量管理器等[1、9、11]）。P4提供了描述这些交换机架构和运行时行为的语言结构。交换机的体系结构描述包括流水线的高层结构、功能和接口。硬件支持的功能作为单独的目标特定库提供。它们都由硬件供应商提供。数据平面程序开发人员使用目标特定库和P4核心库来描述RMT交换机作为P4程序的运行时行为。
RMT交换机的P4编译器：P4语言本质上与目标硬件无关，只提供高级命令式结构来表达各种数据包处理架构的数据包处理逻辑。因此，P4程序和RMT架构的组件之间没有直接映射。将给定P4程序转换为目标交换机执行的特定可执行程序（二级制的硬件配置），P4编译器就是十分必要的。P4编译器（图1）通常由三个主要组件组成[12]：a）负责语法分析的独立于目标的前端，验证目标无关约束（例如，P4所需的无环控制流），并将P4程序转换为目标无关中间表示（IR），表示一系列逻辑匹配动作表之间的控制流。b） 用于独立于体系结构的优化的中间端[13]，以及c）基于目标硬件的后端编译器，负责生成可被目标硬件执行的可执行程序。它需要资源分配机制（图1中的后端编译器映射阶段）来将IR组件映射到目标硬件资源上。它计算P4程序的报头字段到RMT硬件的包报头向量（PHV）映射、包报头解析器状态机（在IR中表示为解析图）到RMT软件的状态表映射以及P4程序控制流（表示为逻辑匹配动作表的图）到RM硬件的物理匹配动作表映射。这些映射需要符合目标相关约束（即，报头向量容量、纵横宽度、匹配动作表维度等）。如果P4程序可以成功地映射到目标硬件上；以可执行硬件配置二进制文件的形式从映射（图1中的后端编译器配置生成阶段）生成相应的硬件配置。该可执行配置由控制平面加载到目标硬件中，并由目标硬件执行。
RMT交换机的开源P4编译器：P4C[14]是P4语言的参考编译器。它由P4语言联盟开发，并遵循图1所示的工作流程[12，14]。它支持两种不同的基于RMT架构的交换机：a）广泛称为V1Model架构的simple_switch模型[15]和b）P4语言协会开发的便携式交换机架构（PSA）[16]（尚未完全实现）。然而，P4C没有为这两种体系结构的实际目标硬件提供任何后端编译器。P4C前端 中端将中间表示作为独立于硬件的JSON文件发送，参考软件交换实现（BMV2[17]）在各自硬件架构的CPU仿真上执行它们。它没有考虑实际目标交换机中存在的实际硬件资源限制。因此，P4C不能决定给定P4程序在这些RMT交换机的特定实例上的可实现性。除了P4C，文献中还提供了其他几种用于基于RMT架构的交换机的开源编译器。然而，其中一些[18]与P4语言的旧版本（P414[4]）一起使用，这在架构上与P4的当前版本（P416[3]）不同。其他一些工作侧重于不同的分组处理语言（例如，Domino[19，20]）、不同的架构（drmt[10]）或不同的硬件平台（例如，FPGA[8]）。因此，研究人员需要使用专有后端编译器[21]来决定是否可以使用RMT交换机实现P4程序。然而，这些系统是封闭源代码的，价格昂贵，并且通常附带额外的保密协议[9]。
为什么选择开源后端编译器：后端编译器负责将P4程序映射到目标硬件，在P4生态系统中起着至关重要的作用。它负责测量RMT管道中P4项目的资源消耗。可编程交换机包含有限的硬件资源。因此，具有实现特定任务所需的最少硬件资源的P4程序更具资源效率。近年来，大量研究工作使用了BMV2[17]模拟器，将P4C编译器作为其目标平台，该模拟器缺乏能够考虑目标硬件中存在的实际资源约束的后端编译器。没有这样的后端编译器，研究人员无法测量其方案的资源需求，也无法比较多个方案的资源使用效率。在最坏情况下，如果没有后端编译器，这些P4程序不能被实现为P4硬件。因此，这些P4程序是否可以通过现实生活中的RMT交换机直接执行，这一点值得商榷。
后端编译器需要解决几个计算上难以解决的问题[18，22]，以找到P4程序到目标硬件的映射。优化算法通常需要很长时间才能完成[18，22]。随着网络内计算[23]范式的不断兴起，各种研究工作[24–28]也将重点放在数据平面中的不同网络功能的开发上。在这些情况下，研究人员不需要安装具有各种功能的成熟交换机所需的大型P4程序。当数据平面程序员需要将如此大的P4程序适配到目标硬件中时，最佳映射算法是很重要的。另一方面，使用基于启发式算法的开源后端编译器可以为研究人员提供关于使用目标硬件实现较小P4程序的快速决策。
后端编译器使用的映射算法对P4程序的资源（TCAM/SRAM存储、ALU数量、纵横宽度等）要求以及目标交换机中的可用资源非常敏感[18]。P4程序的资源需求可以在运行时改变（例如，IPv4转发表的大小增加），这可能使先前计算的映射无效。随着网络虚拟化[29]和网络即服务[30]范式的快速扩散，按需网络功能部署的需求也在快速增长。它需要在短时间内快速自动部署定制的数据平面算法。因此，开发更快、更有效的启发式/近似映射算法具有重大意义。使用封闭源代码后端编译器，研究人员无法尝试不同的映射算法。除此之外，在RMT体系结构中开发支持复杂指令的硬件单元（P4语言中的extern[3]）越来越受到关注[31–33]。
没有开源后端编译器，研究人员无法将新开发的外部程序集成到P4程序中并测试其有效性。从头开始独立开发后端编译器需要各种与映射计算无关的常见和重复任务（即IR解析、使用图形数据结构表示解析的IR、建模硬件资源等）。开源后端编译器可以让研究人员专注于开发高效的映射算法，而不是专注于重复的任务。
受这些因素的启发，在这项工作中，我们为基于V1Model[15]架构的RMT交换机设计了一个开源P4后端编译器（仅映射阶段）。据我们所知，它是第一个基于RMT架构的可编程交换机的开源P416后端编译器。后端编译器需要两个输入：a）V1Model交换机中可用资源的规范，以及b）P4C前端生成的P4程序的中间表示（IR）。由于P4C不提供任何接口来指定V1Model交换机的硬件资源，我们开发了基于JSON格式的硬件规范语言（HSL）（第3.3节）来表示V1Model交换机的硬件资源规范。在讨论了第2节中的相关工作之后，我们在第3节中简要讨论了V1Model架构以及HSL（第3.3节）。然后，我们介绍了P4C编译器前端提供的IR结构（第4节）。该后端使用各种现有的基于启发式的算法来分配V1Model交换机中的流水线资源并计算IR到硬件资源的映射。据我们所知，这是文献中第一个考虑P4程序中使用有状态内存产生的约束及其对映射决策的影响的方案我们在第5节中讨论了映射过程的细节。一旦找到映射，计算硬件配置二进制文件需要将映射直接转换为硬件指令代码。由于这项工作不专注于在V1Model switch的任何特定实例上执行P4程序，因此我们将硬件配置二进制生成留给未来的工作。我们在第6节中讨论了后端编译器的实现和评估，并在第5节中总结了本文。
为什么选择V1Model: V1Model是开源P4C编译器前端完全支持的唯一RMT交换机。此外，主要可编程交换机硬件供应商都支持V1Model架构[9，34]。近年来，大量研究工作[35]将V1Model用作其参考硬件架构（通过使用商用硬件或BMV2模拟器）。此外，V1Model类似于P4语言版本14中使用的抽象交换机模型。因此，所有基于P414的研究工作都可以映射到该模型。最后，P4联盟正在标准化的最新可编程交换机架构是PSA[16]，它也类似于V1Model架构。本文中介绍的后端编译器可以通过少量修改扩展到PSA体系结构。由于这些原因，V1Model是大量研究工作的代表性硬件架构，我们选择为该架构构建后端编译器。
后端编译器不做什么：本文中介绍的后端编译器仅支持V1Model架构和P4语言（P416）结构的子集，它们涵盖了广泛的用例。系统支持的P4结构的完整列表，见[36]。专有硬件可以具有用于数据包处理的特殊指令（如extern[3]），并且它们的系统中也可以具有附加约束。我们的后端编译器不是任何专有系统的完全替代品。它使用启发式算法将P4程序映射到V1Model交换机，尽管存在有效映射，但它可以部分拒绝P4程序（如其他可编程交换机后端[37]）。此外，由于使用了启发式，它不能保证计算映射的最优性。最后，后端编译器仅覆盖图1所示的映射阶段，而不覆盖硬件配置生成阶段。
02
相关工作
在[2]中，作者介绍了一种基于RMT架构的抽象交换转发模型，并提出了P4编程语言，以与协议无关的方式对交换机进行编程。作者还介绍了两级P4语言编译器的高级结构。虽然这项工作简要地讨论了解析器和TDG映射问题，但缺少一个完整的后端编译器开源系统。在[38]中，作者解决了将数据包解析逻辑映射到基于CAM的硬件的问题。然而，它的主要重点是合成解析器硬件电路。因此，它不能直接用于P416后端编译器。在[18]中，作者讨论了将RMT交换机的逻辑匹配动作表映射到物理匹配动作表的计算复杂性。他们提出了一种基于整数线性规划的方法（用于最优解）以及一些基于启发式的映射计算方法
该系统是一个开源项目。然而，它不能支持P4程序中的状态存储器，这是网络内计算范式的关键要求。上面提到的所有工作都是为了支持P4语言的初始版本（又称P414[4]），并且没有一个提供完整的后端编译器。此外，最新版本的P4语言（又称P416）在架构上与P414不同。因此，这些工作不能直接用于编译P416程序
P4语言联盟开发的P416语言的参考编译器是P4C[14]。其前端可以为各种目标体系结构（包括RMT体系结构）编译P416程序。它通过基于CPU的仿真为两个RMT架构交换机提供后端支持：V1Model[15]和PSA[16]。这些仿真后端在CPU上执行P4程序的中间表示。它没有规定对RMT交换机的硬件资源进行建模。在决定P416程序是否可以映射到真实的目标硬件时，无法考虑硬件资源限制约束。在[8]中，作者为基于FPGA的平台提供了一个开源P416后端编译器。然而，该系统的基本块与RMT体系结构中使用的物理匹配动作表不同。这里，基本块可以执行匹配和分支指令；并且基于它们的结果，可以执行一些动作。因此，与原始RMT架构相比，它在每个节点中提供了更灵活的匹配动作能力
RMT体系结构的文献中几乎没有其他开源编译器编译器[37，39]。然而，它们[37]要么不支持P416中编写的程序作为输入，要么是为基于非RMT架构的硬件平台设计的[39]。除了这些开源系统，还存在一些能够支持RMT交换机的P416语言的专有后端编译器[21，40]。然而，它们本质上是封闭源代码，不提供对其内部机制的访问。
03
V1Model架构
V1Model是可重构匹配动作（RMT）体系结构的一个实例。其分组处理流水线（图2）由多个布置在多个阶段中的组件组成。本节描述其组件、不同资源类型的规范以及它们如何处理数据包。最后，在第3.3节中，我们提出了一种硬件规范语言来表示V1Model交换机的资源。
图2 V1Model的流水线结构
3.1解析器和包头向量
在V1Model架构中，传入数据包首先通过基于TCAM的[38]可编程解析器（图3），该解析器执行以状态机形式提供的解析逻辑（由后端编译器转换为状态表）。解析器包含两个主要构建块：
a）报头识别单元：它包含一个PB位宽的缓冲区，用于在数据包中查找并在每个周期识别最多H个包头。它还包含一个TCAM，能够存储PTL条目以实现状态表。每个TCAM条目包含当前解析状态的信息和要匹配的头字段的值（作为位序列）。在每个周期，可以在TCAM中查找最大f TC查找字段值（每个字段具有最大查找宽度f TW b）和当前状态。TCAM条目为PTW b宽，用于存储查找字段值和当前状态值。每个条目还包含指向RAM单元的指针，用于存储下一个解析状态和要由提取单元提取的报头字段的位置。
b） 提取单元：在TCAM中匹配数据包后，存储在SRAM的匹配索引单元中的信息被加载到提取单元中。该单元可以提取最大PEW位宽数据作为报头字段，并将其存储在字段缓冲器中。在每个循环中，提取几个报头字段，并将下一个解析状态馈送到报头识别单元，以便在下一个循环中在TCAM中进行匹配。报头识别单元可以向前移动到分组中的最大PMA位，以开始识别下一报头字段。每个解析器单元都设计为具有最大解析速率（PRate）吞吐量。V1Model交换机可以并行部署多个解析器单元，以实现更高的数据包解析速率。
完成解析后，所有提取的报头字段从字段缓冲器发送到分组报头向量（PHV）。PHV可以存储不同类型的字段；类型i的所有f iC报头字段均为f iW位宽（i=1至F）。PHV中的多个字段可以合并在一起以形成更大的标题字段。除了解析的头字段之外，PHV还存储硬件特定元数据（即入口端口、时间戳等）。PHV通过宽首部总线传递到流水线中的后续组件（图2的N个匹配动作阶段）。
3.2 匹配-动作阶段
经过解析之后，PHV通过N个匹配动作阶段进行入口阶段处理。每个阶段（图3）包含T个TW位宽的TCAM块单元，每个TCAM块能够存储TL条目。它还包含S个SW位宽SRAM块，每个块都能够存储SL条目。TCAM块用于实现三元/范围/前缀/精确匹配的物理匹配动作表（MAT）。一小部分SRAM块（SM块）用于实现基于哈希表（使用HSK-way-Cuckoo哈希表[41，42]）的物理匹配动作表以进行精确匹配，其余用于存储其他信息（即动作参数、下一个MAT地址等）。这些较小的物理匹配动作表可以独立运行，也可以分组在一起，以匹配阶段中更宽的标题字段。跨阶段的MATs可以合并以实现更长的表。头字段分别通过两个交叉开关TCB（TCBW位宽）和SCB（SCBW位宽度）从PHV提供给基于TCAM和SRAM的物理MA。对于MATs中的每个条目，有一个相应的指针指向相应的动作信息（动作参数，动作指令，地址和下一个MAT地址等）。在MATs中找到匹配时，从存储器加载相应的动作信息。每个匹配动作阶段包含用于PHV的每个字段的独立算术逻辑单元（ALU），用于并行计算。两个或多个单元可以组合在一起，以在较大的字段上执行计算。除了每个报头字段ALU单元外，在每个匹配操作阶段，还可以使用固定数量的外部单元（散列、计数器、寄存器、计量器等）进行特殊操作（即散列计算、计数、存储/加载状态等）。
每个阶段可以存储所有用于物理MATs的Ac个VLIW指令。每个VLIW命令都为每个报头字段ALU和外部单元携带单独的指令。数据从PHV通过ACBW位宽交叉开关（ACB）提供给这些处理单元。与匹配交叉开关（TCB和SCB）类似，该交叉开关的每一位都由PHV的所有字段驱动。动作信息（除了动作指令存储在专用存储器中）和外部单元使用的有状态存储器被分配在可用SRAM块（分别为SA块和SS SRAM块）的单独块中。每一级包含MP内存端口（每一个MBW位宽），能够在一个时钟周期内从/读写到SRAM单元。这些端口用于从SRAM块读取/写入数据，以获得精确的MATs、动作存储器和状态存储器。每个基于TCAM的MAT都可以存储固定数量的匹配条目（最大容量）。另一方面，基于SRAM的MAT可以存储可变数量的条目，因为相同的SRAM块被分配用于存储匹配条目、动作条目和有状态存储器。用于精确匹配MAT、动作存储器和有状态存储器的总SRAM块（可用总S块中的SM、SA和SS）的数量取决于第5.3节的逻辑到物理MAT映射算法。为了优化SRAM使用，RMT架构允许字打包，创建多个SRAM块的打包单元
多个条目（匹配、操作或有状态内存条目）可以存储在一个单元中，以减少SRAM浪费。这种可变打包格式不会影响匹配性能，匹配单元可以将数据包与存储在同一SRAM块中的多个字进行匹配。
图3 RMT流水线上的一个匹配-动作阶段
数据包复制引擎和流量管理器（PRE&TM）：完成入口阶段处理后，数据包被提交到出口端口的队列。PRE&TM是一个不可编程的组件，负责处理端口队列中的数据包生命周期，调度数据包，并在必要时复制数据包。除了这些，还有两个用于计算和验证数据包校验和的固定功能组件。由于它们是固定的功能块，我们不讨论它们的细节。
输出阶段：一旦从出口端口的队列中取出数据包，它将进行出口阶段处理。出口级类似于入口级，并共享相同的物理组件进行处理。后端编译器在入口线程和出口线程之间分配资源，使它们不会妨碍彼此的数据包处理活动
逆解析器：出口阶段处理完成后，数据包通过逆解析器块。它重新组合来自分组报头向量字段的数据和有效载荷。则分组最终通过输出信道传播。
3.3 V1Model硬件规范语言
后端编译器需要有关V1Model交换机可用资源的信息。然而，公开可用的P4C编译器不提供任何接口来对其进行建模。包头向量、可编程解析器和匹配动作阶段是V1Model架构中的主要可编程组件。我们开发了一种基于JSON格式的硬件规范语言（HSL），用于指定基于V1Model架构的交换机的可编程组件中的可用资源。该语言允许指定PHV中可以容纳多少标题字段，以及这些字段的位宽。类似地，它允许指定可编程解析器中使用的各种硬件资源的维度（第3.1节）。它还允许指定匹配操作阶段的数量和每个阶段中的资源数量，如第3.2节所述。附录B显示了V1Model交换机的示例硬件规范。
因为篇幅有限，中间内容请参考原文，此处翻译略。
07
讨论
局限：我们的后端编译器支持大多数P4语言结构，涵盖广泛的用例。然而，它仍然不支持可变长度的头解析和操作中的直接有状态内存访问。通过仔细设计P4程序，可以避免这两种情况。除此之外，它不支持P4语言中可用的原子事务机制。我们正在努力支持这些P4语言功能。
扩展V1Model体系结构：PSA[16]或Tofino[47]是V1Model架构的扩展，其中架构支持不同的外部。这些架构可以在一个原子指令中组合多个更简单的指令，以实现复杂的功能。例如，Tofino交换机[9]中可用的寄存器extern可以执行四路分支指令。它可以在一对寄存器（间接有状态内存）上执行两个if-else对和读-修改-写操作。然而，要在P4程序中使用它们（或任何新的外部），P4C编译器前端需要支持它们。之后，这些外部可以在我们的后端编译器中得到支持，只需对P4程序的计算映射进行少量修改。
编写新的映射算法：我们的后端编译器以模块化的方式设计。在解析P4程序的中间表示之后，它将预处理信息（头信息、解析图、TDG）存储在各种方便的数据结构（哈希表、图等）中。除此之外，它还以各种方便的数据结构（哈希表、数组等）存储V1Model交换机中的资源。作为一个开源项目，研究人员可以重用这些处理过的信息来编写用于头映射、解析图映射和TDG映射的新算法。关于源代码组织的详细讨论参见[36]。
08
结论
P4程序的可实现性给出快速决策。我们相信，这个开源后端编译器可以作为一个经济高效的平台，用于分析现实世界V1Model交换机中P4（版本16）程序的可实现性和资源消耗。它允许研究人员作为一个开源平台来试验不同的映射算法。通过支持各种外部单元，它可以扩展到支持V1Model架构的其他派生。这可以为可编程交换机研究人员提供一个开放平台，用于试验不同的映射算法和V1Model交换机的不同变体。
THE END
今天是中秋节，祝大家：中秋节快乐！月光所至，皆为故乡！
更多有关P4编译器涉及到的最优化问题相关的文章可参考Nick教授团队的经典文章：
翻译：郭卫 图文排版：潘伟涛
责任编辑：刘欢 潘伟涛
