應(yīng)用特征驅(qū)動(dòng)的迭代處理優(yōu)化機(jī)制研究.pdf

1、迭代算法是指那些對(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)。

2、然而，迭代算法種類多樣，各具特征。其中可異步性特征和冪律依賴關(guān)系圖（Power-law Dependency Graph，簡(jiǎn)稱PDG）特征對(duì)迭代算法性能影響最大?？僧惒叫蕴卣髦傅惴ㄔ谙鞯鷮哟沃g的同步之后仍能收斂到其所需結(jié)果。具有此特征的迭代算法常稱作異步迭代算法，反之則稱作同步迭代算法。PDG特征指迭代算法的數(shù)據(jù)依賴關(guān)系圖中各圖頂點(diǎn)度數(shù)服從冪函數(shù)分布。由于現(xiàn)有方法沒(méi)有考慮到迭代算法的多樣性，各類迭代算法的高效運(yùn)行可能分別面臨

3、著收斂速度慢、開(kāi)銷高、計(jì)算傾斜和通信傾斜等問(wèn)題。具體體現(xiàn)為：1）具有PDG特征的異步迭代算法面臨慢速的數(shù)據(jù)狀態(tài)傳遞而收斂速度欠佳；2）異步迭代算法在投機(jī)運(yùn)行時(shí)會(huì)面臨冗余計(jì)算開(kāi)銷和冗余通信開(kāi)銷；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)化，有效支持各類典

4、型迭代算法的執(zhí)行。
　　針對(duì)具有PDG特征的異步迭代圖算法，提出基于核心圖的異步圖處理優(yōu)化機(jī)制，解決其收斂速度慢的問(wèn)題。由于PDG特征，此類算法中有部分重要圖頂點(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)以及它們之間的路徑包含在核

5、心圖中，加快重要狀態(tài)在各圖劃分塊之間的推送。然后，它采用交替式策略處理各圖劃分塊，根據(jù)圖頂點(diǎn)在各路徑上的排列順序，以順序-逆序交替的方式處理它們，使重要狀態(tài)快速地在各圖劃分塊內(nèi)擴(kuò)散。
　　針對(duì)異步迭代算法，提出基于組執(zhí)行模型的冗余開(kāi)銷控制機(jī)制，減少其投機(jī)運(yùn)行中的冗余開(kāi)銷。分析發(fā)現(xiàn)，異步迭代算法允許合并和調(diào)度其中間結(jié)果數(shù)據(jù)?；诖颂匦?，該機(jī)制以組的形式對(duì)中間結(jié)果數(shù)據(jù)進(jìn)行管理、調(diào)度和處理，避免它們分別觸發(fā)后續(xù)通信和計(jì)算。該機(jī)制通過(guò)權(quán)值

6、的定義和中間結(jié)果數(shù)據(jù)處理順序的調(diào)度，在投機(jī)運(yùn)行帶來(lái)的利益和開(kāi)銷之間進(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í)

7、現(xiàn)負(fù)載均衡。
　　針對(duì)具有PDG特征的同步迭代算法，提出基于計(jì)算分解的負(fù)載均衡機(jī)制，解決其典型應(yīng)用，即社交網(wǎng)分析應(yīng)用，計(jì)算傾斜問(wèn)題。由于PDG特征，在此類同步迭代算法中，某些任務(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ù)

8、分配策略，實(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ī)制能夠