SMP集群系統的可擴放性分析

田 青，祝永志

(曲阜師范大學 信息科學與工程學院，山東 日照 276826)

SMP集群系統的可擴放性分析

田 青，祝永志

(曲阜師范大學 信息科學與工程學院，山東 日照 276826)

隨著并行計算技術的快速發展和SMP集群的普及，可擴放性已經成為并行應用程序設計和實現方面最重要的性能之一。但傳統的可擴放性評價準則不能對SMP集群的可擴放性進行較精準的評價。為此，在分析SMP集群中處理器集合的特性和傳統等效率模型并掌握其優缺點以及分析并行計算速度的基礎上，給出了一種適合SMP集群系統效率的定義，并基于該定義提出了一種新的可擴放性評價準則(改進的等效率可擴放性評價準則)。該新準則可用來評價并行算法和SMP集群相結合的可擴放性。為驗證所提出評價準則的有效性，在集群平臺上運行矩陣乘法程序進行了相關的擴放性實驗。實驗結果表明，所提出的新評價準則對算法和并行機的最優匹配有指導作用，同時有助于對并行算法的設計和改進。

并行計算；SMP集群；可擴放性；等效率

0 引 言

在高性能計算中有多種不同的體系結構。共享存儲的對稱多處理器(Symmetric Multi-Processor,SMP)和集群(Cluster)是最重要的兩個體系結構。SMP技術和集群技術兩種架構組合成的SMP集群中具有內在的互補性和潛在優勢，既保留了SMP的優點，又增加了集群的可擴放性，節點之間為分布式存儲體系結構，而同一個SMP節點內部各處理器之間組成共享存儲體系結構。SMP集群比單個SMP節點有更好的可擴放性，而比普通的集群有更高的集成度和計算能力[1-2]。

可擴放性研究在大規模并行系統中起著很重要的作用。它是一個用來測量系統硬件和軟件能力的性能指標，進而高效地利用規模增加的處理器。傳統可擴放性評價準則都是等性能的評價準則，即保持某個性能不變而得到可擴放性函數。可擴放性函數是關于問題規模隨處理器規模變化的函數，用于判斷并行系統的可擴放性的好壞[3]。傳統可擴放性的度量方法包括等效率可擴放性評價準則[4]、等速度可擴放性評價準則[5]、等平均延遲可擴放性評價準則[6]等。它們在進行可擴放性預測時基本上是等價的。目前，可擴放性的研究主要集中在并行機和并行算法相結合的可擴展性上，并已有大量的研究成果[7-9]，但是傳統的準則很難直接應用在SMP集群中。為了解決這個問題，對于SMP集群的可擴放性測量給出了一種新方法。

針對多核SMP集群的體系結構特點，在分析現有等效率可擴放性評價準則的特點及其不足的基礎上，改進了傳統等效率可擴放性評價準則以適合SMP集群體系結構，并應用該準則分析了并行算法與該性能并行機相結合的可擴放性。

1 SMP集群結構分析

1.1 SMP集群結構體系

SMP集群中的每個節點是一臺SMP服務器，所有節點(SMP服務器)由高性能網絡或者局域網物理地互聯。所有的集群節點必須能在集體工作，如同單一集成的計算機資源，單獨使用每個節點完成特殊任務除外。SMP集群系統中同時具有分布式存儲和共享存儲結構[2]。SMP集群體系結構如圖1所示。

圖1 SMP集群體系結構

1.2 SMP集群處理器集合的特性

傳統可擴放性評價準則能很好地應用于并行和分布式計算體系結構，但是這些評價準則使用一個參數P來描述并行計算系統的能力。實際上這些傳統可擴放性評價準則除非應用在相同能力的處理器集合中，否則不能較精準地測量其可擴放性，顯然SMP集群不能滿足這樣的假設。在SMP集群中，將具有不同計算能力的不同處理器集合稱為非等價性處理器集合，其中每個處理器集合有相同處理器數，且P表示處理器個數。

為了驗證非等價性的存在，在曙光TC5000集群運行矩陣乘法程序。具有相同問題規模下的三個不同處理器集合的執行時間見表1。從實驗數據可以得出，處理器集合之間是不等價的[10]。

上述實驗數據證明了非等價性的存在，對于給定的算法和處理器集合(m*n)的體系結構組合，其中n是節點的數量，m是節點內處理器的數量。執行程序時間最短的可以稱其為最優處理器集合。在上述例子中，“1*4”是最優處理器集合。

表1 三個不同的處理器集合上的并行執行時間

通過對SMP集群體系結構的詳細分析，得到處理器集合之間的非等價性是由以下兩個異構性引起的[10]：

(1)通信異性：在SMP集群中，有兩種通信方法是節點內共享內存和節點之間消息傳遞。

(2)資源異構性：節點內處理器共享資源，并且各節點有自己的專用資源。

以上因素從不同的方向影響此問題。

2 等效率可擴放性評價準則

2.1 傳統等效率可擴放性評價準則

可擴放性的概念是與加速比和效率的概念緊密相關的。在等效率可擴放性準則中，設P個處理器系統上的工作負載W的程序串行執行時間為Tpara=W·tc，其中tc為常數。可以推出并行系統的運行時間函數[1]如式(1)：

(1)

其中，T0為開銷時間，即所有處理器與相鄰節點進行通信的時間，消息的等待，空閑時間等。

則并行算法的加速比[1]可以表示為：

(2)

并且得出Kumar[4]等提出的等效率公式，即：

(3)

(4)

令a=E/(1-E)，等效率函數可以寫為：

W=a·T0

(5)

傳統等效率函數揭示了并行算法和并行機結構相結合影響下的計算性能。以上函數說明當處理器規模P增加時，如果保持效率不變，必須相應增加工作負載W。W和P增加時，滿足函數關系式W=F(p)，稱F為等效率函數，且并行系統可擴放。而傳統等效率可擴放評價準則把處理器個數P作為一個評價參數，顯然不適合SMP集群系統。

2.2 SMP集群可擴放性準則

基于以上討論，SMP集群中各個處理器集合的處理能力不同，必須先定義系統中處理器集合的處理能力概念。然而無論采用任何一種等性能的評價準則，參數P都會出現在效率E和平均速度V'的定義中[1]。而用參數P描述SMP集群的處理器集合的能力缺乏準確性和適用性。為了解決此問題，需要定義一個新的參數來代替參數P，以改進適合SMP集群系統的可擴放性評價準則。

由并行系統的速度公式可以得知[1]：VP=W/TP=(W·P)/(Te+T0)=P/(1+T0/W)，速度反映了有效計算和通信開銷的比例關系，并且由問題規模W、處理器集合P和通信開銷T0三個性能參數決定。因此它也反映了并行算法和體系結構的影響。所以速度(非平均速度)V是非常適合描述并行系統中處理器集合的處理能力[13]。但是由于P是一種無量綱參數，而不能直接使用速度來代替參數P，所以需要將其轉化成一個無量綱參數。

旨在對可擴放性進行理論研究，在此假定工作負載按比例劃分到處理器中。設W(1)為并行系統中單個處理器上的工作負載，W(m*n)為并行系統中處理器集合上m*n的工作負載，那么可以得到W(m*n)=PW(1)[10]。

設ΦV表示處理器集合規模為m*n的并行系統求解任務規模為W的相對速度因子。

定義1：系統每個處理器集合的相對速度因子為：

ΦV=V(m*n)/V(1)(m=1,2;n=1,2,…,6)

(6)

其中，V(1)為并行程序在單處理器上的運行速度；V(m*n)為并行程序在處理器集合m*n上的運行速度。

在實際操作中，速度是不易直接測量的，經過式(7)推導將速度比轉化為測量執行時間比，計算出相對速度因子，由式(6)推得：

(7)

其中，T(1)為并行程序在單一處理器上的執行時間；T(m*n)為并行程序在處理器集合m*n上的執行時間。

定義2：用相對速度因子代替P，得到新的效率函數：

(8)

從式(8)中可以看出，改進模型與Kumar[4]等提出的方法相比有一個很重要的優勢：改進的模型能夠應用于不等價的處理器集合中。即引入一個新的參數ΦV，此參數能更好地表示處理器集合的處理能力。這個表達式反映了SMP集群系統中的可擴放性依賴于處理器的相對速度因子。

分析一下傳統等效率模型和改進后等效率模型的關系，當改進等效率模型應用于一般并行或分布式體系結構中時，如果每個節點有一個處理器，所有的處理器集合是等價的，并且EP被E替代，也就是說E是EP的一種特殊情況。

3 實 驗

第2節通過問題的分析和公式推導得出改進的等效率可擴放性評價準則，進一步通過相關實驗來驗證模型的有效性。

3.1 實驗配置

在大型科學和工程計算中，矩陣運算是數值計算中最重要的一類運算。矩陣相乘算法由于計算量大、計算和通信相對平衡，常被用來作為并行計算的基準測試程序。

C階的矩陣A和B相乘算法的計算工作負載用W表示。實驗并行矩陣乘法的并行算法有很多，為了便于比較，選擇帶狀劃分的行列劃分算法[14]。

開展實驗的系統平臺為曙光TC5000集群，集群平臺由以6個CB65刀片為計算節點通過高速系統網絡互連，以一臺A620r-H作為登陸管理節點。每個CB65刀片節點擁有兩顆AMD CPU，共計8個核，3.0 Gfloads；操作系統為SUSE Linux Enterprise Server 10SP2，OpenMP編譯器采用OMPi-1.4版，GCC版本為4.8.1，網絡協議為IPv4。OpenMP使用的是支持OpenMP制導語句的GCC4.8.1，MPI使用的是MPICH2，在編譯MPI與OpenMP程序時使用的GCC 4.8.1編譯器，編譯時需加參數-lMPICH和-fOpenMP，在MPICH2環境中運行。

3.2 實驗結果及分析

在曙光TC5000集群平臺上運行實際程序，不斷改變處理器集合的規模和矩陣規模，測量和計算的實驗數據如表2、表3和圖2、圖3所示。

表2是根據2.2節中的定義在集群環境下測得的相對速度因子，它是某一固定程序在單一處理器集合上的運行速度和此程序在處理器集合m*n上的運行速度的比值。

表2 各處理器集合執行時間和相對速度因子

表3 各處理器集合執行時間和效率

表3是在集群環境下測得的實驗數據，得出了在不同的處理器集合和工作負載下的執行時間和效率。從數據可以看出，當工作負載保持不變，只增加處理器集合的數量，會導致額外開銷的增加，系統并行效率EP會有所下降。當處理器集合的數量不變，增加工作負載，因為工作負載增長快于并行效率EP的增長，所以增加了效率EP。

圖2和圖3是表3中測試數據的圖形化表示。可以看出所提出的可擴放性準則在工作負載隨處理器結合擴展時能保持很好的計算效率。

以上實驗和在文獻[4]中該方法產生的結果和理論預測值十分相似，表明以上改進等效率模型是一個準確模型。該模型可以指導工作負載如何隨著機器規模進行擴展，實現了在SMP集群系統中進行可擴放性分析。

圖2 工作負載隨1-處理器集合擴展時的效率變化曲線

圖3 工作負載隨2-處理器集合擴展時效率的變化曲線

4 結束語

為解決SMP集群中存在的問題，在前人工作的基礎上，基于對傳統的等效率可擴放評價準則的分析，將速度作為重要的性能參考因素，并引入到傳統等效率模型，并對其進行改進，保證了經改進的準則在SMP集群環境下能夠滿足矩陣相乘算法與SMP集群系統相結合的可擴放性評價需求。實驗結果表明，并行算法和集群相結合的并行系統具有良好的可擴放性。

[1] 陳國良.并行計算:結構·算法·編程[M].北京:高等教育出版社,2011.

[2] 黃 鎧,徐志偉.可擴展并行計算:技術·結構·編程[M].北京：機械工業出版社,2000.

[3] 遲利華,劉 杰,胡慶豐.數值并行計算可擴展性評價與測試[J].計算機研究與發展,2005,42(6):1073-1078.

[4] Grama A, Gupta A, Kumar V.ISO-efficiency:a scalability metric for parallel algorithms and architectures[J].IEEE Parallel & Distributed Technology Systems & Applications,1993,1(3):12-21.

[5] Sun X H,Rover D T.Scalability of parallel algorithm-machine combinations[J].IEEE Transactions on Parallel Distributed Systems,1994,5(6):599-613.

[6] Zhang X,Yan Y,He K.Latency metric:an experimental meth-od for measuring and evaluating parallel program and architecture scalability[J].Journal of Parallel and Distributed Computing,1994,22(3):392-410.

[7] 王之元.并行計算可擴展性分析與優化[D].長沙:國防科學技術大學,2011.

[8] 陳 軍,李曉梅.近優可擴展性:一種實用的可擴展性度量[J].計算機學報,2001,24(2):179-182.

[9] 祝永志,李丙峰,孫婷婷,等.并行計算系統可擴展性的研究[J].計算機工程與應用,2011,47(21):47-49.

[10] 何家華,陳國良,單久龍.如何測量SMP機群可擴放性(英文)[J].軟件學報,2004,15(7):977-986.

[11] Bosque J,Robles O,Toharia P,et al.Analyzing scalability of parallel systems with unbalanced workload[J].Journal of Supercomputing,2013,64(1):110-119.

[12] 遲利華,劉 杰,李曉梅,等.并行算法與并行機相結合的可擴展性[J].計算機研究與發展,1999,36(1):47-51.

[13] 熊煥亮,曾國蓀,吳滄海.一種等性能面積的并行計算可擴展性度量方法[J].計算機研究與發展,2014,51(11):2547-2558.

[14] 熊煥亮,曾國蓀,吳滄海,等.延遲可擴展性與并行執行時間的關系[J].計算機應用,2014,34(3):663-667.

Analysis on Scalability of SMP Cluster System

TIAN Qing，ZHU Yong-zhi

(School of Information Science and Engineering,Qufu Normal University,Rizhao 276826,China)

With the rapid development of parallel computing technology and the popularity of SMP clusters,scalability has become one of the most important performance for parallel application program design and implementation.However,the traditional scalability metric cannot evaluate the scalability of SMP cluster accurately.Therefore,the definition has been proposed to describe the efficiency of SMP cluster system based on the analysis of the property of the set of processors and the ISO-efficiency function in SMP cluster,understanding their merits and deficiencies,as well as the analysis of the parallel execution speed.Then a new metric,improved ISO-efficiency metric,has been proposed,which can be used to measure and evaluate the scalability of parallel algorithms and SMP cluster.The extension experiments have been carried out on the cluster platforms by running the program for the matrix multiplication algorithm in order to validate the effectiveness of the new evaluation criteria.Experimental results show that the new evaluation criterion has guided the optimal matching of the parallel application and the parallel machines.Thus it is helpful to the design and the improvement of parallel algorithms.

parallel computing;SMP clusters;scalability;ISO-efficiency

2016-08-07

2016-11-16 網絡出版時間：2017-04-28

山東省自然科學基金(ZR2013FL015)；山東省研究生教育創新資助計劃(SDYY12060)

田 青(1989-)，女，碩士研究生，研究方向為并行計算；祝永志，教授，研究生導師，通訊作者，研究方向為并行計算。

http://kns.cnki.net/kcms/detail/61.1450.TP.20170428.1704.092.html

TP301

A

1673-629X(2017)06-0095-04

10.3969/j.issn.1673-629X.2017.06.020