基于FPGA 的有色Petri 網仿真系統設計*

陳成官，張小軍，周韜略，張德學，郭 華

(山東科技大學電子信息工程學院，山東 青島266590)

Petri 網(Petri Net，PN)是一種適合于描述異步、并發、分布式系統的抽象描述方式，可用圖形表示法和代數表示法分別表示，具有直觀性[1]。 由于這些特點，Petri 網的理論得以快速發展和應用，其中有色Petri 網(Colored Petri Net，CPN)已經被廣泛用于系統仿真與驗證[2-4]、工作流分析[5-7]、性能分析[8-9]與算法錯誤檢測[10-11]等工作中。 對于PN 工具的設計與開發，目前已經取得了許多研究成果[12]。 但是，這些項目主要集中于通用計算機系統下對P/T 網(庫所/變遷網)進行的建模及模型的仿真驗證；并且在通用計算機系統上，存在模擬PN 并發性低效與仿真速度慢的問題。

現場可編程門陣列(FPGA)提供了一種新的建模方法。 FPGA 與通用計算機系統相比具有速度快、可重構和能效比高的優勢，并且可直接描述Petri 網異步并發的特性。 隨著Petri 網規模的擴大與復雜度的增加，FPGA 的速度優勢會越來越明顯。目前對基于FPGA 的PN 仿真系統的研究較少，且大多數涉及Petri 網的研究，都是以Petri 網在實際問題的應用研究為導向的，例如，Petri 網在邏輯控制器設計與離散事件系統監控理論中的應用[13]；并且現有的基于FPGA 的PN 實現方法不支持CPN 的仿真[14-15]。

本文實現基于FPGA 的CPN 仿真系統解決了兩個問題:CPN 的硬件架構設計、CPN 硬件模型的自動生成。 由于CPN 的一般定義與描述特別抽象，使得無法直接利用已有描述自動生成硬件模型，因此本文設計了“CPN 描述文檔”的內容及格式，并實現了CPN 硬件模型的自動生成工具，該工具根據“CPN 描述文檔”自動生成相應CPN 模型與仿真控制器的Verilog 代碼描述。 系統設計與驗證方案如圖1 所示，在已知CPN 模型的基礎上，將CPN 用“CPN 描述文檔”進行描述，通過自動生成工具生成Verilog 代碼描述；經過RTL 級仿真驗證后，建立Quartus 工 程， 經 過 編 譯， 在 Altera Cyclone V 5CSEMA5F31C6N FPGA 平臺上運行測試。

圖1 設計與驗證方案

本文內容安排如下:首先介紹了CPN 的基本概念與定義，并設計了CPN 描述文件的內容格式與結構，然后制定了CPN 元素到Verilog 描述的映射規則，給出了自動生成工具的程序流程，最后結合實例進行了運行測試。

1 有色Petri 網與描述

1.1 定義

每個PN 都由三部分組成:表征狀態的庫所、表征動作的變遷以及表征流關系的有向弧。 庫所用于存儲托肯(token)；流關系是權向量，方向與有向弧相同，其大小是權值，變遷的發生通過權值對庫所產生影響。 在CPN 中，每個庫所中可包含多種顏色的token；每個變遷可存在多種激活條件，稱為變遷的發生顏色；每個有向弧可包含多個流關系，每個流關系又對應變遷的一種或多種發生顏色。

一個經典CPN 可定義為一個9 元組N ＝〈P，T，A，Σ，V，C，G，E，I〉[16-17]。 其中:

· P 是庫所的有窮集合，在圖形表示法中，每個庫所用一個圓形(○)表示；

· T 是變遷的有窮集合，在圖形表示法中，每個變遷用一個矩形(□)表示；

· A?P×T∪T×P 是一個有限的“有向弧”集合，用單向箭頭(→)表示一個有向弧，Petri 網中用有向弧表征變遷與庫所之間的流關系；

· Σ 是一個非空有限的顏色集的集合，集合元素是顏色集；

· V 是變量的集合，?v∈V，Type[v]∈Σ，變量的類型由顏色集限定，Type[a]表示a 的類型；

· C 是庫所的顏色集函數，每個庫所與Σ 中的一個顏色集對應，庫所中token 的顏色與顏色集中的元素一一對應；

· G 是從變遷T 到變量表達式集EXPRV的映射函數，表征變遷的發生受到變量表達式的約束，?expression∈EXPRV，Type[expression]∈Σ；

· E 是從弧A 到變量表達式集EXPRV的映射函數；每個“有向弧”由一個變量表達式限定流關系，通常，變量表達式的所有取值對應該弧表示的所有流關系，?a∈A，Type[E(a)]＝C(p)，庫所p 與弧a 相連；

· I 是CPN 的初始化函數，為CPN 中每個庫所分配一個初始化表達式及該表達式對應token 的數量，?p∈P，Type[I(p)]＝C(p)。

1.2 描述文檔設計

CPN 與一般P/T 網不同，其復雜的流關系無法使用單一前后關聯矩陣表示。 為了描述CPN 中的流關系，本文提出了“庫所的全局關聯矩陣W”概念。為庫所Pn定義一個描述其與變遷的流關系的矩陣:

Wn＝NCT-MAX×NT(1)

式中:n∈[1，NP]，NP是CPN 中庫所的數量；列數NT是變遷的數量；行數NCT-MAX是單個變遷發生顏色數量的最大值。 矩陣Wn中的每一項用常數“0”表示顏色C(p)下變遷發生對庫所p 沒有影響，常數“1”表示顏色C(p)下變遷發生會導致該庫所中一種或幾種顏色的token 的數量增加，常數“-1”表示顏色C(p)下變遷發生會導致該庫所中一種或幾種顏色的token 的數量減少，常數“2”表示顏色C(p)下變遷發生會導致使該庫所中一種或幾種顏色的token 的數量增加的同時使該庫所中token 減少。

為增強CPN 描述文檔的可讀性，并清晰地描述變遷與庫所間的流關系，本文將庫所的全局關聯矩陣W 拆成前向Wpre與后向Wpost兩個矩陣進行描述，前向表征有向弧從變遷指向庫所，后向表征有向弧從庫所指向變遷。 將W 中所有“-1”項置為0，“2”項置為1 得到Wpre；將W 中所有“1”項置為0，“2”項置為-1 得到Wpost。 描述文檔包括7 個部分:

(1)庫所與變遷的個數描述:

(2)變遷發生顏色的個數描述:

(4)Pre 描述:

定義表示流關系(權向量)的基本元素為字符串“顏色標識符:權值”，顏色標識符是流關系對應庫所token 的顏色，權值表示此流關系發生時對相應顏色token 數量的影響；將Wpre的每一項用基本元素表示，不同項之間用空格隔開，同一項內的不同流關系之間用“+”連接；如，Wpre的“0”項用“0:0”替換，“1”項用“sand:2+cement:1”替換；得到Wspre。描述格式如下:

圖2 給出了CPN 的Verilog 模塊的映射架構設計，共4 種模塊:頂層模塊、控制器模塊、庫所模塊、變遷模塊；通過模塊中的判斷、判決與更新邏輯實現CPN 的狀態更新；reg 存儲庫所的token 數。

上述描述中，NP是庫所的個數，NT是變遷的個數；NCTi是變遷i 發生顏色的個數；NCPj是庫所j 包含token 的顏色的個數；L 是庫所對該顏色token 的最大容量；M 是在CPN 的初始狀態下庫所中該顏色token 的數量。

2 自動生成工具設計

2.1 CPN 的映射

本文將CPN 狀態的更新分成3 步:變遷的預激活、變遷的激活與庫所token 的更新，每一步消耗一個時鐘完成。 變遷的預激活是根據庫所中當前token 數判斷滿足激活條件的變遷；在變遷的激活階段對滿足激活條件的變遷進行沖突的判斷，并激活符合條件的變遷；在庫所token 的更新階段，根據激活的變遷更新庫所中token 的數量，實現一次CPN狀態的更新。

表1 描述了從CPN 描述到Verilog 描述的映射規則。 在Verilog 設計中，將庫所和變遷分別定義為一個module 模塊；將token 定義為庫所模塊中的output reg 類型的變量，位寬由庫所的token 容限描述確定；在CPN 頂層模塊中，為描述文檔的Pre/Post描述中每個基本元素定義一個wire，連接庫所模塊與變遷模塊，并將權值定義為庫所模塊中的parameter 參量。

表1 映射

圖2 映射架構設計

2.2 工作流程

自動生成工具的工作流程如圖3 所示，主要包括描述文件讀取、參數分析、Verilog 描述文件打印和測試文件打印4 個部分。 測試文件包括用于RTL仿真的testbench 文件和用于Verilog 編譯的自動綜合腳本。 參數分析過程會生成分析文件，可用于檢驗讀取文件得到的CPN 參數的正確性。

圖3 工作流程

3 測試

3.1 測試案例

本文選用一個描述通信中“包傳輸”的CPN 模型[18]作為測試案例，如圖4 所示，其顏色集和變量如表2 所示。 模型可以分為3 個部分:Sender、Network 和Receiver。 庫所Send 存儲要發送的字符串包及其編號，用顏色為(n，p)的token 表示，如(1，“Modellin”)。 變遷SendPacket 的發生根據庫所NextSend 中字符串包的編號將字符串包發送到Network 端的A 庫所。 庫所E、F 與變遷Ok 用來模擬網絡50%的丟包率，本文假設丟包率為50%。 變遷Update 根據庫所NextRec 中包的編號進行包的驗證，若通過驗證(n ＝k)，則將包中字符串與庫所Received 中原有字符串拼接得到的字符串更新到庫所Received 中，同時將C 庫所和NextRec 庫所中token顏色更新為下一個待傳輸包的編號。 最后依次通過變遷TransmitAck 和變遷ReceiveAck 將下一個待傳輸包的編號更新到NextSend 庫所中，使變遷Send-Packet 開始發送一個新的字符串包。

表2 “包傳輸”CPN 模型的顏色集和變量

圖4 “包傳輸”CPN 模型

假設待傳輸包有3 種，為(1，“Modellin”)、(2，“g and An”)和(3，“alysis”)，分別記為包1、包2 和包3，視為庫所Send 中3 種不同顏色的token，分別對應表4 中Send 行的顏色標識C1、C2 和C3；庫所E、 F 包 含 2 種 ok-token， 分 別 用 于 變 遷TransmitPacket 與變遷TransmitAck；將變量n 和k 的每種取值(1，2，3)都視作庫所NextSend、NextRec、C和D 中一種顏色的token。 本例中所有變遷的發生對token 的數量消耗都是1。 本文根據該“包傳輸”CPN 模型得到表3 所示的參數，并以此設計了描述文檔。 庫所容限與CPN 初始狀態如表4 所示。

表3 “包傳輸”CPN 模型的參數

為了簡化表述，本文采用p1、p2 等字符區分不同的庫所，采用t1、t2 區分變遷，采用C1、C2 等字符作為token 的顏色標識，區分庫所中不同的token，對應關系見表3 與表4。 其中p1、p3、p7 的顏色標識的含義對應相同，p2、p4、p8、p9 的顏色標識的含義對應相同，如p1 的C1 與p3 的C1 都指包1，p2 的C3 與p8 的C3 都指數字“3”。

表4 CPN 的庫所容限與初始狀態

在Received(p10)庫所中，C1-token 是指空字符token，即未接收到任何字符包時的token，是CPN 初始狀態下的p10 庫所包含的token；C2-token 是接收包1 后的token；C3-token 是在C2-token 的基礎上接收包2 后的token；C4-token 是在C3-token 的基礎上接收包3 后的token。 Received 庫所中出現C4-token標志著3 個包的成功發送。

3.2 測試結果

在Altera Cyclone V 5CSEMA5F31C6N 平臺上進行綜合，綜合頻率為156.37 MHz，ALMs 資源占用781，Register 資源占用2 027。 CPN 狀態每秒更新5.2×107次。 并采用Quartus 18.1 的Signal tap 邏輯分析儀監控設計的運行，得到圖5 所示的信號波形圖，圖中color2＿of＿place3 信號表示庫所p3 的C2 顏色token，其值是庫所中該token 的數量。

如圖5 所示，rst＿n 信號置為高電平后(圖中虛線)，測試從表4 第3 列所示的CPN 初始狀態開始，此時庫所p1 中有1 個C1-token，庫所p2 中有1 個C1-token，滿足變遷t1 的發生條件，而其他變遷的發生條件不充足；因此從圖中虛線后在outclk＿2 信號第3 個時鐘上升沿時只有color1＿of＿place3 信號變高電平，而其他信號數值不變，表示變遷t1 的發生在庫所p3 中產生了一個C1-token 并且其他庫所的token 數量不發生變化。 測試成功的標志，如圖5 中最下方4 條信號波形所示，庫所p10(Received)的4種token 從C1-token 到C4-token 依次出現，表示庫所從空字符依次接收了3 個字符包的過程，進一步對其他信號進行分析，信號的變化過程與CPN 模型的規定一致，驗證了自動生成工具的正確性。

圖5 Signal tap 邏輯分析儀結果

4 結論

為了加速CPN 模型的仿真，本文設計基于FPGA 的系統進行加速。 本文完成了CPN 的模塊到硬件結構的映射邏輯，設計了基于C 語言的CPN模型的Verilog 自動生成工具，實現了基于FPGA 的有色Petri 網仿真系統設計。 Signal tap 邏輯分析儀采集得到的信號驗證了仿真系統的正確性。