考慮處理機釋放時間的可分任務調度優化模型

王曉麗，王宇平，孟 坤

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

考慮處理機釋放時間的可分任務調度優化模型

王曉麗，王宇平，孟 坤

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

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

可分任務調度；釋放時間；混合時序約束；遺傳算法

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

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

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

1 考慮釋放時間的可分任務調度優化模型

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

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

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

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

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

（2）ri+1＞si+zαi，i=1，2，…，n-1.處理機Pi+1的釋放時間ri+1晚于P0給Pi傳輸完任務αi的時刻，即P0在給Pi傳輸完任務αi后需要等待一段時間直到Pi+1恢復空閑才能為其傳輸任務α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傳輸完數據后緊接著為Pi傳輸數據，中間沒有空閑.此時，處理機Pi的開始時間滿足si=si-1+zαi-1.若ci= Γi（2），表明主處理機P0在給Pi-1傳輸完數據后需要等待Pi由忙碌轉為空閑狀態才能開始傳輸數據，中間存在空閑時間.此時，處理機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　一種滿足混合時序約束條件的可分任務調度圖

根據混合時序約束C，可以得到相鄰處理機開始時間之間的關系:

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

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

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

2 全局優化遺傳算法

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

2.1編碼與解碼

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

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

2.2交叉與變異

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

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

2.3全局優化遺傳算法

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

算法1 求解可分任務調度模型的全局優化遺傳算法.

（1）初始化.根據編碼規則隨機生成初始種群P（0）.令進化代數t=0.

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

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

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

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

3 實驗與結果分析

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

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

表1　不同任務量情況下全局優化遺傳算法（GA）和窮舉算法（EA）對比的實驗結果

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

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

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

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

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

4 結束語

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

［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，FICHERA 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 網絡出版時間：2015-04-14

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

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

網絡出版地址：http://www.cnki.net/kcms/detail/61.1076.TN.20150414.2046.006.html