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

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

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

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

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

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

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

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

主流超級計算機的體系結(jié)構(gòu)日趨復(fù)雜。Top500排行榜中的許多超級計算機采用了異構(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)超級計算機的并行編程非常困難,因為異構(gòu)集群的計算資源、存儲資源、通信資源處于不同層次,需要不同的編程工具庫支持。例如,MPI(消息傳遞接口)支持不同節(jié)點分布式內(nèi)存之間的通信;Pthread支持在共享內(nèi)存下的多線程計算;CUDA (Compute Unified Device Architecture)是NVIDIA GPU設(shè)備指定的開發(fā)架構(gòu),支持更深的存儲和計算層次。Intel MIC的編程,基于X86架構(gòu),支持多種并行模型。

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

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

1 相關(guān)工作

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

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

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

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

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

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

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

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

2 案例說明

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

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

圖2 案例原始圖像

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

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

3.1 性能標(biāo)定

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

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

3.2 標(biāo)定方案

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

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

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

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

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

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

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

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

4.1 原語到工具庫的映射

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

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

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

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

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

4.2.1 計算期望運行時間

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

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

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

(1)

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

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

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

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

(2)

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

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

獲得預(yù)測運行時間后,減去相應(yīng)原語對應(yīng)的程序在每種模式下的期望運行時間,相減之后的絕對值作為預(yù)測運行偏差ΔTp-i,預(yù)測運行偏差即程序的預(yù)測運行時間和期望運行時間的差值,差值越小,預(yù)測運行時間與期望運行時間越接近,對應(yīng)運行模式越適合運行對應(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ù)測運行偏差為:ΔTp-1C,ΔTp-1G,ΔTp-1S.此時,選擇程序的實現(xiàn)模式,判斷預(yù)測運行偏差最小者,即越接近程序的預(yù)測運行時間,選擇最小者ΔTp-1,最小預(yù)測運行偏差對應(yīng)的實現(xiàn)模式即為第一次選擇。

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

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

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

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

(4)

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

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

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

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

ΔTi=Tf-i-Tp-i.

(5)

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

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

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

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

算法描述:

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

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

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

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

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

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

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

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

7) if 程序運行時間t

8) return；

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

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

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

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

13) 返回第7)步；

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

15) end .

5 基于CPN 的性能模擬

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

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

在有色Petri網(wǎng)的基礎(chǔ)上,增加程序的執(zhí)行元素,以表示程序運行時間限制,要求數(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的程序運行時間限制函數(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)整選擇,通過計算得出程序運行模式;AD2部分,將原語部署到前一階段選擇的模式中運行。如果Judge1判斷總時間超過實現(xiàn)約束,重新判斷;AD3部分,表示重新調(diào)整:Judge2判斷調(diào)整運;重新運行;直到運行時間合適。圖4 所示,第一部分提取興趣區(qū)EXTRROI ()，EXTRROI ()原語對應(yīng)程序選擇實現(xiàn)模式,計算程序在每個模式的預(yù)測偏差來選擇程序執(zhí)行模式,對應(yīng)于GPU，CPU，SPARK的預(yù)測運行偏差分別為:d1,d2,d3;圖4所示,將3個模式的預(yù)測偏差進行比較,選擇偏差最小者為運行模式,此時節(jié)點編號iid,最小預(yù)測偏差對應(yīng)的運行模式即為第一次選擇的運行模式。

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

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

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

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

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

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

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

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

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

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

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

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

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

實驗選取6張原始圖像,大小均為250 kB,在Julia云編輯平臺編寫車輛圖像檢索Julia程序。用戶提交程序到云平臺后端運行。測算出每個原語對應(yīng)的程序在每個模式中運行時間,如表5所示。表中數(shù)據(jù)時間可以知,3部分的原語對應(yīng)程序在不同實現(xià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)圖像檢索過程的實際運行時間。

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

圖7 第一張原始圖像檢索,程序三個部分運行時間變化圖

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

6 性能分析

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

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

圖8 隨用戶時限約束的變化六張原始圖像總用時變化對比圖

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

7 結(jié)論

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

(編輯：劉笑達)

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é)院院地合作項目：面向眾核平臺的高能效大規(guī)模圖并行算法研究(61379048)

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

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

TP302.7

A

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