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