檢視 Kahn 處理網路的原始碼

Kahn 流程網路（KPN，或稱流程網路）是一種分散式計算模型，其中一群決定性循序流程透過無界先進先出通道進行通訊。此模型要求從通道讀取是阻塞的，而寫入是非阻塞的。由於這些關鍵限制，所產生的流程網路表現出決定性行為，不依賴於計算的時序或通訊延遲。

Kahn 流程網路最初是為模擬平行程式而開發，但後來證明對於模擬嵌入式系統、高效能運算系統、訊號處理系統、串流處理系統、資料流程式設計語言及其他計算任務相當便利。KPN 由 Gilles Kahn 於 1974 年提出。

==執行模型==
KPN 是描述訊號處理系統的通用模型，在該模型中，無限的資料串流由循序或平行執行的流程進行漸進式轉換。儘管存在平行流程，執行此模型並不需要多工或平行處理。

在 KPN 中，流程透過無界 FIFO 通道進行通訊。流程從通道讀取和寫入不可分割的資料元素，也稱為權杖（token）。寫入通道是非阻塞的，意即它總是會成功且不會使流程停滯；而從通道讀取是阻塞的，意即一個從空通道讀取的流程將會停滯，直到通道包含足夠的資料項（權杖）後才能繼續。流程不被允許在不消耗權杖的情況下測試輸入通道中是否有權杖存在。一個 FIFO 不能被多個流程消耗，多個流程也不能寫入單一的 FIFO。對於一個流程，給定特定的輸入（權杖）歷史，該流程必須是決定性的，以便它總是產生相同的輸出（權杖）。流程的時序或執行順序不得影響結果，因此禁止測試輸入通道中是否有權杖。

===關於流程的注意事項===
* 一個流程不必然需要讀取任何輸入或擁有任何輸入通道，因為它可以作為純粹的資料來源。
* 一個流程不必然需要寫入任何輸出或擁有任何輸出通道。
* 為了最佳化目的，可以允許測試輸入通道是否為空（或非阻塞讀取），但這不應影響輸出。能夠提前做一些事情而不是等待一個通道可能是有益及／或可能的。例如，假設有兩個來自不同通道的讀取。如果第一次讀取會停滯（等待權杖），但第二次讀取可以直接成功，那麼先讀取第二次以節省時間可能是有益的，因為讀取本身通常會消耗一些時間（例如，記憶體分配或複製的時間）。

===作為裴特里網的流程觸發語意===

假設上圖 KPN 中的流程 P 的建構方式是先從通道 A 讀取資料，然後是通道 B，進行一些計算，再將資料寫入通道 C，則該流程的執行模型可以用右圖所示的裴特里網來模擬。PE 資源位置中的單一權杖禁止該流程對不同的輸入資料同時執行。當資料到達通道 A 或 B 時，權杖會分別被放入 FIFO A 和 FIFO B 的位置。裴特里網的轉移與各自的 I/O 操作和計算相關聯。當資料被寫入通道 C 後，PE 資源會再次被其初始標記填滿，從而允許讀取新的資料。

===作為有限狀態機的流程===

一個流程可以被模擬為一個有限狀態機，該狀態機處於以下兩種狀態之一：

* 活動；流程正在計算或寫入資料。
* 等待；流程被阻塞（等待）資料。
假設該有限狀態機讀取與流程相關的程式元素，它可能會讀取三種權杖，分別是「計算」、「讀取」和「寫入權杖」。此外，在等待狀態下，它只能透過讀取一個特殊的「取得權杖」來回到活動狀態，這表示與等待相關的通訊通道包含可讀取的資料。

==屬性==
===通道的有界性===
如果一個通道在任何可能的執行中最多只有  b  個未消耗的權杖，則該通道受  b  嚴格有界。如果一個 KPN 的所有通道都受  b  嚴格有界，則該 KPN 受  b  嚴格有界。

未消耗權杖的數量取決於流程的執行順序（排程）。如果排程器不執行消耗這些權杖的流程，一個自發性資料來源可能會向一個通道產生任意數量的權杖。

一個真實的應用程式不可能有無界 FIFO，因此在實際的實作中必須設計排程和 FIFO 的最大容量。FIFO 的最大容量可以透過幾種方式處理：
* FIFO 的邊界可以在設計時透過數學推導得出，以避免 FIFO 溢位。然而，這並非對所有 KPN 都可行。測試一個 KPN 是否受  b  嚴格有界是一個不可判定問題。此外，在實際情況中，邊界可能與資料相依。
* FIFO 的邊界可以依需求增加。
* 可以使用阻塞式寫入，這樣當 FIFO 滿時，流程會阻塞。不幸的是，這種方法可能導致人為死結，除非設計者為 FIFO 適當地推導出安全的邊界（Parks, 1995）。在執行時期可能需要局部的人為偵測，以保證產生正確的輸出。

===封閉式與開放式系統===
一個封閉式 KPN 沒有外部的輸入或輸出通道。沒有輸入通道的流程作為資料來源，沒有輸出通道的流程作為資料匯。在一個開放式 KPN 中，每個流程至少有一個輸入和輸出通道。

===決定性===
KPN 的流程是決定性的。對於相同的輸入歷史，它們必須總是產生完全相同的輸出。流程可以被模擬為循序程式，只要能保持決定性屬性，就可以按任何順序或數量對埠進行讀取和寫入。因此，KPN 模型是決定性的，系統的輸出完全由以下因素決定：

* 流程
* 網路
* 初始權杖

因此，流程的時序不影響系統的輸出。

===單調性===
KPN 流程是單調的。讀取更多的權杖只會導致寫入更多的權杖。未來讀取的權杖只能影響未來寫入的權杖。在 KPN 中，一個訊號內部的事件存在一個全序關係。然而，不同訊號中的事件之間沒有順序關係。因此，KPN 僅是部分有序的，這將其歸類為非計時模型。

==應用==
由於其高表達能力與簡潔性，KPN 作為計算模型被應用於數個學術模型工具中，用以表示具有特定屬性（例如，以資料流為導向、基於串流）的串流應用程式。

由萊登大學萊登嵌入式研究中心維護的開源 Daedalus 框架，接受以 C 語言編寫的循序程式，並產生相應的 KPN。這個 KPN 可以（舉例來說）被用來將 KPN 系統性地對應到一個基於 FPGA 的平台上。

Ambric Am2045 大規模平行處理器陣列是在實際晶片中實現的 KPN。其 336 個 32 位元處理器透過一個由專用 FIFO 組成的可程式化互連網路連接。因此，它的通道是具有阻塞式寫入的嚴格有界通道。

部分 AMD Xilinx Versal 中的 AI 引擎是 Kahn 流程網路的建構模組。

==參見==
* 同步資料流
* 交談循序程式
* 流程式程式設計
* 資料流程式設計

==參考資料==

==延伸閱讀==

Category:計算模型

[[分類: 待校正]]