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 將程序放入有限的交換機管道資源中，否則這些程序可能會被基于規則的編譯器拒絕。為此，它利用特定領域的合成技術來加速編譯，并使用管道描述語言來定位多個后端。本文所展示的技術和結果有望促進在設計程序綜合算法方面的后續研究，這些算法能夠以更少的計算資源更快地編譯程序，并以更低的交換機資源消耗產生機器代碼。本文作者還認為，本文中的思想更普遍地適用于現場可編程門陣列和基于專用集成電路的智能網卡管道。