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

?

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

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

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

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

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

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

針對并行與分布式系統(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ù)的完成時(shí)間最短。對于異構(gòu)樹型網(wǎng)絡(luò)，文獻(xiàn)[5]的研究表明處理機(jī)的調(diào)度順序只依賴于其通信速率而非計(jì)算速率。然而，這些研究成果都沒有考慮處理機(jī)的計(jì)算啟動(dòng)開銷和網(wǎng)絡(luò)的通信啟動(dòng)開銷。文獻(xiàn)[6-7]在調(diào)度模型中引入了啟動(dòng)開銷，分析了總線型網(wǎng)絡(luò)下啟動(dòng)開銷和處理機(jī)的調(diào)度順序?qū)θ蝿?wù)完成時(shí)間的影響，證明了當(dāng)處理機(jī)遵循計(jì)算速率遞減的順序時(shí)任務(wù)的完成時(shí)間最短。為了使可分任務(wù)調(diào)度模型更符合分布式平臺的實(shí)際網(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ò)展到混合云計(jì)算平臺環(huán)境中，文獻(xiàn)[11-12]將其擴(kuò)展到無線傳感器網(wǎng)絡(luò)中，文獻(xiàn)[13-14]將其擴(kuò)展到實(shí)時(shí)環(huán)境中。

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

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

1.1 問題描述

(1)

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

(3)

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

(5)

(8)

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

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

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

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

2.1 編碼與解碼

2.2 交叉和變異算子

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

圖3 交叉示意圖

2.3 修正算子

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

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

2.4 局部搜索算子

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

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

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

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

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

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

3 實(shí)驗(yàn)與結(jié)果分析

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

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

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

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

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

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

4 結(jié)束語

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

[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ù)費(fèi)專項(xiàng)資金(JB150307)

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