林海濤,姜棟瀚

(海軍工程大學(xué) 電子工程學(xué)院，武漢 430033)

基于重建策略的云工作流調(diào)度算法優(yōu)化

林海濤,姜棟瀚

(海軍工程大學(xué) 電子工程學(xué)院，武漢 430033)

為了進(jìn)一步提高算法性能，提出一種改進(jìn)的蛙跳算法，并與調(diào)度方案相結(jié)合，以期為云工作流資源分配提供最優(yōu)調(diào)度。通過(guò)在蛙跳算法的局部搜索中加入重建策略，提高了數(shù)據(jù)隨機(jī)性，有效避免了局部最優(yōu)。研究了調(diào)度方案生成算法，與改進(jìn)算法相結(jié)合得到接近最優(yōu)的調(diào)度。利用Java模擬器進(jìn)行仿真試驗(yàn)，并與粒子群優(yōu)化算法和傳統(tǒng)蛙跳算法作比較。實(shí)驗(yàn)證明，提出的方法可以在滿(mǎn)足最長(zhǎng)截止時(shí)間約束的情況下，使總執(zhí)行成本最小化。

蛙跳算法；資源調(diào)度；云工作流；重建策略

0 引 言

基礎(chǔ)設(shè)施即服務(wù)(IaaS)是云計(jì)算最基本的應(yīng)用形式[1]。當(dāng)用戶(hù)提出應(yīng)用請(qǐng)求后，IaaS通過(guò)管理中間件中的任務(wù)管理機(jī)制為任務(wù)分配虛擬化資源，其資源調(diào)度機(jī)制是影響云計(jì)算效能的關(guān)鍵。云計(jì)算中的按需配置和資源可用性使其成為執(zhí)行工作流應(yīng)用程序的理想選擇。然而，工作流調(diào)度是一個(gè)非確定性多項(xiàng)式(non-deterministic polynomial，NP)問(wèn)題，云計(jì)算環(huán)境的異質(zhì)性和動(dòng)態(tài)性又使問(wèn)題進(jìn)一步復(fù)雜化。資源調(diào)度高效算法是提升云工作流系統(tǒng)效能亟待解決的問(wèn)題，也是云計(jì)算領(lǐng)域內(nèi)的研究熱點(diǎn)。

工作流是指將一組任務(wù)按照業(yè)務(wù)需求進(jìn)行合理傳遞的工作流程。工作流中任務(wù)數(shù)量大小不等，但所有任務(wù)需要分配至不同的虛擬資源，并在合理的時(shí)間內(nèi)完成。而云計(jì)算環(huán)境下，服務(wù)器被虛擬化成可在同一處理器上運(yùn)行的多個(gè)虛擬機(jī)(virtual machine,VM)，不同的虛擬機(jī)具有不同的CPU、內(nèi)存和帶寬等資源。資源調(diào)度算法就是確定任務(wù)和虛擬資源之間的映射，以便滿(mǎn)足一個(gè)或多個(gè)優(yōu)化目標(biāo)。

國(guó)內(nèi)外已經(jīng)提出了很多云計(jì)算環(huán)境下的資源調(diào)度方案，概括來(lái)說(shuō)主要有2種：①基于最優(yōu)化理論對(duì)云計(jì)算資源調(diào)度問(wèn)題建模，以實(shí)現(xiàn)整個(gè)系統(tǒng)的性能最佳。例如文獻(xiàn)[2]中通過(guò)動(dòng)態(tài)箱包裝，最小化在包裝中使用的最大箱數(shù)，實(shí)現(xiàn)了云計(jì)算整體消耗的最小化；文獻(xiàn)[3]中提出的自適應(yīng)調(diào)度算法(adaptive scheduling algorithm，ASA)首先將任務(wù)從邏輯上分成若干類(lèi)別，再根據(jù)不同資源的特點(diǎn)進(jìn)行合理分配。上述算法在調(diào)度的過(guò)程中實(shí)現(xiàn)了整體效能的最優(yōu)，被廣泛應(yīng)用于小規(guī)模的虛擬機(jī)部署方案。但是，在分布式系統(tǒng)上進(jìn)行資源調(diào)度是NP問(wèn)題，該問(wèn)題無(wú)法在多項(xiàng)式時(shí)間內(nèi)獲得最優(yōu)解。尤其在規(guī)模較大時(shí)，上述算法難以在有效時(shí)間內(nèi)得到最優(yōu)解。因此，另一種基于啟發(fā)式的次優(yōu)算法被提出。②基于啟發(fā)式的次優(yōu)算法，是指在可接受的范圍內(nèi)得到可行解來(lái)處理實(shí)際問(wèn)題。例如文獻(xiàn)[4]中提出了模擬退火算法(simulated annealing algorithm，SAA)，模擬物理學(xué)中的冷卻過(guò)程通過(guò)內(nèi)外循環(huán)使其達(dá)到熱平衡狀態(tài)。即用更優(yōu)解替換原有解，經(jīng)過(guò)多次迭代找到較好的分配方案；文獻(xiàn)[5]中介紹了遺傳算法(genetic algorithm，GA)，通過(guò)初始化、交叉和變異算子，經(jīng)過(guò)多次迭代最終找到較優(yōu)解；文獻(xiàn)[6]提出的粒子群優(yōu)化(particle swarm optimization，PSO)算法通過(guò)在空間中找尋適應(yīng)度最優(yōu)的粒子，找到最佳位置，從而更好地進(jìn)行資源調(diào)度；在蛙跳算法(shuffled frog leaping algorithm，SFLA)中，通過(guò)子種群群內(nèi)通信和群間通信，最差解不斷定向跳躍至最好解的位置，它作為一個(gè)有效的算法被應(yīng)用在各種資源調(diào)度中，如聚類(lèi)、演化查詢(xún)、排序優(yōu)化、推薦系統(tǒng)等[7]。但是上述算法大多不具有約束能力，尤其在規(guī)模較大時(shí)，容易陷入局部最優(yōu)，難以得到全局最優(yōu)解。為了進(jìn)一步提高算法性能，本文對(duì)SFLA進(jìn)行了改進(jìn)，以期為云計(jì)算資源調(diào)度建模提供思路。

1 問(wèn)題描述

1.1 問(wèn)題說(shuō)明

執(zhí)行一個(gè)大型工作流，首先將其分成多個(gè)小任務(wù)，并將其映射在虛擬資源上。云工作流的資源調(diào)度一般分為3個(gè)步驟：①提供可以用來(lái)分配給任務(wù)的可用資源；②將任務(wù)映射到滿(mǎn)足需求的資源上；③按照之前的映射方案將任務(wù)分配到相應(yīng)資源上運(yùn)行。本文所提出的算法結(jié)合了資源提供和調(diào)度的問(wèn)題，并將它們作為一個(gè)問(wèn)題，使用改進(jìn)的蛙跳算法加以解決。目的就是將工作流中的每個(gè)任務(wù)映射到更好的服務(wù)資源，使總執(zhí)行成本最小化，并將完成時(shí)間保持在最后期限內(nèi)。

工作流可以描述為有向無(wú)環(huán)圖(T,E,D)，其中，點(diǎn)集合T表示業(yè)務(wù)應(yīng)用的任務(wù)集合；E表示任務(wù)之間的依賴(lài)關(guān)系，即沿邊緣方向的權(quán)重值(邊緣權(quán)重)；最后期限D(zhuǎn)表示工作流應(yīng)該完成的最長(zhǎng)執(zhí)行時(shí)間。虛擬機(jī)的處理能力根據(jù)每秒浮點(diǎn)運(yùn)算次數(shù)來(lái)確定，并且可從云資源提供者處獲得。基于虛擬機(jī)的處理能力，可以計(jì)算給定虛擬機(jī)上任務(wù)的執(zhí)行時(shí)間。如果T1在任務(wù)圖中位于T2之前，即在T2任務(wù)開(kāi)始執(zhí)行之前要完成T1任務(wù)，則從節(jié)點(diǎn)1到節(jié)點(diǎn)2存在有向邊。沒(méi)有傳入邊的節(jié)點(diǎn)表示進(jìn)入任務(wù)，沒(méi)有傳出邊的節(jié)點(diǎn)表示退出任務(wù)。一種工作流示例如圖1所示。

圖1 一種工作流示例Fig.1 A workflow example

圖2描繪了與圖1任務(wù)圖相對(duì)應(yīng)的調(diào)度示例。

VM1T1T4T6VM2T2T5T9VM3T3T7T8

圖2調(diào)度示例
Fig.2 Example of scheduling

工作流中常見(jiàn)的優(yōu)化標(biāo)準(zhǔn)是任務(wù)完成時(shí)間的最小化、成本最小化、資源利用最大化、滿(mǎn)足目標(biāo)約束等。除此之外，還需要調(diào)度算法來(lái)協(xié)調(diào)工作流中的任務(wù)依賴(lài)性，即在某些情況下，只有當(dāng)工作流中的前一個(gè)任務(wù)已完成執(zhí)行時(shí)，才能執(zhí)行下一個(gè)任務(wù)。另外，云計(jì)算環(huán)境對(duì)于工作流更為有益，因?yàn)樗褂脩?hù)能直接請(qǐng)求業(yè)務(wù)所需的資源，并且由用戶(hù)控制的調(diào)度器來(lái)調(diào)度任務(wù)[8]。這使得用戶(hù)能夠僅在需要時(shí)分配資源，并且一旦分配，該資源可以隨后用于執(zhí)行多種任務(wù)。因此，高效的資源調(diào)度是在云中實(shí)現(xiàn)高性能的主要挑戰(zhàn)[9]。假設(shè)各種類(lèi)型的VM由IaaS提供商提供，用戶(hù)可以根據(jù)需求按需租用它們。本文提出的調(diào)度算法定義任務(wù)和資源之間的映射，并列出了應(yīng)租借的VM的數(shù)量以及應(yīng)租用的時(shí)間長(zhǎng)度。目的是使總執(zhí)行成本最小化并將完成時(shí)間保持在期限內(nèi)。

1.2 基于重建策略改進(jìn)蛙跳算法

2003年，Eusuff和Lansey提出SFLA[10]，旨在模仿一群青蛙的行為，尋找隨機(jī)分布在池塘里的石頭上的食物。它匯集了基于遺傳進(jìn)化的模因演算法(memetic algorithm，MA)以及基于社會(huì)行為的粒子群優(yōu)化(particle swarm optimization，PSO)算法，其已被用于解決諸如資源調(diào)度、車(chē)間作業(yè)生產(chǎn)調(diào)度等許多復(fù)雜的優(yōu)化問(wèn)題。

在傳統(tǒng)的蛙跳算法中，初始種群由一組在池塘中尋找食物的青蛙組成。搜索食物包括2個(gè)交替的過(guò)程：①初始種群被分為若干個(gè)子種群，在子種群內(nèi)青蛙進(jìn)行群內(nèi)通信；②子種群發(fā)展到一定階段，它們之間進(jìn)行群間通信。這個(gè)過(guò)程中，只有最差解被定向跳躍至最好解的位置。然而，由于種群是隨機(jī)生成的，即使適應(yīng)度最好的青蛙也可能不具有真正的全局性，從而易導(dǎo)致局部最優(yōu)。越是食物密集的地方越容易陷入局部最優(yōu)，并且搜索食物的青蛙的跳躍動(dòng)作取決于個(gè)體的慣性運(yùn)動(dòng)，因此，在最好解的周?chē)赡艽嬖诰哂懈嗍澄锏奈恢谩＿@可以通過(guò)更新最佳蛙的慣性矩來(lái)實(shí)現(xiàn)。

因此，我們?cè)O(shè)計(jì)了一種重建策略，重建策略流程如圖3所示。在得到的最好解周?chē)译S機(jī)位置，進(jìn)行適應(yīng)度比較。這種方法有助于最好解跳躍到其附近有更多食物的新位置。在每個(gè)模因中，對(duì)于每次迭代確定最佳和最差解。對(duì)于模因中的替代迭代，最好的青蛙試圖重新建立自我地位以增強(qiáng)他們的位置，而最壞的青蛙努力通過(guò)所有迭代中的信息交互來(lái)改善他們的位置。該策略可以用于解決任何種類(lèi)的離散或連續(xù)優(yōu)化問(wèn)題。對(duì)于任務(wù)調(diào)度，通過(guò)在最佳解決方案處搜索更好的位置來(lái)執(zhí)行重建。如果適應(yīng)度改進(jìn)，則保留適配的解;否則，最好的青蛙保持在其原始位置。

圖3 重建策略流程圖Fig.3 Reconstruction strategy flow chart

圖3中，rand( )函數(shù)用來(lái)生成0到1之間的隨機(jī)數(shù)；Xqb為全局適應(yīng)度最好的青蛙，即全局最好解；Xjb為子種群中適應(yīng)度最好的青蛙，即局部最好解；Xw為子種群中適應(yīng)度最差的青蛙，即局部最差解；a是適合于該問(wèn)題的常數(shù)值。

改進(jìn)的蛙跳算法中的演變是沿著2個(gè)維度進(jìn)行的：①通過(guò)在種群迭代進(jìn)化期間恢復(fù)最好解的位置；②通過(guò)信息交換定期改善最差解的位置。因此，該算法已經(jīng)被修改為如下所示。步驟1到步驟5保持原算法不變。

步驟1將青蛙的大小設(shè)置為d；

步驟2用隨機(jī)位置初始化青蛙種群P，計(jì)算每只青蛙的適應(yīng)度；

步驟3按照其適應(yīng)度的降序?qū)ΨN群P進(jìn)行排序；

步驟4確定全局最好解Xqb的適應(yīng)度為fqb；

步驟5將P分成m個(gè)子種群；

步驟6對(duì)于每個(gè)子種群

①確定局部最好解Xjb的適應(yīng)度為fjb，局部最差解Xw的適應(yīng)度為fw；

②通過(guò)替代迭代嘗試改善局部最好解的位置(即周期性n=2)；

③新的局部最好解Xn=重建Xjb；

④如果局部最好解Xn的適應(yīng)度提高，用新青蛙替換原來(lái)的青蛙；

⑤使用(1)式相對(duì)于局部最好解Xjb，改善局部最差解的位置。如果適應(yīng)度改善，更新局部最差解的位置。

跳躍步長(zhǎng)為

Dd=rand×(Xjb-Xw)

(1)

新位置為

(2)

如果局部最差解的新位置改進(jìn)，即適應(yīng)度更高，則其代替最差解；

⑥否則，使用方程(3)相對(duì)于全局最好解Xqb，改善局部最差解的位置。如果位置改善，更新局部最差解的位置；

跳躍步長(zhǎng)為

Dd=rand×(Xqb-Xw)

(3)

新位置為

(4)

⑦否則，使用新的隨機(jī)生成的解決方案替換最差解；

步驟7將各進(jìn)化后的子種群混合，按照其適應(yīng)度的降序?qū)ΨN群P進(jìn)行重新排序；

步驟8檢查是否滿(mǎn)足收斂要求。是，則結(jié)束算法；否則，轉(zhuǎn)到步驟3。

在步驟6中，通過(guò)子種群內(nèi)的迭代，確定最好解和最差解。對(duì)于子種群中的迭代進(jìn)化，局部最好解嘗試重建以增強(qiáng)他們的位置，而局部最差解努力通過(guò)所有迭代中的信息交換改善他們的位置。

2 資源調(diào)度方案

當(dāng)前用于資源調(diào)度的解決方案面臨成本效率比不高的問(wèn)題，需要探索更好的解決方案。本文提出了一種基于改進(jìn)蛙跳算法的方案，所述算法在最小化成本的同時(shí)，具有滿(mǎn)足最后期限約束的能力。

2.1 問(wèn)題建模

下面將調(diào)度問(wèn)題建模為改進(jìn)蛙跳算法問(wèn)題，假設(shè)將第k個(gè)工作流中的d個(gè)任務(wù)調(diào)度到r個(gè)資源上。工作流被表示為青蛙，每只青蛙攜帶一個(gè)由d個(gè)記憶模塊構(gòu)成的模因，對(duì)應(yīng)于任務(wù)工作流。第k個(gè)蛙F(k)表示為d個(gè)記憶值的向量。單元格的數(shù)量(即單元的維度)d，由工作流中的任務(wù)數(shù)量確定。青蛙的坐標(biāo)范圍和數(shù)量由資源的數(shù)量r決定。此外，可用資源的數(shù)量r表示搜索中允許青蛙移動(dòng)的空間中的食物量。因此，坐標(biāo)的值在0和其可用的資源數(shù)r之間。青蛙的位置代表任務(wù)到資源的映射。例如，一個(gè)青蛙是10維的，則其位置由10個(gè)坐標(biāo)表示，因?yàn)樗硎揪哂?0個(gè)任務(wù)的工作流，坐標(biāo)值如表1所示。如果有4個(gè)資源可用，那么青蛙的每個(gè)坐標(biāo)可以具有在0～4的值。任務(wù)與資源的映射關(guān)系如表2所示，這里，第7坐標(biāo)的值1.9表示任務(wù)7已經(jīng)被映射到資源2。符號(hào)Mi指青蛙的第i個(gè)坐標(biāo)，并且對(duì)應(yīng)于工作流中的任務(wù)ti。

表1 坐標(biāo)值Tab.1 Coordinate values

表2 任務(wù)與資源映射關(guān)系表Tab.2 Task and resource mapping relationship table

2.2 調(diào)度方案生成算法

本文所提出的算法目標(biāo)是最小化工作流的總執(zhí)行成本，并且滿(mǎn)足用戶(hù)要求的截止時(shí)間。使用改進(jìn)的SFLA獲得調(diào)度和資源供應(yīng)問(wèn)題的解決方案包括以青蛙形式生成調(diào)度方案，隨后使用適應(yīng)度函數(shù)計(jì)算蛙的適應(yīng)度的值。適應(yīng)度函數(shù)是基于優(yōu)化問(wèn)題的目標(biāo)，因此，我們?cè)u(píng)估每個(gè)調(diào)度計(jì)劃的總執(zhí)行成本，并將其用作適應(yīng)度函數(shù)。

假定最初v為應(yīng)用程序租用虛擬機(jī)的數(shù)量，即在工作流中并行執(zhí)行任務(wù)的數(shù)量。假設(shè)工作流中的任務(wù)集由數(shù)組T給出。用文獻(xiàn)[11]中的方法計(jì)算每個(gè)資源上的任務(wù)ti所花費(fèi)的時(shí)間，可以在初始虛擬機(jī)組集合(initial virtual machine，IVM)中計(jì)算。時(shí)間由n×v矩陣ETM表示，其中，n是工作流中的任務(wù)數(shù)量，v是IVM中虛擬機(jī)的數(shù)量。此外，工作流中的任務(wù)可以依賴(lài)于工作流中用于其輸出的其他任務(wù)。因此，我們通過(guò)n×n矩陣DM表示工作流的依賴(lài)性，如果任務(wù)ti取決于任務(wù)tj(任務(wù)tj是子任務(wù))，則DM[i][j]=1，否則為0。將任務(wù)的輸出傳送到其子任務(wù)所花費(fèi)的時(shí)間存儲(chǔ)在n×n矩陣TTM中。

通過(guò)遍歷青蛙的每個(gè)記憶類(lèi)型來(lái)評(píng)估青蛙的適應(yīng)度，的維度對(duì)應(yīng)于任務(wù)ti，并且其值對(duì)應(yīng)于由IVM給出的虛擬機(jī)。任務(wù)開(kāi)始的時(shí)間取決于它所依賴(lài)任務(wù)的完成時(shí)間和虛擬機(jī)可用的時(shí)間。算法使用的符號(hào)說(shuō)明如表3所示。

表3 符號(hào)說(shuō)明Tab.3 Symbol description

算法偽代碼如下。

輸入：用戶(hù)提交的工作流應(yīng)用，設(shè)置初始虛擬機(jī)組。

輸出：總執(zhí)行成本和總執(zhí)行時(shí)間。

1. 初始化參數(shù)TEC=0, TST=0, LVM=Φ: flag=0；

2. 計(jì)算時(shí)間ETM，TTM；

3. 添加依賴(lài)關(guān)系DM；

4. For 0 < id-1

i.初始化任務(wù)和虛擬機(jī)，令ti=T[i]，VM(i)= IVM[Mi]，flag=0

ii.for 0 < jd-1；//定義任務(wù)ti的開(kāi)始時(shí)間

IfDM[i][j]==1,{flag=1; STi=max(STi,CTj,CTVM (VM(i))}

If flag==0 STi=CTVM(VM(i))

iii.在資源上執(zhí)行任務(wù)所用時(shí)間exe_time=ETM(ti, VM(i))；

iv. for 0 < jd-1；//定義傳送時(shí)間

IfDM[j][i]==1 and VM(j)< >VM(i)

Trans_time+=Trans_time+TTM[i][j]

v.任務(wù)在虛擬機(jī)上的總運(yùn)行時(shí)間Tot_time (i, VM(i))=exe_time+trans_time

vi. CT(i, VM(i))=STi+ Tot_time (i, VM(i))；//任務(wù)的完成時(shí)間

vii. If VM(i)LVM, add it, STVM (VM(i))=STi；//租用VM的開(kāi)始時(shí)間

viii. CTVM (VM(i))= Tot_time (i, VM(i))+STi；//虛擬機(jī)的租期完成時(shí)間

5. 計(jì)算每個(gè)VM的總執(zhí)行成本和總執(zhí)行時(shí)間，令cLVM；

i. TEC=TEC+((CTVM[c]-STVM[c])*Cost[c])

ii. if(CTVM[c]>TST)

該算法提供了需要為工作流租用的VM的數(shù)量。每個(gè)任務(wù)ti與一個(gè)虛擬機(jī)VM(i)相關(guān)聯(lián)，VM(i)的開(kāi)始和完成時(shí)間分別被給定為STVM和CTVM。此后，算法計(jì)算當(dāng)前解決方案的總執(zhí)行成本(TEC)和總執(zhí)行時(shí)間(TST)。因此，對(duì)應(yīng)于特定青蛙的調(diào)度方案由任務(wù)到VM的映射以及VM的開(kāi)始和結(jié)束時(shí)間給出。

2.3 資源調(diào)度算法整體步驟

改進(jìn)的SFLA和調(diào)度方案生成算法被組合以得到接近最優(yōu)的調(diào)度。在改進(jìn)的SFLA中，根據(jù)總執(zhí)行成本來(lái)計(jì)算蛙的適應(yīng)度，其通過(guò)使用上面給出的調(diào)度方案生成算法生成調(diào)度方案來(lái)評(píng)估。如果對(duì)應(yīng)青蛙的調(diào)度時(shí)間超過(guò)最后期限，改進(jìn)的SFLA用新的隨機(jī)生成解替換該青蛙。以這種方式，改進(jìn)的SFLA僅保留滿(mǎn)足期限約束的調(diào)度方案。

步驟1利用調(diào)度方案生成算法產(chǎn)生工作流的原始調(diào)度；

步驟2通過(guò)改進(jìn)的SFLA，保留滿(mǎn)足期限約束的調(diào)度方案。

3 仿真分析

本文使用JAVA模擬器和3個(gè)不同大小的工作流來(lái)評(píng)估性能。每個(gè)模擬仿真進(jìn)行25次，并且在SFLA和PSO算法中實(shí)現(xiàn)以作比較?？刂茀?shù)如表4所示。

表4 控制參數(shù)Tab.4 Control parameters

假定從一個(gè)資源到另一個(gè)資源具有不同的任務(wù)執(zhí)行時(shí)間[12]。工作流的最后期限是由對(duì)每個(gè)工作流執(zhí)行的最小和最大執(zhí)行時(shí)間的平均值得出。計(jì)算最大執(zhí)行時(shí)間的方法是，租用最少時(shí)間的單個(gè)虛擬機(jī)，并在其上執(zhí)行所有工作流任務(wù)[13-14]。通過(guò)對(duì)每個(gè)工作流任務(wù)使用一個(gè)最快類(lèi)型的虛擬機(jī)來(lái)計(jì)算最小執(zhí)行時(shí)間。

1)周期性參數(shù)“n”控制執(zhí)行重建策略的頻率，也就是最佳青蛙試圖改善其位置的次數(shù)。n=1的值意味著最佳青蛙?chē)L試在每次迭代中重新定位。本文進(jìn)行了具有不同參數(shù)設(shè)置的一系列實(shí)驗(yàn)，最終確定了最佳參數(shù)組合。改進(jìn)的蛙跳算法中，周期參數(shù)的取值為n=2，迭代次數(shù)定為50。

2)任務(wù)流的大小對(duì)總執(zhí)行成本的影響。本研究在3種不同工作流程上進(jìn)行：工作流1為Montage，工作流2為L(zhǎng)IGO，工作流3為Cyber Shake。所有這些工作流具有不同的結(jié)構(gòu)、不同的數(shù)據(jù)和計(jì)算特性。Montage工作流程是一個(gè)天文學(xué)應(yīng)用程序，用于根據(jù)一組輸入圖像生成天空的自定義馬賽克。大多數(shù)任務(wù)是I / O密集型，不需要高CPU處理能力。LIGO工作流程來(lái)自物理學(xué)領(lǐng)域，目的是檢測(cè)引力波。此工作流主要是CPU密集型任務(wù)，需要大量?jī)?nèi)存。Cyber Shake用于通過(guò)生成合成地震圖來(lái)區(qū)分地震危害，并且是具有高CPU和內(nèi)存要求的數(shù)據(jù)密集型工作流。除了給出的3個(gè)應(yīng)用工作流，再隨機(jī)生成其他2個(gè)工作流：①具有少量任務(wù)(任務(wù)= 8)；②具有大量任務(wù)(任務(wù)= 150)。我們?cè)诜抡嬷性O(shè)定云資源的時(shí)間為10，20和30單位，處理器統(tǒng)一設(shè)為4，使用的其他參數(shù)列于表5中。

表5 仿真參數(shù)Tab.5 Simulation parameters

圖4描述了由PSO，SFLA和改進(jìn)的SFLA獲得的總執(zhí)行成本。從結(jié)果中可以觀(guān)察到，與PSO相比，SFLA能夠?qū)⒖倛?zhí)行成本平均降低約42%，改進(jìn)的蛙跳算法平均降低約48%。

圖4 總執(zhí)行成本vs不同任務(wù)數(shù)的工作流Fig.4 Total execution costs vs workflow with different tasks

3)處理器數(shù)量對(duì)總執(zhí)行成本的影響。本文進(jìn)行了嚴(yán)格仿真來(lái)研究不同數(shù)量的資源對(duì)不同大小工作流程的影響。對(duì)于每個(gè)工作流，處理器的數(shù)量在1～10內(nèi)選定；任務(wù)量的大小分別為100，200，300；處理器數(shù)量分別為 2， 4，6，8，10；最大迭代次數(shù)為50。仿真結(jié)果如圖5所示。

圖5 總執(zhí)行成本vs所使用的處理器的數(shù)量Fig.5 Total execution costs vs the number of processors used

從結(jié)果可以觀(guān)察到，執(zhí)行的時(shí)間隨著用于工作流的資源數(shù)量的增加而增加。另外，可以看出，在某些情況下，PSO的性能優(yōu)于SFLA，在其他情況下趨勢(shì)逆轉(zhuǎn)。然而，改進(jìn)的蛙跳算法一直優(yōu)于PSO和SFLA。在仿真期間，隨著較高數(shù)量的資源被用于執(zhí)行，總執(zhí)行時(shí)間減少。這些結(jié)果沒(méi)有列入，因?yàn)樗械臅r(shí)間規(guī)劃都符合截止日期的限制。

4)算法的可擴(kuò)展性評(píng)估。我們使用極大工作流的來(lái)驗(yàn)證算法的可擴(kuò)展性，采用100個(gè)處理器，用于執(zhí)行大小變化為300，500和1 000的隨機(jī)工作流。極大工作流下的總執(zhí)行成本比較如圖6所示。

圖6 極大工作流下的總執(zhí)行成本比較Fig.6 Comparison of total execution costs under maximum workflow

從圖6可以看出，隨著工作流大小的增加，PSO和SFLA給出可比的性能。與PSO和SFLA相比，改進(jìn)的SFLA將總執(zhí)行成本平均降低了約78%，顯示其巨大的性能優(yōu)勢(shì)。因此，本文所提算法是高度可擴(kuò)展的，適于在IaaS云中執(zhí)行較大的工作流應(yīng)用。

5)不同算法的吞吐量比較。進(jìn)行了仿真來(lái)研究不同數(shù)量的資源節(jié)點(diǎn)對(duì)吞吐量的影響。對(duì)于每個(gè)工作流，處理器的數(shù)量在1～10內(nèi)選定，仿真結(jié)果如圖7所示。

從圖7中觀(guān)察到，雖然處理器數(shù)目較少時(shí)，三類(lèi)算法吞吐量相差不大。但是，隨著處理器數(shù)目的增多，本文算法的優(yōu)勢(shì)體現(xiàn)出來(lái)，并且不斷增強(qiáng)。這更適合于大數(shù)據(jù)時(shí)代的挑戰(zhàn)，長(zhǎng)遠(yuǎn)來(lái)看，本文算法的吞吐量更高。

6)關(guān)于魯棒性和開(kāi)銷(xiāo)的推斷。所提出的算法的魯棒性可以從這樣的事實(shí)推斷，本文算法能夠較好地滿(mǎn)足具有不同數(shù)量的任務(wù)工作流的期限約束。此外，與PSO和SFLA相比，改進(jìn)的SFLA能夠?qū)⒖倛?zhí)行成本降低高達(dá)78%，顯示其良好的魯棒性。另外，成本的減少會(huì)增加執(zhí)行時(shí)間的開(kāi)銷(xiāo)，但是本文的算法對(duì)最小化執(zhí)行成本是主要關(guān)注點(diǎn)，故而主要適用于優(yōu)先考慮執(zhí)行成本的情況。

圖7 不同算法的吞吐量比較Fig.7 Comparison of throughput of different algorithms

4 結(jié) 論

本文提出一種改進(jìn)的蛙跳算法，用于云環(huán)境下的資源調(diào)度和調(diào)度。在滿(mǎn)足指定目標(biāo)約束的同時(shí)，優(yōu)化工作流的總執(zhí)行成本。對(duì)各種工作流進(jìn)行了仿真，并且與SFLA和PSO算法的性能比較，仿真分析表明，改進(jìn)的蛙跳算法在降低的工作流總體執(zhí)行時(shí)間方面優(yōu)于其他算法。

[1] ZOU D, XIANG Y, MIN G. Privacy preserving in cloud computing environment[J].Security & Communication Networks, 2016, 9(15):2752-2753.

[2] LI Y, TANG X, CAI W. Dynamic Bin Packing for On-Demand Cloud Resource Allocation[J]. IEEE Transactions on Parallel & Distributed Systems, 2016, 27(1):157-170.

[3] MA J, LI W, FU T, et al. A Novel Dynamic Task Scheduling Algorithm Based on Improved Genetic Algorithm in Cloud Computing[M].Berlin：Springer-Verlag , 2016:184-186.

[4] YOUNG L, MCGOUGH S, NEWHOUSE S, et al. Scheduling Architecture and Algorithms within the ICENI Grid Middleware[C]//RR Holman.UK e-science all hands meeting.Nottingham：Pergamon Press Ltd，2003:5-12.

[5] 賁可榮,張彥鐸.人工智能[M].2版.北京：清華大學(xué)出版社, 2013：134-142.

BEN Kerong, ZHANG Yanduo. Artificial Intelligence. Second Edition[M].2nd.Beijing:Tsinghua University Press, 2013：134-142.

[6] ALRASHIDI M R, ELHAWARY M E. A survey of particle swarm optimization applications in electric power systems[J]. Evolutionary Computation, IEEE Transactions on, 2009, 13(4): 913-918.

[7] ZHU G Y, ZHANG W B. An improved Shuffled Frog-leaping Algorithm to optimize component pick-and-place sequencing optimization problem[J]. Expert Systems with Applications, 2014, 41(15):6818-6829.

[8] BOTTA A, DE DONATO W, PERSICO V, et al. Integration of Cloud computing and Internet of Things[J].Future Generation Computer Systems, 2016, 56(C):684-700.

[9] ZHANG Q, YU G U, YING X U, et al. Feature selection for SAR images using the hybrid intelligent optimization algorithm[J]. Journal of Remote Sensing, 2016，38(18)：110-119.

[10] EUSUFF M M, LANSEY K E. LANSEY, K. Optimization of Water Distribution Network Design Using the Shuffled Frog Leaping Algorithm. Journal of Water Resources Planning and Management[J].Journal of Water Resources Planning & Management, 2003, 129(3):210-225.

[11] JUVE G, CHERVENAK A, DEELMAN E, et al. Characterizing and profiling scientific workflows[J]. Future Generation Computer Systems, 2013, 29(3):682-692.

[12] KOZERA R, OKULICKADF, NOAKES L. Integrated Parallel 2D-Leap-Frog Algorithm for Noisy Three Image Photometric Stereo[C]//PR Jones.PSIVT 2015 Workshops. Berlin：Springer-Verlag，2016：73-87.

[13] 黃婷婷,梁意文.云工作流任務(wù)調(diào)度的模擬退火遺傳改進(jìn)算法[J].微電子學(xué)與計(jì)算機(jī), 2016, 33(1):42-46.

HUANG Tingting, LIANG Yiwen.Improved Anomalous Improvement Algorithm for Task Scheduling of Cloud Workflow[J]. Microelectronics and Computer, 2016, 33(1): 42-46.

[14] FU X, YELIANG C, ZHU L, et al. Deadline based scheduling for data-intensive applications in clouds[J]. Journal of China Universities of Posts & Telecommunications, 2016, 23(6):8-15.

The National Natural Science Foundation of China(61302099)

Optimizationofcloudworkflowschedulingalgorithmbasedonreconstructionstrategy

LIN Haitao, JIANG Donghan

School of Electronic Engineering, Naval University of Engineering, Wuhan 430033, P.R. China)

In order to further improve the performance of the algorithm, this paper proposes an improved leapfrog algorithm, which is combined with the scheduling scheme to provide optimal scheduling for cloud workflow resource allocation. First of all, by means of joining the reconstruction strategy to improve the randomness of data the local search in the frog leaking algorithm the local optimal is effectively prevented. Secondly, we study the scheduling scheme generation algorithm, and get the optimal scheduling with the improved algorithm. Finally, the simulation experiment is carried out using Java simulator, and compared with the particle swarm optimization algorithm and the traditional frog leap algorithm. It is found that the proposed method can minimize the total execution cost while satisfying the longest deadline constraint.

frog leaping algorithm; resource scheduling; cloud workflow; reconstruction strategy

10.3979/j.issn.1673-825X.2017.06.017

2017-02-15

2017-06-05

姜棟瀚 457176001@qq.com

國(guó)家自然科學(xué)基金(61302099)

TN93

A

1673-825X(2017)06-0822-08

林海濤(1974 -)，男，山東濰坊人，副教授，博士，主要研究方向?yàn)榫W(wǎng)絡(luò)規(guī)劃與管理。E-mail：1174756267@qq.com。

姜棟瀚(1992 -)，男，山東煙臺(tái)人，碩士研究生，主要研究方向?yàn)橥ㄐ偶夹g(shù)與網(wǎng)絡(luò)。E-mail：457176001@qq.com。

(編輯：王敏琦)