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

欒 嵐，胡 丹

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

1 引言

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

2 擴展Petri網分析

對于具有并發、互斥，以及非同步任務的系統，為了能夠實現準確合理的重構調度模型，通常采用Petri網進行分析。由于普通Petri網不善于操作數據，因此，本文設計了一種擴展Petri網，用于優化其對數據的操作。

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

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

(1)

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

(2)

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

(3)

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

(4)

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

(5)

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

(6)

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

則的合理，將變遷集合優化如下

(7)

3 重構調度算法設計

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

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

(8)

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

(9)

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

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

(10)

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

(11)

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

(12)

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

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

4 基于FPGA的信號解釋Petri網設計

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

表1 Petri網庫所描述

表2 Petri網變遷描述

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

圖1 Petri網可重構調度模型構造過程

5 仿真分析

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

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

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。

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

圖2 重構和計算時間特性

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

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

圖3 重構準確率結果曲線

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

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

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

6 結束語

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