周藝華,解高純,,段淑鳳,張常有

(1.北京工業(yè)大學(xué) 計(jì)算機(jī)學(xué)院,北京 100124;2.中國科學(xué)院軟件研究所 并行軟件與計(jì)算科學(xué)實(shí)驗(yàn)室,北京 100190;3.石家莊鐵道大學(xué) 信息科學(xué)與技術(shù)學(xué)院,石家莊 050043)

云環(huán)境下的程序運(yùn)行性能自適應(yīng)模擬方法研究

周藝華1,解高純1,2,段淑鳳3,張常有2

(1.北京工業(yè)大學(xué) 計(jì)算機(jī)學(xué)院,北京 100124;2.中國科學(xué)院軟件研究所 并行軟件與計(jì)算科學(xué)實(shí)驗(yàn)室,北京 100190;3.石家莊鐵道大學(xué) 信息科學(xué)與技術(shù)學(xué)院,石家莊 050043)

針對Julia程序運(yùn)行的時限約束,提出一種基于有色Petri網(wǎng)的程序運(yùn)行性能自適應(yīng)模擬方法。面向特定領(lǐng)域構(gòu)建適應(yīng)底層計(jì)算資源特點(diǎn)的工具庫,抽取針對Julia語言的計(jì)算原語；程序員通過Julia語言實(shí)現(xiàn)原語,動態(tài)選取領(lǐng)域工具,適應(yīng)運(yùn)行時限約束。結(jié)合圖像對象識別案例,構(gòu)建Colored Petri Net模型,借助CPN Tools工具模擬運(yùn)行,自動優(yōu)化備選方案。模擬實(shí)驗(yàn)表明,基于工具庫的性能標(biāo)定,CPN模擬得到的工具庫映射方案接近最優(yōu)。

云編程環(huán)境;時限約束;性能自適應(yīng);CPN模型;性能標(biāo)定

主流超級計(jì)算機(jī)的體系結(jié)構(gòu)日趨復(fù)雜。Top500排行榜中的許多超級計(jì)算機(jī)采用了異構(gòu)體系結(jié)構(gòu)[1]。例如天河2號MilkyWay-2 (TH-IVB-FEP Cluster,英特爾 Xeon E5-2692 12C 2.200 GHz,TH Express-2,英特爾 Xeon Phi 31S1P),泰坦-Cray XK7(Opteron 6274 16C 2.200 GHz,Cray Gemini interconnect,NVIDIA K20x)。面向異構(gòu)超級計(jì)算機(jī)的并行編程非常困難,因?yàn)楫悩?gòu)集群的計(jì)算資源、存儲資源、通信資源處于不同層次,需要不同的編程工具庫支持。例如,MPI(消息傳遞接口)支持不同節(jié)點(diǎn)分布式內(nèi)存之間的通信;Pthread支持在共享內(nèi)存下的多線程計(jì)算;CUDA (Compute Unified Device Architecture)是NVIDIA GPU設(shè)備指定的開發(fā)架構(gòu),支持更深的存儲和計(jì)算層次。Intel MIC的編程,基于X86架構(gòu),支持多種并行模型。

Julia語言是一種新的高性能動態(tài)高級編程語言,其設(shè)計(jì)目標(biāo)是滿足科學(xué)和數(shù)值計(jì)算的需求。Julia語言的語法與流行的編程語言相似。Julia語言支持可選的類型聲明,重載和高性能等特性,采用類型推斷和即時(JIT)編譯技術(shù),基于LLVM實(shí)現(xiàn)。Julia與R、Matlab和Python同樣支持通用編程;除了高級數(shù)值計(jì)算,Julia具有默認(rèn)的垃圾收集功能,支持許多成熟的高性能基礎(chǔ)代碼,包括浮點(diǎn)、線性代數(shù)、隨機(jī)數(shù)生成、快速傅里葉變換和正則表達(dá)式匹配的動態(tài)庫。Julia代碼的運(yùn)行速度接近C語言,遠(yuǎn)遠(yuǎn)超過R，Matlab和Python.語言級的分布式進(jìn)程管理是Julia高性能計(jì)算的重要特點(diǎn)。

根據(jù)應(yīng)用背景需要,程序員需要其程序在給定時間內(nèi)完成。出于節(jié)約計(jì)算資源、降低功耗、減少花費(fèi)等方面考慮,不需要追求最快的計(jì)算速度。本文基于Julia云編程環(huán)境中的領(lǐng)域工具庫的性能、功耗、花費(fèi)標(biāo)定數(shù)據(jù),以汽車圖像的車型識別程序?yàn)槔?建立有色Petri網(wǎng)模型,自動映射到合適的領(lǐng)域工具,滿足應(yīng)用程序的時限約束。

1 相關(guān)工作

1.1 基于云計(jì)算的編程環(huán)境

以用戶為中心的交互式編程環(huán)境對于一種很有前途的新語言是必不可少的。例如,作為一個新語言,Julia是面向高性能計(jì)算的。一個友好易用的編程接口,將非常有利于發(fā)展Julia語言。筆者構(gòu)建了一個基于云計(jì)算的Julia的高性能計(jì)算云平臺。這個平臺由三部分組成:用戶編程環(huán)境(UPE),消息傳遞系統(tǒng)(MPS),Julia運(yùn)行環(huán)境(JRE)。該平臺的體系結(jié)構(gòu)如圖1所示。

圖1 julia云編程服務(wù)平臺架構(gòu)

1.2 Julia語言對外部函數(shù)庫的支持能力

在Julia運(yùn)行環(huán)境中運(yùn)行Julia代碼,將Julia程序部署在基于LLVM的實(shí)時(JIT)編輯器中執(zhí)行。

用戶可以使用Julia調(diào)用自己的C/Fortran代碼庫或者專有第三方庫中的外部函數(shù),從而不用寫任何的包裝器代碼或者不用重新編譯現(xiàn)有的代碼,在Julia交互提示符中直接引用外部庫函數(shù),可以直接得到反饋結(jié)果。

1.3 面向性能的調(diào)度方法

任務(wù)調(diào)度是云平臺的最關(guān)鍵的問題,為了滿足用戶的要求,并能解決迫切的資源重用和共享的要求,提高資源的利用率,進(jìn)而提高云計(jì)算環(huán)境的整體性能,文獻(xiàn)[2]中，作者考慮到云計(jì)算和原始的自適應(yīng)遠(yuǎn)傳算法的新特點(diǎn)提出新的調(diào)度算法,基于雙適應(yīng)度的自適應(yīng)算法建立的工作跨越時間和負(fù)載平衡的遺傳算法。文獻(xiàn)[3]中,作者提出了一種任務(wù)調(diào)度算法,這個算法可以優(yōu)化任務(wù)完成時間,以及云計(jì)算任務(wù)調(diào)度問題的負(fù)載平衡和節(jié)能優(yōu)化。文獻(xiàn)[4]中,針對眾核架構(gòu)中隨著核的數(shù)量增加,更有效地安排在資源上運(yùn)行并行應(yīng)用程序,作者在工作竊取思想的基礎(chǔ)上研究了反饋驅(qū)動自適應(yīng)調(diào)度方法,它提供了在眾核系統(tǒng)中同時執(zhí)行一組應(yīng)用的高效解決方案。文獻(xiàn)[5]中提出了一種新的自適應(yīng)調(diào)度的概念,通過運(yùn)行時執(zhí)行和安排使得工作流協(xié)同工作在網(wǎng)格環(huán)境中具有一個非常好的顯著變化。研究大型超級計(jì)算機(jī)調(diào)度策略是希望實(shí)現(xiàn)用戶和系統(tǒng)所有者所期望的無定型的和有時相互沖突的目標(biāo),在這個工作中作業(yè)調(diào)度是最關(guān)鍵的和復(fù)雜的。文獻(xiàn)[6]中提出的是一套優(yōu)化部署異構(gòu)節(jié)點(diǎn)集群上的應(yīng)用程序的整體吞吐量的調(diào)度方式。文獻(xiàn)[7]中提出的基于啟發(fā)式工作流調(diào)度方案,通過使用方案減少所需的虛擬機(jī)實(shí)例的數(shù)目,并達(dá)最小能耗。上述相關(guān)文獻(xiàn)都是追求最大的速度,最小的資源消耗,未考慮可能帶來的節(jié)點(diǎn)使用費(fèi)用。筆者提出的方法,在用戶提出的實(shí)現(xiàn)約束的基礎(chǔ)上調(diào)整實(shí)現(xiàn)模式,即可以實(shí)現(xiàn)用戶的時間要求,同時還可以降低使用硬件的花費(fèi)。

2 案例說明

用戶通過Julia云編程環(huán)境提交程序腳本作為任務(wù)描述,同時通過Web頁面說明其希望該識別任務(wù)最晚完成時間。會話映射服務(wù)器接到程序和時限約束后,啟動自動過程為該計(jì)算任務(wù)挑選合適的子過程集合,保證該任務(wù)在指定期限內(nèi)完成。一般地,用戶既關(guān)心任務(wù)完成時間,同時也關(guān)心減少花費(fèi)等。鑒于用戶不了解計(jì)算資源和收費(fèi)等方面的細(xì)節(jié),Julia編程平臺為用戶自動選擇調(diào)度方案,能提高平臺的可用性和用戶體驗(yàn)。

本實(shí)驗(yàn)采取車臉圖像識別案例作為實(shí)驗(yàn)案例。案例如下:原始圖像涵蓋2個車道,可能有多輛汽車,如圖2所示。一般地,為了更有效地提取車輛特征信息和消除背景干擾,定義原始圖像中汽車的車臉為興趣區(qū)域(ROI,Regin of Interest).

圖2 案例原始圖像

通過提取圖像中的興趣區(qū)域能提高識別性能。因此,針對車型識別用例,其計(jì)算過程主要包括:提取興趣區(qū)域,抽取SIFT特征點(diǎn),特征匹配,車型識別等?？紤]到汽車與攝像機(jī)之間的距離和角度的變化,采用SIFT特征抽取算法(Scale-invariant feature transform)獲取車臉圖像的特征點(diǎn)及特征描述。特征點(diǎn)匹配采用了課題組提出的SiftKeyPre匹配算法。

3 領(lǐng)域工具庫的性能標(biāo)定

3.1 性能標(biāo)定

標(biāo)定性能指標(biāo),時間只是標(biāo)定的一個指標(biāo),另外一個指標(biāo)是用戶花費(fèi)。程序的執(zhí)行需要時間約束,同時需要能耗約束,即能耗越低越好。

車輛圖像檢索案例中,用戶使用云編程平臺,首先,用戶必須提交一個時限約束Tu,表示程序執(zhí)行時間必須小于時限約束。那么,需要調(diào)整程序執(zhí)行策略,使用戶提交的程序在Tu范圍內(nèi)執(zhí)行完成。當(dāng)然,時間在Tu范圍內(nèi)可長可短。要求時間很短,那么就需要將程序運(yùn)行在更高要求的硬件上或者使用更多的硬件并行執(zhí)行,此時花費(fèi)提高。為了降低用戶花費(fèi),可延長執(zhí)行時間,但不超過Tu;即,可調(diào)整到在Tu范圍內(nèi),盡量延長執(zhí)行時間。

3.2 標(biāo)定方案

針對基于靜態(tài)圖像的車型識別案例,為幫助調(diào)度策略生成器更容易估計(jì)任務(wù)執(zhí)行時間和花銷,將車型識別過程抽象成若干原語。程序員通過將程序映射為操作原語,來確定每部分的時間和花銷。如表1所示,列舉了案例的操作原語集。

標(biāo)定數(shù)據(jù)集采用中國某城市公安局收集的中的JPG圖像。圖像的尺寸為2 048×1 536像素,圖像大小為100～250 kB .

表1 本文案例抽象的原語集合

本質(zhì)上,案例包括3個主要原語:EXTRROI ()，EXTSIFTKEY ()，MATCH ().這些原語占用了車型識別任務(wù)的主要時間和花銷。原語標(biāo)定就是這些原語在不同的實(shí)現(xiàn)模式下的時間消耗和用戶花費(fèi)。

原語標(biāo)定,原語的標(biāo)定值如表2所示,當(dāng)前標(biāo)定的原語為案例的3個主要原語。

表中已經(jīng)標(biāo)定原語的運(yùn)行時間。表中左側(cè)為案例原語,右側(cè)為原語可選擇的實(shí)現(xiàn)模式。圖像識別過程,3個主要原語EXTRROI ()，EXTSIFTKEY ()，MATCH ()可以通過自適應(yīng)調(diào)度機(jī)制在和是的模式下運(yùn)行對應(yīng)的程序,表中數(shù)字為程序在對應(yīng)模式中的時間標(biāo)定。

表2 本文案例抽象的原語集合

4 基于時限約束的性能自適應(yīng)

4.1 原語到工具庫的映射

假設(shè)每個操作原語可能運(yùn)行在CPU，GPU，SPARK等3種模式。通過性能自適應(yīng)機(jī)制映射到相應(yīng)的節(jié)點(diǎn)運(yùn)行。如圖3所示,說明自適應(yīng)機(jī)制中操作原語與工具庫之間的映射關(guān)系。

圖3 自適應(yīng)機(jī)制中操作原語與工具庫之間的映射關(guān)系

4.2 性能自適應(yīng)算法

性能自適應(yīng)的原則是:滿足用戶提交的時限約束;用戶花費(fèi)盡可能低。按照完成時間越短,用戶花費(fèi)越大的假設(shè),根據(jù)前文的標(biāo)定結(jié)果,提出車型識別過程的性能自適應(yīng)算法。EXTRROI()原語運(yùn)行時間明顯多于其他原語。也就是說,其運(yùn)行時間和花費(fèi)都是遠(yuǎn)超其他2部分。所以,選擇EXTRROI()原語的實(shí)現(xiàn)模式尤為重要。本文提出的性能自適應(yīng)策略盡可能選擇花費(fèi)較少,運(yùn)行時間合適的運(yùn)行模式。

假設(shè)用戶要求的時限約束為Tu.用戶任務(wù)開始運(yùn)行后,要求在Tu內(nèi)完成整個車型識別過程。性能自適應(yīng)算法的具體步驟如下:

4.2.1 計(jì)算期望運(yùn)行時間

通過大量原始圖像實(shí)驗(yàn),獲得Julia程序中3個部分在每個模式上的運(yùn)行時間。對程序每個部分在每個模式上的運(yùn)行時間分別求均值,獲得Julia程序每部分在每個模式的期望運(yùn)行時間。

程序在每個模式中的期望運(yùn)行時間分別設(shè)定為:T1G,T1C,T1S,T2G,T2C,T2S,T3G,T3C,T3S(例如T1G表示EXTRROI ()原語對應(yīng)程序在GPU模式下的期望運(yùn)行時間,T2C表示EXTSIFTKEY ()原語對應(yīng)程序在CPU模式下的期望運(yùn)行時間,T3S表示MATCH()原語對應(yīng)程序在SPARK模式下的期望運(yùn)行時間)。本案例車輛圖像檢索的最大總期望運(yùn)行時間設(shè)定為T:

T=max{TiG}+max{TiC}+max{TiS} .

(1)

式中:i∈原語3部分編號1,2,3；j∈G，C，S.

4.2.2 計(jì)算預(yù)測運(yùn)行時間

假設(shè)用戶約束時間為程序總運(yùn)行時間,將用戶約束時間與程序每部分平均運(yùn)行時間在最大總期望運(yùn)行時間所占比例相乘,所得結(jié)果作為程序每部分的預(yù)測運(yùn)行時間。定義每個部分的預(yù)測運(yùn)行時間為tp-i,已知用戶時限約束為tu,那么預(yù)測運(yùn)行時間tp-i可由下面公式獲得:

Tp-i=Tu×(max{TiG,TiC,TiS}/T) .

(2)

即,EXTRROI()部分預(yù)測運(yùn)行時間為Tp-1,EXTSIFTKEY ()部分預(yù)測運(yùn)行時間為Tp-2,MATCH()部分的預(yù)測運(yùn)行時間為Tp-3.

4.2.3 計(jì)算預(yù)測運(yùn)行偏差

獲得預(yù)測運(yùn)行時間后,減去相應(yīng)原語對應(yīng)的程序在每種模式下的期望運(yùn)行時間,相減之后的絕對值作為預(yù)測運(yùn)行偏差ΔTp-i,預(yù)測運(yùn)行偏差即程序的預(yù)測運(yùn)行時間和期望運(yùn)行時間的差值,差值越小,預(yù)測運(yùn)行時間與期望運(yùn)行時間越接近,對應(yīng)運(yùn)行模式越適合運(yùn)行對應(yīng)的程序。

ΔTp-iC=|Tp-i-T1C|,ΔTp-iG=|Tp-i-T1G| ,

ΔTp-iS=|Tp-i-T1S| .

(3)

4.2.4 選取程序?qū)崿F(xiàn)模式

EXTRROI()原語對應(yīng)程序在每個模式GPU,CPU,SPARK的預(yù)測運(yùn)行偏差為:ΔTp-1C,ΔTp-1G,ΔTp-1S.此時,選擇程序的實(shí)現(xiàn)模式,判斷預(yù)測運(yùn)行偏差最小者,即越接近程序的預(yù)測運(yùn)行時間,選擇最小者ΔTp-1,最小預(yù)測運(yùn)行偏差對應(yīng)的實(shí)現(xiàn)模式即為第一次選擇。

同理,對應(yīng)于EXTSIFTKEY ()，MATCH()部分執(zhí)行同樣過程。EXTSIFTKEY ()原語對應(yīng)程序在每個實(shí)現(xiàn)模式預(yù)測運(yùn)行偏差為:ΔTp-2C，ΔTp-2G， ΔTp-2S,預(yù)測運(yùn)行偏差最小者ΔTp-2,最小預(yù)測偏差對應(yīng)的實(shí)現(xiàn)模式即為第一次選擇。MATCH()原語對應(yīng)程序在每個實(shí)現(xiàn)模式預(yù)測運(yùn)行偏差為:ΔTp-2C，ΔTp-2G， ΔTp-2S,預(yù)測運(yùn)行偏差最小者為ΔTp-3,最小預(yù)測運(yùn)行偏差對應(yīng)的實(shí)現(xiàn)模式即為第一次選擇。

4.2.5 獲取實(shí)際運(yùn)行時間第一遍自適應(yīng)調(diào)度,實(shí)現(xiàn)程序,程序的總運(yùn)行時間為t

EXTRROI ()，EXTSIFTKEY ()，MATCH()原語對應(yīng)的程序在各自選中實(shí)現(xiàn)模式的實(shí)現(xiàn)時間分別為Tf-1，Tf-2，Tf-3,

t=Tf-1+Tf-2+Tf-3.

(4)

4.2.6 判斷是否繼續(xù)調(diào)整

若,tTu,表示實(shí)現(xiàn)時間超出用戶提交的時限約束,需重新調(diào)整實(shí)現(xiàn)模式。

4.2.7 重新調(diào)整實(shí)現(xiàn)模式

1) 計(jì)算每分程序?qū)嶋H運(yùn)行時間與預(yù)測運(yùn)行時間的偏差值:

ΔTi=Tf-i-Tp-i.

(5)

本案例EXTRROI(),EXTSIFTKEY(),MATCH()原語對應(yīng)的程序?qū)嶋H運(yùn)行時間與預(yù)測運(yùn)行時間偏差分別是:ΔT1,ΔT2,ΔT3.

2) 從上一步計(jì)算的偏差中選擇最大偏差值ΔTi,例如ΔT1為最大值,說明EXTRROI ()部分原語對應(yīng)的程序在當(dāng)前選擇的模式下實(shí)現(xiàn)花費(fèi)的時間過大,需要重新調(diào)整。調(diào)整EXTRROI ()原語對應(yīng)程序的實(shí)現(xiàn)模式。判斷預(yù)測運(yùn)行偏差:ΔTp-1C，ΔTp-1G，ΔTp-1S,從中選擇第二小的值ΔTp-1,此時選擇對應(yīng)的實(shí)現(xiàn)模式運(yùn)行實(shí)現(xiàn)EXTRROI()原語對應(yīng)的程序。其他2部分實(shí)現(xiàn)模式選擇不變,重新模擬實(shí)現(xiàn)整個過程。

獲取運(yùn)行時間,繼續(xù)判斷是否合適。

若t>Tu,繼續(xù)調(diào)整,當(dāng)?shù)谝粋€原語EXTRROI ()對應(yīng)程序的實(shí)現(xiàn)模式選擇了最少的節(jié)點(diǎn)仍然不能滿足,此時根據(jù)ΔT2，ΔT3由大到小的順序繼續(xù)調(diào)整,直到t

算法描述:

輸入:用戶提交約束時間Tu,圖像數(shù)據(jù)data,

輸出:調(diào)整是否成功,原語各部分程序最終實(shí)現(xiàn)模式

1) 計(jì)算原語對應(yīng)程序的期望運(yùn)行時間,得出總運(yùn)行時間T；

2) 計(jì)算預(yù)測運(yùn)行時間Tp-i(i∈1,2,3,j∈G,C,S),第一次調(diào)整k=1,；

3) for預(yù)測運(yùn)行偏差ΔTp-ij(i∈原語各部分編號:1,2,3,j∈G,C,S)；

4) 預(yù)測運(yùn)行偏差ΔTp-ij中去掉已參考偏差后,選擇偏差最小者ΔTp-ij,(i∈1,2,3,j∈G,C,S)；

5) 通過ij判斷程序要實(shí)現(xiàn)模式；

6) 運(yùn)行程序,獲取運(yùn)行時間t,以及每部分的程序運(yùn)行時間Tf-i(i∈1,2,3,j∈G,C,S)；

7) if 程序運(yùn)行時間t

8) return；

9) else獲取實(shí)際運(yùn)行時間與預(yù)測時間的偏差ΔTi(i∈1,2,3)；

10) 選擇ΔTi的最大值,確定最大值的對應(yīng)原語；

11) 當(dāng)前模式i的預(yù)測運(yùn)行偏差ΔTp-ij中去掉已參考偏差后,選擇偏差最小者ΔTp-ij,(i∈1,2,3,j∈G,C,S)；

12) 通過ij判斷程序要運(yùn)行的模式,其他原語實(shí)現(xiàn)模式不變；

13) 返回第7)步；

14) 所有可能調(diào)整完成,t>Tu,返回要求用戶重新調(diào)整約束時間Tu；

15) end .

5 基于CPN 的性能模擬

5.1 有色Petri網(wǎng)模型

運(yùn)行在云平臺的Julia程序,其性能分析需要考慮程序中函數(shù)之間的依賴關(guān)系。有色網(wǎng)系統(tǒng)定義了托肯顏色以區(qū)分資源的種類,增強(qiáng)了其描述系統(tǒng)的能力。對于進(jìn)程間的控制依賴和數(shù)據(jù)依賴,分別抽象為有向弧和托肯。數(shù)據(jù)類型對應(yīng)托肯顏色;消息長度對應(yīng)托肯值;是影響程序運(yùn)行順序和執(zhí)行延遲的重要因素

在有色Petri網(wǎng)的基礎(chǔ)上,增加程序的執(zhí)行元素,以表示程序運(yùn)行時間限制,要求數(shù)據(jù)長度等,Julia云編程平臺系統(tǒng)如定義1。

表3 元素對應(yīng)關(guān)系

定義1 Julia云編程平臺系統(tǒng)∏=(P,T;F,C,I-,I+,K,D,M0)

稱為Julia云編程平臺系統(tǒng)的充分必要條件,是

1) ∑=(P,T;F,C,I-,I+,M0)是有色網(wǎng)系統(tǒng)；

2) 對于t∈T,D(t)為變遷t的程序運(yùn)行時間限制函數(shù)；

3) 對于p∈P,K(p)為庫所p的數(shù)據(jù)長度限制函數(shù)。

5.2 Julia云編程平臺的分析模型

在CPN TOOLS中建立Petri網(wǎng),分析自適應(yīng)策略。在Petri網(wǎng)中直觀描述原語所描述的車輛圖像檢索的過程。本文案例車輛類型識別petri網(wǎng)頂層模型如圖4所示。

主要分為3個部分(虛框部分):AD1部分,表示第一次調(diào)整選擇,通過計(jì)算得出程序運(yùn)行模式;AD2部分,將原語部署到前一階段選擇的模式中運(yùn)行。如果Judge1判斷總時間超過實(shí)現(xiàn)約束,重新判斷;AD3部分,表示重新調(diào)整:Judge2判斷調(diào)整運(yùn);重新運(yùn)行;直到運(yùn)行時間合適。圖4 所示,第一部分提取興趣區(qū)EXTRROI ()，EXTRROI ()原語對應(yīng)程序選擇實(shí)現(xiàn)模式,計(jì)算程序在每個模式的預(yù)測偏差來選擇程序執(zhí)行模式,對應(yīng)于GPU，CPU，SPARK的預(yù)測運(yùn)行偏差分別為:d1,d2,d3;圖4所示,將3個模式的預(yù)測偏差進(jìn)行比較,選擇偏差最小者為運(yùn)行模式,此時節(jié)點(diǎn)編號iid,最小預(yù)測偏差對應(yīng)的運(yùn)行模式即為第一次選擇的運(yùn)行模式。

圖4 車輛圖像檢索頂層網(wǎng)模型

程序部署到選擇的運(yùn)行模式運(yùn)行,在上例中,假設(shè)選擇的運(yùn)行模式為GPU,程序部署到GPU運(yùn)行模式下運(yùn)行。通過A庫所輸入的iid號,同時輸入總實(shí)現(xiàn)tir(tir)。運(yùn)行后,獲取本過程時間ut(tu),以及此過程的實(shí)際偏差dtt1。如圖5中所示。

其余兩部分EXTSIFTKEY ()，MATCH()原語對應(yīng)的程序調(diào)整模型與圖5 結(jié)構(gòu)相同如果在第一遍運(yùn)行完成后tu>tir,表示超時,即調(diào)整不合理,需要重新調(diào)整。判斷每部分偏差,找到最大偏差(最大偏差表示對應(yīng)部分用時超過期望用時,故需要重新調(diào)整)。

獲取最大偏差即為選擇調(diào)整方向,以第一部分的偏差較大為例,將第一部分節(jié)點(diǎn)重新調(diào)整。第一次選擇是對應(yīng)位置預(yù)測運(yùn)行偏差最小者,此時調(diào)整為預(yù)測運(yùn)行偏差第二小者對應(yīng)的模式為運(yùn)行模式。如圖6 所示，后續(xù)判斷調(diào)整部分。

5.3 實(shí)驗(yàn)環(huán)境與參數(shù)設(shè)置

本文中定義的主要參數(shù)的類型、縮寫和說明如表4所示。

圖5 節(jié)點(diǎn)調(diào)整模型

圖6 后續(xù)判斷模型

表4 元素對應(yīng)關(guān)系

名稱類型縮寫說明FIDintfid作業(yè)編號QDALintdal數(shù)據(jù)長度QTIRrealtir約束長度SPTrealspt每部分預(yù)測時長ALTrealalt總預(yù)測長度DEVIrealdt/dt1偏差DAT1realdat1第一部分時長

分析系統(tǒng)的運(yùn)行性能,CPN Tools 支持標(biāo)準(zhǔn)的ML語言,能提供基本的數(shù)據(jù)類型定義、數(shù)據(jù)操作描述等,用以構(gòu)建簡潔的參數(shù)化數(shù)學(xué)模型.定義數(shù)據(jù)類型的取值范圍,并調(diào)用其隨機(jī)函數(shù)生成運(yùn)行時間、執(zhí)行偏差等。

在CPN Tools 4.4.0上仿真運(yùn)行系統(tǒng)模型,觀測各原語對應(yīng)程序的運(yùn)行時間,運(yùn)行偏差、總運(yùn)行時間等。

5.4 實(shí)驗(yàn)環(huán)境與參數(shù)設(shè)置

實(shí)驗(yàn)選取6張?jiān)紙D像,大小均為250 kB,在Julia云編輯平臺編寫車輛圖像檢索Julia程序。用戶提交程序到云平臺后端運(yùn)行。測算出每個原語對應(yīng)的程序在每個模式中運(yùn)行時間,如表5所示。表中數(shù)據(jù)時間可以知,3部分的原語對應(yīng)程序在不同實(shí)現(xiàn)模式上的運(yùn)行時間差距非常大,而不同模式的使用費(fèi)用也是差別很大。

實(shí)施圖像檢索,實(shí)驗(yàn)改變時限約束tR的值(tR=120,130,140,149,150,160,170,180,190,200,250,300,400,500,600,700,800,900,1 000,1 100,1 200,1 300,1 400,1 500,1 600,1 700,1 800,1 900,2 000).測算每個時限約束對應(yīng)圖像檢索過程的實(shí)際運(yùn)行時間。

如圖7所示,為1號圖片對應(yīng)的圖像識別過程運(yùn)行時間,每部分的用時隨時限約束的改變而改變。當(dāng)時限約束tR=140 ms時,自適應(yīng)策略根據(jù)時限約束調(diào)整程序的實(shí)現(xiàn)模式。

圖7 第一張?jiān)紙D像檢索,程序三個部分運(yùn)行時間變化圖

表5 元素對應(yīng)關(guān)系

原始圖像IDSPLIT-CFACE()EXTSIFTKEY()MATCH()GPUCPUSPARKGPUCPUSPARKGPUCPUSPARK1368.321338.12126.213.97195.958.9612.3445.441.212491.31388.72133.914.3123.99.32.0368.040.973298.111278.1108.2612.7786.887.770.663.170.614305.61239.02101.6513.4399.478.430.563.040.155332.151421.13119.1314.07132.229.070.894.310.096367.61255.7898.6112.6124.297.60.955.10.86

EXTRROI()原語實(shí)現(xiàn)模式調(diào)整為SPARK,對應(yīng)的程序?qū)崿F(xiàn)時間為126.2 ms;EXTSIFTKEY ()的實(shí)現(xiàn)模式調(diào)整為SPARK,對應(yīng)程序?qū)崿F(xiàn)時間為8.96ms;第三部分MATCH()原語的實(shí)現(xiàn)模式選擇SPARK,對應(yīng)運(yùn)行時間為1.21 ms,總運(yùn)行時間為136.37 ms,小于時限約束140 ms.例如,時限約束tR=400 ms時,根據(jù)時限約束調(diào)整程序在云編程環(huán)境的實(shí)現(xiàn)模式,EXTRROI ()調(diào)整為GPU,對應(yīng)程序運(yùn)行時間為368.32 ms;EXTSIFTKEY ()部分的程序?qū)崿F(xiàn)模式調(diào)整為SPARK,對應(yīng)程序運(yùn)行時間為13.97 ms;第三部分MATCH()部分對應(yīng)的程序?qū)崿F(xiàn)模式選擇GPU,對應(yīng)程序的運(yùn)行時間為12.34 ms,總運(yùn)行時間為394.63 ms小于實(shí)現(xiàn)約束,實(shí)現(xiàn)模式選擇正確如果用戶時限約束達(dá)到了2 000 ms,此時圖片1的選擇時間可以都選擇CPU,總實(shí)現(xiàn)時間也達(dá)到1 579.71 ms.所以,在時限約束范圍內(nèi),可以選擇出合適的實(shí)現(xiàn)模式。

6 性能分析

實(shí)驗(yàn)使用6張?jiān)紙D像進(jìn)行圖像處理。如圖8所示,6張?jiān)紙D像在時限約束變化下,總運(yùn)行時間的變化狀況,橫坐標(biāo)為時限約束tR,縱坐標(biāo)是圖像的總運(yùn)行時間tu,tR1～tR6為圖像1～圖像6的總使用時間。如圖所示,每張?jiān)紙D像的運(yùn)行時間,都能根據(jù)時限約束改變運(yùn)行時間,根據(jù)我們提出的自適應(yīng)策略,總動調(diào)整程序的實(shí)現(xiàn)模式,調(diào)整模式將運(yùn)行總時間控制在低于時限約束范圍內(nèi),但是盡量能夠延長運(yùn)行時間。

從圖中得出,在時限約束在大于1 600 ms時,自適應(yīng)策略調(diào)整程序的實(shí)現(xiàn)模式均為CPU,在時限約束內(nèi),運(yùn)行時間能夠達(dá)到最高,當(dāng)時限約束繼續(xù)提高時,tu不再變化。

圖8 隨用戶時限約束的變化六張?jiān)紙D像總用時變化對比圖

在低于1 600 ms,大于100 ms的用戶要求時間內(nèi),程序可以合理的調(diào)整實(shí)現(xiàn)模式。時限約束升高后,自適應(yīng)策略修改實(shí)現(xiàn)模式,使程序運(yùn)行時間能夠延長,但是不能超過時限約束。100 ms以下,時間太短,基本無法按要求時間完成,需要重新設(shè)定時限約束。

7 結(jié)論

為Julia云編程環(huán)境設(shè)計(jì)了用戶程序性能自適應(yīng)策略。以車輛圖像檢索為案例,擴(kuò)展有色petri網(wǎng),建立形式化模型,并進(jìn)行模型檢測,驗(yàn)證云編程環(huán)境中的調(diào)度策略的正確性,預(yù)測調(diào)度策略的運(yùn)行性能。通過調(diào)整自適應(yīng)調(diào)度策略內(nèi)部流程和系統(tǒng)結(jié)構(gòu),以及調(diào)度策略的內(nèi)部機(jī)制,優(yōu)化案例的執(zhí)行性能。實(shí)驗(yàn)結(jié)果表明,基于Julia云編程環(huán)境提出的性能自適應(yīng)策略,能根據(jù)用戶提交的時限約束合理安排程序的運(yùn)行,追求程序運(yùn)行時間在時限約束內(nèi)的最大化,模擬用戶提出的時限約束線性變化,實(shí)現(xiàn)程序運(yùn)行時間動態(tài)改變。

[1] Meuer H,Strohmaier E,Dongarra J,et al.Top500 LISTS JVNE2015[EB/OL].http:∥www.top500.org/，2015.

[2] Wang T,Liu Z,Chen Y,et al.Load balancing task scheduling based on genetic algorithm in cloud computing[C]∥Dependable,Autonomic and Secure Computing (DASC).2014 IEEE 12th International Conference onIEEE,2014:146-152.

[3] Xue J,Li L,Zhao S S,et al.A Study of task scheduling based on differential evolution algorithm in cloud computing[C]∥2014 International Conference on Computational Intelligence and Communication Networks (CICN) IEEE Computer Society,2014:637-640.

[4] Mei J,Li K.Energy-Aware scheduling algorithm with duplication on heterogeneous computing systems[C]∥Grid Computing,IEEE/ACM International Workshop onIEEE,2012:122-129.

[5] Yu Zhifeng,Shi Weisong.An adaptive rescheduling strategy for grid workflow applications[C]∥IEEE,2007:1-8.

[6] Ravi V T,Becchi M,Wei J,et al.Scheduling concurrent applications on a cluster of CPU-GPU nodes[J].Future Generation Computer Systems,2013,29(8):2262-2271.

[7] Kang D K,Kim S H,Youn C H,et al.Cost adaptive workflow scheduling in cloud computing[C]∥Proceedings of the 8th International Conference on Ubiquitous Information Management and Communication.ACM,2014:65.

[8] Lou Y,Zhang T,Yan J,et al.Dynamic scheduling strategy for testing task in cloud computing[C]∥Computational Intelligence and Communication Networks (CICN).2014 International Conference onIEEE,2014:633-636.

[9] Muthuvelu N,Chai I,Eswaran C.An adaptive and parameterized job grouping algorithm for scheduling grid jobs[C]∥Advanced Communication Technology.ICACT 2008.10th International Conference on,2008:975-980.

[10] Gabel T,Riedmiller M.Scaling adaptive agent-based reactive job-shop scheduling to large-scale problems[C]∥Computational Intelligence in Scheduling.IEEE Symposium on IEEE,2007:259-266.

[11] ZHANG Changyou,LIU Renfen,DUAN Shufeng,et al.Cloud service platform for julia programming on supercomputer[J].International Journal of Grid and Distributed Computing.2014：177-186.

(編輯：劉笑達(dá))

A Research of Program Performance Adapting Simulationin Cloud Environment

ZHOU Yihua1,XIE Gaochun1,2,DUAN Shufeng3,ZHANG Changyou2

(1.CollegeofComputerScience,BeijingUniversityofTechnology,Beijing100124,China;2.LaboratoryofParallelSoftwareandComputationalScience,InstituteofSoftware,ChineseAcademyofSciences,Beijing100190,China;3.SchoolofInformationScienceandTechnology,ShijiazhuangTiedaoUniversity,Shijiazhuang050043,China)

The parallel program developing is difficult on heterogeneous computing platform.Cloud programming in Julia dynamic language is a reasonable model.For time-constrained cases of the Julia program,a performance self-adaptive simulation method based on the Colored Petri Net is proposed in this paper.Oriented to specific field,such as the case of image object recognition,we constructed a tool-library adapting to the characteristics of the underlying computing resources,and extracted a set of primitives in the Julia language.These primitives are implemented in Julia language,and they select tools dynamically to adapt the time-constrained running limitation.Considering the case of image object recognition,we constructed Colored Petri Net models,and simulated this model on CPN tools to observe the auto-optimizing processes.The simulation experimental results show that the tools mapping scheme produced in CPN simulation is close to the best on the basis of the performance calibration of the tools library.

cloud-based programming environment;time-constrained;performance adapting; CPN Models;performance calibration

1007-9432(2015)06-0727-08

2015-05-15

中國科學(xué)院院地合作項(xiàng)目：面向眾核平臺的高能效大規(guī)模圖并行算法研究(61379048)

周藝華(1969-)，男，濟(jì)南人，博士，副教授，主要從事網(wǎng)絡(luò)與信息安全、多媒體信息檢索與內(nèi)容安全研究， (E-mail)zhouyh@bjut.edu.cn,(Tel)010-67396063

張常有，教授，主要從事并行與分布式計(jì)算、協(xié)同計(jì)算、智能信息網(wǎng)絡(luò)等研究，(E-mail)changyou@iscas.ac.cn

TP302.7

A

10.16355/j.cnki.issn1007-9432tyut.2015.06.017