周韜略，張小軍，陳成官，曾慶田，張德學

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

0 引言

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

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

1 基本理論

1.1 Petri網(wǎng)理論

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

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

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

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

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

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

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

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

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

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

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

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

圖2 程序流程圖

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

圖7 有限自動狀態(tài)機

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

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

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

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

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

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

3.1 測試方案

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

3.2 測試結(jié)果

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

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

4 結(jié)語

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