面向多任務(wù)調(diào)度的可重構(gòu)算法設(shè)計(jì)*

黃慶華

（柳州職業(yè)技術(shù)學(xué)院電子信息工程系，廣西　柳州　545006）

面向多任務(wù)調(diào)度的可重構(gòu)算法設(shè)計(jì)*

黃慶華

（柳州職業(yè)技術(shù)學(xué)院電子信息工程系，廣西柳州545006）

針對(duì)在單個(gè)邏輯芯片上實(shí)現(xiàn)多任務(wù)的應(yīng)用場(chǎng)合，設(shè)計(jì)了面向多任務(wù)調(diào)度的可重構(gòu)算法，以此提高邏輯芯片的資源利用率和任務(wù)的響應(yīng)效率.詳細(xì)描述了面向多任務(wù)調(diào)度的重構(gòu)設(shè)計(jì)原理，并針對(duì)邏輯芯片中多任務(wù)的調(diào)度種類分別設(shè)計(jì)了邏輯芯片的重構(gòu)調(diào)度算法，最后選取了多個(gè)典型的任務(wù)進(jìn)行對(duì)比測(cè)試.測(cè)試結(jié)果表明，使用重構(gòu)算法之后的邏輯芯片在資源占有率和任務(wù)響應(yīng)延遲上均優(yōu)于傳統(tǒng)的邏輯芯片設(shè)計(jì)方法.

重構(gòu)；任務(wù)調(diào)度；邏輯芯片；利用率；加載

0　引言

隨著邏輯芯片的硬件設(shè)計(jì)技術(shù)和生產(chǎn)工藝的提高，在單個(gè)邏輯芯片上所能夠提供的計(jì)算資源和存儲(chǔ)資源越來越豐富，從而促使人們?cè)趩蝹€(gè)邏輯芯片上開發(fā)和設(shè)計(jì)多任務(wù)的應(yīng)用功能.而且在單個(gè)邏輯芯片上開發(fā)多任務(wù)的應(yīng)用功能，也能夠使得單個(gè)邏輯芯片滿足多種不同應(yīng)用需求的場(chǎng)合[1－3].然而在單個(gè)邏輯芯片上設(shè)計(jì)多任務(wù)的應(yīng)用時(shí)，往往面臨邏輯芯片資源利用率不高，任務(wù)響應(yīng)延遲較長(zhǎng)等問題.為此國(guó)內(nèi)很多學(xué)者對(duì)這一問題紛紛開展了相關(guān)研究.比如：劉沙，周學(xué)功[4]等人對(duì)可重構(gòu)系統(tǒng)在線任務(wù)預(yù)約重調(diào)度問題進(jìn)行了研究，并提出了任務(wù)調(diào)度算法，提高了在線任務(wù)預(yù)約調(diào)度效率.周學(xué)功，梁樑[5]等人則研究了可重構(gòu)系統(tǒng)中的實(shí)時(shí)任務(wù)在線調(diào)度問題，并設(shè)計(jì)相應(yīng)的放置算法.李濤，楊愚魯[6]等人針對(duì)可重構(gòu)系統(tǒng)中的資源管理及硬件任務(wù)布局問題開展了研究，并提出實(shí)現(xiàn)算法.

為了更好地提高邏輯芯片在實(shí)現(xiàn)多任務(wù)應(yīng)用時(shí)的綜合效率，筆者設(shè)計(jì)了一種面向多任務(wù)調(diào)度的可重構(gòu)算法，該算法通過對(duì)多任務(wù)的調(diào)度模式進(jìn)行重新設(shè)計(jì)和優(yōu)化，使得在邏輯芯片上能夠同時(shí)實(shí)現(xiàn)多個(gè)應(yīng)用功能，從而實(shí)現(xiàn)提高邏輯芯片綜合利用效率的目的.

1　面向多任務(wù)調(diào)度的重構(gòu)原理

面向多任務(wù)調(diào)度的邏輯芯片重構(gòu)設(shè)計(jì)，目的是為了盡可能提高邏輯芯片的利用率.由于這類邏輯芯片在使用的時(shí)候，往往會(huì)將多個(gè)任務(wù)調(diào)度到該邏輯芯片上進(jìn)行實(shí)現(xiàn)，而每個(gè)任務(wù)所占用的資源，以及持續(xù)的時(shí)間各不相同.傳統(tǒng)的設(shè)計(jì)模式中往往是將邏輯芯片按照不同任務(wù)的調(diào)度順序，依次將不同任務(wù)在邏輯芯片上進(jìn)行實(shí)現(xiàn)[7－8]，實(shí)現(xiàn)過程的示意圖如圖1所示.圖1給出了5個(gè)待執(zhí)行的任務(wù)，這5個(gè)任務(wù)所占用的邏輯芯片資源，以及持續(xù)的時(shí)間都不相同，在傳統(tǒng)的設(shè)計(jì)模式中這5個(gè)任務(wù)都將分別進(jìn)行設(shè)計(jì)并加載至調(diào)度邏輯芯片中，最后完成特定的功能.

傳統(tǒng)的這種任務(wù)調(diào)度模式不能很好地提高邏輯芯片的運(yùn)行效率，尤其是對(duì)邏輯芯片在執(zhí)行過程中，往往會(huì)留下較多的空閑資源區(qū)域，從而降低了邏輯芯片的使用效率[9－10].為了提高邏輯芯片的工作效率，筆者設(shè)計(jì)了一種面向多任務(wù)調(diào)度的邏輯芯片重構(gòu)設(shè)計(jì)方案.其設(shè)計(jì)原理是將待調(diào)度執(zhí)行的任務(wù)進(jìn)行調(diào)整和優(yōu)化次序，盡可能地使得邏輯芯片處于較高的運(yùn)行負(fù)荷.在進(jìn)行重構(gòu)設(shè)計(jì)時(shí)，可以根據(jù)不同任務(wù)的執(zhí)行時(shí)間和所需要占用的邏輯資源，動(dòng)態(tài)的調(diào)整任務(wù)的次序和時(shí)間.通過重構(gòu)設(shè)計(jì)之后，既能夠提高邏輯芯片的資源利用率，同時(shí)由于有些任務(wù)的調(diào)度次序得到了優(yōu)化，因此對(duì)于同樣的任務(wù)其得到的執(zhí)行的響應(yīng)時(shí)間還會(huì)更短.調(diào)度模式如圖2所示.

圖1　傳統(tǒng)的任務(wù)調(diào)度模式Fig.1　The traditional task adjusts one degree mode

圖2　重構(gòu)后的任務(wù)調(diào)度模式Fig.2　The heavy task after reaching adjusts one degree mode

2　重構(gòu)算法設(shè)計(jì)

重構(gòu)算法的設(shè)計(jì)目的是提高邏輯芯片上任務(wù)加載效率.由于任務(wù)加載的時(shí)刻是不確定的，有些任務(wù)要求在固定時(shí)刻必須加載，有些任務(wù)的加載時(shí)刻可以動(dòng)態(tài)調(diào)整，因此，重構(gòu)算法的設(shè)計(jì)分為固定時(shí)刻的任務(wù)調(diào)度模式和非固定時(shí)刻的任務(wù)調(diào)度模式[12－13].其中非固定時(shí)刻的任務(wù)調(diào)度模式又可分為非周期性的任務(wù)最優(yōu)調(diào)度模式和周期性的任務(wù)最優(yōu)調(diào)度模式.

1）固定任務(wù)調(diào)度模式.

假設(shè)有N個(gè)待計(jì)算的任務(wù)序列，首先計(jì)算任務(wù)序列的計(jì)算資源和存儲(chǔ)資源的總占用量，算式如下：

將計(jì)算得到的任務(wù)序列占用計(jì)算資源和存儲(chǔ)資源與邏輯芯片可提供的資源量對(duì)比，對(duì)比之后按如下算式進(jìn)行任務(wù)調(diào)度調(diào)整.

若在給定的時(shí)間段[t1，t2]，F(xiàn)c≤Mc（Mc為邏輯芯片的最大可提供計(jì)算資源），則在時(shí)間段[t1，t2]中，N個(gè)任務(wù)可同時(shí)加載至邏輯芯片中進(jìn)行重構(gòu).

若在給定的時(shí)間段[t1，t2]，F(xiàn)c＞Mc，則對(duì)N個(gè)任務(wù)中的計(jì)算資源占用量進(jìn)行排序，得到序列ΓA，取序列中ΓA的一個(gè)子序列ΓB.

兩個(gè)序列元素之差ΓA－ΓB為新一批待調(diào)度的任務(wù)，記該任務(wù)集以固定任務(wù)調(diào)度模式重新進(jìn)行調(diào)度，過程如上，直至ΓA－ΓB中所有任務(wù)均調(diào)度完成.

2）非周期性的任務(wù)最優(yōu)調(diào)度模式.

為了得到最優(yōu)調(diào)度效果，其實(shí)現(xiàn)原理是通過調(diào)整各個(gè)任務(wù)調(diào)度時(shí)刻，讓邏輯芯片的平均任務(wù)負(fù)荷處于最高的狀態(tài).

假設(shè)有N個(gè)待計(jì)算的任務(wù)序列，每個(gè)任務(wù)Wi的預(yù)定加載時(shí)刻為YTi.因此N個(gè)待計(jì)算的任務(wù)序列的預(yù)定加載時(shí)刻分別為YT1，…，YTi，…，YTN，所有任務(wù)中最長(zhǎng)任務(wù)加載時(shí)間為Tmax.

若將每個(gè)任務(wù)的加載時(shí)刻進(jìn)行調(diào)整，調(diào)整幅度為△ti.則N個(gè)待計(jì)算的任務(wù)序列的加載時(shí)刻分別為YT1＋△t1，…，YTi＋△ti，…，YTN＋△tN.

定義在給定的時(shí)間T內(nèi)，任意時(shí)刻邏輯芯片上占用的計(jì)算資源為Hct.

在給定的時(shí)間T內(nèi)，當(dāng)前任務(wù)序列在邏輯芯片上的計(jì)算資源利用率為Gc.

若給定的T＞Tmax且（T－Tmax）＝ξ，ξ表示一個(gè)無窮小的數(shù)，尋找時(shí)間序列Γ＝｛△t1，…，△ti，…，△tN｝，使得下式成立

式中α為一個(gè)固定的系數(shù)，該系數(shù)的設(shè)定是確保邏輯芯片不影響其計(jì)算能力時(shí)的計(jì)算資源最大占用率，Gck表示任意一個(gè)時(shí)間序列Γk下計(jì)算得到的邏輯芯片計(jì)算資源利用率.

通過極大似然估計(jì)算法，能夠計(jì)算得到近似解Γθ，該近似解中表示的時(shí)間序列Γθ＝｛△t1，…，△ti，…，△tN｝即為最優(yōu)的任務(wù)調(diào)度序列.

3）周期性的任務(wù)最優(yōu)調(diào)度模式.

對(duì)于N個(gè)待計(jì)算的任務(wù)序列，假設(shè)每個(gè)任務(wù)的運(yùn)行周期分別為｛T1，…，Ti，…，TN｝.

定義函數(shù)E（A）如下：

E（A）＝LCM（T1，…，Ti，…，TN）

LCM（T）表示對(duì)集合T中的所有元素計(jì)算最小公倍數(shù).

令T0＝E（A）作為當(dāng)前邏輯芯片的資源統(tǒng)計(jì)周期，選擇一個(gè)T＞T0且（T－T0）＝ξ，

由于每個(gè)任務(wù)為周期性任務(wù)，因此假設(shè)每個(gè)任務(wù)的初始加載時(shí)刻都為0.在統(tǒng)計(jì)的時(shí)間周期T0內(nèi)，每個(gè)任務(wù)Wi的插入的時(shí)間片序列為｛△ti1，…，△tij，…，△timi｝，式中（1≤j≤mi），每個(gè)任務(wù)插入的時(shí)間片個(gè)數(shù)分別為｛m1，m2，…，mN｝.

將每個(gè)任務(wù)的加載時(shí)刻按中間插入的時(shí)間片進(jìn)行調(diào)整，則每個(gè)待計(jì)算的任務(wù)序列的加載時(shí)刻分別為△ti1，…，i*Ti＋△ti1＋△ti2＋…＋△tij，…，mi*Ti＋△ti1＋△ti2＋…＋△timi.同樣上文定義的Gc和Hct.

若給定的T＞T0且（T－T0）＝ξ，尋找時(shí)間序列Γ＝｛△ti1，…，△tij，…，△timi｝，使得下式成立

α和Gck的定義和上文一樣，同理采用極大似然估計(jì)算法，能夠計(jì)算得到近似解Γθ，該近似解中表示的時(shí)間序列Γθ＝｛△ti1，…，△tij，…，△timi｝即為最優(yōu)的任務(wù)調(diào)度序列.

3　實(shí)驗(yàn)測(cè)試

針對(duì)筆者所設(shè)計(jì)的邏輯芯片重構(gòu)算法，選取了10個(gè)典型的待調(diào)度執(zhí)行任務(wù)，在邏輯芯片中進(jìn)行實(shí)現(xiàn)，并分別采用傳統(tǒng)的實(shí)現(xiàn)模式和重構(gòu)優(yōu)化之后的實(shí)現(xiàn)模式進(jìn)行對(duì)比測(cè)試，測(cè)試結(jié)果如圖3和圖4所示.

圖3給出的測(cè)試結(jié)果是針對(duì)邏輯芯片重構(gòu)前后資源占用比率的對(duì)比測(cè)試結(jié)果.從測(cè)試結(jié)果可以看出在重構(gòu)之前，邏輯芯片是按照需要執(zhí)行的任務(wù)順序，依次加載相應(yīng)的任務(wù)，邏輯芯片的資源占用率忽高忽低，在整個(gè)邏輯芯片運(yùn)行周期中，整體的邏輯芯片平均資源利用率并不高.而進(jìn)行重構(gòu)設(shè)計(jì)之后，能夠?qū)⑦壿嬓酒纤枰\(yùn)行的程序，調(diào)度次序進(jìn)行優(yōu)化，從而保證了邏輯芯片的平均資源占用率處于一個(gè)較高的水平.而且在整個(gè)運(yùn)行過程中，邏輯芯片的資源占用率波動(dòng)也很小，確保了邏輯芯片的工作效率一直處于較高的狀態(tài).

圖4給出的是在邏輯芯片重構(gòu)前后對(duì)7個(gè)典型的任務(wù)其響應(yīng)時(shí)間的測(cè)試.從測(cè)試結(jié)果可以看出在重構(gòu)之前，邏輯芯片由于都是單獨(dú)的一次加載任務(wù)，因此在每個(gè)任務(wù)加載之前都會(huì)存在一個(gè)準(zhǔn)備時(shí)間.而且由于任務(wù)的調(diào)度次序也沒有優(yōu)化，從而使得有些任務(wù)在執(zhí)行的時(shí)候需要更多的等待時(shí)間.測(cè)試結(jié)果表明，在重構(gòu)之前任務(wù)2的等待時(shí)間最長(zhǎng)，達(dá)5.6s，而在重構(gòu)之后，最長(zhǎng)的等待仍然為任務(wù)2，其等待時(shí)間只有3.9s.在整個(gè)7個(gè)任務(wù)的測(cè)試過程中，通過重構(gòu)之后所使用的邏輯芯片，其總體的任務(wù)響應(yīng)等待時(shí)間也明顯低于重構(gòu)之前的任務(wù)響應(yīng)時(shí)間.

圖3　邏輯芯片重構(gòu)前后資源占用率對(duì)比Fig.3　The logic chip is heavy to reach front and back resource occupation to lead contrast

圖4　邏輯芯片重構(gòu)前后任務(wù)的響應(yīng)延時(shí)Fig.4　When logic chip was heavy to reach the response of front and back task to postpone

4　結(jié)語

隨著邏輯芯片占的資源越來越豐富，在邏輯芯片上所實(shí)現(xiàn)的任務(wù)數(shù)量也變得越來越多，面向多任務(wù)的邏輯芯片可重構(gòu)設(shè)計(jì)，能夠在單個(gè)芯片上更好地提高芯片的利用效率.同時(shí)對(duì)多個(gè)任務(wù)的執(zhí)行響應(yīng)延遲也有明顯地減少，因此設(shè)計(jì)面向多任務(wù)調(diào)度的可重構(gòu)算法，能夠提高邏輯芯片的綜合應(yīng)用效率.

[1]齊驥，李曦，于海晨，等.一種面向動(dòng)態(tài)可重構(gòu)計(jì)算的調(diào)度算法[J].計(jì)算機(jī)研究與發(fā)展，2007，44（8）：1439－1447.

[2]馬宏星，周學(xué)海，高妍妍，等.一種集成可重構(gòu)硬件的多核片上系統(tǒng)的軟硬件任務(wù)劃分與調(diào)度算法[J].中國(guó)科學(xué)院研究生院學(xué)報(bào)，2010，27（5）：664－669.

[3]焦鉻，李仁發(fā)，彭日光，等.一種動(dòng)態(tài)可重構(gòu)系統(tǒng)的實(shí)時(shí)任務(wù)調(diào)度算法[J].計(jì)算機(jī)工程與科學(xué)，2010，32（12）：145－148.

[4]劉沙，周學(xué)功，王穎，等.可重構(gòu)系統(tǒng)在線任務(wù)預(yù)約重調(diào)度算法[J].計(jì)算機(jī)工程，2011，37（8）：271－274.

[5]周學(xué)功，梁樑，黃勛章，等.可重構(gòu)系統(tǒng)中的實(shí)時(shí)任務(wù)在線調(diào)度與放置算法[J].計(jì)算機(jī)學(xué)報(bào)，2007，30（11）：1901－1909.

[6]李濤，楊愚魯.可重構(gòu)資源管理及硬件任務(wù)布局的算法研究[J].計(jì)算機(jī)研究與發(fā)展，2008，45（2）：375－382.

[7]Nup Kumar Raghavan，Peter Sutton.JPG－A Partial Bitstream Generation Tool to Support Partial Reconfiguration in Virtex FPGAs[C].Proceedings of the 16th International Parallel and Distributed Processing Symposium，2002：155－160.

[8]Steffen Toscher，Thomas Reinemann，Roland Kasper.An Adaptive FPGA－Based Mechatronic Control System Supporting Partial Reconfiguration of Controller Functionalities[C].Adaptive Hardware and Systems，2006（AHS 2006），F(xiàn)irst NASA/ESA Conference on，2006：225－228.

[9]周盛雨.基于FPGA的動(dòng)態(tài)部分重構(gòu)系統(tǒng)實(shí)現(xiàn)[D].中國(guó)科學(xué)院研究生院（空間科學(xué)與應(yīng)用研究中心），2007：1－127.

[10]谷鑾，徐貴力，王友仁.FPGA動(dòng)態(tài)可重構(gòu)理論及其研究進(jìn)展[J].計(jì)算機(jī)測(cè)量與控制，2007，15（11）：1415－1418.

[11]王穎，陳偉男，周學(xué)功，等.可重構(gòu)計(jì)算中的負(fù)載可分應(yīng)用性能分析與預(yù)測(cè)[J].小型微型計(jì)算機(jī)系統(tǒng)，2010，31（8）：1668－1674.

[12]Tanya Vladimirova，XiaoFeng Wu.On－board Partial Runtime Reconfiguration for Pico－Satellite Constellations[C].A-daptive Hardware and Systems，2006（AHS 2006），F(xiàn)irst NASA/ ESA Conference on，2006：262－269.

[13]許駿，晏渭川，彭澄廉.基于模塊的動(dòng)態(tài)可重構(gòu)系統(tǒng)設(shè)計(jì)[J].計(jì)算機(jī)工程與設(shè)計(jì)，2008，29（6）：1367－1369.

[責(zé)任編輯 蘇 琴]

[責(zé)任校對(duì) 黃招揚(yáng)]

Design of Reconfigurable Algorithm for Multi Task Scheduling

HUANG Qing-hua
（Department of Electronic Information Engineering，Liuzhou Vocational ＆Technical College，Liuzhou 545006，China）

Aimed at the application of multi task on a single logic chips，reconfiguration algorithm for multi task scheduling is designed，in order to improve the response efficiency logic chip utilization ratio of resources and tasks.A detailed description of the design principle for the reconstruction of multi task scheduling，and according to the logic chip multi task scheduling are designed reconfigurable scheduling algorithm logic chip，finally selected a number of typical task compared to the test.The test results show that，the logic chip after using the reconstruction algorithm in share and tasks in resource response delay logic chip design method is superior to traditional.

Reconstruction；task scheduling；logic chip；utilization；loading

TP302

A

1673－8462（2015）01－0073－04

2014-09-10.

廣西自然科學(xué)基金項(xiàng)目（2013GXNSFAA019006）.

黃慶華（1969-），男，廣西桂平人，柳州職業(yè)技術(shù)學(xué)院電子信息工程系副教授，研究方向：電氣自動(dòng)化技術(shù).