基于PageRank和基準(zhǔn)測試的異構(gòu)集群節(jié)點性能評價算法研究*

胡亞紅,王一洲,毛家發(fā)

(1.浙江工業(yè)大學(xué)計算機(jī)科學(xué)與技術(shù)學(xué)院,浙江 杭州 310023;2.中國工商銀行,浙江 杭州 310000)

1 引言

高效的任務(wù)調(diào)度是實現(xiàn)集群高性能的基礎(chǔ)?，F(xiàn)有的大多數(shù)研究假設(shè)集群中的計算機(jī)節(jié)點是同構(gòu)的，即所有節(jié)點都具有相同的性能?；谶@一假設(shè)，在進(jìn)行任務(wù)調(diào)度時每個節(jié)點會被分配相同的任務(wù)量。但是在大多數(shù)情況下，集群中各節(jié)點的性能差異很大。顯然給這些節(jié)點分配相同的任務(wù)量會導(dǎo)致任務(wù)執(zhí)行時間較長、系統(tǒng)性能較低[1]。研究表明，集群配置應(yīng)該根據(jù)集群中節(jié)點的性能進(jìn)行[2]。目前關(guān)于集群節(jié)點的負(fù)載均衡和任務(wù)調(diào)度已經(jīng)有了許多研究[3 - 7]。對節(jié)點性能進(jìn)行精準(zhǔn)的評價是進(jìn)行各種調(diào)度的基礎(chǔ)。

本文提出了一個新穎的基于PageRank和基準(zhǔn)測試的節(jié)點性能評價算法?；鶞?zhǔn)測試為評價具有不同架構(gòu)的計算機(jī)系統(tǒng)的性能提供了一種有效的方法，通常一種基準(zhǔn)測試著重于計算機(jī)某一種性能的測試。很多時候一個集群需要為不同類型的任務(wù)提供服務(wù)。例如，集群需要處理的任務(wù)可能是計算密集型、I/O密集型或者沒有明顯的特征的任務(wù)，僅使用一種基準(zhǔn)測試不能全面描述節(jié)點的綜合能力。本文提出的算法中，每個節(jié)點都使用多個基準(zhǔn)測試進(jìn)行評價，再使用PageRank算法處理得到的測試結(jié)果。算法基本思想是使用PageRank對這些基準(zhǔn)測試進(jìn)行排序，然后找到每個基準(zhǔn)測試在計算節(jié)點性能時的權(quán)值。該算法從不同的角度考慮影響節(jié)點性能的因素，因此可以在較短時間內(nèi)為集群中的節(jié)點提供綜合性能指標(biāo)。

本文的組織結(jié)構(gòu)如下：第2節(jié)介紹了與節(jié)點性能評價相關(guān)的研究工作；第3節(jié)詳細(xì)介紹了基于PageRank和基準(zhǔn)測試的節(jié)點性能評價算法；第4節(jié)給出了1個算法應(yīng)用的實例；第5節(jié)則對全文進(jìn)行了總結(jié)。

2 相關(guān)研究工作

大多數(shù)文獻(xiàn)都使用CPU主頻、內(nèi)存大小、磁盤容量、I/O性能或這些因素的組合來表示計算機(jī)的性能。文獻(xiàn)[8]設(shè)計了1個函數(shù)來計算節(jié)點性能，函數(shù)的輸入是從CPU、內(nèi)存、I/O和網(wǎng)絡(luò)設(shè)備獲取的數(shù)據(jù)。文獻(xiàn)[9]使用了靜態(tài)性能和動態(tài)性能來描述節(jié)點的性能。文獻(xiàn)[10]則是通過節(jié)點運(yùn)行指定程序的時間來計算其性能。文獻(xiàn)[11]為合理地進(jìn)行數(shù)據(jù)塊的分配，使用CPU主頻、內(nèi)存大小和I/O性能等對節(jié)點性能進(jìn)行評價。

基準(zhǔn)測試是1組定義好的用以測量計算機(jī)性能的程序集合[12,13]，常用的有LINPACK[14]、高性能共軛梯度基準(zhǔn)測試HPCG (the High Performance Conjugate Gradients)[15]、NASA 并行基準(zhǔn)NPB (NASA Parallel Benchmark)[16]、IDC 平衡評價指標(biāo)、高性能計算基準(zhǔn)測試HPCC (High Performance Computing Challenge)[17]和IOzone等。不同的基準(zhǔn)測試從不同的角度對計算機(jī)節(jié)點進(jìn)行評價。例如，LINPACK主要評價節(jié)點CPU的性能，HPCG 對系統(tǒng)的內(nèi)存和網(wǎng)絡(luò)延遲要求較高，IOzone則是1個文件系統(tǒng)的基準(zhǔn)測試。IOzone被設(shè)計用于分析系統(tǒng)的I/O性能，它對各種文件操作進(jìn)行測量[18]。IDC平衡評價指標(biāo)可以測量CPU、內(nèi)存性能和系統(tǒng)的擴(kuò)展性。可以看出，使用多個基準(zhǔn)測試進(jìn)行節(jié)點評價，可以得到更全面、更合理的節(jié)點評價結(jié)果。

PageRank是衡量網(wǎng)頁重要性的一種算法，Google 的搜索引擎使用它來對網(wǎng)頁的搜索結(jié)果進(jìn)行排序[19]。PageRank的基本假設(shè)是網(wǎng)站越重要，鏈接到它的網(wǎng)站會越多，因此PageRank通過計算網(wǎng)站的入鏈數(shù)量和質(zhì)量來評價其重要性。除了對網(wǎng)頁進(jìn)行排名，PageRank 在其它領(lǐng)域也有很多應(yīng)用。文獻(xiàn)[20,21]應(yīng)用PageRank尋找有向加權(quán)復(fù)雜網(wǎng)絡(luò)中的重要節(jié)點。文獻(xiàn)[22]提出了一種基于PageRank的關(guān)鍵詞提取方法，該方法考慮了詞頻分享權(quán)值和人類語言習(xí)慣特性。文獻(xiàn)[23] 構(gòu)建了1個表征微博用戶交互行為的模型，并利用PageRank計算用戶行為的權(quán)值。文獻(xiàn)[24]中,PageRank 被用于評價不同書籍的影響。文獻(xiàn)[25] 采用基于PageRank的快速篩選方法來識別容易出故障的線路，以防止電網(wǎng)級聯(lián)停電。PageRank也被用于通過引用網(wǎng)絡(luò)來衡量學(xué)術(shù)機(jī)構(gòu)的學(xué)術(shù)聲譽(yù)[26]。

調(diào)研發(fā)現(xiàn)，目前還沒有結(jié)合基準(zhǔn)測試和PageRank算法來評估節(jié)點性能的研究。

3 算法描述

PageRank的假設(shè)是有著更多入鏈的網(wǎng)頁更重要。類似地，本文所提出的算法的假設(shè)是，越多的基準(zhǔn)測試對1個節(jié)點給出相似的評價結(jié)果，那么評價結(jié)果越可靠。

為方便讀者閱讀，表1列出了本文所使用的符號。

Table 1 Symbols used in the paper表1 本文所使用的符號

3.1 性能向量的定義

假設(shè)選取M個基準(zhǔn)測試進(jìn)行集群節(jié)點的性能評價，集群中節(jié)點的個數(shù)為N。使用基準(zhǔn)測試對節(jié)點進(jìn)行評價后，評價的結(jié)果構(gòu)成節(jié)點的性能向量。

令:

其中,i=1,2,…,M，vik(k=1,2,…,N) 表示使用基準(zhǔn)測試i對節(jié)點k的評價。Bi_o即集群中節(jié)點在基準(zhǔn)測試i下的性能向量。

節(jié)點在不同基準(zhǔn)測試下得到的性能向量值的數(shù)量級會有很大的差異，需要進(jìn)行性能向量的預(yù)處理。算法1給出了性能向量歸一化的步驟。

算法1性能向量歸一化

步驟1輸入:Bi_o。

步驟2獲取Bi_o中的最大元素和最小元素

maxBi=max{vi1,vi2,…,viN}

minBi=min{vi1,vi2,…,viN}

步驟3對每1個vik使用式(1) 計算其歸一化數(shù)值vik-less:

(1)

其中,k=1,2,…,N。

步驟4輸出:歸一化性能向量:

3.2 圖模型的建立

為了使用PageRank 計算節(jié)點的性能，需要建立1個圖的模型，圖中的節(jié)點是各歸一化的性能向量，節(jié)點之間有1條邊表示這2個節(jié)點需要進(jìn)行比較，所以建立的圖是1個完全圖。邊的權(quán)值是此邊所關(guān)聯(lián)的2個頂點的相似度，相似度使用歐氏距離計算。2個歸一化性能向量Bi和Bj的相似度類似于經(jīng)典PageRank中頁面間鏈接的相關(guān)性。

(2)

因為共有M個不同的基準(zhǔn)測試，所以歸一化性能向量也有M個，即B1,B2,…,BM。性能距離矩陣D定義如下：

(3)

其中,dij是歸一化性能向量Bi和Bj的相似度。

顯然，dij越大表示基準(zhǔn)測試i和j對節(jié)點的評價結(jié)果差異越大。在經(jīng)典PageRank算法中，概率轉(zhuǎn)移矩陣中元素表示的是所有入鏈的加權(quán)得分，其值越大表示網(wǎng)頁越重要。為使D的含義與經(jīng)典PageRank 算法一致，使用式(4)對其進(jìn)行處理，得到矩陣U?？梢钥闯觯琔中元素越大，表示不同的基準(zhǔn)測試得到的評價結(jié)果越相近。

U=(uij)M×M

(4)

類似于經(jīng)典PageRank算法，在矩陣U的基礎(chǔ)上定義概率轉(zhuǎn)移矩陣W：

WT=(wij)M×M

(5)

3.3 基準(zhǔn)測試排名的計算

矩陣A采用經(jīng)典PageRank算法中的定義，如式 (6) 所示:

(6)

其中,q是阻尼系數(shù),eeT是M×M的全1矩陣。

基準(zhǔn)測試排名矩陣R可以用式 (7) 算出:

R=lims→∞AsX

(7)

其中,M×1向量X表示每個基準(zhǔn)測試的初始排名。

算法2給出了R的計算方法。

算法2基準(zhǔn)測試排名計算

步驟1輸入:歸一化性能向量Bi(i=1,…,M) 和閾值δ。

步驟3使用式 (3) 計算D。

步驟4使用式 (4) 計算U。

步驟5使用式 (5) 計算W。

步驟6使用式 (6) 計算A。

步驟7R=AX。

步驟8計算歐氏距離|R-X|。

步驟9如果|R-X|≤δ,返回R的值，算法結(jié)束。

步驟10X=R。

步驟11轉(zhuǎn)至步驟7。

步驟12輸出:基準(zhǔn)測試排名向量R。

3.4 節(jié)點性能計算

利用基準(zhǔn)測試排名向量R和每個基準(zhǔn)測試i的性能向量Bi，使用算法3就可以得到集群中每1個節(jié)點的綜合性能評分。

算法3節(jié)點綜合性能評分計算

步驟2使用式 (8) 計算每1個基準(zhǔn)測試i的權(quán)值：

(8)

步驟3使用式 (9) 計算綜合性能向量:

(9)

其中，k=1,2,…,N。

步驟4輸出:節(jié)點綜合性能向量CB。

3.5 算法復(fù)雜度分析

假設(shè)有M個基準(zhǔn)測試對N個節(jié)點進(jìn)行性能評價，則算法1的復(fù)雜度為(MN);由于需要計算DM×M,算法2的復(fù)雜度為O(M2N)；算法3的復(fù)雜度為O(MN)。因此本文算法的復(fù)雜度為O(M2N)。通常M的數(shù)值不會很大，因此本文算法的復(fù)雜度很低。

4 算法實例

本節(jié)通過1個實例對算法進(jìn)行解釋。實例中使用 LINPACK、IOzone 和NPB對4個節(jié)點進(jìn)行性能評價。LINPACK主要考察節(jié)點的浮點運(yùn)算能力，因此適合于CPU性能評價。IOzone則適合評價系統(tǒng)的I/O性能。評價結(jié)果如表2所示。

Table 2 Performance evaluation results表2 性能評價結(jié)果

從表2中可以得到各個原始的性能向量。

進(jìn)行歸一化計算后，得到的性能向量為：

兩兩比較基準(zhǔn)測試得到的評價結(jié)果，可得:

進(jìn)一步計算WT為：

根據(jù)WT得到概率轉(zhuǎn)移矩陣W：

使用式 (6) 計算矩陣A，其中阻尼系數(shù)q取值為0.85,閾值δ取值為0.000 1,與大多數(shù)文獻(xiàn)中使用的一致。

假設(shè)所有基準(zhǔn)測試的初始排名均為1，即:

僅執(zhí)行了10步，算法2就得到了最終的基準(zhǔn)測試排名向量R:

通過R很容易計算得到每1個基準(zhǔn)測試的權(quán)值:

類似地可以得到RB2=0.21，RB3=0.39。

根據(jù)上面的計算結(jié)果，可以得到每1個節(jié)點的綜合性能。

CB=0.40×BLinpack+0.21×Biozone+

向量CB給出了各節(jié)點綜合性能的比值，此例中節(jié)點1，2，3，4的性能比為0.61∶0.51∶0.54∶0.18，或者表示為1∶0.84∶0.89∶0.30。在進(jìn)行任務(wù)分配或數(shù)據(jù)部署時，可以使用這個比例進(jìn)行分配，從而最小化任務(wù)執(zhí)行時間。

一般情況下初始化向量X取全1向量,當(dāng)處理不同類型任務(wù)時，可以調(diào)整X的值以反映不同基準(zhǔn)測試的重要程度。例如，如果集群需要處理一批計算密集型任務(wù)，在進(jìn)行節(jié)點性能評價時，可以調(diào)高X中LINPACK 對應(yīng)的數(shù)值；若處理I/O密集型的任務(wù)，可以調(diào)整 IOzone 對應(yīng)的數(shù)值?？梢钥闯?，本文提出的算法不但能夠?qū)?jié)點性能進(jìn)行有效的評價，還可以在評價時考慮任務(wù)的特點。

5 結(jié)束語

本文提出了一個新穎的異構(gòu)集群中節(jié)點性能評價算法,借鑒PageRank 算法的思想，本文算法能夠綜合考慮多個基準(zhǔn)測試對節(jié)點的評價結(jié)果。算法具有復(fù)雜度低、對節(jié)點評價更為全面的特點。通過調(diào)整初始化向量X的取值，本文算法還可以體現(xiàn)出節(jié)點對不同類型任務(wù)的支持程度。

下一步將在真實集群中進(jìn)行進(jìn)一步實驗，以檢驗本文算法的使用效果。