考慮處理機釋放時間的可分任務(wù)調(diào)度優(yōu)化模型

王曉麗，王宇平，孟 坤

（西安電子科技大學(xué)計算機學(xué)院，陜西西安 710071）

考慮處理機釋放時間的可分任務(wù)調(diào)度優(yōu)化模型

王曉麗，王宇平，孟 坤

（西安電子科技大學(xué)計算機學(xué)院，陜西西安 710071）

可分任務(wù)調(diào)度是近年來信息技術(shù)領(lǐng)域研究的熱點課題.已有的可分任務(wù)調(diào)度模型大多假設(shè)所有處理機在任務(wù)分配之初全部處于空閑狀態(tài)，而實際上，當新的任務(wù)到來時很多處理機可能尚處于忙碌狀態(tài).每臺處理機從忙碌狀態(tài)轉(zhuǎn)到空閑狀態(tài)的時間不同，即處理機可能具有不同的釋放時間.在充分考慮處理機釋放時間不同的基礎(chǔ)上，建立了一種新的混合時序約束的可分任務(wù)調(diào)度模型，并設(shè)計了高效的全局優(yōu)化遺傳算法求解該模型.實驗結(jié)果表明了模型的合理性和算法的有效性.

可分任務(wù)調(diào)度；釋放時間；混合時序約束；遺傳算法

在并行與分布式系統(tǒng)中，大規(guī)模計算任務(wù)的處理逐漸成為了極具挑戰(zhàn)性的課題.為系統(tǒng)建立合理且貼近實際的任務(wù)調(diào)度模型成了該領(lǐng)域最大的難點，其中可分任務(wù)調(diào)度模型［1-3］就是典型的代表之一.可分任務(wù)是指任務(wù)可以被切分為任意大小的若干子任務(wù)且子任務(wù)間不具有優(yōu)先關(guān)系.在并行與分布式系統(tǒng)下，可分任務(wù)調(diào)度的主要目標是尋求合理的任務(wù)調(diào)度策略，使得任務(wù)的完成時間最短.

針對現(xiàn)實生活中常見的線性網(wǎng)路、總線型網(wǎng)絡(luò)和樹形網(wǎng)絡(luò)，已經(jīng)有很多文獻研究可分任務(wù)調(diào)度方案的最優(yōu)解.例如，文獻［4］給出了齊次線性網(wǎng)絡(luò)中任務(wù)完成時間的緊式耦合解，文獻［5-6］給出了齊次樹形網(wǎng)絡(luò)與總線型網(wǎng)絡(luò)下任務(wù)完成時間的漸進解.文獻［7］給出了異構(gòu)星形網(wǎng)絡(luò)下任務(wù)最短完成時間的緊式耦合解，且證明了在遵循通信速率遞減作為處理機調(diào)度順序的情況下任務(wù)的完成時間最短.對于異構(gòu)樹形網(wǎng)絡(luò)，文獻［8］的研究表明處理機的調(diào)度順序只依賴于節(jié)點的通信速率而非計算速率.然而，這些研究成果都沒有考慮到處理機的計算啟動開銷和網(wǎng)絡(luò)的通信啟動開銷.文獻［9-11］研究了具有常啟動開銷的總線型網(wǎng)絡(luò)中啟動開銷和處理機調(diào)度序列的變化對任務(wù)完成時間的影響，證明了當遵循計算速率遞減作為處理機調(diào)度順序時將獲得任務(wù)的最短完成時間.文獻［12］的研究表明，在具有任意啟動開銷的異構(gòu)分布式環(huán)境下，若任務(wù)足夠大，則遵循通信速率遞減作為處理機調(diào)度順序時任務(wù)的完成時間最短.文獻［13］將可分任務(wù)調(diào)度模型擴展到多源網(wǎng)格環(huán)境中，文獻［14-15］將其擴展到云計算平臺，文獻［16］將其擴展到無線傳感器網(wǎng)絡(luò)中，文獻［17-19］將其擴展到實時環(huán)境中.

已有的研究大多假定處理機在任務(wù)到來時均處于空閑狀態(tài)，然而在實際的并行與分布式應(yīng)用場景中這個假設(shè)并非總是成立的.當新的任務(wù)到來時，處理機可能尚未完成前一個任務(wù)，從而處于忙碌狀態(tài)，不能立即參與新任務(wù)的計算.筆者將新任務(wù)到來后，處理機由忙碌狀態(tài)轉(zhuǎn)變?yōu)榭臻e狀態(tài)的時間間隔稱為該處理機的釋放時間.考慮處理機釋放時間的可分任務(wù)調(diào)度的研究尚處于起步階段，文獻［20］給出了一種窮舉方法用于同構(gòu)總線型網(wǎng)絡(luò)的可分任務(wù)調(diào)度問題.為了避免窮舉法的巨額時間開銷，筆者構(gòu)建了一種新的考慮釋放時間的可分任務(wù)調(diào)度智能優(yōu)化模型，并提出了一種高效的遺傳算法對模型進行求解.

1 考慮釋放時間的可分任務(wù)調(diào)度優(yōu)化模型

稱處理機Pi（i=1，2，…，n）開始從主處理機接收任務(wù)的時刻為Pi的開始時刻，記為si.給定所有處理機的釋放時間，下面分3種情況討論處理機釋放時間與開始時間之間可能滿足的約束條件:

（1）ri+1≤si+zαi，i=1，2，…，n-1.處理機Pi+1的釋放時間ri+1早于主處理機P0給Pi+1分配任務(wù)的時刻，即Pi+1由忙碌狀態(tài)轉(zhuǎn)為空閑狀態(tài)發(fā)生在P0給Pi傳輸任務(wù)αi的過程中.

文獻［3］證明了只有當所有處理機同時完成計算時任務(wù)的完成時間最短，否則完全可以將后完成計算的處理機上的部分任務(wù)調(diào)度到先完成計算的處理機上執(zhí)行.由所有處理機同時完成計算，可以得到

由圖1可以看出，Pi的開始時間si滿足

由式（1）和式（2）可得

（2）ri+1＞si+zαi，i=1，2，…，n-1.處理機Pi+1的釋放時間ri+1晚于P0給Pi傳輸完任務(wù)αi的時刻，即P0在給Pi傳輸完任務(wù)αi后需要等待一段時間直到Pi+1恢復(fù)空閑才能為其傳輸任務(wù)αi+1.同樣地，由所有處理機同時完成計算可得式（1）.處理機Pi（i=1，2，…，n）的釋放時間ri和開始時間si是相等的，即si=ri.將式（1）中的si替換為ri可得

（3）混合時序約束.任意兩個相鄰的從處理機之間可能滿足約束條件（1），也可能滿足約束條件（2）.若有n臺處理機參與計算，所有可能的情況有2（n-1）種，圖1給出了其中一種可能的情況.

將處理機Pi-1和Pi滿足約束條件（1）和條件（2）的情況分別記為Γi（1）和Γi（2），其中i=2，3，…，n.用C=（c2，c3，…，cn）表示一種混合時序約束，其中ci∈｛Γi（1），Γi（2）｝.若ci= Γi（1），表明主處理機P0在給Pi-1傳輸完數(shù)據(jù)后緊接著為Pi傳輸數(shù)據(jù)，中間沒有空閑.此時，處理機Pi的開始時間滿足si=si-1+zαi-1.若ci= Γi（2），表明主處理機P0在給Pi-1傳輸完數(shù)據(jù)后需要等待Pi由忙碌轉(zhuǎn)為空閑狀態(tài)才能開始傳輸數(shù)據(jù)，中間存在空閑時間.此時，處理機Pi的開始時間滿足si=ri.

以圖1為例，其混合時序約束C滿足C= （Γ2（1），…，Γk（1），Γk+1（2），Γk+2（2），…，Γk+m（2），Γk+m+1（1），…，Γn（1））.

圖1　一種滿足混合時序約束條件的可分任務(wù)調(diào)度圖

根據(jù)混合時序約束C，可以得到相鄰處理機開始時間之間的關(guān)系:

將式（6）帶入式（1），可得每臺處理機分配的任務(wù)αi:

其中α表示的是待求的n×1維解變量（α1，α2，…，αn），A是n×n的系數(shù)矩陣，b是n×1維的向量.在圖1給出的任務(wù)調(diào)度圖中，A和b可以分別表示為

給定一種混合時序約束C=（c2，c3，…，cn），就可以求得一個形如A·α=b的標準式，進而可以采用線性規(guī)劃的方法求出任務(wù)分配方案α的解.下面給出考慮釋放時間的可分任務(wù)調(diào)度模型:

2 全局優(yōu)化遺傳算法

遺傳算法已經(jīng)被證明能很好地解決工程技術(shù)領(lǐng)域的優(yōu)化、設(shè)計、控制等實際應(yīng)用問題，尤其是針對任務(wù)調(diào)度等NP-hard的組合優(yōu)化問題［21］.因此，筆者設(shè)計了一種新的全局優(yōu)化遺傳算法來求解上文提出的混合時序約束可分任務(wù)調(diào)度模型.

2.1編碼與解碼

筆者采用實數(shù)編碼方式，將混合時序約束的可分任務(wù)調(diào)度問題表示成一個向量I=（n，H），其中n表示參與計算的處理機數(shù)目，種群初始化時設(shè)為處理機總數(shù)N；H=（h2，h3，…，hN），表示一種混合時序約束，hi∈｛1，0｝.若hi=1，表示處理機Pi-1和Pi滿足約束條件（1）；反之，hi=0，表示滿足約束條件（2）.

舉例說明:假設(shè)共有6臺處理機，一種可能的編碼方案為I=（6，1，0，1，1，0），其中第1位n=6，表示參與計算的處理機數(shù)目（初始時設(shè)定為處理機總數(shù)）；h2=1，表示第1和2臺處理機滿足約束（1）；h3=0，表示第2 和3臺處理機滿足約束（2），第3和4臺滿足約束（1），第5和6臺滿足約束（1），第7和8臺滿足約束（2）.

2.2交叉與變異

交叉操作是遺傳算法的主要進化手段，且模擬了生物繁殖和基因重組機理，通過兩兩染色體基因交叉互換，繁殖兩個新的子代個體，并將父代好的基因遺傳至子代個體.交叉操作保持了遺傳算法種群個體的多樣性和全局搜索能力.筆者采用兩點交叉方式生成新個體:隨機生成兩個整數(shù)p和q，滿足2≤p＜q≤N，作為交叉點，將兩個父代個體交叉點之間的基因進行交換，生成兩個后代個體.由于個體第1位表示參與計算的處理機數(shù)目，因此交叉后的后代個體第1位均置為處理機總數(shù)N.

變異操作是推動遺傳算法進化的重要手段.通過一定概率的基因變異，保持種群多樣性，強化了遺傳算法的局部搜索能力.筆者采用單點變異方式生成新個體:隨機生成一個整數(shù)p，滿足2≤p≤N，作為變異點，將個體在該點的基因位取反，產(chǎn)生新的后代個體；同時，將后代個體的第1位置為處理機總數(shù)N.

2.3全局優(yōu)化遺傳算法

下面給出具體的遺傳算法框架.

算法1 求解可分任務(wù)調(diào)度模型的全局優(yōu)化遺傳算法.

（1）初始化.根據(jù)編碼規(guī)則隨機生成初始種群P（0）.令進化代數(shù)t=0.

（2）交叉.以概率pcros從P（t）之中選擇父代個體進行兩點交叉.交叉獲得的全部后代個體定義為集合O1.

（3）變異.以概率pmut從集合O1中選擇個體進行變異.新的后代個體定義為集合O2.

（4）選擇.從集合P（t）∪O1∪O2中選擇最優(yōu)的E個個體直接保留到下一代種群以加快收斂速度.使用輪盤賭選擇操作從集合P（t）∪O1∪O2選擇N-E個個體保留到下一代種群P（t+1）中.令t=t+1.

（5）終止條件.如果滿足終止條件，則終止算法；否則，轉(zhuǎn)向步驟（2）.

3 實驗與結(jié)果分析

針對筆者提出的模型和算法，對比已有算法進行了多組實驗.系統(tǒng)參數(shù)設(shè)置如下:處理機個數(shù)N=20，z=0.8，w=1.2，處理機P1～P20的釋放時間r1～r20是指數(shù)分布的隨機數(shù).遺傳算法中參數(shù)設(shè)置如下:種群大小SP=100，交叉概率pcros=0.6，變異概率pmut=0.02，精英保留個數(shù)E=5，終止條件為進化代數(shù)t=100.

表1給出了不同任務(wù)量情況下（Wtotal=1.0～10.0）兩種算法對比的實驗結(jié)果，其中GA代表筆者提出的全局優(yōu)化遺傳算法，EA代表文獻［20］提出的窮舉算法（Exhaustive Algorithm）.從表1可以看出，兩個算法針對同樣大小的任務(wù)，調(diào)度后得到的參與計算的處理機數(shù)目和任務(wù)的完成時間完全相同，可見筆者提出的算法能夠有效地求出任務(wù)的最優(yōu)調(diào)度策略.在算法運行時間方面，筆者提出的算法GA的運行時間遠遠小于窮舉算法的時間，可見筆者提出的算法不僅有效而且高效.

表1　不同任務(wù)量情況下全局優(yōu)化遺傳算法（GA）和窮舉算法（EA）對比的實驗結(jié)果

下面分兩種情況對考慮釋放時間的可分任務(wù)調(diào)度優(yōu)化模型進行定性分析，著重考查任務(wù)的最短完成時間受處理機釋放時間的影響.圖2和圖3分別表示任務(wù)較?。╓total=1.0～10.0）和任務(wù)較大（Wtotal=20.0 ～100.0）兩種情況下，任務(wù)最短完成時間和參與計算的處理機數(shù)目隨任務(wù)大小和處理機平均釋放時間的變化趨勢.

圖2　在任務(wù)較小的情況下最短完成時間和參與計算的處理機數(shù)目隨任務(wù)大小和處理機平均釋放時間的變化趨勢

圖3　在任務(wù)較大的情況下最短完成時間和參與計算的處理機數(shù)目隨任務(wù)大小和處理機平均釋放時間的變化趨勢

由圖2（a）可以看出，在任務(wù)較小的情況下，隨著處理機平均釋放時間和任務(wù)的逐漸增大，任務(wù)的最短完成時間也在逐漸增大.由圖2（b）可以看出，對于同樣大小的任務(wù)，參與計算的處理機數(shù)目隨處理機平均釋放時間的增大而逐漸減少.這是由于某些處理機的釋放時間過大，超過了任務(wù)的最短完成時間，因而無法參與計算.隨著任務(wù)的增大，任務(wù)的最短完成時間也逐漸增大，會有更多的處理機參與任務(wù)的計算.通過上面的分析可知，在任務(wù)較小的情況下，處理機的釋放時間會較大程度地影響任務(wù)的最短完成時間和參與計算的處理機數(shù)目.

由圖3可以看出，當任務(wù)量足夠大時，所有的處理機都參與計算，任務(wù)的最短完成時間隨任務(wù)量的增加近似呈線性增長趨勢，處理機的釋放時間對任務(wù)最短完成時間的影響幾乎可以忽略.這主要是由于模型采用的是阻塞通信模式，后分配任務(wù)的處理機需要等待先分配任務(wù)的處理機完成數(shù)據(jù)的傳輸后才能開始接收任務(wù)，當任務(wù)量足夠大時，等待時間已經(jīng)超過了處理機的釋放時間，所以釋放時間對任務(wù)的最短完成時間不再構(gòu)成影響.

4 結(jié)束語

在考慮實際并行與分布式環(huán)境下處理機存在釋放時間的基礎(chǔ)上，筆者詳細分析了3種不同約束條件下的任務(wù)調(diào)度過程，進而提出了一種新的混合時序約束的可分任務(wù)調(diào)度模型，并設(shè)計了高效的全局優(yōu)化遺傳算法對其進行求解，實驗結(jié)果表明了模型的合理性和算法的有效性.

［1］BHARADWAJ V，GHOSE D，MANI V，et al.Scheduling Divisible Loads in Parallel and Distributed Systems［M］. Los Alamitos:IEEE Computer Society Press，1996.

［2］BHARADWAJ V，GHOSE D，ROBERTAZZI T G.Divisible Load Theory:A New Paradigm for Load Scheduling in Distributed Systems［J］.Cluster Computing，2003，6（1）:7-18.

［3］ROBERTAZZI T G.Ten Reasons to Use Divisible Load Theory［J］.Computer，2003，36:63-68.

［4］MANI V，GHOSE D.Distributed Computation in Linear Networks:Closed Form Solutions［J］.IEEE Transactions on Aerospace and Electronic Systems，1994，30:471-483.

［5］BATAINEH S，ROBERTAZZI T G.Ultimate Performance Limits for Networks of Load Sharing Processors［C］// Proceedings of the Conference on Information Sciences and Systems.New York:Princeton University，1992:794-799.

［6］GHOSE D，MANI V.Distributed Computation with Communication Delays:Asymptotic Performance Analysis［J］. Journal of Parallel and Distributed Computing，1994，23:293-305.

［7］BHARADWAJ V，GHOSE D，MANI V.Optimal Sequencing and Arrangement in Distributed Single-Level Networks with Communication Delays［J］.IEEE Transactions on Parallel and Distributed Systems，1994，5:968-976.

［8］KIM H J，JEE G I，LEE J G.Optimal Load Distribution for Tree Network Processors［J］.IEEE Transactions on Aerospace and Electronic Systems，1996，32（2）:607-612.

［9］SURESH S，MANI V，OMKAR S N.The Effect of Start-up Delays in Scheduling Divisible Load on Bus Networks:an Alternate Approach［J］.Journal of Computational and Applied Mathematics，2003，46（10/11）:1545-1557.

［10］BHARADWAJ V，LI X L，CHUNG C K.On the Influence of Start-up Costs in Scheduling Divisible Load on Bus Networks［J］.IEEE Transactions on Parallel and Distributed Systems，2000，11（12）:1288-1305.

［11］SOHN J，ROBERTAZZI T G.Optimal Load Sharing for a Divisible Job on a Bus Network［J］.IEEE Transactions on Aerospace and Electronic Systems，1996，32（1）:34-40.

［12］SHANG M S.Optimal Algorithm for Scheduling Large Divisible Workload on Heterogeneous System［J］.Applied Mathematical Modeling，2008，32:1682-1695.

［13］MURUGESAN G，CHELLAPPAN C.Multi-source Task Scheduling in Grid Computing Environment Using Linear Programming［J］.International Journal of Computer Science and Engineering，2014，9（1）:80-85.

［14］IYER G N，VEERAVALLI B，KRISHNAMOORTHY S G.On Handling Large-scale Polynomial Multiplication in Compute Cloud Environments using Divisible Load Paradigm［J］.IEEE Transactions on Aerospace and Electronic Systems，2012，48（1）:820-831.

［15］LIN W，LIANG C，WANG J Z，et al.Bandwidth-aware Divisible Task Scheduling for Cloud Computing［J］.Software: Practice and Experience，2014，44（2）:163-174.

［16］SHI H Y，WANG W L，KWOK N M，et al.Adaptive Indexed Divisible Load Theory for Wireless Sensor Network Workload Allocation［J］.International Journal of Distributed Sensor Networks，2013，2013:484796.

［17］MAMAT A，LU Y，DEOGUN J，et al.Efficient Real-time Divisible Load Scheduling［J］.Journal of Parallel and Distributed Computing，2012，72（12）:1603-1616.

［18］HU M，VEERAVALLI B.Dynamic Scheduling of Hybrid Real-time Tasks on Clusters［J］.IEEE Transactions on Computers，2013，99:1.

［19］HU M，VEERAVALLI B.Requirement-aware Strategies for Scheduling Real-time Divisible Loads on Clusters［J］. Journal of Parallel and Distributed Computing，2013，73（8）:1083-1091.

［20］CHOI K，ROBERTAZZI T G.An Exhaustive Approach to Release Time Aware Divisible Load Scheduling［J］. International Journal of Internet and Distributed Computing Systems，2011，1（2）:40-50.

［21］COSTA A，CAPPADONNA F A，F(xiàn)ICHERA S.A Novel Genetic Algorithm for the Hybrid Flow Shop Scheduling with Parallel Batching and Eligibility Constraints［J］.The International Journal of Advanced Manufacturing Technology，2014，75（5-8）:833-847.

（編輯:郭 華）

Release time aware divisible-load scheduling optimization model

WANG Xiaoli，WANG Yuping，MENG Kun
（School of Computer Science and Technology，Xidian Univ.，Xi’an 710071，China）

Divisible-load scheduling has become an increasingly hot subject in the research on information technologies in recent years.Most existing divisible-load scheduling models assume that all processors are idle at the beginning of workload assignment.In fact，many processors may still in the busy state when a new workload arrives.Processors may have different waiting times from the busy state to the idle，that is，processors have different release times.This paper proposes a new release time aware divisible-load scheduling model with hybrid time constraints and designs an effective global optimization genetic algorithm to solve it.Finally，experimental results show the effectiveness of the proposed model and the efficiency of the proposed algorithm.

divisible-load scheduling；release time；hybrid time constraints；genetic algorithm

TP301

A

1001-2400（2016）01-0047-07

10.3969/j.issn.1001-2400.2016.01.009

2014-08-11 網(wǎng)絡(luò)出版時間：2015-04-14

國家自然科學(xué)基金資助項目（61402350，61472297，61272119）；中央高?；究蒲袠I(yè)務(wù)費專項資金資助項目（JB150307）

王曉麗（1987-），女，講師，博士，E-mail:wangxiaoli@mail.xidian.edu.cn.

網(wǎng)絡(luò)出版地址：http://www.cnki.net/kcms/detail/61.1076.TN.20150414.2046.006.html