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

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

1 引言

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

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

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

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

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

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

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

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

3 算法描述

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

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

Table 1 Symbols used in the paper表1 本文所使用的符號(hào)

3.1 性能向量的定義

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

令:

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

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

算法1性能向量歸一化

步驟1輸入:Bi_o。

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

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

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

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

(1)

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

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

3.2 圖模型的建立

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

(2)

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

(3)

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

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

U=(uij)M×M

(4)

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

WT=(wij)M×M

(5)

3.3 基準(zhǔn)測(cè)試排名的計(jì)算

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

(6)

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

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

R=lims→∞AsX

(7)

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

算法2給出了R的計(jì)算方法。

算法2基準(zhǔn)測(cè)試排名計(jì)算

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

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

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

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

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

步驟7R=AX。

步驟8計(jì)算歐氏距離|R-X|。

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

步驟10X=R。

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

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

3.4 節(jié)點(diǎn)性能計(jì)算

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

算法3節(jié)點(diǎn)綜合性能評(píng)分計(jì)算

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

(8)

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

(9)

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

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

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

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

4 算法實(shí)例

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

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

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

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

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

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

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

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

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

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

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

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

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

CB=0.40×BLinpack+0.21×Biozone+

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

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

5 結(jié)束語

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

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