田 青，祝永志

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

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

田 青，祝永志

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

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

并行計(jì)算；SMP集群；可擴(kuò)放性；等效率

0 引 言

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

以上因素從不同的方向影響此問(wèn)題。

2 等效率可擴(kuò)放性評(píng)價(jià)準(zhǔn)則

2.1 傳統(tǒng)等效率可擴(kuò)放性評(píng)價(jià)準(zhǔn)則

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

(1)

其中，T0為開(kāi)銷時(shí)間，即所有處理器與相鄰節(jié)點(diǎn)進(jìn)行通信的時(shí)間，消息的等待，空閑時(shí)間等。

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

(2)

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

(3)

(4)

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

W=a·T0

(5)

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

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

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

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

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

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

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

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

(6)

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

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

(7)

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

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

(8)

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

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

3 實(shí) 驗(yàn)

第2節(jié)通過(guò)問(wèn)題的分析和公式推導(dǎo)得出改進(jìn)的等效率可擴(kuò)放性評(píng)價(jià)準(zhǔn)則，進(jìn)一步通過(guò)相關(guān)實(shí)驗(yàn)來(lái)驗(yàn)證模型的有效性。

3.1 實(shí)驗(yàn)配置

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

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

開(kāi)展實(shí)驗(yàn)的系統(tǒng)平臺(tái)為曙光TC5000集群，集群平臺(tái)由以6個(gè)CB65刀片為計(jì)算節(jié)點(diǎn)通過(guò)高速系統(tǒng)網(wǎng)絡(luò)互連，以一臺(tái)A620r-H作為登陸管理節(jié)點(diǎn)。每個(gè)CB65刀片節(jié)點(diǎn)擁有兩顆AMD CPU，共計(jì)8個(gè)核，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)語(yǔ)句的GCC4.8.1，MPI使用的是MPICH2，在編譯MPI與OpenMP程序時(shí)使用的GCC 4.8.1編譯器，編譯時(shí)需加參數(shù)-lMPICH和-fOpenMP，在MPICH2環(huán)境中運(yùn)行。

3.2 實(shí)驗(yàn)結(jié)果及分析

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

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

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

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

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

圖2和圖3是表3中測(cè)試數(shù)據(jù)的圖形化表示。可以看出所提出的可擴(kuò)放性準(zhǔn)則在工作負(fù)載隨處理器結(jié)合擴(kuò)展時(shí)能保持很好的計(jì)算效率。

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

圖2 工作負(fù)載隨1-處理器集合擴(kuò)展時(shí)的效率變化曲線

圖3 工作負(fù)載隨2-處理器集合擴(kuò)展時(shí)效率的變化曲線

4 結(jié)束語(yǔ)

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

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

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

[3] 遲利華,劉 杰,胡慶豐.數(shù)值并行計(jì)算可擴(kuò)展性評(píng)價(jià)與測(cè)試[J].計(jì)算機(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] 王之元.并行計(jì)算可擴(kuò)展性分析與優(yōu)化[D].長(zhǎng)沙:國(guó)防科學(xué)技術(shù)大學(xué),2011.

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

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

[10] 何家華,陳國(guó)良,單久龍.如何測(cè)量SMP機(jī)群可擴(kuò)放性(英文)[J].軟件學(xué)報(bào),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ī)相結(jié)合的可擴(kuò)展性[J].計(jì)算機(jī)研究與發(fā)展,1999,36(1):47-51.

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

[14] 熊煥亮,曾國(guó)蓀,吳滄海,等.延遲可擴(kuò)展性與并行執(zhí)行時(shí)間的關(guān)系[J].計(jì)算機(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ò)出版時(shí)間：2017-04-28

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

田 青(1989-)，女，碩士研究生，研究方向?yàn)椴⑿杏?jì)算；祝永志，教授，研究生導(dǎo)師，通訊作者，研究方向?yàn)椴⑿杏?jì)算。

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