王曉麗，王宇平，蔡 坤，賴俊凡

?

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

王曉麗，王宇平，蔡 坤，賴俊凡

(西安電子科技大學(xué)計算機(jī)學(xué)院 西安 710071)

隨著科學(xué)應(yīng)用逐漸趨于數(shù)據(jù)密集型計算，為并行與分布式系統(tǒng)尋求高效的任務(wù)調(diào)度策略成了研究的熱點問題。已有的可分任務(wù)調(diào)度模型均假設(shè)所有處理機(jī)都能100%的完成子任務(wù)的計算，即處理機(jī)在完成任務(wù)計算之前一直保持在線狀態(tài)。實際上，并行與分布式系統(tǒng)中不同處理機(jī)的在線時間可能不同。若忽略處理機(jī)的在線時間，為其分配的任務(wù)量過大，則任務(wù)的完成時間可能超出處理機(jī)的下線時間，從而造成任務(wù)的計算無法按時完成。因此，為處理機(jī)分配任務(wù)時應(yīng)充分考慮處理機(jī)下線時間的限制。為解決上述問題，該文提出了一種新的考慮處理機(jī)下線時間的可分任務(wù)調(diào)度優(yōu)化模型，并設(shè)計了全局優(yōu)化遺傳算法求解該模型。最后，通過仿真實驗結(jié)果驗證了模型和算法的有效性。

可分任務(wù)調(diào)度; 遺傳算法; 下線時間; 并行與分布式系統(tǒng)

隨著大數(shù)據(jù)時代的來臨，數(shù)據(jù)的規(guī)模呈爆炸式增長，如何高效快速處理并分析數(shù)據(jù)成了研究的重點和難點問題。大數(shù)據(jù)應(yīng)用問題，如大規(guī)模矩陣運算、DNA測序分析、衛(wèi)星圖像處理等，雖然數(shù)據(jù)規(guī)模龐大，但是大都可以抽象為可分任務(wù)，即任務(wù)可以被劃分為任意大小的子任務(wù)，子任務(wù)間相互獨立且沒有優(yōu)先級關(guān)系[1]。并行與分布式系統(tǒng)下可分任務(wù)調(diào)度問題的目標(biāo)是尋求最優(yōu)的任務(wù)分配方案使得任務(wù)的完成時間最短。

針對并行與分布式系統(tǒng)下常見的線型拓?fù)浣Y(jié)構(gòu)、總線型拓?fù)浣Y(jié)構(gòu)和樹型拓?fù)浣Y(jié)構(gòu)，已有很多文獻(xiàn)對可分任務(wù)的最優(yōu)調(diào)度策略進(jìn)行了研究。文獻(xiàn)[2]給出了同構(gòu)線型網(wǎng)絡(luò)下最優(yōu)任務(wù)分配方案的緊式耦合解，文獻(xiàn)[3]給出了同構(gòu)樹型網(wǎng)絡(luò)與總線型網(wǎng)絡(luò)下任務(wù)分配方案的漸近解。文獻(xiàn)[4]給出了異構(gòu)星型網(wǎng)絡(luò)下任務(wù)分配方案的緊式耦合解，并且證明了處理機(jī)調(diào)度順序在遵循通信速率遞減的情況下任務(wù)的完成時間最短。對于異構(gòu)樹型網(wǎng)絡(luò)，文獻(xiàn)[5]的研究表明處理機(jī)的調(diào)度順序只依賴于其通信速率而非計算速率。然而，這些研究成果都沒有考慮處理機(jī)的計算啟動開銷和網(wǎng)絡(luò)的通信啟動開銷。文獻(xiàn)[6-7]在調(diào)度模型中引入了啟動開銷，分析了總線型網(wǎng)絡(luò)下啟動開銷和處理機(jī)的調(diào)度順序?qū)θ蝿?wù)完成時間的影響，證明了當(dāng)處理機(jī)遵循計算速率遞減的順序時任務(wù)的完成時間最短。為了使可分任務(wù)調(diào)度模型更符合分布式平臺的實際網(wǎng)絡(luò)環(huán)境，文獻(xiàn)[8]將可分任務(wù)調(diào)度模型擴(kuò)展到多源網(wǎng)格環(huán)境中，文獻(xiàn)[9]研究了云平臺下處理機(jī)帶寬受限的可分任務(wù)調(diào)度問題，文獻(xiàn)[10]將其擴(kuò)展到混合云計算平臺環(huán)境中，文獻(xiàn)[11-12]將其擴(kuò)展到無線傳感器網(wǎng)絡(luò)中，文獻(xiàn)[13-14]將其擴(kuò)展到實時環(huán)境中。

但是，已有的可分任務(wù)調(diào)度模型均假設(shè)所有處理機(jī)都能100%的完成所分配的子任務(wù)，即處理機(jī)在完成所分配的子任務(wù)之前一直保持在線狀態(tài)[15]。然而在實際的網(wǎng)絡(luò)環(huán)境下這個假設(shè)并不成立，不同處理機(jī)的下線時間可能不同。若為處理機(jī)分配的任務(wù)量過大，則任務(wù)的完成時間可能超出處理機(jī)的下線時間，從而造成任務(wù)的計算無法按時完成。若處理機(jī)未完成計算就已下線，則為其分配的任務(wù)需要等待其他處理機(jī)完成計算空閑后，調(diào)度到其他仍在線的處理機(jī)上重新開始計算，從而導(dǎo)致任務(wù)的總完成時間增大。鑒于此，本文提出了一種新的考慮處理機(jī)下線時間的可分任務(wù)調(diào)度優(yōu)化模型，并且設(shè)計了新的遺傳算法對模型進(jìn)行求解。

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

1.1 問題描述

(1)

1.2 可分任務(wù)調(diào)度優(yōu)化模型

(3)

將式(4)帶入式(1)可得：

(5)

(8)

與情況1不同的是，對于情況2，無法直接通過計算得到所有處理機(jī)的最優(yōu)任務(wù)分配方案，也就無法直接得到總?cè)蝿?wù)的完成時間。這主要是因為可能只有部分處理機(jī)受下線時間的約束，因此無法通過式(7)得到所有處理機(jī)的最優(yōu)任務(wù)分配方案。鑒于此，本文建立了以下考慮處理機(jī)下線時間的可分任務(wù)調(diào)度優(yōu)化模型：

模型的目標(biāo)是總?cè)蝿?wù)的完成時間最短，變量是參與計算的最優(yōu)處理機(jī)數(shù)目和處理機(jī)的最優(yōu)任務(wù)分配方案。模型的約束條件1)表示并非所有的處理機(jī)都必須參與計算；約束條件2)表示每個處理機(jī)所分配的任務(wù)量必須非負(fù)，且不能超過總?cè)蝿?wù)量；約束條件3)表示所有處理機(jī)分配的任務(wù)量之和為總?cè)蝿?wù)量；約束條件4)表示所有處理機(jī)完成所分配任務(wù)的時間必須小于等于其下線時間。

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

為了求解建立的優(yōu)化模型，本文設(shè)計了新的全局優(yōu)化遺傳算法，包括編碼與解碼規(guī)則、交叉與變異算子、修正算子和局部搜索算子。

2.1 編碼與解碼

2.2 交叉和變異算子

交叉算子采用三三交叉的方式，即3個父代兩兩交叉生成3個子代。具體操作步驟如下：首先，按照交叉概率從交叉池中選擇3個個體作為父代，然后隨機(jī)生成3個整數(shù)、和滿足，按照圖3所示的方法進(jìn)行交叉，使得每個子代個體都包含3個父代個體的部分基因。通過三三交叉可以更大程度地增加種群的多樣性，較常用的兩兩交叉而言，可以加快算法收斂于全局最優(yōu)解，從而提高整個算法的執(zhí)行效率。

圖3 交叉示意圖

2.3 修正算子

如前文所述，不論是種群的初始化，還是交叉及變異產(chǎn)生的新個體，都不能保證個體滿足模型的全部約束條件，因此需要對個體進(jìn)行修正。修正算子的主要思想如下：若處理機(jī)完成所分配的任務(wù)量的時間超出了其下線時間，則將超出下線時間的部分(又稱為沖突部分)調(diào)整到相鄰的下一臺處理機(jī)上執(zhí)行。若第一輪調(diào)整過后，處理機(jī)的完成時間也超出了其下線時間，則繼續(xù)將的沖突部分調(diào)整到相鄰的下一臺處理機(jī)上執(zhí)行，循環(huán)此過程，直至沖突完全消除?？梢?，修正的過程是一個迭代的過程。

圖4給出了一種不滿足模型約束的可分任務(wù)調(diào)度時序圖。從該圖可以看出，處理機(jī)完成任務(wù)所需要的時間超出了該處理機(jī)的下線時間，圖中灰色部分即為沖突部分。因此，需要對處理機(jī)的任務(wù)量進(jìn)行調(diào)整。首先，將沖突部分對應(yīng)的任務(wù)量分配給處理機(jī)，圖5給出了調(diào)整后的可分任務(wù)調(diào)度時序圖。選擇分配給相鄰的下一臺處理機(jī)是考慮到每臺處理機(jī)的開始時間與其前面的所有處理機(jī)的任務(wù)分配量直接相關(guān)。如果將沖突部分調(diào)整到前面的處理機(jī)，調(diào)整后將推遲后續(xù)所有處理機(jī)的開始時間，導(dǎo)致新的沖突產(chǎn)生。從圖5可以看出，將處理機(jī)的沖突部分調(diào)整給處理機(jī)后，處理機(jī)產(chǎn)生了新的沖突部分，因此需要繼續(xù)迭代修正過程，直至沖突全部消除。

2.4 局部搜索算子

為了增強(qiáng)算法的局部搜索能力，提高算法的收斂速度，本文為遺傳算法引入了局部搜索算子。

算子的設(shè)計思想如下：由于所有處理機(jī)是同構(gòu)的，因此若不考慮處理機(jī)的下線時間，為達(dá)到總?cè)蝿?wù)的完成時間最短，調(diào)度順序靠前的處理機(jī)其分配的任務(wù)量應(yīng)大于調(diào)度順序靠后的處理機(jī)。鑒于此，可以通過置換相鄰兩臺處理機(jī)的任務(wù)分配量來尋求更優(yōu)的個體。局部搜索算子的具體執(zhí)行過程如下：對所有處理機(jī)的任務(wù)量從后向前逐個進(jìn)行比較，如相鄰兩個處理機(jī)中，前面處理機(jī)的任務(wù)完成時間小于其下線時間且后面處理機(jī)所分配的任務(wù)量大于前面處理機(jī)的任務(wù)量，那么將兩個處理機(jī)的任務(wù)量進(jìn)行交換。圖6給出了一種可能的局部搜索執(zhí)行過程。

2.5 可分任務(wù)調(diào)度遺傳算法整體框架

基于前文設(shè)計的編碼與解碼規(guī)則、交叉與變異算子、修正算子和局部搜索算子，下面給出考慮處理機(jī)下線時間的可分任務(wù)調(diào)度遺傳算法整體框架。

算法1 考慮處理機(jī)下線時間的可分任務(wù)調(diào)度遺傳算法。

7) (終止條件)若算法達(dá)到終止條件，則終止；否則，轉(zhuǎn)至2)。

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

為了驗證本文提出的算法的有效性，將其與已有算法[15]進(jìn)行了多組對比實驗，其中并行與分布式系統(tǒng)的參數(shù)設(shè)置如下：，，，，；遺傳算法的參數(shù)設(shè)置如下：種群大小，交叉概率，變異概率，精英保留個數(shù)，終止條件為進(jìn)化代數(shù)。

實驗1 固定處理機(jī)的下線時間，對比兩個算法在不同任務(wù)量情況下求得的任務(wù)完成時間。20臺處理機(jī)的下線時間分別為：

表1 不同任務(wù)量情況下兩種算法對比的實驗結(jié)果

為了更直觀地反應(yīng)表1中兩種算法的對比結(jié)果，圖7給出了兩種算法的任務(wù)完成時間隨任務(wù)大小的變化趨勢。由圖7可以看出，隨著任務(wù)量的增大，兩個算法求得的任務(wù)完成時間的差距越來越大。這主要是因為本文的算法在任務(wù)調(diào)度前充分考慮到各個處理機(jī)下線時間的限制，為下線時間較早的處理機(jī)分配合理的任務(wù)量，避免了任務(wù)的重新分配和重新計算，從而減少了總?cè)蝿?wù)的完成時間。隨著任務(wù)量的增大，處理機(jī)下線時間的影響越來越明顯，因此兩個算法求得的任務(wù)完成時間的差距就越來越大。

實驗2 固定任務(wù)量，對比兩個算法在不同下線時間情況下求得的任務(wù)完成時間。任務(wù)量，處理機(jī)～的下線時間～是指數(shù)分布的隨機(jī)數(shù)。圖8和圖9分別給出了算法GA和TSA的任務(wù)完成時間隨處理機(jī)下線時間的平均值(300～1 200)的變化趨勢。

由圖8和圖9可以看出，隨著處理機(jī)下線時間平均值的增大，兩個算法求得的任務(wù)完成時間趨于平穩(wěn)，結(jié)果趨于一致。這主要是因為針對固定大小的任務(wù)，隨著下線時間的增大，處理機(jī)不再受下線時間的影響，當(dāng)所有處理機(jī)同時完成計算時任務(wù)的完成時間最短，因此兩個算法求得的任務(wù)完成時間相同。當(dāng)下線時間的平均值較小時，部分處理機(jī)開始受到下線時間的影響，兩個算法求得的任務(wù)完成時間不同且GA求得的任務(wù)完成時間要遠(yuǎn)小于對比算法TSA求得的任務(wù)完成時間。而且，針對固定大小的任務(wù)，處理機(jī)下線時間的平均值越小，對任務(wù)完成時間的影響越大，本文提出的算法GA相較于TSA的優(yōu)勢就越明顯。

4 結(jié)束語

本文在考慮實際并行與分布式環(huán)境中處理機(jī)存在下線時間的基礎(chǔ)上，分析了兩種不同時間約束下的任務(wù)調(diào)度過程，提出了一種新的考慮處理機(jī)下線時間的可分任務(wù)優(yōu)化調(diào)度模型，并設(shè)計了高效的全局優(yōu)化遺傳算法對其進(jìn)行求解。實驗結(jié)果表明本文提出的算法能夠針對不同處理機(jī)的下線時間有針對性的為其分配任務(wù)，使得總?cè)蝿?wù)的完成時間最短。

[1] BHARDWAJ V, GHOSE D, MANI V, et al. Scheduling divisible loads in parallel and distributed systems[M]. Los Alamitos CA: IEEE Computer Society Press, 1996.

[2] MANI V, GHOSE D. Distributed computation in linear networks: Closed-form solutions[J]. IEEE Transactions on Aerospace and Electronic Systems, 1994, 30(2): 471-483.

[3] GHOSE D, MANI V. Distributed computation with communication delays: Asymptotic performance analysis[J]. Journal of Parallel and Distributed Computing, 1994, 23(3): 293-305.

[4] BHARADWAJ V, GHOSE D, MANI V. Optimal sequencing and arrangement in distributed single-level tree networks with communication delays[J]. IEEE Transactions on Parallel and Distributed Systems, 1994, 5(9): 968-976.

[5] 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.

[6] SURESH S, MANI V, OMKAR S N. The effect of start-up delays in scheduling divisible loads on bus networks: an alternate approach[J]. Computers & Mathematics with Applications, 2003, 46(10): 1545-1557.

[7] VEERAVALLI B, LI X, KO C C. On the influence of start-up costs in scheduling divisible loads on bus networks[J]. IEEE Transactions on Parallel and Distributed Systems, 2000, 11(12): 1288-1305.

[8] MURUGESAN G, CHELLAPPAN C. Multi-source task scheduling in grid computing environment using linear programming[J]. International Journal of Computational Science and Engineering, 2014, 9(1): 80-85.

[9] 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.

[10] HOSEINYFARAHABADY M R, LEE Y C, ZOMAYA A Y. Randomized approximation scheme for resource allocation in hybrid-cloud environment[J]. The Journal of Supercomputing, 2014, 69(2): 576-592.

[11] SHI H, WANG W, KWOK N M, et al. Adaptive indexed divisible load theory for wireless sensor network workload allocation[J]. International Journal of Distributed Sensor Networks, 2013(1): 1-18.

[12] DAI L, SHEN Z, CHEN T, et al. Analysis and modeling of task scheduling in wireless sensor network based on divisible load theory[J]. International Journal of Communication Systems, 2014, 27(5): 721-731.

[13] HU M, VEERAVALLI B. Dynamic scheduling of hybrid real-time tasks on clusters[J]. IEEE Transactions on Computers, 2014, 63(12): 2988-2997.

[14] 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.

[15] ROSAS C, SIKORA A, JORBA J, et al. Improving performance on data-intensive applications using a load balancing methodology based on divisible load theory[J]. International Journal of Parallel Programming, 2013, 42(1): 94-118.

編 輯 漆 蓉

Off-Line Time Aware Divisible-Load Scheduling Optimization Model

WANG Xiao-li, WANG Yu-ping, CAI Kun, and LAI Jun-fan

(School of Computer Science and Technology, Xidian University Xi’an 710071)

As scientific applications become more data intensive, finding an efficient scheduling strategy for massive computing in parallel and distributed systems has drawn increasingly attention. Most existing scheduling models assume that all processors can 100% finish computing, that is, they keep online during the completion of assigned workload fractions. In fact, in the real parallel and distributed environments, different processors have different off-line time. Therefore, off-line time constraints of processors should be taken into account before distributing of the workload fractions; otherwise, some processors may not be able to fish computing their assignments. To solve the above issue, this paper proposes an off-line time aware divisible-load scheduling model and designs an effective global optimization genetic algorithm to solve it. Finally, experimental results illustrate the effectiveness of the proposed model and the efficiency of the proposed algorithm.

divisible-load scheduling; genetic algorithm; off-line time; parallel and distributed systems

TP393

A

10.3969/j.issn.1001-0548.2017.01.014

2015-07-13；

2016-05-31

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

王曉麗(1987-)，女，博士，主要從事并行與分布式系統(tǒng)下的任務(wù)調(diào)度方面的研究.