SMP集群系統(tǒng)的可擴放性分析

田 青，祝永志

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

SMP集群系統(tǒng)的可擴放性分析

田 青，祝永志

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

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

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

0 引 言

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

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

針對多核SMP集群的體系結(jié)構(gòu)特點，在分析現(xiàn)有等效率可擴放性評價準(zhǔn)則的特點及其不足的基礎(chǔ)上，改進了傳統(tǒng)等效率可擴放性評價準(zhǔn)則以適合SMP集群體系結(jié)構(gòu)，并應(yīng)用該準(zhǔn)則分析了并行算法與該性能并行機相結(jié)合的可擴放性。

1 SMP集群結(jié)構(gòu)分析

1.1 SMP集群結(jié)構(gòu)體系

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

圖1 SMP集群體系結(jié)構(gòu)

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

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

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

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

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

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

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

(2)資源異構(gòu)性：節(jié)點內(nèi)處理器共享資源，并且各節(jié)點有自己的專用資源。

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

2 等效率可擴放性評價準(zhǔn)則

2.1 傳統(tǒng)等效率可擴放性評價準(zhǔn)則

可擴放性的概念是與加速比和效率的概念緊密相關(guān)的。在等效率可擴放性準(zhǔn)則中，設(shè)P個處理器系統(tǒng)上的工作負載W的程序串行執(zhí)行時間為Tpara=W·tc，其中tc為常數(shù)?？梢酝瞥霾⑿邢到y(tǒng)的運行時間函數(shù)[1]如式(1)：

(1)

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

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

(2)

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

(3)

(4)

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

W=a·T0

(5)

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

2.2 SMP集群可擴放性準(zhǔn)則

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

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

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

設(shè)ΦV表示處理器集合規(guī)模為m*n的并行系統(tǒng)求解任務(wù)規(guī)模為W的相對速度因子。

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

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

(6)

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

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

(7)

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

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

(8)

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

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

3 實 驗

第2節(jié)通過問題的分析和公式推導(dǎo)得出改進的等效率可擴放性評價準(zhǔn)則，進一步通過相關(guān)實驗來驗證模型的有效性。

3.1 實驗配置

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

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

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

3.2 實驗結(jié)果及分析

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

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

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

表3 各處理器集合執(zhí)行時間和效率

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

圖2和圖3是表3中測試數(shù)據(jù)的圖形化表示?？梢钥闯鏊岢龅目蓴U放性準(zhǔn)則在工作負載隨處理器結(jié)合擴展時能保持很好的計算效率。

以上實驗和在文獻[4]中該方法產(chǎn)生的結(jié)果和理論預(yù)測值十分相似，表明以上改進等效率模型是一個準(zhǔn)確模型。該模型可以指導(dǎo)工作負載如何隨著機器規(guī)模進行擴展，實現(xiàn)了在SMP集群系統(tǒng)中進行可擴放性分析。

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

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

4 結(jié)束語

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

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

[2] 黃 鎧,徐志偉.可擴展并行計算:技術(shù)·結(jié)構(gòu)·編程[M].北京：機械工業(yè)出版社,2000.

[3] 遲利華,劉 杰,胡慶豐.數(shù)值并行計算可擴展性評價與測試[J].計算機研究與發(fā)展,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] 王之元.并行計算可擴展性分析與優(yōu)化[D].長沙:國防科學(xué)技術(shù)大學(xué),2011.

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

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

[10] 何家華,陳國良,單久龍.如何測量SMP機群可擴放性(英文)[J].軟件學(xué)報,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] 遲利華,劉 杰,李曉梅,等.并行算法與并行機相結(jié)合的可擴展性[J].計算機研究與發(fā)展,1999,36(1):47-51.

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

[14] 熊煥亮,曾國蓀,吳滄海,等.延遲可擴展性與并行執(zhí)行時間的關(guān)系[J].計算機應(yīng)用,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 網(wǎng)絡(luò)出版時間：2017-04-28

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

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

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