面向多任務調度的可重構算法設計*

黃慶華

（柳州職業技術學院電子信息工程系，廣西　柳州　545006）

面向多任務調度的可重構算法設計*

黃慶華

（柳州職業技術學院電子信息工程系，廣西柳州545006）

針對在單個邏輯芯片上實現多任務的應用場合，設計了面向多任務調度的可重構算法，以此提高邏輯芯片的資源利用率和任務的響應效率.詳細描述了面向多任務調度的重構設計原理，并針對邏輯芯片中多任務的調度種類分別設計了邏輯芯片的重構調度算法，最后選取了多個典型的任務進行對比測試.測試結果表明，使用重構算法之后的邏輯芯片在資源占有率和任務響應延遲上均優于傳統的邏輯芯片設計方法.

重構；任務調度；邏輯芯片；利用率；加載

0　引言

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

為了更好地提高邏輯芯片在實現多任務應用時的綜合效率，筆者設計了一種面向多任務調度的可重構算法，該算法通過對多任務的調度模式進行重新設計和優化，使得在邏輯芯片上能夠同時實現多個應用功能，從而實現提高邏輯芯片綜合利用效率的目的.

1　面向多任務調度的重構原理

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

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

圖1　傳統的任務調度模式Fig.1　The traditional task adjusts one degree mode

圖2　重構后的任務調度模式Fig.2　The heavy task after reaching adjusts one degree mode

2　重構算法設計

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

1）固定任務調度模式.

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

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

若在給定的時間段[t1，t2]，Fc≤Mc（Mc為邏輯芯片的最大可提供計算資源），則在時間段[t1，t2]中，N個任務可同時加載至邏輯芯片中進行重構.

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

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

2）非周期性的任務最優調度模式.

為了得到最優調度效果，其實現原理是通過調整各個任務調度時刻，讓邏輯芯片的平均任務負荷處于最高的狀態.

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

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

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

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

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

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

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

3）周期性的任務最優調度模式.

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

定義函數E（A）如下：

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

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

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

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

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

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

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

3　實驗測試

針對筆者所設計的邏輯芯片重構算法，選取了10個典型的待調度執行任務，在邏輯芯片中進行實現，并分別采用傳統的實現模式和重構優化之后的實現模式進行對比測試，測試結果如圖3和圖4所示.

圖3給出的測試結果是針對邏輯芯片重構前后資源占用比率的對比測試結果.從測試結果可以看出在重構之前，邏輯芯片是按照需要執行的任務順序，依次加載相應的任務，邏輯芯片的資源占用率忽高忽低，在整個邏輯芯片運行周期中，整體的邏輯芯片平均資源利用率并不高.而進行重構設計之后，能夠將邏輯芯片上所需要運行的程序，調度次序進行優化，從而保證了邏輯芯片的平均資源占用率處于一個較高的水平.而且在整個運行過程中，邏輯芯片的資源占用率波動也很小，確保了邏輯芯片的工作效率一直處于較高的狀態.

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

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

圖4　邏輯芯片重構前后任務的響應延時Fig.4　When logic chip was heavy to reach the response of front and back task to postpone

4　結語

隨著邏輯芯片占的資源越來越豐富，在邏輯芯片上所實現的任務數量也變得越來越多，面向多任務的邏輯芯片可重構設計，能夠在單個芯片上更好地提高芯片的利用效率.同時對多個任務的執行響應延遲也有明顯地減少，因此設計面向多任務調度的可重構算法，能夠提高邏輯芯片的綜合應用效率.

[1]齊驥，李曦，于海晨，等.一種面向動態可重構計算的調度算法[J].計算機研究與發展，2007，44（8）：1439－1447.

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

[3]焦鉻，李仁發，彭日光，等.一種動態可重構系統的實時任務調度算法[J].計算機工程與科學，2010，32（12）：145－148.

[4]劉沙，周學功，王穎，等.可重構系統在線任務預約重調度算法[J].計算機工程，2011，37（8）：271－274.

[5]周學功，梁樑，黃勛章，等.可重構系統中的實時任務在線調度與放置算法[J].計算機學報，2007，30（11）：1901－1909.

[6]李濤，楊愚魯.可重構資源管理及硬件任務布局的算法研究[J].計算機研究與發展，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），First NASA/ESA Conference on，2006：225－228.

[9]周盛雨.基于FPGA的動態部分重構系統實現[D].中國科學院研究生院（空間科學與應用研究中心），2007：1－127.

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

[11]王穎，陳偉男，周學功，等.可重構計算中的負載可分應用性能分析與預測[J].小型微型計算機系統，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），First NASA/ ESA Conference on，2006：262－269.

[13]許駿，晏渭川，彭澄廉.基于模塊的動態可重構系統設計[J].計算機工程與設計，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-），男，廣西桂平人，柳州職業技術學院電子信息工程系副教授，研究方向：電氣自動化技術.