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

黃慶華

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

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

黃慶華

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

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

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

0　引言

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3　實驗測試

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

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

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

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

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

4　結(jié)語

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

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

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

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

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

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

[6]李濤，楊愚魯.可重構(gòu)資源管理及硬件任務(wù)布局的算法研究[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的動態(tài)部分重構(gòu)系統(tǒng)實現(xiàn)[D].中國科學院研究生院（空間科學與應(yīng)用研究中心），2007：1－127.

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

[11]王穎，陳偉男，周學功，等.可重構(gòu)計算中的負載可分應(yīng)用性能分析與預測[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]許駿，晏渭川，彭澄廉.基于模塊的動態(tài)可重構(gòu)系統(tǒng)設(shè)計[J].計算機工程與設(shè)計，2008，29（6）：1367－1369.

[責任編輯 蘇 琴]

[責任校對 黃招揚]

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.

廣西自然科學基金項目（2013GXNSFAA019006）.

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