国产日韩欧美一区二区三区三州_亚洲少妇熟女av_久久久久亚洲av国产精品_波多野结衣网站一区二区_亚洲欧美色片在线91_国产亚洲精品精品国产优播av_日本一区二区三区波多野结衣 _久久国产av不卡

?

公有云環(huán)境基于路徑聚簇的工作流費(fèi)用優(yōu)化算法

2016-09-23 05:51王彬
現(xiàn)代計(jì)算機(jī) 2016年3期
關(guān)鍵詞:花費(fèi)實(shí)例綜合性

王彬

(四川大學(xué)計(jì)算機(jī)學(xué)院,成都610065)

公有云環(huán)境基于路徑聚簇的工作流費(fèi)用優(yōu)化算法

王彬

(四川大學(xué)計(jì)算機(jī)學(xué)院,成都610065)

0 引言

計(jì)算科學(xué)家進(jìn)行海量數(shù)據(jù)的復(fù)雜模擬和精確分析,常常用工作流來解決該問題[1]。航天學(xué)的Montage將一系列的FITS(彈性圖像傳輸系統(tǒng),F(xiàn)lexible Image Transport System)格式的圖像合成外天空的星云圖;地震學(xué)的CyberShake利用PSHA(概率地震災(zāi)害分析,Probabilistic Seismic Hazard Analysis)技術(shù)形象地刻畫地震災(zāi)害情況。這些工作流需要大量的計(jì)算、內(nèi)存、帶寬等資源,Montage是帶寬密集型的,CyberShake是內(nèi)存密集型和帶寬密集型的。由于資源需求過大,工作流的高效資源配置難度增加。

虛擬化、高速網(wǎng)絡(luò)和安全技術(shù)的成熟,促使云計(jì)算的蓬勃發(fā)展。由于云計(jì)算的彈性使用、按使用量計(jì)費(fèi)的特性,企業(yè)和機(jī)構(gòu)逐漸將自身的應(yīng)用遷移至公有云。云服務(wù)提供商擁有數(shù)以萬計(jì)的主機(jī)和存儲設(shè)備,向云用戶提供充足的計(jì)算資源和存儲資源。由于工作流對計(jì)算資源和存儲資源的海量需求,因而將工作流遷移至公有云平臺執(zhí)行[2-3]。

工作流在公有云的資源分配,對于云服務(wù)提供商高效地使用公有云資源和計(jì)算科學(xué)家降低工作流的執(zhí)行費(fèi)用,是至關(guān)重要的。因此,資源分配時應(yīng)充分考慮工作流本身的特性和公有云資源的特征,從而提高資源分配效率,降低工作流執(zhí)行費(fèi)用。

1 相關(guān)工作

目前,對于傳統(tǒng)的工作流調(diào)度算法,由于未考慮綜合工作流的資源需求特征和云服務(wù)提供商提供的供給資源的特征,使得工作流的任務(wù)資源分配低效,云用戶執(zhí)行工作流的費(fèi)用普遍很高,無法真正地將工作流部署至公有云環(huán)境[4]。Amazon Simple Workflow Service使用RoundRobin算法進(jìn)行工作流的調(diào)度,將工作流的任務(wù)依次分配給未使用的虛擬機(jī)實(shí)例,并未考慮虛擬機(jī)實(shí)例的擁有計(jì)算資源。異構(gòu)最早完成時間(HEFT,Heterogeneous Earliest Finish Time)[5]調(diào)度算法常用以工作流的調(diào)度,降低工作流的執(zhí)行時間,并未能考慮公有云的計(jì)費(fèi)和虛擬機(jī)間的性能干擾,導(dǎo)致執(zhí)行工作流費(fèi)用偏高。由于工作流的數(shù)據(jù)通信量過大,國內(nèi)外學(xué)者也相繼提出了降低通信開銷的調(diào)度算法,主要思想是通過聚簇不同的任務(wù)成為新的任務(wù)集合,然后統(tǒng)一分配至同一資源,從而降低數(shù)據(jù)的通信量。聚簇算法分為水平聚簇和路徑聚簇,水平聚簇指將處于工作流同一層的任務(wù)聚簇,例如水平運(yùn)行時間平衡算法 (HRB,Horizontal Runtime Balancing)[6]、水平影響因子平衡算法(HIFB,Horizontal Impact Factor Balancing)[7]路徑聚簇指將具有數(shù)據(jù)依賴關(guān)系的任務(wù)合合并,比如路徑啟發(fā)式聚簇算法(PCH,Path Clustering Heuristic)[8]。文獻(xiàn)[6-8]并未考慮云環(huán)境下的彈性資源配置、同構(gòu)網(wǎng)絡(luò)、按使用量付費(fèi)的特性,使得公有云執(zhí)行工作流的費(fèi)用增加,導(dǎo)致機(jī)構(gòu)執(zhí)行效率降低。

由于工作流的任務(wù)個數(shù)多、任務(wù)依賴和資源需求異構(gòu)性,使得工作流的資源分配是NP-問題。針對數(shù)據(jù)密集型的工作流調(diào)度算法普遍存在以下問題:一是未考慮任務(wù)間的數(shù)據(jù)通信,導(dǎo)致依賴任務(wù)間延遲過大,如基于HEFT調(diào)度算法;而是未考慮公有云的計(jì)費(fèi)策略,導(dǎo)致工作流的執(zhí)行費(fèi)用過高,如基于PCH調(diào)度算法。本文相較其他算法創(chuàng)新之處在于通過對工作流關(guān)鍵路徑的任務(wù),根據(jù)任務(wù)優(yōu)先級和最早結(jié)束時間來進(jìn)行聚簇,根據(jù)工作流的任務(wù)需求特性和資源能力及相關(guān)費(fèi)用,找出費(fèi)用最低且能盡快完成任務(wù)的資源進(jìn)行放置任務(wù),從而降低工作流的總運(yùn)行時間和運(yùn)行費(fèi)用,降低執(zhí)行機(jī)構(gòu)的費(fèi)用支出,提高執(zhí)行機(jī)構(gòu)的執(zhí)行效率。

2 基于改進(jìn)PCH的費(fèi)用優(yōu)化調(diào)度算法

工作流workflow={T,D}可用有向無環(huán)圖DAG={V,E}進(jìn)行表示。任務(wù)Task的計(jì)算量等同于結(jié)點(diǎn)Vertex的權(quán)重,任務(wù)間的數(shù)據(jù)通信量等同于邊Edge的權(quán)重。任務(wù)只有在它的所有前驅(qū)任務(wù)執(zhí)行完成并且所需數(shù)據(jù)準(zhǔn)備就緒后,才能開始執(zhí)行。沒有前驅(qū)的任務(wù)節(jié)點(diǎn)成為開始結(jié)點(diǎn),沒有后驅(qū)的任務(wù)節(jié)點(diǎn)成為結(jié)束結(jié)點(diǎn)。當(dāng)存在多個開始結(jié)點(diǎn)時,新增一個虛擬開始結(jié)點(diǎn)和相應(yīng)的依賴關(guān)系;同理,當(dāng)存在多個結(jié)束結(jié)點(diǎn)時,新增一個虛擬結(jié)束結(jié)點(diǎn)和相應(yīng)的依賴關(guān)系。

公有云向云用戶提供可彈性計(jì)算、按使用量付費(fèi)的虛擬機(jī)實(shí)例資源。每類虛擬機(jī)實(shí)例資源擁有不同的計(jì)算資源CPU、內(nèi)存資源MEM、網(wǎng)絡(luò)帶寬資源BW。根據(jù)虛擬機(jī)的處理能力,公有云服務(wù)提供商制定不同的價格,并向云用戶收取多個計(jì)費(fèi)周期的費(fèi)用。需注意的是,不滿一個計(jì)算周期的時間,按照一個完整地進(jìn)行收費(fèi)。

假定,工作流的所需初始數(shù)據(jù)和輸出數(shù)據(jù)都被存放在云存儲服務(wù)里,由于數(shù)據(jù)存儲費(fèi)用和公有云和云用戶間的數(shù)據(jù)傳輸都是存在的,公有云內(nèi)部的數(shù)據(jù)傳輸是免費(fèi)的。

2.1概念定義

定義1給定一組虛擬機(jī)實(shí)例,未調(diào)度任務(wù)的最早開始執(zhí)行的時刻被稱為任務(wù)最早開始時間ESTTi(Earliest Finish Time)。工作流的任務(wù)越早執(zhí)行完成,其后繼任務(wù)被執(zhí)行的時間就會提前,因而每個任務(wù)的最早開始時間決定著整個工作流的執(zhí)行時間。任務(wù)Ti最早開始執(zhí)行時間ESTTi可由公式 (1),(2),(3),(4)計(jì)算而來。

定義2某個任務(wù)Ti的最早完成時間EFTTi,其計(jì)算如公式(5)所示。任務(wù)的最早完成時間越小,其后繼任務(wù)的開始執(zhí)行時間將提前,能有效降低工作流的執(zhí)行時間。

定義4給定一個工作流和多個虛擬機(jī)實(shí)例資源,工作流每個任務(wù)Ti放置在某個虛擬機(jī)實(shí)例VMj用∏i表示,工作流調(diào)度算法∏用公式(7)表示。

2.2基于改進(jìn)PCH的工作流調(diào)度算法

PCH調(diào)度算法從未調(diào)度的任務(wù)中選擇優(yōu)先級高和最早開始時間之和最高的進(jìn)行任務(wù)聚簇,但PCH調(diào)度并未考慮資源的使用情況和資源費(fèi)用,從而可能導(dǎo)致任務(wù)的執(zhí)行費(fèi)用增高。針對PCH的改進(jìn)主要在①針對工作流所有未調(diào)度的任務(wù)進(jìn)行優(yōu)先級和最早結(jié)束時間進(jìn)行任務(wù)排序選擇,聚簇優(yōu)先級和最早結(jié)束時間最大的任務(wù)成任務(wù)集合;②根據(jù)虛擬機(jī)的運(yùn)行情況和費(fèi)用,綜合考慮任務(wù)執(zhí)行時間和費(fèi)用的虛擬機(jī)資源進(jìn)行任務(wù)放置?;诟倪M(jìn)PCH的工作流調(diào)度算法如算法1。首先,初始化工作流所有任務(wù)的CT、EST、EFT、Pi,此時計(jì)算資源和網(wǎng)絡(luò)資源按照最好的資源進(jìn)行計(jì)算;其次,根據(jù)改進(jìn)的PCH算法聚簇任務(wù)集合,根據(jù)執(zhí)行費(fèi)用和時間選擇最優(yōu)的虛擬機(jī)實(shí)例放置任務(wù);然后,更新所有未調(diào)度的任務(wù)的EST、EFT;最后,直到所有任務(wù)都被調(diào)度完成,返回調(diào)度策略∏。

基于改進(jìn)PCH的工作流調(diào)度算法:

算法1:

Workflow Scheduling Based on Improved PCH

Input:Workflow,VMs

Output:∏

∏=?;

initialize workflow's tasks'CT,EST,EFT,Pi;

While(tasks is not empty)

get next Cluster which composed of unscheduled tasks having highest EFT and Pi on the same path;

get best resource from VMs based on smallest EFT and Cost;

schedule cluster on best resource,add task allocation to schedule;

updated unscheduled tasks’EST,EFT;

end While

return∏;

3 試驗(yàn)仿真與分析

為了驗(yàn)證提出的算法有效性與正確性,故采用CloudSim[9]模擬工作流在公有云的調(diào)度。CloudSim專業(yè)用于模擬工作負(fù)載在數(shù)據(jù)中心運(yùn)行的工具。工作流采用Pegasus[10]所產(chǎn)生的兩類科學(xué)工作流Montage和CyberShake,Montage的任務(wù)節(jié)點(diǎn)數(shù)量有 25、50、100和1000,CyberShake的任務(wù)節(jié)點(diǎn)數(shù)量有 30、50、100和1000,每個工作流的節(jié)點(diǎn)數(shù)、計(jì)算總量、依賴文件數(shù)和數(shù)據(jù)通信總量見表2。虛擬機(jī)實(shí)例類型選擇當(dāng)前A-mazon EC2的計(jì)算優(yōu)化實(shí)例,其vCPU個數(shù)為2,內(nèi)存為3.75GB,帶寬量為25Mbps,價格為0.3$/h。文獻(xiàn)[11]指由于虛擬化技術(shù),使得公有云中虛擬機(jī)實(shí)例的處理能力出現(xiàn)波動。因而,每個虛擬機(jī)每隔半小時處理器性能按照變化幅度0.054和帶寬性能按照變化幅度0.04進(jìn)行動態(tài)調(diào)整。

表1 

本文對比指標(biāo)包括執(zhí)行工作流花費(fèi)Cost和考慮時間和花費(fèi)的綜合性能比P。工作流費(fèi)用由公式(8)計(jì)算,其中,TimeVMi表示VMi所使用的時長,T表示公有云服務(wù)商計(jì)價周期,CostVMi表示VMi在一個計(jì)價周期的費(fèi)用。

綜合性能比P由公式(9)來計(jì)算,其中Cost∏為調(diào)度算法∏的費(fèi)用,MakeSpan∏為調(diào)度算法∏的執(zhí)行時間。P值越低,調(diào)度算法的綜合性能越高。

改進(jìn)算法分別與RoundRobin調(diào)度算法、HEFT調(diào)度算法、PCH調(diào)度進(jìn)行了對比。其一,在執(zhí)行工作流花費(fèi)方面,圖1是工作流Montage在不同調(diào)度算法下的花費(fèi)對比圖,圖2是工作流CyberShake在不同調(diào)度算法下花費(fèi)對比圖。PCH和改進(jìn)PCH優(yōu)于RoundRobin 和HEFT算法,而改進(jìn)PCH略低于PCH在Montage工作流調(diào)度的花費(fèi),但改進(jìn)PCH在工作流CyberShake明顯優(yōu)于PCH。其二,在執(zhí)行工作流的綜合性能比方面,圖3是工作流Montage在不同調(diào)度算法下的綜合性能比圖,圖4是工作流CyberShake在不同調(diào)度算法下的綜合性能對比圖。改進(jìn)PCH與HEFT具有較穩(wěn)定的綜合性能比,優(yōu)于RoundRobin和PCH,改進(jìn)PCH在大部分情況下優(yōu)于HEFT。因而,改進(jìn)PCH調(diào)度算法比其他算法更好地降低工作流執(zhí)行費(fèi)用,并且提高機(jī)構(gòu)的執(zhí)行效率。

圖1 工作流Montage的花費(fèi)對比圖

圖2 工作流CyberShake的花費(fèi)對比圖

圖3 工作流Montage的綜合性能比圖 

圖4 工作流CyberShake的綜合性能比圖

4 結(jié)語

本文提出了基于改進(jìn)的路徑聚簇啟發(fā)式工作流費(fèi)用優(yōu)化調(diào)度算法,根據(jù)工作流的任務(wù)資源需求和任務(wù)數(shù)據(jù)依賴關(guān)系,考慮虛擬機(jī)的處理能力和費(fèi)用,為工作流每個任務(wù)選擇合適的虛擬機(jī)實(shí)例資源,降低工作流的執(zhí)行花費(fèi),提高機(jī)構(gòu)的執(zhí)行效率。實(shí)驗(yàn)仿真表明該調(diào)度算法在工作流Montage和CyberShake上能高效地資源分配和任務(wù)調(diào)度,降低執(zhí)行工作流的花費(fèi),同時提高工作流的綜合性能比。

[1]Juve G,Chervenak A,Deelman E,et al.Characterizing and Profiling Scientific Workflows[J].Future Generation Computer Systems, 2013,29(3):682-692.

[2]Lee Y C,Han H,Zomaya A Y,et al.Resource-Efficient Workflow Scheduling in Clouds[J].Knowledge-Based Systems,2015,80: 153-162.

[3]Zhao Y,Li Y,Raicu I,et al.Enabling Scalable Scientific Workflow Management in the Cloud[J].Future Generation Computer Systems, 2015,46:3-16.

[4]Liu L,Zhang M,Lin Y,et al.A Survey on Workflow Management and Scheduling in Cloud Computing[C]//Cluster,Cloud and Grid Computing(CCGrid),2014 14th IEEE/ACM International Symposium on.IEEE,2014:837-846.

[5]Durillo J J,Prodan R.Multi-objective Workflow Scheduling in Amazon EC2[J].Cluster Computing,2014,17(2):169-189.

[6]Chen W,da Silva R F,Deelman E,et al.Using Imbalance Metrics to Optimize Task Clustering in Scientific Workflow Executions[J]. Future Generation Computer Systems,2015,46:69-84.

[7]Chen W,Da Silva R F,Deelman E,et al.Balanced Task Clustering in Scientific Workflows[C].eScience(eScience),2013 IEEE 9th International Conference on.IEEE,2013:188-195.

[8]Bittencourt L F,Madeira E R M.A Performance-Oriented Adaptive Scheduler for Dependent Tasks on Grids[J].Concurrency and Computation:Practice and Experience,2008,20(9):1029-1049.

[9]Calheiros R N,Ranjan R,Beloglazov A,et al.CloudSim:a Toolkit for Modeling and Simulation of Cloud Computing Environments and Evaluation of Resource Provisioning Algorithms[J].Software:Practice and Experience,2011,41(1):23-50.

[10]Deelman E,Vahi K,Juve G,et al.Pegasus,a Workflow Management System for Science Automation[J].Future Generation ComputerSystems,2015,46:17-35.

[11]Bux M,Leser U.DynamicCloudSim:Simulating Heterogeneity in Computational Clouds[J].Future Generation Computer Systems,2015,46:85-99.

Public Cloud;Workflow Scheduling;Path Clustering;Cost Optimaztion

Workflow Cost Optimization Scheduling Algorithm Based on Path Clustering in Public Cloud

WANG Bin
(College of Computer Science,Sichuan University,Chengdu 610065)

1007-1423(2016)03-0008-05

10.3969/j.issn.1007-1423.2016.03.002

王彬(1991-),男,四川廣安人,在讀碩士研究生,研究方向?yàn)樵朴?jì)算資源調(diào)度

2015-12-18

2016-01-10

針對工作流在公有云環(huán)境執(zhí)行的費(fèi)用過高問題,提出基于路徑聚簇的費(fèi)用優(yōu)化調(diào)度算法。算法結(jié)合工作流的任務(wù)資源、任務(wù)依賴等特征,計(jì)算任務(wù)的最早開始時間、最早完成時間和優(yōu)先級,聚簇最早完成時間和優(yōu)先級高的任務(wù)進(jìn)行統(tǒng)一放置,從而減少任務(wù)間的數(shù)據(jù)通信量,降低工作流的執(zhí)行時間和費(fèi)用,從而提高機(jī)構(gòu)的執(zhí)行效率。平臺仿真顯示改進(jìn)后算法可有效地降低執(zhí)行工作流的花費(fèi),提高執(zhí)行工作流的綜合性能比。

公有云;工作流調(diào)度;路徑聚簇;費(fèi)用優(yōu)化

To solve outrageous cost of workflow execution in public cloud environment,proposes a workflow scheduling algorithm based on path clustering on the same path.Combining tasks’resources requirements and tasks dependence of workflow will be scheduled,computed earliest start time,earliest finish time and priority of tasks,clustered tasks have the highest earliest finish time and priority,thus reduces data traffic between tasks,shortens workflow makespan and reduce workflow running cost,and improves organization efficiency.Platform emulation shows that the improved algorithm can effectively reduce cost of executing workflow,improve the comprehensive performance of workflow execution.

猜你喜歡
花費(fèi)實(shí)例綜合性
國外艦載直升機(jī)助降與牽引裝備綜合性能對比分析
新春開拍小禮物
情況不同,“花費(fèi)”不一樣
基于語文綜合性學(xué)習(xí)的作文教學(xué)策略
綜合性醫(yī)院人力資源開發(fā)與利用的探索
2014年世界杯會花費(fèi)多少?
完形填空Ⅱ
完形填空Ⅰ
綜合性圖書
如何“花費(fèi)”?