并行处理技术

并行处理技术

（并行计算）

第一部分

并行基本概念

自90年代以来，并行计算得以空前的飞速发展,

一方面，由于单处理机的计算速度不断提高，并行

计算机的体系结构趋于成熟，数据传输网络的标准

化和传输速率的大幅提升，使得并行计算机的研制

周期能够从几年到几个月，为研制并行计算机系统

创造了有利条件。另一方面，推动并行计算发展的

主要动力来自于国际上的一些重要研究计划。

（1）美国HPCC计划：科学和工程计算需要能够提供

1TFLOPS计算能力、仃B内存容量、1TB/S的I/O

带宽，也就是3T性能目标。美国为了保持其在高性

能计算与计算机通信领域的领先地位，在1993年，

由科学、工程、技术联邦协调理事会向国会提交了

“重大挑战项目：高性能计算与通信”的报告，也

就是被称为HPCC计划的报告，即美国总统科学战

略项目，其目的是通过加强研究与开发解决一批重

要的科学与技术挑战问题。

(2)美国ASCI计划：全面禁止核试验条约签订后，

对核武器的研制只能通过在实验室的数值模拟来完

成。1996年6月由美国能源部提出了“加速战略计

算创新”计划，也即ASCI计划项目。提出通过数

值模拟来评估核武器的性能、安全性、可靠性、更

新等。要求数值模拟达到高分辨率、高逼真度、三

维、全物理、全系统的规模和能力。该计划被认为

是与当年曼哈顿计划等同的一个巨大的挑战，它不

仅需要自然科学家的参与，而且也需要与计算机等

工业界的合作，提供保障ASCI计划中的应用所需

的计算机平台。

•并行处理技术

并行处理是一种有效地强调开发计算过程中并

行事件的信息处理方式。

(1)并行性含义

同时性：指两个或多个事件在同一时刻发生在

多个资源中。

并发性：指两个或多个事件在同一时间间隔内

发生在多个资源中。

流水线：指两个或多个事件发生在可能重叠的

时间段内。

并行计算之所以可行，主要在于，并发性是物

质世界的一种普遍属性，具有实际应用背景的计算

问题在许多情况下都可以分解为能并行计算的多个

子任务。

(2)并行计算

给定一个问题，并行计算就是这样的过程：把

问题分解成子问题，同时计算子问题，最后把子问题

的解合并得到原问题的解。

把每一个非常大的问题分成子问题是很不容易的,

这是由于子问题之间可能存在数据相关性。由于数据

相关性，处理器之间必须相互通信，通常两个处理器

之间的通信时间与处理时间相比是很高的。因此，为

了得到好的并行算法，通信方案应该进行很好地规划。

并行处理面临着两个重要的挑战：

(a)程序中有限的并行性

(b)相对较高的通信开销

并行计算（高性能计算、超级计算）

分解

大任务।多个子任务

分给

协同合作-二

快速求解不同处理单元

由此，为了成功开展并行计算，必须具备三个

基本条件：

(a)并行机。并行机至少包含两台或两台以上处理机,

这些处理机通过互连网络相互连接，相互通信。

(b)应用问题必须具有并行度。也就是说，应用可以

分解为多个子任务，这些子任务可以并行地执行。

将应用分解为多个子任务的过程，称为并行算法设

并。

(c)并行编程。在并行机提供的并行环境上，具体实

现并行算法，编制并行程序，并运行该程序，从而

达到求解应用问题的目的

•并行计算研究的目的

对于具体的应用问题，采用并行计算技术的主

要目的在于两个方面：

(1)加速求解问题的速度。例如，给定某应用，在单

处理器上，执行需要两个星期(14天)；而借助并

行计算，使用100台处理器，加速50倍，则执行时间

缩短为6.72个小时。

(2)提高求解问题的规模。例如，在单处理器上，受

内存资源2GB的限制，只能计算10万个网格，但当数

值模拟要求计算1千万个网格时，则仍需借助并行计

算，使用100个处理器，将问题规模线性地扩大100

倍。

•并行计算的研究内容：

(1)并行计算机设计

(2)有效算法的设计

(3)评价并行算法的方法

(4)并行计算机语言

(5)并行编程环境与工具

(6)并行程序的可移植性

(7)并行计算机的自动编程

(3)并行的层次

(a)串行处理

(b)程序级并行(作业级并行)f子程序级并行

(任务级并行)f语句级并行一操作级并行f

微操作级并行。

(4)并行性等级

从执行程序的角度看：指令内部并行、指令间并行、

任务间并行、作业间并行。

从处理数据的角度看：字串位串、字串位并、字并位

串、字并位并。

•问题的并行求解过程

问题的并行求解过程

•并行计算机的理论模型（PRAM模型）

PRAM（ParallelRandomAccessMachine）模型

又称共享存储器模型，具有4种不同的操作方式：

EREW（互斥读互斥写）CREW（并发读互斥写）

ERCW（互斥读并发写）CRCW（并发读并发写）

(1)分类

(a)PRAM-CRCW并发读并发写

♦CPRAM-CRCW(CommonPRAM-CRCW)：仅允

许写入相同数据

^PPRAM-CRCW(PriorityPRAM-CRCW)：仅允

许优先级最高的处理器写入

，APRAM-CRCW(ArbitraryPRAM-CRCW)：允

许任意处理器自由写入

(b)PRAM-CREW并发读互斥写

(c)PRAM-EREW互斥读互斥写

(2)计算能力比较

PRAM-CRCW是最强的计算模型，PRAM-EREW

可logp倍模拟PRAM-CREW和PRAM-CRCW

TE…

EREW。（TCREW「OgP）=OJRCW」°gP）

(3)优缺点

优点：适合并行算法表示和复杂性分析，易于使用，隐

藏了并行机的通讯、同步等细节。

缺点：不适合MIMD并行机，忽略了SM的竞争、通讯

延迟等因素。

•并行计算与计算科学

并行计算，简单地讲，就是在并行计算机上所

做的计算，它和常说的高性能计算、超级计算是同

义词，因为任何高性能计算和超级计算总离不开使

用并行技术。

当今，计算科学已经和传统的两种学科：理论

科学和实验科学，并列为第三门科学，它们彼此相

辅相成地推动科学发展与社会进步。

并行处理是计算科学的重要内容，是实现高性

能计算的重要途径，是并行算法设计、并行程序设

计语言和并行计算机体系结构三者相结合的产物，

是一门计算科学与其它工程学科相结合的处于发展

过程中的交叉学科，其研究重点在于挖掘各个计算

层次的并行性。

•大型并行机系统一般可分为：

(1)单指令多数据流机(SIMD)

(2)多指令多数据流机(MIMD)

MIMD类机器又可分为：并行向量处理机PVP、

对称多处理机SMP、大规模并行处理机MPP、工作

站机群COW、分布共享存储多处理机DSM五类。

(c)MPP

(d)DSM

(e)COW

•并行性的发展

并行性概念乃是推动计算机系统结构发展的重要因

素，为了达到高性能的要求并满足大量计算应用领域

的需要，一方面可在单处理内广泛采取多种并行性措

施，沿着时间重叠、资源重复和资源共享三条技术途

径向现代并行处理领域发展，另一方面把多台计算机

连接起来、相互配合、各尽其能，沿着功能专门化、

多机群和网络化这三种基本技术途径向现代并行处理

领域发展。

(1)时间重叠

在并行性概念中引入时间因素，即多个处理过程在

时间上相互错开轮流重叠使用同一套硬件的各个部件

以加快部件的周转而提高速度。

(2)资源重复

在并行性概念中引入空间因素，根据以数量取胜的原则，

重复设置硬件资源以大幅度提高计算机系统的性能。

（3）资源共享

利用软件的方法，使多个用户分时使用同一个计算

机系统，以提高计算机系统资源的利用率。

单处理机系统朝并行处理领域发展

多计算机

网络化功能专用化

通信处理机松散耦合系统

计算机网络专用外围机

处

局部计高级语言］理

算机网络数据库/机

分布处同构型异构型

理系统多处理机多处理机

多计算机机系统朝并行处理领域发展

分布式计算机系统特征

•资源分散性

通常计算机系统包括物理资源（中央处理器、

存储器、输出输入设备）和逻辑资源（文件系统、各

种软件系统等）。所谓分布式是相对于集中式而言的,

一般是指其功能是分布式的，是通过资源分散配置

来实现的。传统的VonNeumann计算机是单机集中式，

其功能和资源都是集中式。而分布式系统是把处理

功能、存储功能、传输功能分散到各个系统，软件

的资源分散到各个系统上，通过通信网络和软件把

它们连成一个整体。

■工作并行性

工作并行性是由于它的资源分散和重复性，真正实

现了多指令多数据流。这是一种真正的并行而不是并发

执行。分时系统中，对每个用户来说宏观上好象是并行

工作。但某一时刻，中央处理器只能处理一个作业。实

质上是串行地执行。而分布式系统，每台计算机都具有

自己的CPU和存储器，允许多个进程真正并行执行。

•结构模块性

结构模块性是指系统由多个分散的物理和逻辑资源

组成。它们虽然互连成一个整体，但它们分别又是相互

独立的。每个子系统或节点有独立的处理功能、存储功

能、I/O设备、通信功能，这样就形成一个完整的模块,

这种模块性的结构易于扩展、更新和重构。

•协作自治性

分布式系统中控制上的自治性是区别多处理机系统的关键

所在。并行处理和多处理机系统大多共享它们的内存，对资源集

中控制和管理。而分布式计算机系统采用协作自治管理方式。这

种控制自治性体现在各个模块是处于平等自治地位，分别是在统

一协调配合下自主地工作。这种工作方式使系统有了任意扩展的

可能，并使其工作可靠性得到确实的保证。

•运行坚定性

系统总是会出错的，这包括硬件系统和软件系统的

故障。为了提高系统的可利用性和可靠性，近几年对容

错技术进行了大量的研究。分布式系统对于冗余、重构、

快速恢复的潜在能力具有突出的优越性。由于模块结构

和在操作系统级采用了容错的措施，使分布式系统在当

出现故障时，首先可以降级使用或采用重构的措施，特

别是近几年在分布式操作系统级实现了进程迁移，使系

统对用户运行更加坚定。

•系统透明性

系统对用户透明己成为分布式计算机系统最

关键的特征之一。很多多机系统和网络系统不满

足这个条件。对于局域网.其系统的拓扑结构、

互联网方式、传输介质、通信速率和辖域与分布

式系统类似，但只是为了通信和共享资源而已，

而分布式计算机系统对用户是透明的，即用户不

知道它的程序在哪一台机器上运行，也不知道它

的文件存于何处，当调用一个文件系统时，系统

能保证总是提供最新版本。

下面是ASSA(AdvancedNetworkSystemArchitecture)

定义的8种透明性：

1.访问透明性：可用同样的操作访问本地和远程的文件以及其他

对象。

2.位置透明性：访问任何对象时都不必了解其所在位置。

并发透明性：多个用户或应用程序在使用共享数据时互相不干

3.Iio

4.复制透明性：可以使用文件或其他数据的多个副本以增加可靠

性和性能，但用户或应用程序不必了解是否使用了副本。

5.错误透明性：错误被封闭起来.即使山现了软硬件故障，也不影

响应用程序完成任务。

6.迁移透明性：系统中的对象可在不同机器之间迁移，但不影响

应用程序运行。

7.性能透明性：允许系统进行重构来改变性能，从而适应用户负

载的变化。

8.伸缩透明性：允许系统或应用扩充规栉而不必改变系统结构或

应用算法。

例：两个浮点向量Xi和Yi(i=l,2,・・.n),相加后

的结果为Zi。设浮点加法运算分4段(对阶、

尾加、规格化、舍入)完成。分别计算当

n=100,m=4(段数)，N=20(处理单兀数)

时，T=1US(每段时间)时，串行、流水和向

量运算所需的时间。

T串行=m*n*工=4*100*lus=400us

T流水=(m+n-1)*T=(4+100-1)*lus=103us

T向量=t#*「n/Nl=m*T*rn/N

=4*lus*「100/201=20us

其中N〈n,t#为首先计算N对元素(Xi,Yi,

i=l,2,…N)所需的时间。

第二部分

流水线（并行）技术

•流水线技术

流水线技术是并行计算中一个非常有效

的、常用的手段，在并行计算中起着非常重

要的作用。

流水线技术在60年代中开始用于计算机系

统，该技术采用时间上重叠的方法来实现并

行性，因而可以用较少的设备取得较高的性

能。目前，几乎所有的计算机系统都采用了

流水线技术。

流水原理

所谓流水就是将一个过程分解成若干个子过程,

使每个子过程都可以有效地在其专用的功能段上

与其它子过程并行执行。

例如，将指令的执行过程分成6个阶段：取指(FI)、指

令译码(DI)、计算操作数地址(CO)、取操作数(F0)、执行

指令(EI)、写操作数(W0)。每段都在其相应的功能部件上

实现，且执行时间为△仁

AtAtAtAtAtAt

入出

•流水线的性能参数

设流水线段数=m,每段执行时间=Z\t,指令数=n。

串行处理所需时间：T§=m*n*Zkt

流水处理所需时间：TP=(m+n-l)*At

流水线时■空图：(m=4,n=7)

入求阶差对阶尾数相加规格化出

-A-△&A-A

(a)浮点加法流水线

空间A

规格化123456?

尾数相加1234567

对阶1234567

求阶差1234567

G&6匕bifah5时间

(b)描述流水线工作的时空图

三项性能指标：吞吐率、加速比和效率

(1)流水线的吞吐率

吞吐率是指单位时间内流水线所完成的任务数或输出结果

的数量。(单位时间内流水线能处理的指令数)

实际吞吐率：TP=n/Tp=n/[(m+n—1)*Zkt]

最大吞吐率明数是指流水线在达到稳定状态后所得到的

吞吐率。

最大吞吐率：TPmax=1/At

(2)加速比

加速比是指流水线速度与等功能的非流水线速度之比。

S=Ts/TP当n»m时，S-m

(3)效率

效率是指流水线设备的利用率。

E=n*At/TP

例2：设有一个15000条指令的程序在一台时钟速率为

25MHz的线性流水线处理机上执行。假设指令流水

线有5段，且每个时钟周期发射一条指令。求流水线

的吞吐率TP、加速比S、效率E。(不考虑相关问题)

则：

n=15000,m=5,At=1/25=0.04us

TP=(5+15000-1)*0.04=600.16us

T=5*15000*0.04=3000us

TP=15000/600.16=24.99MIPS

S=3000/600.16=4.99

E=15000*0.04/600.16=99.97%

・各功能段时间不相等时的参数计算

设流水线段数=m,第i段执行时间=△［指

令（或任务）数=n,贝ll：

m

串行处理所需时间：T=〃xZAti

sz=l

m

流水处理所需时间:Tp=EAti+(^-l)Atj

Z=1

其中即最慢一段所需的时间。

最大吞吐率：TPmax=l/maxfAtJ

最大吞吐率取决于流水线中最慢一段所需的时间,

该段成为流水线的瓶颈

实际吞吐率：

n

实际吞吐率型=军方可

加速比:

mm

S=Ts/Tp=〃xEAti/ZAti+（〃一l）Atj

z=1z=1

效率：从时-空图上看，效率就是力个任务所占的时空

区与5个段总的时空区之比，因此从时-空图上看，

效率就是刀个任务所占的时空区与5个段总的时空区

之比。

石,里务占用的时空区

5个段总的时空区

例：设某指令流水线为4段，各段的执行时间如图所示,

且△t°=lus,求执行3条指令时，流水线的吞吐率、

加速比、效率。

kkk

，At0—3At0—At0—"At0一

m

Ati

串行处理所需时间：T=-xZ=18us

smf=l

流水处理所需时间：Tp=EAti+-OAtj=12US

Z=1

最大吞吐率：TPmax=l/max{Ati}=1/(3At0)=O.33MIPS

实际吞吐率：TP=n/Tp=3/12=0.25MIPS

加速比：S=TS/TP=18/12=1.5

效率：E=18At0/(4xl2At0)=37.5%

•相关问题

所谓相关是指程序的相近指令之间出现某

种关联，使指令流水线出现停顿，影响了流水线

的效率。指令间的相关大体可分控制相关和数据

相关两类。

(a)控制相关：如果一条指令要等前一条(或几

条)指令作出转移方向的决定后，才能进入流水

线，便发生了控制相关。包括转移和中断两种情

况。

条件转移：为了在遇到条件转移指令后，流水线仍能继续

向前流动，多数机器采用的是“猜测法”技术。猜测

哪个分支是事先确定的，一般选择转移不成功的分支。

(b)数据相关：数据相关是在几条相近的指令间共用同

一个存储单元或寄存器时发生的。三种数据相关如下：

先写后读相关：指对同一个单元，要求在前的指令先写入,

在后的指令才能读出的关联。

例：L：R1=R2+R3

I2：R4=Ri*R5

先读后写相关：指对同一个单元，要求在前的指令先读出,

在后的指令才能写入的关联。

例：I1：RLR2+R3

=

I2：R2R4*R5

写-写相关：指对同一个单元，要求在前的指令先写入，

在后的指令才能写入的关联。

例：L：R=R2+R3资源相关

[2：R]=R4+R5

例：有一8段顺序流动流水线，其中第2段为读段，第7

段为写段。指令串h、i、j、k、1、m、n>依次进

入流水线。如果第j条指令的源操作数地址与第h条

指令的结果地址相同，则可断定指令h和j之间发生

了先写后读相关。

kj***ih顺序流动

指令kjihj和h相关

两种解决方法如下：相关专用通路

推后读：当j到达读段时，流水线断流，直到h到达写段并完成写入后在继续。

设置相关专用通路：避免相关单元的写入和读出时间，使指令j提前流动。

•流水线的分类

（1）按完成的功能分

单功能流水线：指只能完成一种固定功能的流水线。

多功能流水线：指各段可以进行不同的连接，从而完成

不同的功能。

（2）按同一时间内各段之间的连接方式分

静态流水线：指在同一时间内，流水线的各段只能按同

一种功能的连接方式工作。

动态流水线：指在同一时间内，流水线的各段可按不同

运算的连接方式工作，即当某些段正在实现某种运算

时，另一些段却在实现另一种运算。

（3）按任务输入/输出的顺序分

顺序流动流水线和异步流动流水线。异步流动流

水线也可称为无序流水线、错序流水线或乱序流水线。

（4）按流水线的级别分

部件级流水线：又叫运算操作流水线，是把处理机的

算术逻辑部件分段，使得各种数据类型的操作能够

进行流水。

处理机级流水线：又叫指令流水线，是把解释指令的

过程按照流水方式处理。

系统级流水线（处理机间流水线）：又叫宏流水线，

是由两个以上的处理机串行地对同一数据流进行处

理，每个处理机完成一项任务。

（5）按数据表示分

标量流水线（处理机）：是指处理机不具有向量数据

表示，仅对标量数据进行流水处理。

向量流水线（处理机）：是指处理机具有向量数据表

示，并通过向量指令对向量的各元素进行处理。

（6）按流水线中是否有反馈回路分

线性流水线：指流水线的各段串行连接，没有反馈回路。

非线性流水线：指流水线中除有串行连接的通路外，还有

反馈回路。

非线性流水线存在流水线调度问题，即确定什么时

候向流水线引进新的输入，从而使新输入的数据和先前

操作的反馈数据在流水线中不产生冲突。

反馈回路

出

Soo

流动顺序：S］、S2>S3、S4、s2>S3、S4、o

•CRAY-1向量流水处理机

(1)向量冲突

数相关：V2=V0+V1部件相关：V4=v2+v3

V4=V2*V3V5=V1+V6

源向量冲突（相关）：V4=V1+V2

%=V\+V3

无相关，可并行执行的两组向量：V0=Vi+V2

*

(2)四种典型的向量指令

V、¥Vj

功访

能存

部

件

向量一向量向量一标量向量取向量存

运算指令运算指令数指令数指令

(3)链接技术

链接技术是流水线中加快运算速度的一种重要技术。

只要不发生功能部件冲突和源向量冲突，就可以把两个

或两个以上的功能部件连接起来形成一条链子进行流水

处理。通过链接结构，可使数据相关的向量指令也能并

行执行。

例1.向量运算：D=A*(B+C),向量长度n064。

则当B、C取到V。、Vi后，就可用以下三条指令求解。

(a)V3—存储器(访内取A)

(b)V2―V0+V1(浮点力口)

(c)V4<-V2*V3(浮点乘，V4存放D)

(a)、(b)两条指令无相关，可以并行执行。而(c)与

(a)、(b)两条指令有数相关，本不能并行执行，但若能

把(a)、(b)两条指令的结果元素直接链接进⑹条指令所

用的功能部件，则第(c)条指令就能与(a)、(b)两条指令

并行执行。

设从功能部件取数和向

功能部件存数都需一拍，访

存需6拍,浮点加需6拍,浮

点乘需7拍，则从访内开始,访

存

直至把第一个结果元素存入

浮

V4,所需拍数为：

1+6+1+1+7+1=17拍点

当向量元素N=64时，加

链接运算所需时间为：

T=17+(N-1)=80拍。

非链接运算所需时间为：

T=17+m(N-l)

=17+2(64-1)浮

—]43拍点

m为链接的指令数。乘

取向量长度N=3,链接指令数m=2时,

链接与非链接的时间对比。

013456789101112131415161718192021222324252627

•单功能非线性流水线调度问题

非线性流水线调度要解决的问题是：确定控制

处理对象流入流水线的时间间隔，使其既不发生对象

争用流水线段的冲突，又有较高的吞吐率和效率。

（1）预约表

行：表示流水线中的段。

歹U：表示任务经过流水线所需的时间（时钟数）。

如果任务在tj时刻需学处理，则在表中的i行和第

j列的交叉处用“X”表示。

调度：每个时钟周期

（每拍）向流水线输

入一个新任务。

4段线性流水线预约表

每个任务按S1，S2,S3,S3,S4,S2,S［顺序流过

各段，预约表如下：其中每个任务从输入到输出共需

7个时钟周期。

tlht

4t5t6

S1XX

XX

S2

S3XX

S4X

4段非线性流水线预约表

(2)禁止表

如果表中的&行有两个(或多个)“义”，它们

之间相距d个时钟周期，那么在相隔d个时钟周期

输入新任务时，则一定会出现新任务与旧任务同时

争用*段的情况，即在号段上产生冲突。

禁止表：由预约表中每一行所有不同的两个“x”

之间距离的集合组成。

m

其中，m为段数，fi={d|d为Sj行中所有不同的两

个“x”之间距离}。

例如：4段非线性流水线的禁止表为

F={6}o{4}u{l}={1,4,6)

（3）均匀调度（等间隔调度）

在非线性流水线的任务输入过程中，找出一个

最小时间间隔，并按此时间间隔进行调度，使多个

任务输入非线性流水线，并在处理过程中不会出现

争用某段的情况。

由上面禁止表F可以看出，相邻两任务输入流水

线的时间间隔数不能是1,4和6,即这些值在调度时

应当禁止使用。

一般地当连续输入多个任务时，对于任何一个

任务T（T>1）,流水线按时间间隔K进行进行均匀

调度，不发生争用冲突的条件是：

T*KeF

其中TNI,k£l且为正整数，但若要提高非线性流水

线的效率，则对均匀调度来说，应取：min{kJo

例：对于禁止表F二{1,4,6},确定均匀调度方案。

取曷=2,T=2,则T*k"F,不能按相隔2拍调度

取曷=3,T=2,则T*k”F,不能按相隔3拍调度

取曷=5,T>1,则T*leF,可以按相隔5拍调度

取k2=7,T>1,则T*k2eF,可以按相隔7拍调度

由此得K={kpk2,...}={5,7,…},所以取

min{kJ=5,进行均匀调度时会吐率最高。

若设n=3,每个时钟周期为At,贝小

最大吞吐率：TPmax=l/(5At)

实际存吐率：TP=3/(17At)

效率：E=(3x7)/(4xl7)=30.9%

按K=5均匀调度

（4）非均匀调度

由前面分析可知，在任一时刻输入新任务与当

时在流水线中各任务的推进情况有关，因此新任务

与旧任务是否发生争用冲突，可以用一个n位冲突向

量C表示。即:

C=（CnCn/…C2C。

其中，第i位的状态表示与当时相隔i个时钟周期

是否允许向流水线输入新的任务，该位为“0”表示允

许输入，该位为“1”表示不允许输入。

初始冲突向量：输入第一个任务时建立的冲突向量。

此向量的位数n是最大的禁止间隔，故Cn总是等于1。

例：对于禁止表F二{1,4,6},当流水线输入第一个

任务后，初始冲突向量为：

C=（C6c5c4c3c2力）=（101001）

非均匀调度基本思想：

根据冲突向量概念，将初始冲突向量中5=0所对

应的时间间隔作为第2个任务的输入时刻，但5=0所

对应的时间间隔并不一定能作为第3个任务的输入时

亥I」。通常，根据初始冲突向量输入第2个任务后，又

会产生新的冲突向量，然后由这个新的冲突向量再决

定第3个任务在什么时刻输入等等。按照此思路，选

择各种可能的时钟周期数（时间间隔）输入新的任务,

产生新的冲突向量，此过程一直进行到不再产生不同

的新的冲突向量为止。在此基础上进行的非线性流水

线调度，则不会产生段的争用冲突。

新的冲突向量产生方法：

随着流水线中第1个任务每个时钟周期向前推进

一段，原先禁止第2个任务输入流水线的各种间隔时

钟数均应减去1,这相当于将初始冲突向量右移1位,

左边空位补“0、动态形成当时的冲突向量。随着

任务在流水线中的推进，会不断地形成当时的冲突

向量。

新的冲突向量=当时的冲突向量v初始冲突向量

其中，7'为按位或操作。

例：已知初始冲突向量C=(101001),贝IJ：

(a)选择第2个任务间隔2个时钟周期输入流水线，当

时的冲突向量为：(001010),新的冲突向量为：

(001010)V(101001)=(101011)

(b)选择第2个任务间隔3个时钟周期输入流水线，当

时的冲突向量为：(000101),新的冲突向量为：

(000101)V(101001)=(101101)

(c)选择第2个任务间隔5个时钟周期输入流水线，当

时的冲突向量为：(000001),新的冲突向量为：

(000001)V(101001)=(101001)

非线性流水线状态转移图

图中，两个冲突向量之间有向弧上的数字为引

入后继任务的时间间隔数，对于图中的多种闭合回

路，按其中的任何一个回路进行流水线调度都不会

产生段争用冲突。

最佳调度方法：

表中给出了各回路的平均时间间隔数，显然按

其中的最小者进行调度，流水线的存吐率最高，即

所谓最佳调度。

调度方法平均时间间隔TAPxmax

(5)51/(5At)

(2,3),(3,2)2.52/(5At)

(2,5),(5,2)3.52/(7At)

(3,5),(5,3)4l/(4At)

(2,3,5),(3,2,5)3.333/(10At)

按(2,3)非均匀调度

n=5,TP=5/(17At)

最优调度方法获得最优调度策略的步骤是：

(1)根据处理对象对流水线各段的使用时间要

求建立一个预约表。

(2)由预约表得出禁止表，禁止表是禁止后续

对象流入流水线的时间间隔的集合。

(3)由禁止表得出初始冲突向量。

(4)由初始冲突向量得出状态有向图。

(5)由状态有向图得出最优调度策略。有向图

的任何一条环路都是一个可用的无冲突调度策

略，从中选择一个平均时间间隔最小的调度策

略就是最优调度策略。

练习：

在一个5段的流水线处理机上需经过9Z\t才能完

成一个任务，各段执行时间均为43任务处理过程对

各段使用时间的预约表如下所示：

x

s1x

x

S2x

XXX

XX

XX

按最优调度策略输入6个任务，求流水线的实际

吞吐率和加速比。

第三部分

并行计算机互连网络

并行计算性能评测

并行计算机是由一组处理单元组成的，这组处

理单元通过相互之间的通信与协作，以更快的速度

共同完成一项大规模的计算任务。因此，并行计算

机的两个最主要的组成部分是计算节点和节点间的

通信与协作机制。并行计算机体系结构的发展也主

要体现在计算节点性能的提高以及节点间通信技术

的改进两方面。

•并行计算(处理)机的组成

大多数并行处理机都由一定数量的处理单元

(PE),一定数量的存储体(M),某种形式的互连网络

(ICN),和某种形式的控制部件(CU)组成。根据这

些部件不同的连接方法以及不同的相互作用方法，

可构成两种典型的并行处理机结构。

控

制

具有分布存储器的并行处理机结构

>sc

sc：管理处理机

控CU：控制部件

制

PEi：处理单元

ICN：互连网络

全局存储器

I/O-CH：I/O通道

I/O：I/O设备

SM：外存储器

具有共享存储器的并行处理机结构

SIMD和MIMD计算机都使用了各种形式的互连

网络，从而实现处理器之间的通信和协同工作。每

种并行计算机体系结构分别使用不同的互连网络方

式。在分布式存储器SIMD体系结构中，互连网络物

理地连接这些处理器，从而使处理器将数据按某种

顺序存储在寄存器中。在共享存储器SIMD计算机中,

互连网络为不同的处理器提供了直接访问不同存储

模块数据的功能。在分布式存储器结构中，互连网

络物理地连接系统中的CPU,并且在CPU之间直接提

供显式的发送和接收通信的功能。在共享存储器

MIMD系统中，互连网络为CPU提供访问系统中所有

存储模块的功能，处理器通信通过读写共享存储器

来实现。因此，互连网络的目的就是为了把信息可

靠地传输到正确的目的地。

•静态与动态互连网络

静态互连网络各结点之间的连接是固定的，不能

重新组合。

所谓静态网络是指处理单元间有着固定连接的一

类网络，在程序执行期间，这种点到点链接保持不

变。典型的静态网络有：一维线性阵列、二维网孔、

树连接、超立方网络、立方环、洗牌交换网、蝶形

网络等。

所谓动态网络是用开关单元构成的，可按应用程

序的要求动态地改变连接组态。典型的动态网络包括:

总线、交叉开关和多级互连网络等。

互连网络具有三大要素抑结点间互连拓扑（包含

连接通路）、开关元件和控制方式。在不同的系统中，

开关元件所处的物理位置可能是不同的。

互连网络的直接作用是建立机间连接通路。互连

网络有两种形式。一种是非共享连接通路，即结点与

结点直接相连，非直接相连的结点之间的通信经过中

间结点转送。另一种是共享连接通路，即多个结点相互

间经过开关元件相连，以建立可变的连接通路，同一路

径段通过开关元件的选择在不同时刻可为不同的结点

对服务，达到共享的目的。

不同网络之间的差异主要表现在以下几

个方面：

(1)编址方案。

(2)最大分组尺寸。

(3)网络访问机制。

(4)超时机制。

(5)差错恢复。

(6)状态报告。

(7)路由选择。

(8)用户访问控制。

(9)连接和无连接服务。

•静态互连网络的几个性能参数

定义1:射入或射出一个节点的边数称为节点度。

定义2：网络中任何两个节点之间的最长距离（最大路

径数）称为网络直径。

定义3：如果从任一节点看网络都一样，则称网络为对

称的。

定义4：对分网络各半所必须移去的最少边数称为对剖

宽度。

网络名称网络规模节点度网络直径对剖宽度对称链路数

线性阵列N个节点2N-11非N-1

环形N个节点2l_N/2_|（双向）2是N

星形N个节点N-12LN/2J非N-1

超立方N=2n个节点nnN/2是nN/2

•互连网络的定义和模型

定义：互连网络是一种由开关元件按一定的拓扑

结构和控制形式构成的网络。

模型：互连网络可以表示为一个三元组(N,M,C),

N为输入端数，M为输出端数，C为连接能力，即

网络能同时实现的连接的最大数目。

输输

入c出

端端

控制机制

•互连函数

(a)恒等互连

I(Xn-lXn-2…X1X。)=..X^Q

(b)交换(方体)互连

Ck(Xn-l…Xk+1XkXk-l•••XO)=Xn-1•••Xk+1XkXk-l•••XO^

(C)混洗互连

0(Xn-lXn-2・・・XiXo)=Xn.2...X^Q

(d)蝶式互连

B(Xn/Xn.2・・・XiXo)=X。Xn.2...X^

(e)反位序互连

P(Xn-lXn_2・・・XiXo)=X。X】・・・Xn.2X”/

例：

000——000000000000000

001——001001001001001

010——010010010010010

Oil——OilonononOil

100——100100100100100

101——101101101101101

110——110110110110110

111——111111111111111

(

I(X2X1XO)=x2x1x0ox2x1x0>x1x0x2P(X2X1X0>X0X/2

c0(x2x1x0)=x2x1x0B(X2X1X0>X0X1X2

•单级互连网络

例：单级立方体网络

010011010011010011

100101100101100101

c0a

单级立方体互连网络函数：

Cube={孰，CPC2,1}

•多级互连网络

单级互连网络只能实现有限的几种基本

连接，并不能实现任意处理器之间的连接。

基本构件：交叉开关。

下播

例：多级立方体网络

o

1AEI

2

3

出

入

端

端4

5

6

7

直

连

级o

换

交

ABCD=1,EFGH=1,IJKL=1n(07)(16)(25)(34)

级控制信号(K^KQ)

000001010011100101110111

001234567

110325476

入223016745

端332107654

号445670123

554761032

667452301

776543210

4组2元

4组2元2组4元+4组2元

恒等4组2元+2组4元+2组4元+1组8元

2组4元1组8元+1组8元

1组8元

例：多级混洗交换（Omega）网络

o0

11

22

入33出

端端

44

55

66

77

级012

立方体网络可以同时实现5到0,7到1的连接，Omega网络可以

同时实现0到5,1到7的连接。

并行计算性能评测

并行计算的性能评测与并行计算机体系结构、

并行计算和并行程序设计一道构成了“并行计算”

研究的四大分支。

•几个性能参数

(1)粒度：是各个处理机可独立并行执行的任务大小

的度量。大粒度反映可并行执行的运算量大，亦称

为粗粒度。指令级并行等则是小粒度并行，亦称为

细粒度。

(2)加速比：串行执行时间为Ts,使用q个处理机并

行执行的时间为Tp(q),则加速比为

Sp(q)=Ts/7p(q)

(3)效率:设q个处理机的加速比为Sp(q),则并行算

法的效率

Ep(q)=Sp(q)/q

(4)性能：求接一个问题的计算量为I/IA执行时间为了,

则性能(FLOP⑸为

Perf=W/T

在80年代，使用FLO■为单位，90年代，使

用MFLOP/s和GFLOP/s,27世纪普遍使用

GFLOP/s和TFLOP/s,目前也逐渐开始使用

PFLOP/s。

•计算机性能的评测

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

所处的角度有关。计算机用户说机器很快，

往往是因为程序运行时间少；而计算中心管

理员说机器很快，则往往是因为在一段时间

里它能够完成更多的任务。用户关心的是响

应时间，即从事件开始到结束之间的时间，

也称为执行时间；而管理员关心的是如何提

高流量，即在单位时间内所能完成的工作量。

为了比较不同设计的差别，通常要对两

台机器的性能进行比较。假设这两台计算机为

X和Y,“X比Y快”的含义是：对于给定任务，X的

响应时间比丫少o"X比Y快n倍”是指：

响应时间y

=n

响应时间x

由于响应时间与性能成反比，又有：

1

口向应时间y，性育旨y，性育旨管

口向应日寸间牙1，性育旨y

，性能X

响应时间最直观的定义是计算机完成某一任务

所花费的全部时间，包括访问磁盘、访问存储器、

输入/输出、操作系统开销等。

•加速比性能定律

在不同计算对象和资源约束条件下，有三种加速

比模型：适用于固定负载的Amdahl定律（1967）、适用

于可扩展问题的Gustafson可扩展加速比定律（1988）、

受限于存储器的Sun与Ni加速比模型（1993）。

（1）并行度

并行计算机执行一个程序可以在执行过程的不同

时间范围内使用不同数目的处理机，我们将每个时间

范围内用来执行程序的处理机数目称为并行度（DOP）o

并行度反映了软件并行性与硬件并行性匹配的程

度，这是一个离散时间函数，只取非负整数。

DOP的时间函数曲线称为一给定程序的并行性分

布图。

算法的并行度是指该算法中可并行执行的操作次

数。

(2)并行系统的加速比

并行系统的加速比是指对于一个给定的应用，并

行算法(或并行程序)的执行速度相对于串行算法

(或串行程序)的执行速度加快了多少倍。

加速比=Ts/Tp

(3)Amdahl定律

Amdahl定律指出：加快某部件执行速度所获得

的系统加速比，受限于该部件在系统中的重要性。

Amdahl定律即可以用来确定系统中对性能限制

最大的部件，也可以用来计算通过改进某些部件所获

得的系统性能的提高。Amdahl定律是研究并行系统

中最基本的定律之一。

假定对机器进行某种改进,那么机器系统的加

速比就是：

力少|土一改进后系统的性能改进前总执行时间

系统加速比==

改进前系统的性能改进后总执行时间

系统加速比告诉我们改进后的机器比改进前快多

少倍。系统加速比与两个因素有关：

(1)计算机执行某个任务的总时间中可被改进部分的

时间所占的百分比，记为冗，它总是小于1。例如，

一个需运行60s的程序中有20s的运算可以加速，那么

该比例就是20/60。

(2)改进部分采用改进措施后比没有采用改进措施前

性能提高的倍数，记为，，它总是大于1。例如，系

统改进后执行程序，其中可改进部分花费的时间为2s,

而改进前该部分需花费的时间为5s,则性能提高为

5/2o

改进后整个任务的执行时间1口为：

F

T

n=T。。-Fe+U

式中，1为改进前整个任务而执行时间。

改进后整个系统的加速比Sp为：

To1

S==

Tn(1-Fe)+Fe/Se

式中，(1-Fe)表示不可改进部分。当Fe为0,即

没有可改进部分时，Sp为1,所以性能的提高幅度受

改进部分所占比例的慎制。当Se-00,贝IJS”-。

Amdahl定律

•系统加速比依赖于两个因素：

・“可改进比例”：可改进部分在原系统计算时间中所

占的比例，它总是小于等于1的。

・“部件加速比”可改进部分改进以后的性能提高，一

般情况下它是大于1的。

Amdahl定律

i

s=

(i-/J+-

se

Amdahl定律练习

例：假设在某程序的执行过程中，浮点操作时间

占整个执行时间的10%,现希望对浮点操作加速。

-设对浮点操作的加速比为与。请画出程序总的加

速比S和y之间的关系曲线；

-请问程序的最大加速比可达多少?

Amdahl定律练习

I(i-/J+f

sf

i

—10%

1(1-10%)+

Smax_lim01S/

000.9+

s,1

—0.1

=10/90.9+——

S,

例1：假设系统某一部件的处理速度加快9倍，但该部

件的原处理时间仅为整个运行时间的45%,则采用加

快措施后能使整个系统的性能提高多少？

由题意Fe=0.45,Se=9

则11

二二

SP«1.56

0.55+0.45/90.64

例2:如果想用100个处理器达到80的加速比，求原计

算程序中串行部分所占比例。

由Amdahl定律

（I一E皿舞翱口F糊）+（E卯翅毡5尔糊\镭彤川彝尔）

皿厚尔=

I

假设并行模式下的理论加速比即为处理器的个

数，加速部分的比例即并行部分所占的比例，代入

上式：