基于加速擴(kuò)散算法的同構(gòu)系統(tǒng)動(dòng)態(tài)負(fù)載平衡

隨著分布式計(jì)算技術(shù)的普及，越來(lái)越多的科學(xué)家在分布式并行系統(tǒng)中進(jìn)行科學(xué)計(jì)算。當(dāng)并行系統(tǒng)的所有節(jié)點(diǎn)都完整時(shí)，這種系統(tǒng)被稱為相同的結(jié)構(gòu)，相反，異構(gòu)平行系統(tǒng)在工作站網(wǎng)絡(luò)環(huán)境中經(jīng)常被稱為相同結(jié)構(gòu)的系統(tǒng)。負(fù)載平衡問(wèn)題是許多研究學(xué)者的研究焦點(diǎn).如果計(jì)算負(fù)載可以在運(yùn)行之前確定,可以事先將負(fù)載劃分這是靜態(tài)負(fù)載平衡問(wèn)題;若只能在運(yùn)行時(shí)測(cè)量計(jì)算負(fù)載并動(dòng)態(tài)確定負(fù)載劃分,則是動(dòng)態(tài)負(fù)載平衡問(wèn)題.對(duì)于異構(gòu)系統(tǒng),不同體系結(jié)構(gòu)的處理機(jī)的計(jì)算速度、利用率等等很難事先估算,靜態(tài)負(fù)載平衡需要很多假定;動(dòng)態(tài)負(fù)載平衡無(wú)須對(duì)處理機(jī)的計(jì)算速度作假定,可根據(jù)實(shí)際測(cè)量數(shù)據(jù)進(jìn)行調(diào)整.實(shí)現(xiàn)動(dòng)態(tài)負(fù)載平衡的方法很多,一些學(xué)者采用由一個(gè)節(jié)點(diǎn)監(jiān)視整個(gè)系統(tǒng)的負(fù)載狀況,并控制整個(gè)系統(tǒng)的負(fù)載分配的方法,這稱為直接方法,它的優(yōu)點(diǎn)是簡(jiǎn)單、直觀,在一些應(yīng)用中取得了較好的效果.另一類方法是緊鄰方法(nearest-neighborapproach),它假定并行處理系統(tǒng)是由多個(gè)節(jié)點(diǎn)按照一定的結(jié)構(gòu)相互連接構(gòu)成的并行處理網(wǎng)絡(luò),每個(gè)節(jié)點(diǎn)只能與其直接連接的節(jié)點(diǎn)通信,計(jì)算負(fù)載也只能通過(guò)這些連接移動(dòng).在負(fù)載平衡過(guò)程中,每個(gè)節(jié)點(diǎn)只能與其周圍的節(jié)點(diǎn)進(jìn)行負(fù)載交換,通過(guò)多次循環(huán)迭代實(shí)現(xiàn)系統(tǒng)的負(fù)載平衡.采用這種模式的負(fù)載平衡算法有:擴(kuò)散方法(diffusionmethod)、維交換法(dimensionexchangemethod)和基于梯度的方法(gradientbasedmethod)等.在維交換法中,每個(gè)節(jié)點(diǎn)在一個(gè)時(shí)間內(nèi)只與它的一個(gè)相鄰的節(jié)點(diǎn)進(jìn)行負(fù)載平衡.在超立方體結(jié)構(gòu)中在每個(gè)節(jié)點(diǎn)與其所有相鄰的節(jié)點(diǎn)進(jìn)行負(fù)載平衡后,整個(gè)系統(tǒng)達(dá)到負(fù)載平衡.基于梯度的方法有多種,其共同特點(diǎn)是用負(fù)載梯度圖來(lái)描述整個(gè)系統(tǒng)的負(fù)載情況,負(fù)載是向著梯度最陡方向的節(jié)點(diǎn)移動(dòng)的.其中,梯度模式方法(gradientmodelmethod)用計(jì)算負(fù)載壓力面來(lái)表示負(fù)載的移動(dòng).在擴(kuò)散算法中,每個(gè)節(jié)點(diǎn)向它周圍計(jì)算負(fù)載較低的節(jié)點(diǎn),在送出計(jì)算負(fù)載的同時(shí)從計(jì)算負(fù)載高的節(jié)點(diǎn)接受計(jì)算負(fù)載.一些學(xué)者還研究了構(gòu)造切比雪夫多項(xiàng)式來(lái)加速收斂的方法.但是,上述算法都是針對(duì)同構(gòu)系統(tǒng)的.Chi-ChungHui提出了針對(duì)異構(gòu)系統(tǒng)的流體負(fù)載平衡(hydrodynamicloadbalancing)方法,該方法用連通器中水的流動(dòng)來(lái)計(jì)算負(fù)載的移動(dòng),還應(yīng)用水的位能在平衡時(shí)最低的原理計(jì)算負(fù)載的移動(dòng).本文將擴(kuò)散方法擴(kuò)展到異構(gòu)系統(tǒng),重點(diǎn)研究了不同速度的處理機(jī)安排在異構(gòu)系統(tǒng)的不同位置對(duì)收斂速度的影響,并利用它來(lái)加速擴(kuò)散算法收斂速度,提出了一種找到收斂速度較快的處理機(jī)安排的算法.1節(jié)點(diǎn)計(jì)算負(fù)載轉(zhuǎn)移的一般方法我們假設(shè)并行處理系統(tǒng)是由用某種拓?fù)浣Y(jié)構(gòu)的網(wǎng)絡(luò)相連的處理速度不同的節(jié)點(diǎn)構(gòu)成.該系統(tǒng)可以用節(jié)點(diǎn)圖G=(V,E)來(lái)表示,其中V是節(jié)點(diǎn),P是節(jié)點(diǎn)數(shù)量,|V|=P,E是邊,代表節(jié)點(diǎn)之間的通信連接.我們將節(jié)點(diǎn)從1~P順序編號(hào),使每個(gè)節(jié)點(diǎn)有惟一的序號(hào)與之對(duì)應(yīng),節(jié)點(diǎn)用ni表示.同樣,我們將邊從1~|E|編號(hào),使每個(gè)邊也有惟一的序號(hào)與之對(duì)應(yīng),用ei表示,也可用eij表示連接節(jié)點(diǎn)ni,nj的邊,|E|是邊的數(shù)量.第i個(gè)節(jié)點(diǎn)的計(jì)算速度是si,計(jì)算負(fù)載是wi,計(jì)算時(shí)間是li=wi/si,節(jié)點(diǎn)的最缺計(jì)算時(shí)間是負(fù)載平衡問(wèn)題可以歸結(jié)為通過(guò)調(diào)整計(jì)算時(shí)間wi,使該節(jié)點(diǎn)的時(shí)間為l,則系統(tǒng)達(dá)到負(fù)載平衡,節(jié)點(diǎn)計(jì)算時(shí)間變化向量是其中()T為()的轉(zhuǎn)置矩陣.我們規(guī)定,節(jié)點(diǎn)間的每一條邊都有一個(gè)方向,從序號(hào)大的處理節(jié)點(diǎn)指向序號(hào)小的節(jié)點(diǎn).設(shè)沿ei邊計(jì)算負(fù)載的轉(zhuǎn)移量是δi,計(jì)算負(fù)載轉(zhuǎn)移向量x=(δ1,δ2,δ3,…,δ|E|)T,沿邊eij的負(fù)載轉(zhuǎn)移量也可成δij,對(duì)于節(jié)點(diǎn)i,它的計(jì)算負(fù)載總變化量是,其中j?i表示節(jié)點(diǎn)j與節(jié)點(diǎn)i之間有邊直接相連,稱為節(jié)點(diǎn)j與節(jié)點(diǎn)i相鄰.如果整個(gè)系統(tǒng)達(dá)到負(fù)載平衡,對(duì)于節(jié)點(diǎn)i有寫(xiě)成矩陣的形式為其中S為對(duì)角矩陣,S=diag(s1,s2,s3,...,sP),A為圖G的鄰接矩陣,其維數(shù)為|V|×|E|,其元素aij為因此,負(fù)載平衡算法歸結(jié)為求出每一條邊的計(jì)算負(fù)載轉(zhuǎn)移量,即向量x,使計(jì)算時(shí)間相同.對(duì)于給定的系統(tǒng),已知速度對(duì)角矩陣S和鄰接矩陣A,向量b可以通過(guò)測(cè)量處理節(jié)點(diǎn)的處理時(shí)間li并通過(guò)式(1)和式(2)得出,因此,動(dòng)態(tài)負(fù)載平衡問(wèn)題歸結(jié)于求解代數(shù)方程式(3).它有|E|個(gè)未知變量,有P=|V|個(gè)方程,一般地,|E|>P,所以式(3)的解不惟一,存在多種方法來(lái)求解該方程,各種方法的結(jié)果也可以各不相同.2節(jié)點(diǎn)的擴(kuò)散算法如圖1所示,用一組相互連接的連通器建立異構(gòu)擴(kuò)散算法的模型.設(shè)有P個(gè)水平截面積不同的容器,在底部有管道相互連接,容器內(nèi)有水,可以通過(guò)連接管在容器之間流動(dòng).容器的底面都在同一水平面上.如果在初始時(shí)刻液面有高有低,水就會(huì)在容器之間流動(dòng),直到所有容器的液面高度相同為止.在此模型中,水的體積與計(jì)算量相對(duì)應(yīng),水位與節(jié)點(diǎn)的計(jì)算時(shí)間相對(duì)應(yīng),容器的橫截面積與節(jié)點(diǎn)的處理速度相對(duì)應(yīng),連接管與節(jié)點(diǎn)之間的通信線路對(duì)應(yīng),如果計(jì)算時(shí)間(水位)不相同,一些計(jì)算負(fù)載(水)會(huì)通過(guò)處理節(jié)點(diǎn)間的通信連接(管道)從一個(gè)節(jié)點(diǎn)轉(zhuǎn)移到另一個(gè)節(jié)點(diǎn).如果計(jì)算時(shí)間相等,整個(gè)系統(tǒng)達(dá)到負(fù)載均衡,則計(jì)算負(fù)載不再移動(dòng).設(shè)節(jié)點(diǎn)i,j相鄰,一個(gè)時(shí)間步內(nèi)通過(guò)eij到達(dá)ni的流量正比于節(jié)點(diǎn)i,j的水位差.設(shè)在第t次迭代時(shí),各節(jié)點(diǎn)的水位(運(yùn)算時(shí)間)是li(t),擴(kuò)散算法的公式是其中πij是非負(fù)的常量.St是節(jié)點(diǎn)i的橫截面積(計(jì)算速度).此式表示每一步,節(jié)點(diǎn)i,j之間交換的計(jì)算負(fù)載為τij(ljt-lit),引起的計(jì)算時(shí)間的變化為.我們考慮的通信線路是雙向的,因此τji=τij.公式可改寫(xiě)為其中j?i表示所有與節(jié)點(diǎn)i相鄰的節(jié)點(diǎn).如果與節(jié)點(diǎn)i相鄰的節(jié)點(diǎn)在初始時(shí)刻的計(jì)算時(shí)間為0,在一個(gè)迭代步內(nèi),處理節(jié)點(diǎn)i上的計(jì)算時(shí)間不能為負(fù),所以對(duì)于常數(shù)πij的兩個(gè)約束條件是顯然,對(duì)于其中的每一行元素都有,容易驗(yàn)證M=I-S-1AWAT,其中W=diag(τ1,τ2,τ3,...,τE),A為圖G的鄰接矩陣,S=diag(s1,s2,s3,...,sP),令則方程(3)的解為.在實(shí)際計(jì)算中,只取前面一些項(xiàng).顯然,擴(kuò)散矩陣M不是對(duì)稱矩陣.關(guān)于擴(kuò)散矩陣M=I-S-1AWAT,可以證明在迭代過(guò)程式(7)中,總計(jì)算量不變,即為常量;M所有特征值均為實(shí)數(shù);M的所有特征值的絕對(duì)值小于等于1;-1不是M的特征值.證明從略.如果所有權(quán)重系數(shù)相同τij=τ,矩陣M可以寫(xiě)為M=I-τS-1M′,M′=AAT.設(shè)M的特征值為η,S-1M′的特征值為λ.M與S-1M′特征值的關(guān)系為η=1-τλ.因?yàn)?1<η≤1,所以可以得出S-1M′的特征值λ≥0,設(shè)它們是0=λ1<λ2≤λ3…≤λP,則M的特征值η1=1-τλ1=1,η2=1-τλ2,…,ηP=1-τλP,相應(yīng)特征的向量為α1,α2,…,αP.其中α1=(1,1,…,1)T.向量l0可以表示為它們的線性組合其中1aα1是負(fù)載平衡項(xiàng).所以,循環(huán)(5)的收斂速度取決于η2和ηP中絕對(duì)值較大者.由η2=1-τλ2,ηP=1-τλP可得,當(dāng)時(shí),η2,ηP的絕對(duì)值相等并達(dá)到最小,若令,則收斂速度取決于所以,p越接近1,收斂速度越快,p越大,收斂速度越慢.3遍歷方法.我們手工隨機(jī)畫(huà)出一個(gè)連接圖,共有9個(gè)處理節(jié)點(diǎn),如圖1所示,假定節(jié)點(diǎn)的速度分別是1,2,3,…,9,我們遍歷了所有362880種不同的可能,得到p的最小值是4.2,最大值是146.1,因此研究比如找到p達(dá)到最小或比較小的節(jié)點(diǎn)的安排方式對(duì)加快擴(kuò)散算法的收斂速度是很有意義的.加快擴(kuò)散算法的收斂速度的方法是找到p值比較小的節(jié)點(diǎn)速度安排的方法.它是特征值問(wèn)題的反問(wèn)題,要求特征值滿足一定的要求,即求矩陣的問(wèn)題.這類問(wèn)題一般來(lái)講是比較困難的.最容易的方法是遍歷方法,即計(jì)算所有可能的安排的p值,從中挑選出p最小的情況.這種方法只能在節(jié)點(diǎn)數(shù)量比較少(P<10)的情況下采用,由于需要試驗(yàn)的數(shù)量是P!,計(jì)算量隨著節(jié)點(diǎn)數(shù)量增加很快,節(jié)點(diǎn)數(shù)量在10個(gè)以上時(shí)這種方法基本不可用.為了找出計(jì)算量更少、速度更快的方法,本文提出了一種將節(jié)點(diǎn)逐次加入連接圖的方法,需要實(shí)驗(yàn)的數(shù)量比遍歷方法要少得多,但是該方法不能求出最小的p值的節(jié)點(diǎn)安排.事實(shí)上,我們沒(méi)有必要求出p達(dá)到最小值時(shí)的最佳安排,只需找出一種p比較接近最小值的情況,能夠加速擴(kuò)散的收斂速度即可.具體方法如下:·測(cè)量節(jié)點(diǎn)速度si,將所得到的節(jié)點(diǎn)速度除以速度最慢的節(jié)點(diǎn)的速度.這樣,最慢節(jié)點(diǎn)速度為1,其他節(jié)點(diǎn)速度就是與它的相對(duì)速度.按照速度由大至小逆序排列.·根據(jù)圖建立矩陣M′.·令速度矩陣S為單位矩陣.·將所有節(jié)點(diǎn)位置置標(biāo)志0.·do,對(duì)節(jié)點(diǎn)i從1~P循環(huán)do,對(duì)節(jié)點(diǎn)位置j從1~P循環(huán)if(位置j標(biāo)志為0)then令速度矩陣S的第j行對(duì)角元素為si,計(jì)算矩陣S-1M′的特征值λ2和λn如果p=λn/λ2<pmin,令k=j將速度矩陣j行對(duì)角元素還原成1將位置k記標(biāo)記為1,令速度矩陣S的第k個(gè)對(duì)角元素為si顯然,本方法需要試驗(yàn)種情況,比遍歷方法的P!要少得多.我們?nèi)匀皇褂玫?節(jié)的例子.在該例中用本方法得到的p值為15.55,可見(jiàn),用本方法求出的p值是比較小的.4節(jié)點(diǎn)兩性關(guān)系用p值、pmua為了進(jìn)一步驗(yàn)證提出方法的有效性和可靠性,我們?cè)O(shè)計(jì)了一些實(shí)驗(yàn),對(duì)能夠遍歷的規(guī)模較小的系統(tǒng)的所有情況進(jìn)行統(tǒng)計(jì),給出比較詳細(xì)的分析;對(duì)于規(guī)模較大的系統(tǒng),用蒙特卡洛方法進(jìn)行分析實(shí)驗(yàn).表1是實(shí)驗(yàn)的結(jié)果.實(shí)驗(yàn)1.我們用節(jié)點(diǎn)數(shù)量比較小的系統(tǒng)進(jìn)行實(shí)驗(yàn),以便用遍歷方法求出最佳方案進(jìn)行對(duì)比.實(shí)驗(yàn)方法如下(見(jiàn)表1):·假定系統(tǒng)由9個(gè)節(jié)點(diǎn)組成,每個(gè)節(jié)點(diǎn)的速度分別為1,2,3,…,9;·用手工方法確定9個(gè)節(jié)點(diǎn)間的連接圖,其中8個(gè)連接圖隨機(jī)確定,另一個(gè)是3×3的二維格柵網(wǎng);·我們用本文介紹的方法求出它們的p值,用p1表示;·采用遍歷方法,求出p的最小值pmin,最大值pmax.在表1中,第1行是連接圖的標(biāo)號(hào),第2行表示圖的連接情況,第i行的數(shù)字表示節(jié)點(diǎn)i與標(biāo)號(hào)為該行數(shù)字的節(jié)點(diǎn)相連,p1是用本方法求出的p值,pmax,pmin是用遍歷方法找到的最大和最小p值,pr越接近0,表示p1越接近最小值;越接近1,表示p1越接近最大值,Np<p1,Np>p1是p值小于、大于p1的數(shù)量,是p值小于p1占總數(shù)的百分比.可見(jiàn),用本方法找出的p值是比較小的,一般pr<30%,比較接近最小值,pctp<p1<1%實(shí)驗(yàn)2.主要考察節(jié)點(diǎn)速度對(duì)本方法效果的影響.用白噪聲隨機(jī)數(shù)發(fā)生器在區(qū)域內(nèi)產(chǎn)生9組節(jié)點(diǎn)速度,采用與實(shí)驗(yàn)1相同的連接方式,分別進(jìn)行實(shí)驗(yàn),結(jié)果見(jiàn)表2和表3.其中,表2為9組節(jié)點(diǎn)速度,表3為實(shí)驗(yàn)結(jié)果.可見(jiàn),節(jié)點(diǎn)速度的不同對(duì)結(jié)果有一些影響,但是并不嚴(yán)重.影響最大的還是連接圖.選擇比較好的連接圖是重要的.實(shí)驗(yàn)3.為了考察本方法對(duì)更大規(guī)模系統(tǒng)的有效性,我們采用更大規(guī)模的系統(tǒng)進(jìn)行實(shí)驗(yàn).規(guī)模擴(kuò)大以后,遍歷方法的計(jì)算量太大,因此我們采用蒙特卡洛方法對(duì)p的分布情況進(jìn)行估計(jì).由于二維格柵網(wǎng)是經(jīng)常采用的一種連接方式,因此我們以它為例進(jìn)行實(shí)驗(yàn).所采用的方法是:·假定網(wǎng)絡(luò)是8×8二維格柵網(wǎng),對(duì)格柵網(wǎng)節(jié)點(diǎn)按行標(biāo)號(hào),算出矩陣M′.·隨機(jī)數(shù)發(fā)生器在區(qū)間,產(chǎn)生64個(gè)隨機(jī)數(shù),并除以最小數(shù)得到節(jié)點(diǎn)的運(yùn)算速度,將所有節(jié)點(diǎn)按照速度快慢按逆序排列,最小節(jié)點(diǎn)速度為1.·用本文的方法計(jì)算出p1.·用白噪聲發(fā)生器產(chǎn)生隨機(jī)整數(shù)m,將序號(hào)為mod(m,P)+1的節(jié)點(diǎn)放在1號(hào)節(jié)點(diǎn)位置,將該節(jié)點(diǎn)以后的節(jié)點(diǎn)序號(hào)依次前移.產(chǎn)生第2個(gè)隨機(jī)數(shù)m,將序號(hào)為mod(m,P-1)+1的節(jié)點(diǎn)放在2號(hào)節(jié)點(diǎn)位置,依此類推,得到一個(gè)節(jié)點(diǎn)的隨機(jī)排列.·計(jì)算該排列的p值.·重復(fù)上述過(guò)程100000次,統(tǒng)計(jì)p的最小值、最大值、p小于p1的次數(shù)等.用得到的統(tǒng)計(jì)值得出pmin,pmaxPr,pctp<p1等的近似值.圖2是我們得到的結(jié)果,其中縱坐標(biāo)是p∈(n-,1n]的次數(shù),橫坐標(biāo)是n,箭頭是p1=939.的位置.p基本呈現(xiàn)出一種近似正態(tài)分布的情況,最大值和最小值的情況比較少,絕大多數(shù)情況的p值是在其平均值附近.p的最小值是63.8,最大值是225.2,pr≈18.6%,共有23次p<p1,pctp<p1≈0.023%.可見(jiàn),本實(shí)驗(yàn)的結(jié)論與前兩