基于FPGA的Petri網(wǎng)的硬件實(shí)現(xiàn)

1、引言

Petri網(wǎng)是一種系統(tǒng)的、數(shù)學(xué)的和圖形的描述和分析工具，它具有強(qiáng)大的描述并發(fā)、異步、分布、并行、不確定/隨機(jī)性的信息處理系統(tǒng)的能力，目前已被廣泛應(yīng)用于計(jì)算機(jī)通訊系統(tǒng)、實(shí)時(shí)多媒體系統(tǒng)及離散事件系統(tǒng)的研究中。而Petri網(wǎng)的硬件實(shí)現(xiàn)將為并行控制器的設(shè)計(jì)提供一條有效的途徑。因此，其硬件實(shí)現(xiàn)成為許多專家、學(xué)者研究的熱點(diǎn)。

現(xiàn)場(chǎng)可編程門陣列FPGA是美國(guó)Minx公司于1984年首先開(kāi)發(fā)的一種通用型用戶可編程邏輯器件。它具有容量大、速度高、價(jià)格低的優(yōu)點(diǎn)，同時(shí)，硬件描述語(yǔ)言VHDL具有的強(qiáng)大的行為描述能力及與硬件行為無(wú)關(guān)的特性，實(shí)現(xiàn)了硬件電路設(shè)計(jì)的軟件化，這為Petri網(wǎng)的硬件實(shí)現(xiàn)提供了有力的工具。

本文探討了Petri網(wǎng)基于VHDL語(yǔ)言的FPGA實(shí)現(xiàn)。

2、Petri網(wǎng)基本類型的實(shí)現(xiàn)

2.1基本Petri網(wǎng)的實(shí)現(xiàn)

2.1.1基本Petri網(wǎng)簡(jiǎn)介

定義1 六元組Z=(P,T,F,K,W,M0)稱為一個(gè)網(wǎng)系統(tǒng)，其中N=(P,T,F)是一個(gè)有向網(wǎng)，滿足:

1)P∪T≠φ

2)P∪T=φ

3)F∈PxT∪TxP，只能從P->7或T->P，不準(zhǔn)P->P或T->T.

4)Dom(F)∪cod(F)=P∪T

K，W，M0依次是N上的容量函數(shù)，權(quán)函數(shù)和標(biāo)識(shí)，M0稱為∑的初始標(biāo)識(shí)。基本Petri網(wǎng)就是K=1,W=1,這時(shí)庫(kù)所內(nèi)的標(biāo)識(shí)數(shù)要么是0，要么是1，而且所有的弧權(quán)都是1。對(duì)于基本的Petri網(wǎng)，變遷的激發(fā)就是一個(gè)瞬時(shí)事件。

2.1.2基本Petri網(wǎng)的元件實(shí)現(xiàn)

圖1(a)是一個(gè)簡(jiǎn)單的基本Petri網(wǎng)系統(tǒng)，庫(kù)所P具有兩個(gè)輸入變遷和兩個(gè)輸出變遷，當(dāng)庫(kù)所P中沒(méi)有托肯且?guī)焖鵓O或P1中有托肯時(shí)，變遷t0或11激發(fā)，則托肯從庫(kù)所PO或P1移動(dòng)到庫(kù)所P;當(dāng)P中有托肯且?guī)焖鵓2或P3中沒(méi)有托肯時(shí)，變遷t2或0激發(fā)，則托肯從庫(kù)所P移動(dòng)到庫(kù)所P2或P3。

實(shí)現(xiàn)庫(kù)所P的模塊如圖1(b)，元件幾M有兩個(gè)輸入變遷inl,in2和兩個(gè)輸出變遷。outl,out2，當(dāng)變遷使能時(shí)，其值為邏輯1，否則為邏輯0;reset為復(fù)位信號(hào)，用來(lái)置庫(kù)所的初始狀態(tài)。clk為全局時(shí)鐘。P的值表示庫(kù)所中是否含義托肯，若含有托肯，取值為邏輯1，否則為邏輯。。元件PM是在EDA軟件Max+PlusII中采用VHDL語(yǔ)言描述，經(jīng)過(guò)編譯、仿真后形成模塊。

用VHDL語(yǔ)言描述源程序如下:

entity p_mis

port(reset,clk:instdlogic;

inl,in2,outl,out2:instdlogic;

p:outstdlogic);

end p_m;

architecture beh ofp_m is()P

signal p0,np0:stdlogic;

begin

np0<-not p0;

process(clk,reset)

variablefstdlogic;

begin

f:=((inlorin2)and

ifclk'eventandclk='1

ifreset='1'then

p0<='1';

elsiff='1'then

(a).(b)

np0)or((outlorout2)andp0);

.then

PO<=npO;

endif;

endif;

endprocess;p<=p0;

end beh;

圖2(a)是一個(gè)簡(jiǎn)單的基本Petri網(wǎng)系統(tǒng)，其激發(fā)規(guī)則是當(dāng)庫(kù)所PO和P1中有托肯，變遷T具有兩個(gè)輸入庫(kù)所PO和P1，P3，而庫(kù)所P2和P3中沒(méi)有托肯，且事件x兩個(gè)輸出庫(kù)所P2和發(fā)生時(shí)，變遷激發(fā)。圖2(b)是建立的變遷元件T_M,inl,in2,outl,out2分別表示輸入庫(kù)所和輸出庫(kù)所中含有托肯的狀態(tài)，若含有托肯，則取值為邏輯1，否則為邏輯0,x是外部事件。T表示變遷的激發(fā)狀態(tài)，若可激發(fā)則取值為邏輯1。

用VHDL語(yǔ)言描述源程序如下:

entityt_mis

port(inl,in2,outl,out2,x:in std_logic;

t:out stdlogic);，

end t_m;

architecture beh of t_m is

signal t0:stdlogic;

begin

t<-x and in land in2 and (notoutl) and (notout2)end beh;

庫(kù)所元件P_M和變遷元件T_M均存放在Max+Plusll中建立的元件庫(kù)中，可以調(diào)用使用的。

2.2時(shí)EEPetriR的實(shí)IT

2.2.1時(shí)延Petri網(wǎng)的定義

定義2變遷時(shí)化Petri網(wǎng)(timed petri net)TN={P,T,F,I']，其中I':T->0∪R+，規(guī)定TPetri網(wǎng)中的每一個(gè)變遷的持續(xù)時(shí)間。{T,P,F}的定義與PN一致。

在變遷時(shí)化Petri網(wǎng)中，每個(gè)變遷均有一為零或任一正實(shí)數(shù)的持續(xù)時(shí)間。而庫(kù)所中沒(méi)有持續(xù)時(shí)間，只要和它相連的變遷發(fā)生，庫(kù)所就可失去或獲得托肯。當(dāng)變遷的輸入庫(kù)所中含有托肯時(shí)，變遷是可激發(fā)的，但要真正激發(fā)需要經(jīng)過(guò)一段持續(xù)時(shí)間。

2.2.2變遷時(shí)化Petri網(wǎng)元件的實(shí)現(xiàn)

變遷時(shí)化Petri網(wǎng)中庫(kù)所元件與基本Petri網(wǎng)一致。

變遷時(shí)化Petri網(wǎng)中變遷元件的實(shí)現(xiàn)是在基本Petri網(wǎng)中變遷元件的基礎(chǔ)上設(shè)計(jì)了一個(gè)計(jì)時(shí)器TIME,如圖3(b),clk為計(jì)時(shí)頻率，決定了計(jì)時(shí)的精度;en為其使能端，當(dāng)變遷可激發(fā)時(shí)，en為1，計(jì)時(shí)器開(kāi)始計(jì)時(shí)，計(jì)時(shí)結(jié)束時(shí)co輸出為t。圖3(a)是一個(gè)簡(jiǎn)單的變遷時(shí)化Petri網(wǎng)，變遷T與時(shí)延D=n相連，當(dāng)庫(kù)所PO和P1中各有一個(gè)托肯時(shí)，變遷T獲得發(fā)生權(quán)，但到T發(fā)生，需有n個(gè)單位的延時(shí).調(diào)用元件幾M和計(jì)時(shí)元件TIME，建立邏輯電路如圖3(c)示，并經(jīng)過(guò)編譯形成圖3(d)所示邏輯模塊時(shí)化變遷元件。

用VHDL語(yǔ)言實(shí)現(xiàn)計(jì)時(shí)器模塊源程序如下

if clk'event and clk='1'then

if en='l'then

if q=nthenq<=0;co<='1';

elseq<=q+lco<='0':

end if;

else q<=0;co<='0'

end if;

end process;

endbeh;

3、應(yīng)用舉例

兩臺(tái)計(jì)算機(jī)使用一個(gè)公共存儲(chǔ)器，(a)不需要該存儲(chǔ)器，(b)需要存儲(chǔ)器但還沒(méi)有使用它;(c)正在使用存儲(chǔ)器。

則對(duì)其建立Petri網(wǎng)模型如圖5示。各庫(kù)所和變遷的含義解釋為:P1,P4分別表示CPI,CP2發(fā)出需要該存儲(chǔ)器請(qǐng)求;P2,P5分別表示CPI,CP2占用該存儲(chǔ);P3,P6分別表示CPI,CP2不需要該存儲(chǔ)器;P7表示存儲(chǔ)器;變遷中與時(shí)間相關(guān)的是T2.T5,分別表示cp占用存儲(chǔ)器的時(shí)間。這是一個(gè)時(shí)延Petri網(wǎng)系統(tǒng)。分別調(diào)用元件庫(kù)中所形成的庫(kù)所元件、變遷元件和時(shí)延變遷元件，作出該系統(tǒng)的邏輯電路圖，并在EDA軟件Max+PlusI中對(duì)其編譯、仿真下載，仿真波形如圖示。

4、結(jié)論

Petri網(wǎng)是異步并發(fā)現(xiàn)象建模的重要工具，Petri網(wǎng)的硬件實(shí)現(xiàn)將為并行控制器的設(shè)計(jì)提供一種有效的途徑.這使Petri網(wǎng)的硬件實(shí)現(xiàn)顯得尤為重要。本文給出了基本Petri網(wǎng)系統(tǒng)的硬件實(shí)現(xiàn)方案，采用VHDL語(yǔ)言分模塊實(shí)現(xiàn)，描述元件的功能并將元件存入WORK庫(kù)中，使設(shè)計(jì)具有很強(qiáng)的可讀性、可重復(fù)性、及可修改性，大大提高了系統(tǒng)的開(kāi)發(fā)效率。