高级计算机体系结构第3幸性能评测

m

第3幸性能评测

五神敖师,‘未明

电话：67792165

Email:zhuming@

0♦也

本章学习要求:

合了解：什么是并行机的基本性能。

卷了解：为什么要研究并行机的性能评测。

⑥掌握：如何评测并行机的性能：

B机器级性能评测

■算法级性能评测

I程序级性能评测

3

3.1什么是并行机的基本性能

♦所谓机器的性能(Performance)通常是指机器的速度，

它是程序执行时间的倒数。而程序执行时间是指用户

向计算机送入一个任务后，直到获得他需要的结果这一

段等待时间，包括访问磁盘和访问存储器的时间，CPU

运算时间，I/0动作时间以及操作系统的开销时间等。

但在多任务系统中，CPU在等待I/0操作的同时可以转去

处理另一个任务,这样分析起来就比较麻烦。所以在讨

论性能时，有时也使用CPU时间，它表示CPU的工作时间,

不包括I/O等待时间和运行其它任务的时间。很显然，

用户所看到的执行时间是程序结束时所花费的全部时

间，而不单是CPU时间。

4

1.单CPU性能

假定机器的时钟周期为Tc,程序中指令总条数为IN，

执行每条指令所需的平均时钟周期数为CPI,则一个程

序在CPU上运行的时间Tcpu为：

=【(3.1)

TCPUNxCPIxTc

其中,n

执行整个程序所需的睡中周期数二'（b'x，）

(3.2)

程序中指令总数■TN

nA/、

cpi-ycPL1x，T(3.3)

i=l\】NJ

n为程序中所有指令种类数

"In表示第i种指令在程序中所占的比例

5

0■也

«TFT夕A千八3

2.MIPS和MFLOPS

MIPS(Mi11ionInstructionsPerSecond)即每

秒百万条指令，它很适合于评测标量机。对于一个给定

的程序，MIPS可表示为：

66

MIPS=IN/(TEX10)=RC/(CPIx10)

=IN/(INxCPIxTcx1Q6)(3.4)

其中，TE表示程序执行时间，Rc表示时钟速率，它是Tc的倒数。

MFLOPS(Mi1lionFloatingPointOperations

PerSecond)常用来评价向量计算机的性能，表示每

秒百万次浮点运算：

6

MFLOPS=IFN/(TEX10)(3.5)

其中，IFN表示程序中的浮点运算次数。

6

）熏学大号

3.并行机的基本性能指标

并行计算机的基本性能参数可概括于表3.1中。

7

0■也

林口

名称付万含意单位

机器规模n处理器的数目无量纲

时钟速率f时钟周期长度的倒数MHZ

工作负载W计算操作的数目Mflop

顺序执行时间J程序在单处理机上的运行时间s（秒）

并行执行时间程序在并行机上的运行时间S（秒）

Tn

速度每秒百万次浮点运算Mflop/s

Rn=W/Tn

加速ST£衡量并行机有多快无量纲

效率En=S"n衡量处理器的利用率无量纲

峰值速度Rpeak—□Rpeak所有处理器峰值速度之积，R”akMflop/s

为一个处理器的峰值速度

利用率可达速度与峰值速度之比无量纲

U=R"Roeak

通信延迟传送0-字节或单字的时间Ms

渐近带宽_传送长消息通信速率___________MB/j

8

当今,计算机的性能评价与测试是一个正在研究中

的课题,它与计算机体系结构,计算机软件,计算机算法

共同构成了新兴的计算科学(ComputationalSciences)

的四大支柱。并行计算机系统远比单处理机系统复杂

得多，所以为了更好地用好并行机,充分发挥其长处，以

适应不同应用问题的需求,评价与测试并行计算机的多

种性能是非常必要的。

9

«0T■FT也夕A千八3

1.发挥并行机长处,提高并行机的使用效率

通过对不同并行计算机的性能进行测试,可以评价

其优、缺点。根据它们的特点，对口相应的应用领域，

充分发挥其长处，以提高并行计算机的使用效率。例如,

通过测试CPU性能可以为计算密集(Compute-

Intensive)型应用问题建议较合适的并行机；通过测

试网络性能，可以为网络密集(Network-Intensive)型

应用问题建议较适宜的并行机；通过对存储器和I/O

通道性能的评试,可以为数据密集(Data-Intensive)型

应用问题建议较满意的并行机等。

10

«0T■FT也夕A千八3

2.减少用户购机盲目性，降低投资风险

对于某一特定用户而言，并非购买越贵的机器越好。

应该根据自己的计算问题特点，通过使用基准测试程序

（见本章2.4节）所得到的一些结果数据，来帮助你决策

购买何种并行计算机。并行计算机一般都很贵,一旦所

购买的计算机在具体的应用中不能发挥应有的作用，那

将是莫大的浪费。一般而言，用户大都不是并行计算机

方面的专家，为减少购买并行机的投资风险，通过各种

性能评测手段来最大限度地减少引进和购买并行计算

机的盲目性是非常重要的。

11

0■也

3.改进系统结构设计，提高机器的性能

并行计算机是个庞大复杂的系统，即使具有丰富

设计经验的人员，也很难保证所设计出的计算机系统

十全十美。任何成功的设计都不可能一次完成，总是

通过测试试用，不断修改、补充以臻完善。其中，按照

性能测试所产生的测试结果比较全面，能够暴露设计中

的一些问题，这些问题对计算机设计者具有比较大的指

导意义,针对这些问题改进现有的设计,可进一步提高

计算机的性能，以适应各方面的应用需求。

12

«0T■FT也夕A千八3

4.促进软/硬件结合，合理功能划分

根据对计算机性能的实际测试和统计分析,可以明

确计算机所应完成的软件与硬件职能，合理的功能划

分以及适当的软/硬件折衷。对于那些使用频繁、功能

较简单的操作，在硬件工艺许可的情况下，当以硬件实

现之；而对于那些不常使用、功能又较复杂的操作，在

软件复杂度允许的情况下，当以软件代替之。这些常识

范围内的知识，必须建立在对计算机的性能进行全面地

测试和客观地分析的基础上。特别是在技术工艺水平

不断提高，器件成本不断下降的今天,计算机软件功能

硬化的趋势似乎越来越明显。

13

«0T■FT也夕A千八3

5.优化“结构-算法-应用”的最佳组合

通过对计算机性能的评测，可以发现什么类型的体

系结构比较适合于什么类型的问题求解算法；哪一类

体系结构对哪一类应用问题比较有效；某类算法比较

适合于求解某类应用问题。例如，网孔连接的并行机

结构比较适合于矩阵运算之类的算法；树连接的并行

结构比较适合于与数据库有关的一类应用问题；数字

滤波这一类的算法是数字信号处理应用中经常使用的

算法。当通过性能评测得出上述结论后，我们就可针

对某类应用问题，设计出可以高效运行某种体系结构

上的算法了。

14

0■也

«TFT夕A千八3

6.提供客观、公正的评价并行机的标准

不同的用户（包括机器的系统操作员），会从不

同的角度来评价并行机的性能优劣。研究并行机的性

能评测的根本目的之一，就是要试图提供一个统一的、

客观的、公正的和可相互比较的评价并行计算机的标

准。为此就要从并行机的硬件体系、软件功能、解题

能力、使用目的和测试手段等各个方面来评测并行计

算机的性能。

15

3.3如何评测并行机的性能

怎样评测一台计算机的性能，与测试者的出发点

有关。例如，计算机用户说机器很快，往往是因为程

序运行时间短；而计算机管理员说机器很快，往往是

因为在一段时间内它能够完成更多的任务。用户所关

心的是从提交任务开始到运行结束之间的时间，即执

行时间；而管理员所关心的是在单位时间能完成的工

作量，即吞吐率(Throughput)。

所以，如何客观、公正地评价计算机的性能不是

一件容易的事，要涉及到计算机系统的诸多因素，它不

仅与机器硬件速度有关，而且还与机器体系结构、计算

方法与算法、程序编译优化、编程工具与环境,甚至与

测试方法手段等有关。

16

0■也

■■

本节试图根据机器性能评测的层次,分别从

机器级、算法级和程序级三个层次来研究它们。

请注意这种分层也只是为了讨论的方便。

17

3.3.1机器级的性能评测

机器级的性能评测，包括:

AcPU和存储器的某些基本性能指标；

►并行和通信开销分析；

A并行机的可用性与好用性；

A机器成本、价格与性/价比等。

它们中的有些是由机器厂商在销售时直接提供给

用户的，是广大用户对并行计算机的第一印象,是引进

和购买并行计算机时最主要的选择依据,特别是机器的

基本性能指标和机器的价格是诸多并行机之间最可比

的数据,也是非计算机专业用户选购并行机时决策的主

要依据。

18

CPU和存储器的某些基本性能

指标

1.CPU性能

⑴工作负载(W)：所谓工作负载(荷)，就是计算操作的

数目，通常可用执行时间，所执行的指令数目和所完成

的浮点运算数三个物理量来度量它。其中，

①执行时间：它可定义为在特定的计算机系统上的一

个给定的应用所占用的总时间，系指应用程序从开始到

结束所掠过的时间(ElapsedTime),它不只是CPU时间,

还包括了访问存储器、磁盘、I/O通道的时间和OS开

销等。影响执行时间主要因素有求解应用问题所使用

的算法；输入数据集及其数据结构；求解问题的硬件

平台和操作系统以及所使用的语言、编译/编辑器和二

进制代码的库函数等。

19

0■也

②浮点运算数：对于大型科学与工程计算问题,使用所

执行的浮点运算数目来表示工作负载是很自然的。对

于程序中的其它类型的运算，可按如下经验规则折算

成浮点运算（FLOP）数：在运算表达式中的赋值操作、

变址计算等均不单独考虑（即它们被折算成0FLOP）;

单独赋值操作、加法、减法、乘法、比较、数据类型

转换等运算均各折算成1FLOP;除法和开平方运算各

折算成4FLOP;正（余）弦、指数类运算各折算成8

FLOP;其它类运算，可按其复杂程度，参照上述经验

数据进行折算之。注意，在理论分析时，常常假定各

条指令和每个浮点运算均取相同时间，这种均匀一致

的速度假定在实际的计算系统中总是难以成立的。

20

«0T■FT也夕A千八3

③指令数目：它与机器的指令系统有关。对于任何给

定的应用，它所执行的指令条数就可视为工作负载，

常以百万条指令为计算单位，与其相应的速度单位就

是MIPS（每秒百万条指令）。不过用MIPS来表示工作

负载时要注意机器实际执行的指令数不一定就是汇编

程序中的指令数；所需执行的指令数目可能是依赖于

输入数据值；即使对于固定的输入使用相同的高级语

言，执行在RISC机器上的指令数通常比在CISC机器上

指令数要多50%〜150%;即使在相同的机器上，使用固

定的输入，程序执行的指令数也会因不同的编译或优

化方法而不同；最后，较多的指令数也不一定意味着

程序地执行时间就长。

21

«0T■FT也夕A千八3

（2）并行执行时间：

在无重叠操作的假定下，并行程序的执行时间Tn为：

T_T_|_T+T6）

1n-1comput1paro1comm0）

其中，、。呻玳为计算时间，Tparo为并行开销时

间，几。1nm为相互通信时间。而Tpar。包括进程管理（如进

程生成、结束和切换等）时间，组操作（如进程组的生成

与消亡等）时间和进程查寻（如询问进程的标志、等级、

组标志和组大小等）时间；口项包括同步（如路障、锁、

临界区、事件等）时间，通信（如点到点通信、整体

通信、读/写共享变量等）时间和聚合操作（如归约、

前缀运算等）时间。

22

（0E■也/灯千入J

了解这些额外开销对开发并行程序大有好处：例如,

要是并行开销Tpar。较小，则程序员可使用动态并行程

序；否则使用静态并行程序较好，因为进程只在开始

时生成而结束时消灭。又如，如果机器支持路障同步，

则可使用同步算法；如果路障操作太费时，则可使用

异步算法。

下面让我们使用异步PRAM模型（即APRAM）来估计

一下并行执行时间。

23

簸群大号

卷在APRAM模型中，计算系由一系列用同步路障分开的所

谓相(Phase)所组成。在每个相内，各个处理器均异

步地执行局部计算，每个相中最后一条指令是同步路

障指令。假定在第i相内计算量(即工作负载)为W追

计算时间为T](i)。令DOP(DegreeofParalleiism)

表示能够同时执行的最大进程数，称之为并行度。对

于n个处理器的并行系统，显然14DOPi《n。而在

第i相中并行执行时间为T0(i)=TNi)/n,所以在n个

处理器的系统中，其总的并行执行时间为：

T_x1（，）______7+7

±±3.7

n-/.•/八八厂！\parocomm

24

11打号

令Ts代表在使用无限多的处理器（n-8）且不考虑

Tparo和Tc°mm时的应用程序执行时间，于是有：

T二丁T1⑴

00幺DOPj3.8

定义为了达到Tn=Too的最小n值为N啥，称其为最

大并行度，也就是能够用来降低执行时间的最大处理

器数，则有：

Nmax=max（。。尸J

IIIdX-J»XI/3.9

\<i<k

可能达到的最高性能之上界可定义为:

S———W340

8FTJ25

00

而n个处理器的执行时间下界为：

TGmaxCTi/n,TQ(3.11)

Brent[1]已经证明，不考虑丁。&1。和丁阿皿时，北满足

下式：

工5占十兀(3.12)

nn

将(3.11)代入(3.12),则有:

(T、T

max△，兀工14二+图(3.13)

\n)n

0■也

,TFTj、A¥入3

♦2.存储器性能

(1)存储器的层次结构：

在近代计算机中，为了加快处理器与存储器之间的

数据移动，存储器通常按层次结构进行组织。如图3.1

所示，对于每一层均可用三个参数表征之：①容量C:

表示各层的物理存储器件能保存多少字节的数据；②

延迟L：表示读取各层物理器件中一个字所需的时间；

③带宽B：表示在1秒钟内各层的物理器件中能传送多

少个字节。各层存储器及其相应的典型的C、L、B值示

于图3.1中。

27

C<2KB4-256KB64KB-4MB16MB-16GB1-100GB

『0周期0-2周期2-10周期10-100周期100KTM周期

B=1-32GB/S1-16GB/S1-4GB/S0.4-2GB/S1-16MB/S

图3.1各层存储器的典型性能参数

28

0■也

«TFT夕A千八3

■BaBBBaaMMaMBasBsaBBBMBBMHaaaMBaaMBBHBaBBBaaMMaMBasaBaBHBMBBQflHaaaMBaaMBBHBaBBBaBMaaMBasaBaBHBMBBaaaaaaMBaaMBBHBas

(2)存储器带宽的估算：

假定字长为64位，即8字节。对于RISC类型机器中

的加法操作，它从寄存器中取2个64位的字相加后再回

送至寄存器。通常RISC加法指令可在单拍内完成，如果

使用100MHZ的时钟,那么存储带宽将是

3x8x100x106=2.4GB/S可见，较快的时钟和处理器中

较高的并行操作,可获得较宽的带宽。

29

并行和通信开销分析

这一节主要讨论由于并行而招致的时间开销Tparo

和多进程相互作用所引起的通信开销Tcomni。这两种时

间开销均比普通的计算时间要长得多，而且随系统不同

而变化很大。例如，一个P0WER2处理器每个时钟周期

(15ns)能执行4个浮点运算，但生成一个Unix进程

(1.4口s)可长得足以执行372000个浮点运算!通常，这

么大的开销主要是由OS核和系统软件所造成的。有了

这样的数字印象后，在使用并行和通信操作时就要慎重。

30

0■也

1.开销的量化

既然这些额外开销如此之大，那么就应该定量化它们。

但是,现实情况是计算机厂商们既很少提供数据,也很

少提供开销的估计方法。Hockney曾针对点到点通信给

出了几个有关开销的参数r8、nil/2、tO和兀0。下面

我们修介绍使用测量的方法来量化这些开销参数。开

销的测量与所使用的数据结构、程序语言、通信硬件

与协议以及计时方法（挂钟时间或CPU时间）等有关。为

了获得精确的测量值并非易事，因为绝大多数机器系统

只提供粗的时间分辩率（微秒级，甚至毫秒级）；并行机

中的各处理器常以异步方式操作，不合公共时钟节拍；

测量结果离散性太大，所以比较普遍的方法是采用点

到点乒一乓测量法。

31

、静0■也”"号

2.开销的测量

对于点到点的通信，测量开销使用使用乒一乓方法

(Ping-PongScheme)：节点0发送m个字节给节点1;节

点1从节点0接收m个字节后，立即将消息发回节点0。总

的时间除以2,即可得到点到点通信时间，也就是执行单

一发送或接收操作的时间。用乒一乓方式测量延迟的

代码段如下：

乒-乓方法可一般化为热土豆法(Hot-Potato),也

称为救火队法(Fire-Brigade)：节点。发送m个字节

点1,节点1在将其发送给接点2,依此类堆，最后节点

n-1再将苴法回给节占0.最后时间再除以n即可一

32

//*乒_乓法测量延迟的代码段*//

fori=0toRuns-1do/*发送者*/

if(my-node_id=0)then

temp=second()/*second()为时标函数*/

start_time=second()

sendanm-bytemessagetonode1

receiveanm-bytemessagefromnode1

end-time=second()

timer-overhead=start-time-timer_overhead

tota1_time=end-time-start-time+timer.overhead

communication_time[i]=total.time/2

elseif(my_node_id=1)then/*接收者*/

receiveanm-bytemessagefromnode0

sendanm-bytemessagetonode0

endif

endif

33

）熏学大号

3.开销的表达式

通过测试方法所获得的开销数据，通常有3种方法

进行解释：

列表法

绘图法

解析法

其中解析表示法是最通用的。

34

0■也

,TFTj、A¥入3

⑥⑴点到点的通信:Hockney对于点到点的通信,给出

了如下所示的通信开销t(ni)的解析表达式，它是消息

长度m(字节)的线性函数：

t(m)=t0+m/r0G(3.14)

其中，t0是启动时间(RS);一是渐近带宽(MB/S),

表示传送无限长的消息时的通信速率。Hockney也同时

引入了两个附加参数：半峰值长度叫〃(字节)，表示达

到一半渐近带宽(即1/21)所需要的消息长度；特定

性能兀°(MB/S),表示短消息带宽。4个参数t。、■、

叫/2和兀0中只有两个是独立的，其它两个可使用如下关

系式推导出：

tO=ml/2/r°°=1/TTO(3.15)

35

0■也

«TFT夕A千八3

⑵整体通信：

几种典型的整体通信有：

①播送(Broadcasting)：处理器。发送m个字节

给所有的n个处理器；

②收集(Gather)：处理。接收所有n个处理器发来

在消息，所以处理器。最终接收了mn个字节；

③散射(Scatter)：处理器0发送了m个字节的不同

消息给所有n个处理器，因此处理器。最终发送了nin个

字节；

④全交换(TotalExchange)：每个处理器均彼此

相互发送m个字节的不同消息给对方，所以总通信量为

nm2个字节；

36

)熏学大号

⑤循环移位(Circular-shift):处理器i发送m个

字节给处理器i+1,处理器n-1发送ni个字节给处理器0,

所以通信量为mn个字节。有文献将公式(3.14)推广之,

使得通信开销T(ni,n)是m和n的函数，但与1co只是n

的函数：

T(m,n)=t0(n)+m/1co(n)(3.16)

同时,他们对SP2机器所测得的数据进行拟合，推导

出如表3.2所示的整体通信和路障同步开销表达式。

注意，当超过256个处理器时，路障开销为768RS,

等效于执行768x266=204,288个浮点运算。可见只有

当大的计算粒度时，才宜于使用路障操作。

37

0■也

表3.2SP?机器的整体通信和路障同步开销表达式一览表

整体通信操作表达式

播送521ogn+(0.0291ogn)m

收集/散射(171ogn+15)+(0.025n-0.02)m

全交换801ogn+(0.03nL29)m

循环移位(61ogn+60)+(0.0031ogn+0.04)m

路障同步94logn+10

38

”红号并行机的可用性与好用性

一个优良的并行机系统，除了应具有高的基本性能

指标以及低的并行与通信开销外,还应具有：

可用性(Availability):是指系统正常运行时间

的百分比

好用性(Usability):是指用户使用机器时的感受

程度

39

0■也

«TFT夕A千八3

L机器的可用性

人们常将机器的可靠性(Reiiabi1ity),可用性

(Availabi1ity),与服务性(Serviceabi1ity)合在一起

简称为机器的RAS性能，但有时候易将它们的概念相混

淆。事实上，可靠性是用平均无故障时间MTTF(Mean

TimeToFai1)来度量，系指系统失效前平均正常运行

的时间;服务性是用平均修复时间MTTR(MeanTimeTo

Repair)来度量，系指系统失效后修理恢复正常工作的

时间；而可用性被定义为：

Availability=MTTF/(MTTF+MTTR)(2.18)

40

0■也

,TFTj、A¥入3

卷2.并行机的好用性

因为机器的好用性直接与用户有关，所以机器的好

用性的讨论是与并行机系统所提供的用户环境分不开

的。目前用户使用并行机的环境主要有：

①远程登录结合命令行：

这是早期并行机典型的用户环境，用户通过登录到

并行机上，再调用系统命令来完成自己的工作。其优点

是简单、通用，只要并行机提供Telnet服务既可；而缺

点是用户必须熟悉机器的有关命令,且没有图形用户界

面GUI(GraphicUserInterface),所以不够直观。

41

②GUI+X协议:

用户从客户端直接登录到并行机上，利用X协议修

并行机上的用户GUI窗口输送到本地计算机，从而达到

远程使用并行机的目的。其优点是用户远程使用并行

机尤如在本地使用并行机一样，所以很方便；而缺点

是由于用户的图形界面是在并行机上实现的，所以占

用了宝贵的并行计算资源。此外，本地机必须支持X协

议，否则窗口无法传到本地计算机来。

③客户GUI+服务器：

这种方式是由客户端提供用户环境的GUI,并行机

作为服务器解释和执行客户端发来的请求。其优点是

GUI不占用并行计算资源；而缺点是当客户端的机器平

台发生变化时，用户环境的GUI需要专门定制，所以通用

性较差。42

0■也

«TFT夕A千八3

■BaBBBaaMMaMBasBsaBBBMBBMHaaaMBaaMBBHBaBBBaaMMaMBasaBaBHBMBBQflHaaaMBaaMBBHBaBBBaBMaaMBasaBaBHBMBBaaaaaaMBaaMBBHBas

④Web月艮务器+浏览器：

以Web浏览器作为用户环境界面，用户通过统一资

源定位URL(UnifiedResourcesLocation)指定Web服

务器，提出服务请求；Web服务器分析用户请求，再向并

行机发送命令，执行用户请求，并修结果传回给用户界

面。其优点是由于Web的跨平台特性,用户可在任何机

器平台上远程使用并行机,所以通用性非常好；而缺点

是由于浏览器界面(如Applet、Form、Cookie)的表

达能力有限，所以难以修并行机的用户环境全面地、动

态地提供给用户，速度也比较慢。

43

机器的成本、价格与性/价比

高的性能/价格比(Performance/CostRatio)是计

算机设计者和使用者一致的目标。性/价比可定义为速

度/买价，系指用单位代价(通常以百万美元表示)所

获取的性能(通常以MIPS或MFL0PS表示)。例如说,每百

万元能获取多少个MIPS(每秒百万条指令)或多少个

MFL0PS(每秒百万次浮点运算)。高的性/价比就意味着

是成本有效的(Cost-Effectively)。而成本有效性

(Cost-Effectiveness)可用利用率(Uti1ization)来指

示。利用率可定义为可达到的速度与峰值速度之比。

较高的利用率对应着每美元较多的Gflops。

44

（蜘）熏学大号

SPP1000C916J916T916T3D8400SP2-WideSP2-ThinSX-4/16PCXL75

ConvexCrayCrayCrayCrayDECIBMIBMNECSGI

图3.410台并行机的性/价比（1995年）

45

332算法级的性能评测

算法级的性能评测方法，最初大都是为了评价并行

算法的性能提出的，后来这些评测方法也被推广到并行

程序上。众所周知,在并行机上进行计算的主要目的就

是要加速整个计算过程,所以研究并行算法的加速(比)

性能是最根本的。它体现了对于一个给定的应用，并行

算法相对于串行算法的执行速度加快了多少倍。此外，

随着计算负载的增加和机器规模的扩大,研究并行算法

的性能是否能随着处理器数目的增加而按比例的增加

也是很主要的，这就是所谓的并行算法的可扩放性

(Scalabi1ity)问题。由于可扩放性是个很主要的概念,

所以后来推而广之，就出现了诸如程序的可扩放性、

体系结构的可扩放性、工艺技术的可扩放性以及应用

的可扩放性等等。

46

加速比性能定律

简单地讲,并行系统的加速（比）是指对于一个给定

的应用，并行算法（或并行程序）的执行速度相对于串行

算法（或串行程序）的执行速度加快了多少倍。本节修

要讨论三种加速比性能定律：适用于固定计算负载的

Amdahl定律；适用于可扩放问题的Gustafson定律和

受限于存储器的Sun-Ni定律。为了以下讨论方便，兹定

义如下参数：令p是并行系统中处理器数；W是问题规

模（下文中也常叫作计算负载、工作负载，它定义为给

定问题的总计算量），Ws是应用程序中的串行分量,W中

可并行化部分为WP（显然Ws+Wp=W）;f是串行分量比

例（f=Ws/W,Ws=Wl）,l-f为并行分量比例（显然f+量-

f）=l）;Ts=Tl为串行执行时间，Tp为并行执行时间；S

为加速（比）,E为效率。

47

0■也

«TFT夕A千八3

1.Amdahl定律

Amdahl加速定律的基本出发点是：

①对于很多科学计算，实时性要求很高，即在此类应用

中时间是个关键因素，而计算负载是固定不变的。为此

在一定的计算负载下，为达到实时性可利用增加处理器

数来提高计算速度；

②因为固定的计算负载是可分布在多个处理器上的，这

样增加了处理器就加快了执行速度,从而达到了加速的

目的。

在此意义下，1967年Amdahl推导出了如下固定负载的加

速公式：

48

cWs+Wp

s=-------------(3.18)

Ws+Wp/p

为了归一化,Ws+Wp可相应地表示为f+(l-f),所以:

3二-------------------------二----------------------------(3.19)

y1X-f1+f(P-1)

P

当PT8时，上式极限为：

S=1/f(3.20)

49

(9)熏学大号

这就是著名的Amdahl加速定律，它意味着处理器

数目的无限增大，并行系统所能达到的加速之上限为

1/f，此结论在历史上曾对并行系统的发展起到了悲观

的作用。Amdahl定律的几何意义可清楚地表示在图

3.5(a),(b)和(c)中。

J

叵

篇4

屋fe

坛fc

H第

50

(a)(b)(c)

实际上并行加速不仅受限于程序的串行分量，而且

也受并行程序运行时的额外开销影响。令w。为额外开

销，则(3.18)式应修改为：

W

S=p(3.21)

匕+%+畋57/1—7)Rl+/(2一1)+%2/%

fW+—+wo

Pp

当p-8时，上式变为:

(3.22)

f+Wo!W

可见，串行分量越大和并行额外开销越大,则加速越

小。

51

«0T■FT也夕A千八3

2.Gustafson定律

Gustafson加速定律的基本出发点是：

①对于很多大型计算,精度要求很高，即在此类应用中

精度是个关键因素，而计算时间是固定不变的。此时为

了提高精度，必须加大计算量，相应地亦必须增多处理

器数才能维持时间不变；

②除非学术研究，在实际应用中没有必要固定工作负载

而计算程序运行在不同数目的处理器上,增多处理器必

须相应地增大问题规模才有实际意义。

按此意义，1987年Gustafson给出如下放大问题规模的

加速公式：

52

S，=匕+2即=，+—即(323)

~Ws+p-Wp/p~WS+WPI,J

归一化后可得

S'=7+夕(1-f)=p+/(l-p)=p-f(pi)(3.24)

当p充分大时，S，与p几乎成线性关系，其斜率为1-f。

这就是著名Gustafson加速定律,它意味着随着处理器

数目的增多，加速几乎与处理器数成比例的线性增加，

串行比例f不再是程序的瓶颈，这对并行系统的发展是

个非常乐观的结论。

53

Gustafson定律的几何意义可清楚地表示在图3.6(a),⑹

和(c)中。

工

A1024x

w

1014x1004x993x983x

e-

HHS

面

MS'JO24=1O24TO23f

0%1%2%3%4%

123456123456

处理器数夕处理器数P程序中顺序部分的百分比f

(b)

(a)(c)

54

同样，当考虑到并行程序运行时的额外开销w。时，

(3.23)式应修改为:

S，=%+pWp=7）（325）

;

WS+WP+WO1+WO/WI.

注意，w。是P的函数，它可能随P增大、减小或不变。

一般化的Gustafson定律欲达到线性加速必须使Wo

随P减小，但这常常是困难的。

55

0■也

«TFT夕A千八3

3.Sun和Ni定律

Xian-HeSun和LionelNi于1993年将Amdahl定

律和Gustafson定律一般化，提出了存储受限的加速定

律。其基本思想是只要存储空间许可，应尽量增大问

题规模以产生更好和更精确的解（此时可能使执行时

间略有增加）。换句话说，假若有足够的存储容量，

并且规模可扩放的问题满足Gustafson定律规定的时

间要求，那么就有可能进一步增大问题规模求得更好

或更精确的解。

56

-熏学大号

给定一个存储受限问题,假定在单节点上使用了全

部存储容量M并在相应于W的时间内求解之，此时工作负

载川=fW+(l-f)Wo在p个节点的并行系统上，能够

求解较大规模的问题是因为存储容量可增加到pM。令

因子G(p)反应存储容量增加到p倍时工作负载的增加量,

所以扩大后的工作负载W=fW+(l-f)G(p)Wo对照

(3.23)式,存储受限的加速公式及归一化相应为：

S”=”+(­/)G())少

(3.26)

"+(1-/)G()"/夕

(3.27)

/+(1—/)G(〃)/〃

>Sun和Ni定律的几何意义可清楚地表示在图3.7(a)

和⑹中。

叫

号

森

必

H世

必

5-------------►

123456123456

处理器数〃处理器数产

(a)⑹

58

N大号

⑥同样，当考虑到并行程序运行时的额外开销W0时,

(3.26)式和(3.27)式可修改为：

"+(1-"VG(p)=/+(1-/)G(p)

S=(3.28)

?+(l—/)G(p)少/2+%/+(1-/)G储)/p+%/%

由(3.27)可知，当G(p)=l时，它变为/+(//)/.,这

就是Amdahl加速定律(3.19)式；当G(p)=p时，它变

为f+为l-f),这就是Gustafson加速定律(3.24)式;

当G(p)>p时，它相应于计算机负载比存储要求增加得快,

此时Sun和Ni加速均比Amdahl加速和Gustafson

加速为高。

59

0■也

«TFT夕A千八3

4.有关加速的讨论

在实际应用中，可供参考的加速经验公式是：

p/logp<S<P(3.29)

可达线性加速的应用问题有诸如矩阵相加，内积运算等,

此类问题几乎没有通信开销；对于分治类的应用问题，

它类似于二叉树，树的同级可并行执行,但向根逐级推

进时，并行度将逐渐减少，此类问题可望达到p/logp的

加速；对于通信密集类的应用问题,其加速经验公式可

参考下式：

S=1/C(p)(3.30)

其中C(p)是p个处理器的某一通信函数,或为线性的或

为对数的。

60

0■也

(E/灯千入J

严格的线性加速是难以达到的，更何况超线性加速

(SuperlinearSpeedup)o但在某些算法或程序中，可

能会出现超线性加速现象：例如,在某些并行搜索算法

中，允许不同的处理器在不同的分枝方向上同时搜索，

当某一处理器一旦迅速地找到了解，它就向其余的处理

器发出中止搜索的信号，这就会提前取消那些在串行算

法中所作的无谓的搜索分枝，从而出现超线性加速现象;

又如,在绝大多数并行机中，每个处理器均有少量的高

速缓存，当某一问题执行在大量的处理器上，而其大多

的数据均放在高速缓存中时，总的计算时间趋于减少，

如果由于这种高速缓存效应所造成的计算时间下降补

偿了由于通信等所造成的额外开销时间，则有可能造成

超线性加速现象。

61

0■也

(E/灯千入J

最后值得指出的是,加速的含意对科学研究者和工

程实用者可能有所不同：前者乐于使用绝对加速

(AbsoluteSpeedup)的定义，即对于给定的问题，最佳

串行算法所用的时间除以同一问题其并行算法所用的

时间；后者乐于使用相对加速(RelativeSpeedup)的

定义，即对于给定的问题，同一算法在单处理器上运行

的时间除以在多个处理器上运行的时间。显然相对加

速的定义是较宽松和实际的。

62

可扩放性评测标准

评价并行计算性能的指标，除了上节所介绍的加速

比以外,并行计算的可扩放性（Scalability）也是主要

性能指标之一。可扩放性最简朴的含意是在确定的应

用背景下，计算机系统（或算法或程序等）性能随处理器

数的增加而按比例提高的能力。现今它已成为并行处

理中一个重要的研究问题,被越来越广泛地用来描述并

行算法（并行程序）能否有效利用可扩充的处理器数的

能力。

63

«0T■FT也夕A千八3

1.并行计算的可扩放性

从上节所介绍的三种加速定律可知，增加处理器和

求解问题的规模都可能提高加速比，而影响加速的因素

有：

①求解问题中的串行分量；

②并行处理所引起的额外开销（通信、等待、竞争、

冗余操作和同步等）；

③加大的处理器数超过了算法中的并发程度。

64

0■也

«TFT夕A千八3

■BaBBBaaMMaMBasBsaBBBMBBMHaaaMBaaMBBHBaBBBaaMMaMBasaBaBHBMBBQflHaaaMBaaMBBHBaBBBaBMaaMBasaBaBHBMBBaaaaaaMBaaMBBHBM

增加问题的规模有利于提高加速的因素是：

①较大的问题规模可提供较高的并发度；

②额外开销的增加可能慢于有效计算的增加；

③算法中的串行分量比例不是固定不变的（串行部

分所占的比例随着问题规模的增大而缩小）。

一般情况下，增加处理器数,是会增大额外开销和

降低处理器利用率的，所以对于一个特定的并行系统，

并行算法或并行程序，它们能否有效利用不断增加的处

理器的能力应是受限的，而度量这种能力就是可扩放性

这一指标。

65

0■也

«TFT夕A千八3

按照Webster字典所作的定义（Scalabi1ityis

theabilitytoscale,i.e,theabilityto

adjustaccordingtoaproportion）,可扩放性涉及

到调整什么和按什么比例两方面的问题。对于并行计

算而言，要调整的是处理数P和问题规模W,两者可按不

同比例进行调整，此比例关系（可能是线性的，多项式的

或指数的等）就反映了可扩放的程度。

当研究可扩放性时，总是将并行算法和体系结构一

并考虑,也就是说可扩放性应该是算法和结构的组合。

所以当谈论算法的可扩放性时，实际上是指该算法针对

某一特定机器结构的可扩放性；同样当谈论体系结构

的可扩放性时，实际上是指运行于该体系结构的机器上

的某一个（或某一类）并行算法的可扩放性。

66

0■也

(E/灯千入J

进行可扩放性研究的主要目的是：①确定解决某

类问题用何种并行算法与何种并行体系结构的组合,可

以有效地利用大量的处理器；②对于运行于某种体系

结构的并行机上的某种算法当移植到大规模处理机上

后运行的性能；③对固定的问题规模，确定在某类并行

机上最优的处理器数与可获得的最大的加速比；④用

于指导改进并行算法和并行机体系结构，以使并行算法

尽可能地充分利用可扩充的大量处理器。

尽管可扩放性如此重要,并且已被广泛的研究，但

目前仍无一个公认的、标准的和被普遍接受的严格定

义和评判它的标准。下面从不同的角度,介绍三种典型

的可扩放性度量方法，即等效率,等速度和平均延迟方

法。

67

康学大号

2.等效率度量标准

可扩放性的概念是与加速和效率的概念紧密相关的,

为此必须先从加速S和效率E讲起。令