基于PageRank和基準測試的異構集群節點性能評價算法研究*

胡亞紅,王一洲,毛家發

(1.浙江工業大學計算機科學與技術學院,浙江 杭州 310023;2.中國工商銀行,浙江 杭州 310000)

1 引言

高效的任務調度是實現集群高性能的基礎。現有的大多數研究假設集群中的計算機節點是同構的，即所有節點都具有相同的性能。基于這一假設，在進行任務調度時每個節點會被分配相同的任務量。但是在大多數情況下，集群中各節點的性能差異很大。顯然給這些節點分配相同的任務量會導致任務執行時間較長、系統性能較低[1]。研究表明，集群配置應該根據集群中節點的性能進行[2]。目前關于集群節點的負載均衡和任務調度已經有了許多研究[3 - 7]。對節點性能進行精準的評價是進行各種調度的基礎。

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

本文的組織結構如下：第2節介紹了與節點性能評價相關的研究工作；第3節詳細介紹了基于PageRank和基準測試的節點性能評價算法；第4節給出了1個算法應用的實例；第5節則對全文進行了總結。

2 相關研究工作

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

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

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

調研發現，目前還沒有結合基準測試和PageRank算法來評估節點性能的研究。

3 算法描述

PageRank的假設是有著更多入鏈的網頁更重要。類似地，本文所提出的算法的假設是，越多的基準測試對1個節點給出相似的評價結果，那么評價結果越可靠。

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

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

3.1 性能向量的定義

假設選取M個基準測試進行集群節點的性能評價，集群中節點的個數為N。使用基準測試對節點進行評價后，評價的結果構成節點的性能向量。

令:

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

節點在不同基準測試下得到的性能向量值的數量級會有很大的差異，需要進行性能向量的預處理。算法1給出了性能向量歸一化的步驟。

算法1性能向量歸一化

步驟1輸入:Bi_o。

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

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

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

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

(1)

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

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

3.2 圖模型的建立

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

(2)

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

(3)

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

顯然，dij越大表示基準測試i和j對節點的評價結果差異越大。在經典PageRank算法中，概率轉移矩陣中元素表示的是所有入鏈的加權得分，其值越大表示網頁越重要。為使D的含義與經典PageRank 算法一致，使用式(4)對其進行處理，得到矩陣U。可以看出，U中元素越大，表示不同的基準測試得到的評價結果越相近。

U=(uij)M×M

(4)

類似于經典PageRank算法，在矩陣U的基礎上定義概率轉移矩陣W：

WT=(wij)M×M

(5)

3.3 基準測試排名的計算

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

(6)

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

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

R=lims→∞AsX

(7)

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

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

算法2基準測試排名計算

步驟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的值，算法結束。

步驟10X=R。

步驟11轉至步驟7。

步驟12輸出:基準測試排名向量R。

3.4 節點性能計算

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

算法3節點綜合性能評分計算

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

(8)

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

(9)

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

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

3.5 算法復雜度分析

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

4 算法實例

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

Table 2 Performance evaluation results表2 性能評價結果

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

進行歸一化計算后，得到的性能向量為：

兩兩比較基準測試得到的評價結果，可得:

進一步計算WT為：

根據WT得到概率轉移矩陣W：

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

假設所有基準測試的初始排名均為1，即:

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

通過R很容易計算得到每1個基準測試的權值:

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

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

CB=0.40×BLinpack+0.21×Biozone+

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

一般情況下初始化向量X取全1向量,當處理不同類型任務時，可以調整X的值以反映不同基準測試的重要程度。例如，如果集群需要處理一批計算密集型任務，在進行節點性能評價時，可以調高X中LINPACK 對應的數值；若處理I/O密集型的任務，可以調整 IOzone 對應的數值。可以看出，本文提出的算法不但能夠對節點性能進行有效的評價，還可以在評價時考慮任務的特點。

5 結束語

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

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