欒 嵐，胡 丹

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

1 引言

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

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

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

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

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

(1)

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

(2)

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

(3)

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

(4)

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

(5)

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

(6)

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

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

(7)

3 重構(gòu)調(diào)度算法設(shè)計(jì)

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

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

(8)

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

(9)

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

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

(10)

假定該時(shí)間片長(zhǎng)度為τ，則此時(shí)的資源消耗情況描述為

(11)

為了滿足非周期任務(wù)的調(diào)度需要，應(yīng)該保證分配的時(shí)間片符合條件τ>Tmax，同時(shí)保證它們的差值最小，通過(guò)時(shí)間片集合的求解可以得到如下關(guān)系

(12)

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

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

4 基于FPGA的信號(hào)解釋Petri網(wǎng)設(shè)計(jì)

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

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

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

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

圖1 Petri網(wǎng)可重構(gòu)調(diào)度模型構(gòu)造過(guò)程

5 仿真分析

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

由于在對(duì)Petri網(wǎng)變遷描述時(shí)，表1中v1～v7分別代表了變遷t1～t7的執(zhí)行速度，v1～v7的有效區(qū)間是[0.1，6.5]Gb/s。為了驗(yàn)證本文設(shè)計(jì)的信號(hào)解釋Petri網(wǎng)的重構(gòu)和計(jì)算時(shí)間特性，本文設(shè)計(jì)了三種速度場(chǎ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。

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

圖2 重構(gòu)和計(jì)算時(shí)間特性

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

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

圖3 重構(gòu)準(zhǔn)確率結(jié)果曲線

圖4 任務(wù)完成時(shí)間結(jié)果曲線

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

根據(jù)任務(wù)完成的時(shí)間結(jié)果分析可知，系統(tǒng)規(guī)則的增多會(huì)導(dǎo)致任務(wù)完成時(shí)間的增加。當(dāng)規(guī)則較少時(shí)，各方法的任務(wù)完成時(shí)間相差不大，表明重構(gòu)調(diào)度性能相似。但是隨著規(guī)則的增多，本文方法的時(shí)間增速明顯小于文獻(xiàn)方法，表明具有更好的重構(gòu)與調(diào)度速度。

6 結(jié)束語(yǔ)

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