陳成官，張小軍，周韜略，張德學(xué)，郭 華

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

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

現(xiàn)場(chǎng)可編程門(mén)陣列(FPGA)提供了一種新的建模方法。 FPGA 與通用計(jì)算機(jī)系統(tǒng)相比具有速度快、可重構(gòu)和能效比高的優(yōu)勢(shì)，并且可直接描述Petri 網(wǎng)異步并發(fā)的特性。 隨著Petri 網(wǎng)規(guī)模的擴(kuò)大與復(fù)雜度的增加，F(xiàn)PGA 的速度優(yōu)勢(shì)會(huì)越來(lái)越明顯。目前對(duì)基于FPGA 的PN 仿真系統(tǒng)的研究較少，且大多數(shù)涉及Petri 網(wǎng)的研究，都是以Petri 網(wǎng)在實(shí)際問(wèn)題的應(yīng)用研究為導(dǎo)向的，例如，Petri 網(wǎng)在邏輯控制器設(shè)計(jì)與離散事件系統(tǒng)監(jiān)控理論中的應(yīng)用[13]；并且現(xiàn)有的基于FPGA 的PN 實(shí)現(xiàn)方法不支持CPN 的仿真[14-15]。

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

圖1 設(shè)計(jì)與驗(yàn)證方案

本文內(nèi)容安排如下:首先介紹了CPN 的基本概念與定義，并設(shè)計(jì)了CPN 描述文件的內(nèi)容格式與結(jié)構(gòu)，然后制定了CPN 元素到Verilog 描述的映射規(guī)則，給出了自動(dòng)生成工具的程序流程，最后結(jié)合實(shí)例進(jìn)行了運(yùn)行測(cè)試。

1 有色Petri 網(wǎng)與描述

1.1 定義

每個(gè)PN 都由三部分組成:表征狀態(tài)的庫(kù)所、表征動(dòng)作的變遷以及表征流關(guān)系的有向弧。 庫(kù)所用于存儲(chǔ)托肯(token)；流關(guān)系是權(quán)向量，方向與有向弧相同，其大小是權(quán)值，變遷的發(fā)生通過(guò)權(quán)值對(duì)庫(kù)所產(chǎn)生影響。 在CPN 中，每個(gè)庫(kù)所中可包含多種顏色的token；每個(gè)變遷可存在多種激活條件，稱(chēng)為變遷的發(fā)生顏色；每個(gè)有向弧可包含多個(gè)流關(guān)系，每個(gè)流關(guān)系又對(duì)應(yīng)變遷的一種或多種發(fā)生顏色。

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

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

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

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

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

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

· C 是庫(kù)所的顏色集函數(shù)，每個(gè)庫(kù)所與Σ 中的一個(gè)顏色集對(duì)應(yīng)，庫(kù)所中token 的顏色與顏色集中的元素一一對(duì)應(yīng)；

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

· E 是從弧A 到變量表達(dá)式集EXPRV的映射函數(shù)；每個(gè)“有向弧”由一個(gè)變量表達(dá)式限定流關(guān)系，通常，變量表達(dá)式的所有取值對(duì)應(yīng)該弧表示的所有流關(guān)系，?a∈A，Type[E(a)]＝C(p)，庫(kù)所p 與弧a 相連；

· I 是CPN 的初始化函數(shù)，為CPN 中每個(gè)庫(kù)所分配一個(gè)初始化表達(dá)式及該表達(dá)式對(duì)應(yīng)token 的數(shù)量，?p∈P，Type[I(p)]＝C(p)。

1.2 描述文檔設(shè)計(jì)

CPN 與一般P/T 網(wǎng)不同，其復(fù)雜的流關(guān)系無(wú)法使用單一前后關(guān)聯(lián)矩陣表示。 為了描述CPN 中的流關(guān)系，本文提出了“庫(kù)所的全局關(guān)聯(lián)矩陣W”概念。為庫(kù)所Pn定義一個(gè)描述其與變遷的流關(guān)系的矩陣:

Wn＝NCT-MAX×NT(1)

式中:n∈[1，NP]，NP是CPN 中庫(kù)所的數(shù)量；列數(shù)NT是變遷的數(shù)量；行數(shù)NCT-MAX是單個(gè)變遷發(fā)生顏色數(shù)量的最大值。 矩陣Wn中的每一項(xiàng)用常數(shù)“0”表示顏色C(p)下變遷發(fā)生對(duì)庫(kù)所p 沒(méi)有影響，常數(shù)“1”表示顏色C(p)下變遷發(fā)生會(huì)導(dǎo)致該庫(kù)所中一種或幾種顏色的token 的數(shù)量增加，常數(shù)“-1”表示顏色C(p)下變遷發(fā)生會(huì)導(dǎo)致該庫(kù)所中一種或幾種顏色的token 的數(shù)量減少，常數(shù)“2”表示顏色C(p)下變遷發(fā)生會(huì)導(dǎo)致使該庫(kù)所中一種或幾種顏色的token 的數(shù)量增加的同時(shí)使該庫(kù)所中token 減少。

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

(1)庫(kù)所與變遷的個(gè)數(shù)描述:

(2)變遷發(fā)生顏色的個(gè)數(shù)描述:

(4)Pre 描述:

定義表示流關(guān)系(權(quán)向量)的基本元素為字符串“顏色標(biāo)識(shí)符:權(quán)值”，顏色標(biāo)識(shí)符是流關(guān)系對(duì)應(yīng)庫(kù)所token 的顏色，權(quán)值表示此流關(guān)系發(fā)生時(shí)對(duì)相應(yīng)顏色token 數(shù)量的影響；將Wpre的每一項(xiàng)用基本元素表示，不同項(xiàng)之間用空格隔開(kāi)，同一項(xiàng)內(nèi)的不同流關(guān)系之間用“+”連接；如，Wpre的“0”項(xiàng)用“0:0”替換，“1”項(xiàng)用“sand:2+cement:1”替換；得到Wspre。描述格式如下:

圖2 給出了CPN 的Verilog 模塊的映射架構(gòu)設(shè)計(jì)，共4 種模塊:頂層模塊、控制器模塊、庫(kù)所模塊、變遷模塊；通過(guò)模塊中的判斷、判決與更新邏輯實(shí)現(xiàn)CPN 的狀態(tài)更新；reg 存儲(chǔ)庫(kù)所的token 數(shù)。

上述描述中，NP是庫(kù)所的個(gè)數(shù)，NT是變遷的個(gè)數(shù)；NCTi是變遷i 發(fā)生顏色的個(gè)數(shù)；NCPj是庫(kù)所j 包含token 的顏色的個(gè)數(shù)；L 是庫(kù)所對(duì)該顏色token 的最大容量；M 是在CPN 的初始狀態(tài)下庫(kù)所中該顏色token 的數(shù)量。

2 自動(dòng)生成工具設(shè)計(jì)

2.1 CPN 的映射

本文將CPN 狀態(tài)的更新分成3 步:變遷的預(yù)激活、變遷的激活與庫(kù)所token 的更新，每一步消耗一個(gè)時(shí)鐘完成。 變遷的預(yù)激活是根據(jù)庫(kù)所中當(dāng)前token 數(shù)判斷滿(mǎn)足激活條件的變遷；在變遷的激活階段對(duì)滿(mǎn)足激活條件的變遷進(jìn)行沖突的判斷，并激活符合條件的變遷；在庫(kù)所token 的更新階段，根據(jù)激活的變遷更新庫(kù)所中token 的數(shù)量，實(shí)現(xiàn)一次CPN狀態(tài)的更新。

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

表1 映射

圖2 映射架構(gòu)設(shè)計(jì)

2.2 工作流程

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

圖3 工作流程

3 測(cè)試

3.1 測(cè)試案例

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

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

圖4 “包傳輸”CPN 模型

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

表3 “包傳輸”CPN 模型的參數(shù)

為了簡(jiǎn)化表述，本文采用p1、p2 等字符區(qū)分不同的庫(kù)所，采用t1、t2 區(qū)分變遷，采用C1、C2 等字符作為token 的顏色標(biāo)識(shí)，區(qū)分庫(kù)所中不同的token，對(duì)應(yīng)關(guān)系見(jiàn)表3 與表4。 其中p1、p3、p7 的顏色標(biāo)識(shí)的含義對(duì)應(yīng)相同，p2、p4、p8、p9 的顏色標(biāo)識(shí)的含義對(duì)應(yīng)相同，如p1 的C1 與p3 的C1 都指包1，p2 的C3 與p8 的C3 都指數(shù)字“3”。

表4 CPN 的庫(kù)所容限與初始狀態(tài)

在Received(p10)庫(kù)所中，C1-token 是指空字符token，即未接收到任何字符包時(shí)的token，是CPN 初始狀態(tài)下的p10 庫(kù)所包含的token；C2-token 是接收包1 后的token；C3-token 是在C2-token 的基礎(chǔ)上接收包2 后的token；C4-token 是在C3-token 的基礎(chǔ)上接收包3 后的token。 Received 庫(kù)所中出現(xiàn)C4-token標(biāo)志著3 個(gè)包的成功發(fā)送。

3.2 測(cè)試結(jié)果

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

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

圖5 Signal tap 邏輯分析儀結(jié)果

4 結(jié)論

為了加速CPN 模型的仿真，本文設(shè)計(jì)基于FPGA 的系統(tǒng)進(jìn)行加速。 本文完成了CPN 的模塊到硬件結(jié)構(gòu)的映射邏輯，設(shè)計(jì)了基于C 語(yǔ)言的CPN模型的Verilog 自動(dòng)生成工具，實(shí)現(xiàn)了基于FPGA 的有色Petri 網(wǎng)仿真系統(tǒng)設(shè)計(jì)。 Signal tap 邏輯分析儀采集得到的信號(hào)驗(yàn)證了仿真系統(tǒng)的正確性。