周韜略，張小軍，陳成官，曾慶田，張德學(xué)

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

0 引言

Petri網(wǎng)是一種抽象規(guī)范語言特別適用于并發(fā)系統(tǒng)建模，不僅可以用常規(guī)語言描述，還能使用可視化圖形表示。這些特性使得Petri 網(wǎng)作為實(shí)現(xiàn)工具被廣泛應(yīng)用。國內(nèi)外學(xué)者一直保持著對其理論研究［1-3］。Petri網(wǎng)被認(rèn)為是對離散事件系統(tǒng)并發(fā)行為建模的有效方法。具有充分的模擬能力和豐富的分析方法，是一種適合描述和分析具備異步性、并發(fā)性、并行性等特點(diǎn)的形式化語言［4-5］，Petri 網(wǎng)的應(yīng)用領(lǐng)域也隨著理論的發(fā)展而不斷拓寬。盡管它們被廣泛使用［6-8］，也主要集中在建模、驗(yàn)證和系統(tǒng)模型驗(yàn)證上，硬件發(fā)展的同時(shí)促進(jìn)了Petri網(wǎng)的應(yīng)用［9-10］，但基于FPGA 設(shè)計(jì)Petri網(wǎng)硬件模擬器的研究較少。Gomes等［11-13］已經(jīng)用硬件描述語言VHDL設(shè)計(jì)Petri 網(wǎng)，但用Verilog HDL 描述的研究方面甚少。Verilog HDL 語言具有行為描述能力及與硬件行為無關(guān)的優(yōu)勢，可實(shí)現(xiàn)硬件電路與軟件設(shè)計(jì)相結(jié)合，適合用于描述異步并發(fā)系統(tǒng)，是Petri 網(wǎng)硬件實(shí)現(xiàn)的有力工具［14］。

本文研究Petri網(wǎng)關(guān)聯(lián)矩陣到Verilog HDL語言編譯程序設(shè)計(jì)的方案，實(shí)現(xiàn)基本Petri 網(wǎng)的P／T 系統(tǒng)到Verilog HDL語言轉(zhuǎn)換的自動(dòng)編譯程序，采用Verilog HDL來對系統(tǒng)的Petri網(wǎng)模型、控制器模塊和存儲器模塊進(jìn)行描述。并在EDA 軟件平臺下（Modelsim 和Quartus II）對綜合模塊的Verilog HDL 語言描述進(jìn)行綜合、仿真、適配，并下載到FPGA 中。最后將指令信號寫入寄存器，使得運(yùn)行結(jié)果在Quartus軟件中的信號邏輯分析儀（SignalTap II Logic Analyzer）內(nèi)顯示。

1 基本理論

1.1 Petri網(wǎng)理論

圖1 為一個(gè)基本Petri 網(wǎng)，其中s1、s2、s3、s4為庫所，t1、t2、t3、t4為變遷。在使用Petri網(wǎng)模擬系統(tǒng)時(shí)，M0來描述其初始狀態(tài)。在初始狀態(tài)時(shí)，因?yàn)榭赡苡胁恢挂粋€(gè)變遷具備發(fā)生權(quán)，使得系統(tǒng)存在著多種可能性。只要有變遷發(fā)生，系統(tǒng)就會進(jìn)入一個(gè)新的狀態(tài)，同時(shí)得到新的標(biāo)識M1。在新標(biāo)識M1下可能也會存在有發(fā)生權(quán)的變遷。網(wǎng)系統(tǒng)就是伴隨著變遷的發(fā)生而運(yùn)行的。

圖1 典型的基本Petri網(wǎng)

Petri網(wǎng)可看作是對狀態(tài)機(jī)的一種推廣：變遷起源于多個(gè)活動(dòng)狀態(tài)，若干狀態(tài)可能需要處于活動(dòng)狀態(tài)才能使能變遷。Petri網(wǎng)是一種并發(fā)模型，可同時(shí)觸發(fā)多個(gè)變遷。Petri網(wǎng)可用簡單的圖形表示：被動(dòng)實(shí)體（例如狀態(tài)或資源），命名庫所，表示為圓或橢圓；活動(dòng)實(shí)體（例如動(dòng)作或函數(shù)），命名變遷，表示為矩形或條形。庫所只能連接變遷，變遷只能連接到庫所。庫所內(nèi)的資源命名為托肯（token），可刪減和增加，有向弧指向的每個(gè)變遷只能在所有輸入弧連接到的庫所內(nèi)托肯個(gè)數(shù)滿足條件才能工作［15］。

根據(jù)變遷規(guī)則，給出網(wǎng)系統(tǒng)（net system）的變換規(guī)律。一個(gè)標(biāo)識網(wǎng)Σ ＝（S，T；M，F(xiàn)）的網(wǎng)系統(tǒng)（S 中的元素為庫所，T 中的元素為變遷，M 是狀態(tài)標(biāo)識，F(xiàn) 是一個(gè)有向邊的集合），具有以下發(fā)生規(guī)則：

（2）若M［t ＞，則在標(biāo)識M 下，變遷t 可以發(fā)生，從標(biāo)識M發(fā)生變遷t得到一個(gè)新標(biāo)識M′（記做M［t ＞M′］），對于?s∈S，

1.2 關(guān)聯(lián)矩陣

關(guān)聯(lián)矩陣分為輸入和輸出矩陣，輸入和輸出矩陣的每行和每列分別為一個(gè)庫所和一個(gè)變遷，矩陣的長度和寬度分別為該P(yáng)etri 網(wǎng)庫所和變遷的數(shù)量，輸入、輸出矩陣的每行和每列非零值的個(gè)數(shù)分別為該庫所和該變遷的出度和入度，矩陣中非零元素的位置和數(shù)值分別為弧的連接置位和權(quán)值，輸入和輸出矩陣分別為弧的方向。

以圖1 中的Petri網(wǎng)為例，s1～s4表示4 個(gè)庫所，其關(guān)聯(lián)矩陣的列數(shù)為4。t1～t4為4 個(gè)變遷，其關(guān)聯(lián)矩陣的行數(shù)為4。若某庫所與某變遷間有輸出弧，則輸入矩陣的對應(yīng)位置的元素為該弧的權(quán)值，因?yàn)閟1有一個(gè)指向t2的弧，假如圖中弧上權(quán)值都等于1，則輸入矩陣的第2 行第1 列為1；若某變遷與某庫所間有輸出弧，則輸出矩陣對應(yīng)位置為該弧的權(quán)值，例如t2有一個(gè)指向s2的弧，因此輸出矩陣的第2 行第2 列為1；若某庫所與某變遷之間沒有連接關(guān)系，則對應(yīng)位置元素為0。根據(jù)以上規(guī)則，圖1 中Petri 網(wǎng)的輸入和輸出矩陣分別為

2 Petri網(wǎng)硬件設(shè)計(jì)

每個(gè)Petri 網(wǎng)具有不同的形狀和規(guī)模，如果采用Verilog HDL 針對每個(gè)Petri 網(wǎng)進(jìn)行編程，將會面臨龐大的代碼工作量，本文運(yùn)用基本Petri網(wǎng)理論和關(guān)聯(lián)矩陣?yán)碚搧碓O(shè)計(jì)一個(gè)自動(dòng)代碼生成器。

具體程序流程如圖2 所示。

用戶輸入關(guān)聯(lián)矩陣的長度和寬度（即Petri網(wǎng)的規(guī)模），根據(jù)輸入的信息，程序讀取關(guān)聯(lián)矩陣，若成功讀取，用戶界面將會輸出該P(yáng)etri 網(wǎng)的基本信息，之后程序繼續(xù)讀取延時(shí)矩陣信息生成延時(shí)文件。若延時(shí)信息成功讀取，用戶可繼續(xù)輸入Petri網(wǎng)的初始標(biāo)識和庫所容量。程序根據(jù)以上讀取的信息，分別生成控制器文件、存儲器文件、頂層文件和測試文件的Verilog代碼。

圖2 程序流程圖

2.1 從關(guān)聯(lián)矩陣到Verilog HDL 編譯程序的自動(dòng)生成

將2 個(gè)關(guān)聯(lián)矩陣分別寫入2 個(gè)文本文件中，利用C語言讀取文件內(nèi)的矩陣信息，存入2 個(gè)二維數(shù)組，輸入容量函數(shù)和初始標(biāo)識并將其存入2 個(gè)一維數(shù)組。再用C語言解析以上信息，根據(jù)Verilog HDL 的語法和Petri網(wǎng)硬件建模的方法，建立Verilog 文件并打印Verilog代碼，自動(dòng)生成Petri網(wǎng)的硬件架構(gòu)。本設(shè)計(jì)不止局限于2 個(gè)8 ×10 的輸入、輸出矩陣，隨著庫所、變遷個(gè)數(shù)的增加，可根據(jù)不同的輸入、輸出矩陣生成數(shù)據(jù)寬度以及加載初始值的深度同時(shí)改變的Verilog文件。

2.2 基本Petri網(wǎng)庫所和變遷的實(shí)現(xiàn)

對于基本Petri網(wǎng)，其庫所內(nèi)的標(biāo)識數(shù)只有0 和1兩種狀態(tài)，且所有弧的權(quán)值為1。對于基本Petri網(wǎng)，只對庫所、變遷兩個(gè)行為可進(jìn)行如下描述。

圖3 是一個(gè)基本Petri網(wǎng)庫所模塊。庫所名為s1，有兩個(gè)前驅(qū)變遷t1和t2，一個(gè)后繼變遷t3。若前驅(qū)變遷t1和t2只發(fā)生1 個(gè)，庫所s1內(nèi)的托肯數(shù)加1；若前驅(qū)變遷t1和t2都發(fā)生，庫所s1內(nèi)的托肯數(shù)量加2；因庫所s1內(nèi)托肯數(shù)量大于0 而滿足變遷t3發(fā)生條件，t3發(fā)生，同時(shí)消耗掉s1內(nèi)的一個(gè)托肯。

圖3 Petri網(wǎng)的庫所實(shí)現(xiàn)

圖4 是一個(gè)基本Petri網(wǎng)變遷模塊。變遷名為t1，有3 個(gè)前驅(qū)庫所s1、s2和s3，兩個(gè)后繼庫所s4和s5。當(dāng)前驅(qū)庫所s1、s2和s3內(nèi)托肯數(shù)同時(shí)滿足條件即3 個(gè)庫所內(nèi)托肯數(shù)都不為0 時(shí)，變遷t1發(fā)生，同時(shí)消耗s1、s2和s3內(nèi)各1 個(gè)托肯；變遷t1發(fā)生后，s4和s5獲得1 個(gè)托肯。

圖4 Petri網(wǎng)的變遷實(shí)現(xiàn)

在Verilog語言中，可以將每個(gè)庫所和變遷作為單獨(dú)模塊連接起來。每個(gè)庫所模塊的輸入信號為所有前驅(qū)變遷模塊的信號和后繼變遷模塊的反饋信號，輸出信號為托肯個(gè)數(shù)；變遷模塊的輸入信號為所有前置庫所模塊的托肯個(gè)數(shù)，若變遷發(fā)生，則向后繼庫所模塊輸出1，若變遷不發(fā)生，輸出0。每當(dāng)庫所模塊接收到所有的前驅(qū)變遷模塊發(fā)生信號都為1 時(shí)，庫所模塊輸出的托肯數(shù)加1；每當(dāng)變遷模塊的所有前驅(qū)庫所模塊皆滿足變遷發(fā)生條件時(shí)，該變遷模塊發(fā)生，同時(shí)向前驅(qū)庫所模塊發(fā)送反饋信號，前驅(qū)庫所模塊根據(jù)反饋信號將托肯數(shù)減1。庫所的硬件結(jié)構(gòu)如圖5 所示。

圖5 庫所的硬件架構(gòu)

該模塊有一個(gè)前驅(qū)變遷，兩個(gè)后繼變遷。其中：load、p＿init、clk、p＿in、p＿T1、p＿T2均為輸入信號；out 和conflict為輸出信號；clk 為時(shí)鐘信號；load 為加載信號。當(dāng)load 為1 時(shí)，該庫所模塊的托肯數(shù)等于賦初值輸入信號p＿init 的值。若load 信號為0，則當(dāng)前庫所托肯數(shù)根據(jù)p＿in、p＿T1和p＿T2進(jìn)行修改，p＿in 是前驅(qū)變遷的輸入值，p＿T1和p＿T2分別為2 個(gè)后繼變遷的資源請求值，修改內(nèi)容是：當(dāng)前值加上來自前驅(qū)變遷的輸入值p＿in，減去2 個(gè)來自后繼變遷的輸入值p＿T1和p＿T2。在修改前，先判斷庫所內(nèi)部資源是否足夠進(jìn)行修改操作，若不足則不修改。模塊內(nèi)還有一個(gè)比較器，將2 個(gè)資源請求值p＿T1、p＿T2的和與當(dāng)前庫所值和p＿in的和比較，若資源請求過大，即該庫所模塊的資源不足以滿足2 個(gè)后繼變遷的需求而產(chǎn)生沖突，沖突信號conflict向控制器模塊輸出1，令控制器模塊來解決沖突。

變遷的硬件結(jié)構(gòu)如圖6 所示，該模塊有2 個(gè)前驅(qū)庫所，1 個(gè)后繼庫所。其中t＿inp1、t＿inp2、t＿enp1、t＿enp2均為輸入信號，t和T為輸出信號。2 個(gè)前驅(qū)庫所模塊傳遞過來的輸入信號t＿inp1 和t＿inp2 經(jīng)過一個(gè)與門，產(chǎn)生t信號，t 信號表示變遷是否有發(fā)生的條件。還需要2 個(gè)來自庫所控制器的使能信號與t信號通過與操作，最終產(chǎn)生真正表示變遷的發(fā)生信號T。

圖6 變遷的硬件架構(gòu)

2.3 存在沖突的P／T系統(tǒng)

存在沖突的P／T系統(tǒng)相較于基本的Petri網(wǎng)，需要判斷可能產(chǎn)生沖突的位置、時(shí)間以及沖突產(chǎn)生后資源分配等問題。本文引入了控制器（controller），每個(gè)可能發(fā)生沖突的庫所模塊都配備一個(gè)控制器模塊，且在變遷模塊中引進(jìn)了一個(gè)變遷使能信號，變遷模塊滿足發(fā)生的條件便可使能，庫所模塊根據(jù)變遷模塊的使能信號判斷是否會發(fā)生沖突，若存在沖突，資源的分配問題交由控制器來處理，獲得資源的變遷模塊才能獲得發(fā)生權(quán)。

控制器模塊負(fù)責(zé)存在沖突的變遷資源分配，即變遷發(fā)生權(quán)選擇模塊。本文將控制器分為兩種，輪換型和隨機(jī)分配型，用戶可根據(jù)處理沖突的機(jī)制進(jìn)行選擇。兩種控制器通過不同的方法解決存在沖突的變遷資源分配問題。根據(jù)上述改進(jìn)后的庫所模塊所給出的沖突發(fā)生信號，若信號為1，則啟用資源分配機(jī)制，選出可以發(fā)生的變遷，并將該變遷的控制信號置1，其他變遷控制信號置0；若信號沖突發(fā)生為0，則該控制器控制的所有的變遷控制信號均置1。

輪換分配控制器定義一個(gè)種子，復(fù)位時(shí)種子的值為0，每發(fā)生一次沖突種子的值加1，當(dāng)種子的值超過n－1 時(shí)（假設(shè)該控制器控制n個(gè)變遷）種子的值置0，以此循環(huán)。當(dāng)種子的值為i－1 時(shí)，則該控制器控制的第i 個(gè)變遷的控制信號為1，其他變遷的控制信號為0。

隨機(jī)分配控制器采用線性反饋移位寄存器（linear feedback shift register，LFSR）偽隨機(jī)數(shù)發(fā)生器，偽隨機(jī)數(shù)等概率產(chǎn)生，可能產(chǎn)生的偽隨機(jī)數(shù)平均的映射到該控制器控制的每一個(gè)變遷。若沖突發(fā)生，偽隨機(jī)數(shù)發(fā)生器產(chǎn)生一個(gè)偽隨機(jī)數(shù)，映射到對應(yīng)的變遷獲得發(fā)生權(quán)。

2.4 控制器模塊的實(shí)現(xiàn)

該控制器區(qū)別于2.3 節(jié)中用于處理沖突的控制器，是輸出控制信號控制整個(gè)Petri網(wǎng)的運(yùn)行狀態(tài)的模塊。此模塊通過檢測按鍵的上升沿來選擇Petri 網(wǎng)的運(yùn)行模式，各模式及其功能見表1。

表1 Petri網(wǎng)模式和功能

狀態(tài)轉(zhuǎn)換圖如圖7 所示。IDLE為空閑狀態(tài)，是系統(tǒng)啟動(dòng)時(shí)的初始狀態(tài)；CONFIG＿P 狀態(tài)下可以接收外部庫所初始值數(shù)據(jù)的輸入；LOAD＿OUT狀態(tài)下各庫所加載上階段接收到的值；START為系統(tǒng)進(jìn)入調(diào)試的準(zhǔn)備階段，此時(shí)可通過鍵值選擇4 種調(diào)試模式；調(diào)試結(jié)束后進(jìn)入STOP狀態(tài)。

圖7 有限自動(dòng)狀態(tài)機(jī)

2.5 存儲器模塊的硬件實(shí)現(xiàn)

為準(zhǔn)確地加載的庫所初始值以及將得到的P／T結(jié)果值回傳，需要存儲器模塊提供緩沖的空間，存儲結(jié)構(gòu)如圖8 所示。

圖8 RAM存儲結(jié)構(gòu)

加載初始值在使能信號有效時(shí)，根據(jù)讀寫地址將128 bit的value值加載給庫所，初始值的bit數(shù)可根據(jù)庫所的個(gè)數(shù)改變。以10 個(gè)庫所、8 個(gè)變遷為例，從最上層開始依次往下保存p1、p2～p10 的初始值，多余部分則忽略。在Petri網(wǎng)運(yùn)行過程中，s10～s1內(nèi)儲存實(shí)時(shí)采集到的庫所內(nèi)托肯數(shù)，t8～t1儲存實(shí)時(shí)采集到的變遷狀態(tài)?！癱ount”內(nèi)保存實(shí)時(shí)運(yùn)行步數(shù)。

3 基于FPGA的Petri網(wǎng)測試系統(tǒng)

在Modelsim仿真平臺測試的基礎(chǔ)上，本文采用QuartusⅡ15.0 進(jìn)行綜合測試。采用Altera Stratix V（5SGXEA7N2F45C2）器件綜合，并下載到開發(fā)板中進(jìn)一步測試。其工作頻率為300 MHz，ALMs 資源量為477，Registers資源量為1 034。

3.1 測試方案

在Quartus編譯、綜合并下載到開發(fā)板后，通過檢測按鍵上升沿，將指令信號寫入寄存器中。button［0］對應(yīng)復(fù)位鍵，可使Petri網(wǎng)進(jìn)入初始狀態(tài)。button［1］控制狀態(tài)機(jī)轉(zhuǎn)換到加載庫所初始值的狀態(tài)。數(shù)據(jù)加載后用button［2］將狀態(tài)機(jī)轉(zhuǎn)換到START 狀態(tài)，啟動(dòng)Petri網(wǎng)的調(diào)試模式。

3.2 測試結(jié)果

此處以Continue模式為例，按下button［5］切換到該模式下，如圖9 所示，在Quartus軟件的SignalTap II Logic Analyzer中可看見，在時(shí)刻4，各庫所第一次被初始化（加載入初始托肯數(shù)值），P1 內(nèi)部托肯數(shù)為4，P2為2，P3 為5，P4 為1，P5 為1，P8 為2，P9 為2。同時(shí)庫所的初始化使得變遷發(fā)生，由圖中可見，變遷T3 和T4 發(fā)生。變遷發(fā)生后，在時(shí)刻9，可以看到P4 和P5 內(nèi)托肯被消耗，P6 和P7 內(nèi)托肯個(gè)數(shù)加1，P10 因有2 個(gè)前驅(qū)變遷而托肯個(gè)數(shù)加2，此時(shí)變遷T1 和T2 因滿足條件而發(fā)生。Petri 網(wǎng)保持運(yùn)行，直到狀態(tài)機(jī)轉(zhuǎn)換到STOP狀態(tài)下才停止運(yùn)行。

圖9 CONTINUE模式下運(yùn)行的Petri網(wǎng)

4 結(jié)語

本文對Petri網(wǎng)的硬件模擬進(jìn)行了研究，設(shè)計(jì)了基于FPGA的Petri網(wǎng)硬件仿真器，采用C語言實(shí)現(xiàn)代碼自動(dòng)生成器。該生成器根據(jù)輸入的關(guān)聯(lián)矩陣，以庫所和變遷作為基本模塊，同時(shí)引入controller 模塊解決沖突問題，最終生成整個(gè)Petri 網(wǎng)的硬件架構(gòu)，并編譯下載到FPGA 中。該仿真器可運(yùn)行150 M／s 步仿真，實(shí)現(xiàn)了較快的仿真速度。