基于信號解釋Petri網(wǎng)的可重構調度模型分析研究

欒 嵐，胡 丹

(1.貴州商學院計算機與信息工程學院，貴州 貴陽 550061；2.貴州大學大數(shù)據(jù)與信息工程學院，貴州 貴陽 550025)

1 引言

在制造系統(tǒng)、服務系統(tǒng)、數(shù)據(jù)處理系統(tǒng)中，常常需要完成復雜的任務調度功能，由于對系統(tǒng)性能要求的不斷提升，使得可重構系統(tǒng)和邏輯控制成為系統(tǒng)優(yōu)化的研究重點?？芍貥嬆Ｐ湍軌蛱岣呦到y(tǒng)的靈活性，根據(jù)任務需求及時變更調度方案[1-2]，邏輯控制負責重構任務的執(zhí)行。在復雜系統(tǒng)中，任務通常呈現(xiàn)出并發(fā)、互斥，以及非同步性，Petri網(wǎng)擅長對這類系統(tǒng)進行描述[3-5]，所以一些研究人員將Petri網(wǎng)應用于可重構系統(tǒng)中。文獻[6]針對參數(shù)的不確定性，根據(jù)模糊理論設計了隨機Petri網(wǎng)；文獻[7]針對3D NoC測試任務的并行處理，設計了賦時Petri網(wǎng)；文獻[8]為避免機器人信息沖突，通過Petri網(wǎng)構造功能子模塊。除了Petri網(wǎng)在復雜系統(tǒng)重構調度方面的應用，還經常用到FPGA，它可以完成對軟硬件的計算處理，因此，很適合用于系統(tǒng)的重構調度[9]。于是，本文引入Petri網(wǎng)描述復雜系統(tǒng)，并在此基礎上設計了重構調度算法，用以應對任務時間的模糊性，并最終完成信號解釋Petri網(wǎng)與FPGA邏輯芯片的功能部署。

2 擴展Petri網(wǎng)分析

對于具有并發(fā)、互斥，以及非同步任務的系統(tǒng)，為了能夠實現(xiàn)準確合理的重構調度模型，通常采用Petri網(wǎng)進行分析。由于普通Petri網(wǎng)不善于操作數(shù)據(jù)，因此，本文設計了一種擴展Petri網(wǎng)，用于優(yōu)化其對數(shù)據(jù)的操作。

基于Petri網(wǎng)，考慮到其重構系統(tǒng)時的影響因素，這里定義包含七個變量的集合

PG=(C，T，D，Q，S，W，F(xiàn))，C∩T∩D∩Q=?

(1)

其中，集合C為使用Petri網(wǎng)建立目標系統(tǒng)時所需的配置庫；T為目標模型建立時C對應的變遷；D為持久化設備，用以保存中間數(shù)據(jù)；Q為對數(shù)據(jù)的操作；S為操作的約束條件；W為權重；F為模型分析時配置和數(shù)據(jù)的消耗情況。PG數(shù)據(jù)實際上用以表示Petri網(wǎng)重構調度模型中配置和數(shù)據(jù)的變遷過程，以及對應的約束條件。對配置和數(shù)據(jù)的雙重約束可以表示為

(2)

為了模擬動態(tài)系統(tǒng)的變化，針對Petri網(wǎng)依次分析關于配置與數(shù)據(jù)的變遷關系。當滿足條件?x∈C∪T∪Q時，變遷前后的配置可以表示為

(3)

其中，x0表示變遷之前的配置；x1表示變遷之后對應的配置。當滿足條件?x∈Q∪D時，變遷前后的數(shù)據(jù)可以表示為

(4)

其中，x0和x1分別代表變遷前后所對應的數(shù)據(jù)。假定在變遷過程中，當發(fā)現(xiàn)變遷之前的配置或者數(shù)據(jù)標志大于等于其權重時，應當對權重集合W進行調整，同時對消耗標志集合F采取更新。F對應的配置變遷更新方式如下

(5)

其中，t∈T，且?u∈t0。F對應的數(shù)據(jù)變遷更新方式如下

(6)

其中，q∈Q，且?u∈q0。為了確保變遷規(guī)

則的合理，將變遷集合優(yōu)化如下

(7)

3 重構調度算法設計

由于重構調度算法最終要在邏輯芯片上實現(xiàn)[10]，所以在對系統(tǒng)進行重構調度建模分析時，充分考慮調度與時間片的分配。這里，根據(jù)任務執(zhí)行對時間的要求，分成固定時間調度、周期調度，以及觸發(fā)調度三種模式，并依次進行模型的分析優(yōu)化。

當某任務為固定時間調度時，代表每次主函數(shù)循環(huán)代碼都要執(zhí)行該任務，如果該類任務數(shù)量為N，則可以求解出該類任務執(zhí)行時累計消耗的配置和數(shù)據(jù)資源，以及持久化資源，求解方式為

(8)

其中，F(xiàn)CA包含配置和數(shù)據(jù)兩部分，又表示計算資源；FST表示持久化資源。把調度所需的資源情況和邏輯器件的剩余資源進行比較。在這里，即把FCA、FST和PG中的F做比較，再根據(jù)比較結果，對調度方案采取相應調節(jié)。任意時間片[t1，t2]中，當判斷得到FCA≤FC，表明所需資源充足，此時間片中能夠完成全部任務的執(zhí)行。當判斷得到FCA≤FC，表明所需資源不足，此時需要將全部任務采取資源排序，并節(jié)選一部分執(zhí)行。設Sa和Sb分別代表完整序列和節(jié)選序列，求解Sb內所有任務的資源消耗，當其結果不超過給定資源，且最為接近時，將對應的Sb確定為最優(yōu)調度，公式描述為

(9)

式中，求得最小diff的Sb即代表此時間片的調度方案。而Sa中剩余的任務則在下一時間片中執(zhí)行。

當固定時間的任務重構調度的過程中，任務差異使得對邏輯芯片資源消耗產生影響。為盡可能保持最優(yōu)性能，可以在其中觸發(fā)非周期性的調度方案。將具有非周期特征的任務表示成集合{AT1，AT2，…，ATK}，調度執(zhí)行時，其加載至邏輯芯片所需的最大時間是Tmax，所需的計算資源表示如下

(10)

假定該時間片長度為τ，則此時的資源消耗情況描述為

(11)

為了滿足非周期任務的調度需要，應該保證分配的時間片符合條件τ>Tmax，同時保證它們的差值最小，通過時間片集合的求解可以得到如下關系

(12)

其中，λ代表常量因子，利用λ的調節(jié)，使得資源消耗率處于最優(yōu)狀態(tài)。UCK是某時間片集合TK對應的資源消耗率。對上述表達式，根據(jù)極大似然法求解出相應的時間片集合，從而得到最終的優(yōu)化調度方案。

有些任務需要周期性調度時，根據(jù)各自需求的得到周期集合{T1，T2，…，TM}，并求解出全部周期的最小公倍數(shù)，記做T0。在這M個任務執(zhí)行過程中，對應的執(zhí)行時間集可以表示成{Δti1，Δti2，…，Δtim1}，其中的mi代表i任務所需時間片數(shù)量。與非周期任務相似，同樣需要保證時間片大于T0，同時滿足最小差值，得到最優(yōu)時間片集合應該符合表達式(12)的關系，并采用相同的方法求解出最優(yōu)的調度方案。

4 基于FPGA的信號解釋Petri網(wǎng)設計

在采用FPGA作為一個系統(tǒng)重構調度的邏輯芯片時，信號解釋Petri網(wǎng)把FPGA和接口表示為庫所，并把FPGA和接口相互存在的操作表示為向邊，把FPGA的每次調度表示為一次變遷。于是，這里利用兩個FPGA來構造系統(tǒng)模型，并通過信號解釋Petri網(wǎng)完成調度分析。令兩個FPGA型號與性能一致，且在運行過程中需要進行靜態(tài)與動態(tài)重構，由此來保證對系統(tǒng)任務的準確合理調節(jié)。根據(jù)所有的資源即為庫所，所有的操作即為變遷的規(guī)則，資源與操作的聯(lián)系即為信號解釋，于是，可重構調度模型描述如表1和表2所示。

表1 Petri網(wǎng)庫所描述

表2 Petri網(wǎng)變遷描述

靜態(tài)重構應該在FPGA未對計算任務采取調度時完成。在該過程中，OMC把相關的配置參數(shù)傳輸至FPGA1，F(xiàn)PGA1再傳輸至FPGA2，F(xiàn)PGA1與FPGA2根據(jù)配置參數(shù)分別完成相應配置工作。隨后啟動信號解釋，在獲取到信號后，F(xiàn)PGA開始計算任務，當系統(tǒng)出現(xiàn)擾動時，F(xiàn)PGA根據(jù)具體情況采取動態(tài)重構。與靜態(tài)重構一樣，依然利用OMC把配置參數(shù)傳輸至FPGA，F(xiàn)PGA通過計算后得到當前任務的最佳調度，并把調度方案向后傳輸至RPC。圖1描述了信號解釋Petri網(wǎng)的可重構調度模型構造的完整過程。

圖1 Petri網(wǎng)可重構調度模型構造過程

5 仿真分析

針對信號解釋Petri網(wǎng)的可重構調度模型，設計相應的仿真場景，考慮到數(shù)據(jù)采集系統(tǒng)需要對繁雜的多源異構信號進行處理，且缺少有效的調度模型分析方法，于是，基于數(shù)據(jù)采集系統(tǒng)進行仿真分析。數(shù)據(jù)庫采用MySq1，通過爬蟲從網(wǎng)絡中獲取109324組與FPGA相關的數(shù)據(jù)，采集系統(tǒng)的任務是從爬取的數(shù)據(jù)中清洗出FPGA與Petri網(wǎng)相關的數(shù)據(jù)。

由于在對Petri網(wǎng)變遷描述時，表1中v1～v7分別代表了變遷t1～t7的執(zhí)行速度，v1～v7的有效區(qū)間是[0.1，6.5]Gb/s。為了驗證本文設計的信號解釋Petri網(wǎng)的重構和計算時間特性，本文設計了三種速度場景，如下

1)v1=v2=v3=v4=v6=v7=1.0Gb/s，v5=2Gb/s；

2)v1=v2=v3=v4=v6=v7=3.2Gb/s，v5=2Gb/s；

3)v1=v2=v3=v4=v6=v7=6.5Gb/s，v5=2Gb/s。

三種場景的速度依次增加，基于以上場景，設置默認規(guī)則數(shù)為40，分別得到各場景下數(shù)據(jù)采集系統(tǒng)的重構與計算時間。其中重構時間包括動靜態(tài)兩部分數(shù)據(jù)，由于各場景下計算任務所需的發(fā)送和處理時間很短，這里忽略不計。最終得到重構與計算時間的仿真結果如圖2所示。

圖2 重構和計算時間特性

從圖2結果分析可知，隨著場景1到場景3的執(zhí)行速度增加，無論是重構時間，還是計算任務的累計時間，均出現(xiàn)了大幅度的下降。在場景1中，三個時間依次是7.24s、9.83s、19.47s；在場景2中，三個時間依次是2.97s、3.13s、6.24s；在場景3中，三個時間依次是0.91s、0.91s、1.84s。其中，在場景1下，由于動態(tài)重構耗時較為嚴重，且中間的延遲時間較多，導致計算任務的累計時間超過重構時間約2.4s。而在執(zhí)行速度上升時，計算任務的累計時間與重構時間越來越接近，在場景3下，它們的時間差已經縮小至0.02s。由此可見，任務調度的時間主要受動態(tài)重構的影響。也就是說在可重構調度模型中，對系統(tǒng)任務調度的計算響應是影響完成時間的主要因素。

為了充分驗證本文方法的有效性，通過改變規(guī)則數(shù)量，分別得到任務重構準確率的變化趨勢，以及任務完成時間的變化趨勢，同時提取文獻[6]和文獻[7]中的方法進行實驗對比。結果如圖3和圖4所示。

圖3 重構準確率結果曲線

圖4 任務完成時間結果曲線

根據(jù)準確率結果曲線分析可知，系統(tǒng)規(guī)則的增多會導致任務重構的準確性降低，影響任務執(zhí)行的準確性。當規(guī)則數(shù)量較少時，三種方法的重構準確性基本相似，但規(guī)則增多的過程中，本文方法的重構準確性明顯優(yōu)于文獻方法，保持比較平穩(wěn)的速度下降。這是由于本文方法在對系統(tǒng)進行重構調度建模時，充分考慮了重構與時間片的分配，將任務分成固定時間調度、周期調度，以及觸發(fā)調度三種模式，并針對每種模式進行了資源與時間的優(yōu)化。

根據(jù)任務完成的時間結果分析可知，系統(tǒng)規(guī)則的增多會導致任務完成時間的增加。當規(guī)則較少時，各方法的任務完成時間相差不大，表明重構調度性能相似。但是隨著規(guī)則的增多，本文方法的時間增速明顯小于文獻方法，表明具有更好的重構與調度速度。

6 結束語

由于可重構系統(tǒng)的不斷發(fā)展，邏輯控制性能也被寄予更高的期望，為了實現(xiàn)更好的優(yōu)化效果，本文提出并設計基于信號解釋Petri網(wǎng)可重構調度模型。首先針對可重構系統(tǒng)存在的并發(fā)、互斥，以及非同步特點，進行了Petri網(wǎng)擴展；然后根據(jù)任務執(zhí)行對時間的要求，設計了重構調度算法；最后基于FPGA實現(xiàn)了信號解釋Petri網(wǎng)的可重構調度模型。實驗結果表明，本文方法對于復雜的系統(tǒng)任務具有良好的靜態(tài)和動態(tài)重構性能，顯著提高了重構的準確率，以及任務執(zhí)行速度。