發(fā)布時(shí)間：2017-12-23 14:24

  本文關(guān)鍵詞：應(yīng)用特征驅(qū)動(dòng)的迭代處理優(yōu)化機(jī)制研究　出處：《華中科技大學(xué)》2016年博士論文　論文類(lèi)型：學(xué)位論文

  更多相關(guān)文章： 大數(shù)據(jù) 異步/同步迭代處理 收斂速度 運(yùn)行時(shí)開(kāi)銷(xiāo) 計(jì)算/通信傾斜

【摘要】：迭代算法是指那些對(duì)初始輸入數(shù)據(jù)集進(jìn)行多輪反復(fù)處理尋找所需近似解或者精確解的算法。它在早期用于數(shù)值分析中線性方程組和微分方程等方面的近似求解。經(jīng)過(guò)幾十年的發(fā)展,迭代算法現(xiàn)已廣泛應(yīng)用于數(shù)據(jù)挖掘、機(jī)器學(xué)習(xí)和科學(xué)模擬等領(lǐng)域。在大數(shù)據(jù)時(shí)代,各行各業(yè)所產(chǎn)生的數(shù)據(jù)呈爆炸式增長(zhǎng),如何有效支持大規(guī)模迭代算法,快速挖掘海量數(shù)據(jù)背后潛在的商業(yè)或科學(xué)價(jià)值,已成為目前急需解決的重要任務(wù)。為了有效支持迭代算法,目前國(guó)內(nèi)外學(xué)者已初步提出多個(gè)迭代處理系統(tǒng)。然而,迭代算法種類(lèi)多樣,各具特征。其中可異步性特征和冪律依賴(lài)關(guān)系圖(Power-law Dependency Graph,簡(jiǎn)稱(chēng)PDG)特征對(duì)迭代算法性能影響最大�？僧惒叫蕴卣髦傅惴ㄔ谙鞯鷮哟沃g的同步之后仍能收斂到其所需結(jié)果。具有此特征的迭代算法常稱(chēng)作異步迭代算法,反之則稱(chēng)作同步迭代算法。PDG特征指迭代算法的數(shù)據(jù)依賴(lài)關(guān)系圖中各圖頂點(diǎn)度數(shù)服從冪函數(shù)分布。由于現(xiàn)有方法沒(méi)有考慮到迭代算法的多樣性,各類(lèi)迭代算法的高效運(yùn)行可能分別面臨著收斂速度慢、開(kāi)銷(xiāo)高、計(jì)算傾斜和通信傾斜等問(wèn)題。具體體現(xiàn)為：1)具有PDG特征的異步迭代算法面臨慢速的數(shù)據(jù)狀態(tài)傳遞而收斂速度欠佳；2)異步迭代算法在投機(jī)運(yùn)行時(shí)會(huì)面臨冗余計(jì)算開(kāi)銷(xiāo)和冗余通信開(kāi)銷(xiāo);3)具有PDG和不具有PDG特征的同步迭代算法將分別面臨不同原因?qū)е碌挠?jì)算傾斜；4)同步迭代算法由于各迭代層次之間的全局同步而面臨網(wǎng)絡(luò)抖動(dòng)和計(jì)算傾斜負(fù)面影響累積問(wèn)題。為了解決這些挑戰(zhàn),提出多個(gè)針對(duì)性的優(yōu)化機(jī)制對(duì)運(yùn)行時(shí)系統(tǒng)進(jìn)行相應(yīng)優(yōu)化,有效支持各類(lèi)典型迭代算法的執(zhí)行。針對(duì)具有PDG特征的異步迭代圖算法,提出基于核心圖的異步圖處理優(yōu)化機(jī)制,解決其收斂速度慢的問(wèn)題。由于PDG特征,此類(lèi)算法中有部分重要圖頂點(diǎn)。其狀態(tài)傳遞速度決定整個(gè)算法收斂所需時(shí)間。然而,采用目前策略,重要圖頂點(diǎn)之間的狀態(tài)難于快速傳遞,導(dǎo)致其收斂速度無(wú)法達(dá)到最優(yōu)。分析發(fā)現(xiàn),異步圖處理有級(jí)聯(lián)效應(yīng),允許圖頂點(diǎn)狀態(tài)沿路徑快速傳遞�；诖耸聦�(shí),為加快收斂速度,該機(jī)制將各圖劃分塊中重要的圖頂點(diǎn)以及它們之間的路徑包含在核心圖中,加快重要狀態(tài)在各圖劃分塊之間的推送。然后,它采用交替式策略處理各圖劃分塊,根據(jù)圖頂點(diǎn)在各路徑上的排列順序,以順序-逆序交替的方式處理它們,使重要狀態(tài)快速地在各圖劃分塊內(nèi)擴(kuò)散。針對(duì)異步迭代算法,提出基于組執(zhí)行模型的冗余開(kāi)銷(xiāo)控制機(jī)制,減少其投機(jī)運(yùn)行中的冗余開(kāi)銷(xiāo)。分析發(fā)現(xiàn),異步迭代算法允許合并和調(diào)度其中間結(jié)果數(shù)據(jù)。基于此特性,該機(jī)制以組的形式對(duì)中間結(jié)果數(shù)據(jù)進(jìn)行管理、調(diào)度和處理,避免它們分別觸發(fā)后續(xù)通信和計(jì)算。該機(jī)制通過(guò)權(quán)值的定義和中間結(jié)果數(shù)據(jù)處理順序的調(diào)度,在投機(jī)運(yùn)行帶來(lái)的利益和開(kāi)銷(xiāo)之間進(jìn)行折中,以獲得最佳性能。針對(duì)不具有PDG特征的同步迭代算法,提出局限性感知的增量計(jì)算傾斜消除機(jī)制,解決其典型應(yīng)用,即行為模擬應(yīng)用,群遷移導(dǎo)致的持續(xù)性計(jì)算傾斜。分析發(fā)現(xiàn),在行為模擬應(yīng)用中,模擬對(duì)象移動(dòng)范圍具有局限性�；诖颂卣�,該機(jī)制根據(jù)鄰居域的負(fù)載變化情況實(shí)時(shí)增量地評(píng)估每個(gè)域(對(duì)應(yīng)一個(gè)任務(wù))的負(fù)載,然后在以前域劃分基礎(chǔ)上增量地進(jìn)行域劃分、合并以及分配,有效實(shí)現(xiàn)負(fù)載均衡。針對(duì)具有PDG特征的同步迭代算法,提出基于計(jì)算分解的負(fù)載均衡機(jī)制,解決其典型應(yīng)用,即社交網(wǎng)分析應(yīng)用,計(jì)算傾斜問(wèn)題。由于PDG特征,在此類(lèi)同步迭代算法中,某些任務(wù)所需計(jì)算量會(huì)是所有任務(wù)所需平均計(jì)算量的數(shù)倍,并且大量任務(wù)會(huì)在運(yùn)行過(guò)程中收斂,導(dǎo)致計(jì)算傾斜。分析發(fā)現(xiàn),同樣由于PDG特征,其任務(wù)是對(duì)大量數(shù)據(jù)對(duì)象進(jìn)行匯總的過(guò)程�；诖耸聦�(shí),該機(jī)制動(dòng)態(tài)識(shí)別掉隊(duì)的任務(wù),將其大部分計(jì)算分解為多個(gè)子任務(wù)用于并行處理,然后采用動(dòng)態(tài)任務(wù)分配策略,實(shí)現(xiàn)負(fù)載均衡。針對(duì)同步迭代算法,提出基于細(xì)粒度并行的傾斜容忍機(jī)制,解決其傾斜負(fù)面影響累積問(wèn)題。分析發(fā)現(xiàn),在大多數(shù)同步迭代算法中,各數(shù)據(jù)對(duì)象在每輪迭代之后只會(huì)對(duì)其鄰居數(shù)據(jù)對(duì)象產(chǎn)生影響�；诖擞绊懢植啃蕴卣�,該機(jī)制通過(guò)挖掘多個(gè)迭代層次之間大量存在的可并行處理部分,利用各輪迭代中傾斜導(dǎo)致的閑散時(shí)間提前運(yùn)行后續(xù)迭代層次中這些可并行處理部分,以容忍傾斜的負(fù)面影響,解決其隨時(shí)間累積的問(wèn)題。綜上所述,這些優(yōu)化機(jī)制能夠加快異步迭代算法收斂速度并減少其運(yùn)行時(shí)開(kāi)銷(xiāo),消除和容忍同步迭代算法中的計(jì)算傾斜和網(wǎng)絡(luò)抖動(dòng)導(dǎo)致的通信傾斜,顯著提升各類(lèi)迭代算法在大規(guī)模云平臺(tái)上的執(zhí)行性能。
【學(xué)位授予單位】：華中科技大學(xué)
【學(xué)位級(jí)別】：博士
【學(xué)位授予年份】：2016
【分類(lèi)號(hào)】：O241.6

【相似文獻(xiàn)】

相關(guān)期刊論文 前5條

1 鄭克旺;;一類(lèi)發(fā)展型方程迭代型橫向算法[J];河北化工學(xué)院學(xué)報(bào);1988年01期

2 黃國(guó)麟,鄔家邦;3N+1猜想中的通常迭代與伸長(zhǎng)迭代[J];中南民族學(xué)院學(xué)報(bào)(自然科學(xué)版);2001年04期

3 鄔家邦,黃國(guó)麟;3N+1猜想中的通常迭代與伸長(zhǎng)迭代[J];廣州大學(xué)學(xué)報(bào)(綜合版);2001年05期

4 段昌國(guó);電算機(jī)模擬水輪機(jī)瞬變過(guò)程的誤差函數(shù)校正迭代方法和快速收斂程序[J];科學(xué)通報(bào);1984年22期

5 ;[J];;年期

相關(guān)博士學(xué)位論文 前2條

1 張宇;應(yīng)用特征驅(qū)動(dòng)的迭代處理優(yōu)化機(jī)制研究[D];華中科技大學(xué);2016年

2 別志松;基于因子圖的迭代接收機(jī)設(shè)計(jì)與優(yōu)化[D];北京郵電大學(xué);2007年

相關(guān)碩士學(xué)位論文 前1條

1 徐偉;面向聚類(lèi)分析的迭代MapReduce計(jì)算模型研究[D];天津大學(xué);2012年

，

本文編號(hào)：1324248