隨著P4語言正逐漸成為可編程交換機事實上的可編程語言標準，越來越多的人希望打造屬于自己的支持P4語言的可編程交換機或智能網卡或DPU，因此支持P4語言的編譯器的開發至關重要。P4編譯器負責如何將邏輯查找表映射到物理表，同時要滿足程序中的數據和控制依賴關系，這里面涉及到數學的最優化問題。拋開最優化問題不談，能否打造一款不是最優的但也能支持P4語言的編譯器呢？打造編譯器的過程中會遇到什么問題呢？有沒有可以參考的開源資源？或許2022年8月26日arvix網站上的一篇文章會告訴你答案。本文將該文的部分內容進行了翻譯。

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交換機的不同變體。

—END—

審核編輯 ：李倩