并行计算
——结构?算法?编程国家高性能计算中心（合肥） 22009-7-24
并行计算 ——结构?算法?编程
第一篇 并行计算的基础
第一章 并行计算机系统及其结构模型
第二章 当代并行机系统,SMP,MPP和 Cluster
第三章 并行计算性能评测
第二篇 并行算法的设计
第四章 并行算法的设计基础
第五章 并行算法的一般设计方法
第六章 并行算法的基本设计技术
第七章 并行算法的一般设计过程国家高性能计算中心（合肥） 32009-7-24
并行计算 ——结构?算法?编程
第三篇 并行数值算法
第八章 基本通信操作
第九章 稠密矩阵运算
第十章 线性方程组的求解
第十一章 快速傅里叶变换
第四篇 并行程序设计
第十二章 并行程序设计基础
第十三章 并行程序设计模型和共享存储系统编程
第十四章 分布存储系统并行编程
第十五章 并行程序设计环境与工具国家高性能计算中心（合肥） 42009-7-24
第一章并行计算机系统及结构模型
1.1 并行计算
1.1.1 并行计算与计算科学
1.1.2 当代科学与工程问题的计算需求
1.2 并行计算机系统互连
1.2.1 系统互连
1.2.2 静态互联网络
1.2.3 动态互连网络
1.2.4 标准互联网络
1.3 并行计算机系统结构
1.3.1 并行计算机结构模型
1.3.2 并行计算机访存模型国家高性能计算中心（合肥） 52009-7-24
并行计算
并行计算：并行机上所作的计算，又称高性能计算或超级计算。
计算科学：计算物理、计算化学、计算生物等
科学与工程问题的需求：气象预报、油藏模拟、核武器数值模拟、航天器设计、基因测序等。
需求类型：计算密集、数据密集、网络密集。
美国 HPCC计划：重大挑战性课题,3T性能
美国 Petaflops研究项目,Pflop/s。
美国 ASCI计划：核武器数值模拟。
国家高性能计算中心（合肥） 62009-7-24
高性能计算机
Intel（ Option Red)：
1Tflops,1997,Pentium Pro
SGI(Option Blue Mountain),
3Tflops,1998,MIPS10000
IBM(Option White),
7Tflops,Top4,2001,Power3
日本 Earth Simulator,
35Tflops,Top1,2002,VP
Hewlett-Packard ASCI Q：
7Tflops,Top2,3,2002,Alpha Server
中国联想：
1Tflops,Top43,2002
国家高性能计算中心（合肥） 72009-7-24
系统互连
不同带宽与距离的互连技术,
总线,SAN,LAN,MAN,WAN
局部总线
I/O
总线
SCI
HiPPI
Myrinet
千兆位 以太网光纤通道快速以太网以太网
10 Base T
FDDI
ATM
总线或开关 SAN LAN MAN WAN
100
Gb/s
10
Gb/s
1
Gb/s
100
Mb/s
10
Mb/s IsoEnet
网络带宽交叉开关
MIN 或
100 Base T
国家高性能计算中心（合肥） 82009-7-24
局部总线,I/O总线,SAN和 LAN
P M
I/O
桥磁盘
SAN(e.g.Myrinet)
LAN(e.g.以 太网,FDDI) 系统 I I
I / O 总线,
接口系统 I
处理器总线局部总线,存储器总线
SCSI
节点 2 节点 N
系统总线节点 1
国家高性能计算中心（合肥） 92009-7-24
网络性能指标
节点度（ Node Degree）,射入或射出一个节点的边数。在单向网络中，入射和出射边之和称为节点度。
网络直径（ Network Diameter）,网络中任何两个节点之间的最长距离，即最大路径数。
对剖宽度（ Bisection Width）,对分网络各半所必须移去的最少边数
对剖带宽（ Bisection Bandwidth）,每秒钟内，在最小的对剖平面上通过所有连线的最大信息位（或字节）数
如果从任一节点观看网络都一样，则称网络为对称的
（ Symmetry）
国家高性能计算中心（合肥） 102009-7-24
静态互连网络 与动态互连网络
静态互连网络：处理单元间有着固定连接的一类网络，
在程序执行期间，这种点到点的链接保持不变；典型的静态网络有一维线性阵列、二维网孔、树连接、超立方网络、立方环、洗牌交换网、蝶形网络等
动态网络：用交换开关构成的，可按应用程序的要求动态地改变连接组态；典型的动态网络包括总线、交叉开关和多级互连网络等。
国家高性能计算中心（合肥） 112009-7-24
静态互连网络（ 1）
一维线性阵列（ 1-D Linear Array）：
并行机中最简单、最基本的互连方式，
每个节点只与其左、右近邻相连，也叫二近邻连接，
N个节点用 N-1条边串接之，内节点度为 2，直径为 N-1,对剖宽度为 1
当首、尾节点相连时可构成循环移位器，在拓扑结构上等同于环，环可以是单向的或双向的，其节点度恒为 2，直径或为
（双向环）或为 N-1（ 单向环），对剖宽度为 2
2/N
国家高性能计算中心（合肥） 122009-7-24
静态互连网络（ 2）
二维网孔（ 2-D Mesh）：
每个节点只与其上、下、左、右的近邻相连（边界节点除外），
节点度为 4，网络直径为,对剖宽度为
在垂直方向上带环绕，水平方向呈蛇状，就变成 Illiac网孔了，
节点度恒为 4，网络直径为,而对剖宽度为
垂直和水平方向均带环绕，则变成了 2-D环绕（ 2-D Torus），
节点度恒为 4，网络直径为,对剖宽度为
)1(2?N N
1?N N2
2/2 N N2
NN?
(a)2-D网孔 (b)Illiac网孔 (c)2-D环绕国家高性能计算中心（合肥） 132009-7-24
静态互连网络（ 3）
二叉树：
除了根、叶节点，每个内节点只与其父节点和两个子节点相连。
节点度为 3，对剖宽度为 1，而树的直径为
如果尽量增大节点度为，则直径缩小为 2，此时就变成了星形网络，其对剖宽度为
传统二叉树的主要问题是根易成为通信瓶颈。胖树节点间的通路自叶向根逐渐变宽。
1log2?N
2/N
(a) 二叉树 (b) 星形连接
(c) 二叉胖树国家高性能计算中心（合肥） 142009-7-24
静态互连网络（ 4）
超立方,
一个 n-立方由 个顶点组成,3-立方如图 (a)所示； 4-立方如图 (b)所示，由两个 3-立方的对应顶点连接而成。
n-立方的节点度为 n,网络直径也是 n,而对剖宽度为 。
如果将 3-立方的每个顶点代之以一个环就构成了如图 (d)所示的 3-立方环，此时每个顶点的度为 3，而不像超立方那样节点度为 n。
nN 2?
2/N
(b )4 -立 方(a )3 -立 方
(c )顶 点代之以环 (d )3 -立 方环国家高性能计算中心（合肥） 152009-7-24
嵌入
将网络中的各节点映射到另一个网络中去
用 膨胀 （ Dilation）系数来描述嵌入的质量，它是指被嵌入网络中的一条链路在所要嵌入的网络中对应所需的最大链路数
如果该系数为 1，则称为完美嵌入。
环网可完美嵌入到 2-D环绕网中
超立方网可完美嵌入到 2－ D环绕网中国家高性能计算中心（合肥） 162009-7-24
嵌入
1000 1001 1011 1010
1100 1101 1111 1110
0100 0101 0111 0110
0000 0001 0011 0010
01010100
0000 0001
01110110
0010 0011
11011100
1000 1001
11111110
1010 1011
国家高性能计算中心（合肥） 172009-7-24
网络名称 网络规模 节点度 网络直径 对剖宽度 对称 链路数线性阵列 2 1 非环形 2 （双向）
2 是
2-D网孔 4 非
Illiac网孔 4 非
2-D环绕 4 是二叉树 3 1 非星形 2 非超立方 n n 是立方环 3 是
N
N
N
N
NN?
NN?
NN?
nN 2?
kkN 2
1?N
1?N
2/N
)1(2?N
1?N
2/2 N
1log2?N
2/12 kk
N
N2
N2
2/N
2/N
)2/(kN
1?N
N
)(2 NN?
N2
N2
1?N
1?N
2/nN
2/3N
静态互连网络特性比较国家高性能计算中心（合肥） 182009-7-24
动态互连网络 (1)
总线,PCI,VME,Multics,Sbus,MicroChannel
多处理机总线系统的主要问题包括总线仲裁、中断处理、协议转换、
快速同步、高速缓存一致性协议、分事务、总线桥和层次总线扩展等
LM IOC
本地总线高速缓存
CPU
IF IF
IF
存储器总线存储器单元
IF
IF
CPU板 存储器板
I/O板 通信板系统总线 (底 板上)
数据总线缓冲
CCIOP
数据总线网络
(以 太网等)
磁盘和磁带部件打印机或绘图仪本地外围设备
(S CS I总 线)
MC
IF缓冲国家高性能计算中心（合肥） 192009-7-24
动态互连网络 （ 2）
交叉开关（ Crossbar）：
单级交换网络，可为每个端口提供更高的带宽。象电话交换机一样，交叉点开关可由程序控制动态设置其处于,开,或,关,
状态，而能提供所有（源、目的）对之间的动态连接。
交叉开关一般有两种使用方式：一种是用于对称的多处理机或多计算机机群中的处理器间的通信；另一种是用于 SMP服务器或向量超级计算机中处理器和存储器之间的存取。
国家高性能计算中心（合肥） 202009-7-24
动态互联网络 （ 3）
单级交叉开关级联起来形成多级互连网络 MIN
（ Multistage Interconnection Network）
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
(a) 4种 可能的开关连接
000
001
010
011
100
101
110
111
输入
000
001
010
011
100
101
110
111
输出第0 级 第1 级 第2 级
(b) 一种8输 入的Ome ga网 络国家高性能计算中心（合肥） 212009-7-24
动态互连网络（ 4）
交换开关模块：
一个交换开关模块有 n个输入和 n个输出，每个输入可连接到任意输出端口，但只允许一对一或一对多的映射，不允许多对一的映射，因为这将发生输出冲突
级间互连（ Interstage Connection ）：
均匀洗牌、蝶网、多路均匀洗牌、交叉开关、立方连接
n输入的 Ω网络需要 级 开关，在 Ilinois大学的
Cedar[2]多处理机系统中采用了 Ω网络
Cray Y/MP多级网络，该网络用来支持 8个向量处理器和 256
个存储器模块之间的数据传输。网络能够避免 8个处理器同时进行存储器存取时的冲突。
n2log 22?
国家高性能计算中心（合肥） 222009-7-24
动态互连网络比较
n,节点规模 w,数据宽度动态互连网络的复杂度和带宽性能一览表网络特性 总线系统 多级互连网络 交叉开关硬件复杂度每个处理器带宽
～
报道的聚集带宽 SunFire服务器中的 Gigaplane
总线,2.67GB/s
IBM SP2中的
512节点的 HPS：
10.24GB/s
Digital的千兆开关,3.4GB/s
)( wnO? ))lo g(( wnnO k )( 2wnO
)/( nwfO )(wfO )(wfO )(wfO
国家高性能计算中心（合肥） 232009-7-24
标准互联网络（ 1）
Myrinet:
Myrinet是由 Myricom公司设计的千兆位包交换网络，其目的是为了构筑计算机机群，使系统互连成为一种商业产品。
Myrinet是基于加州理工学院开发的多计算机和 VLSI技术以及在南加州大学开发的 ATOMIC/LAN技术。 Myrinet能假设任意拓扑结构，不必限定为开关网孔或任何规则的结构。
Myrinet在数据链路层具有可变长的包格式，对每条链路施行流控制和错误控制，并使用切通选路法以及定制的可编程的主机接口。在物理层上,Myrinet网使用全双工 SAN链路，最长可达 3米，峰值速率为（ 1.28＋ 1.28） Gbps（ 目前有
2.56+2.56)
Myrinet交换开关,8,12,16端口
Myrinet主机接口,32位的称作 LANai芯片的用户定制的 VLSI
处理器，它带有 Myrinet接口、包接口,DMA引擎和快速静态随机存取存储器 SRAM。
140 of the November 2002 TOP500 use Myrinet,
including 15 of the top 100
国家高性能计算中心（合肥） 242009-7-24
Myrinet连接的 LAN/Cluster
交换开关 交换开关交换开关 交换开关桌面主机机箱内多计算机机群多处理机机群网络R A M 和
VME 单板磁盘国家高性能计算中心（合肥） 252009-7-24
标准互连网络（ 2)
高性能并行接口（ HiPPI）
Los Alamos国家实验室于 1987年提出的一个标准，其目的是试图统一来自不同产商生产的所有大型机和超级计算机的接口。
在大型机和超级计算机工业界,HiPPI作为短距离的系统到系统以及系统到外设连接的高速 I/O通道。
1993年,ANSI X3T9.3委员会认可了 HiPPI标准，它覆盖了物理和数据链路层，但在这两层之上的任何规定却取决于用户。
HiPPI是个单工的点到点的数据传输接口，其速率可达
800Mbps到 1.6Gbps。
开发成功了一种能提供潜在的 6.4Gbps速率，比 HiPPI快 8倍且有很低时延的超级 HiPPI技术，
SGI公司和 Los Alamos国家实验室都开发了用来构筑速率高达
25.6Gbps的 HiPPI交换开关的 HiPPI技术。
HiPPI通道和 HiPPI交换开关被用在 SGI Power Challenge服务器,IBM 390主机,Cray Y/MP,C90和 T3D/T3E等系统国家高性能计算中心（合肥） 262009-7-24
使用 HiPPI通道和开关构筑的
LAN主干网
HiPPI
交换开关超级计算机 帧缓冲器
RGB
显示器
HiPPI
串行文件服务器工作站小型机大规模并行处理系统
25米
300米
25米
25米
HiPPI
串行
300米直至10千米
300米
HiPPI
串行存储器服务器工作站光纤扩展器 光纤扩展器
HiPPI
交换开关国家高性能计算中心（合肥） 272009-7-24
标准互连网络（ 3）
光纤通道 FC（ Fiber Channel）,
通道和网络标准的集成
光纤通道既可以是共享介质，也可以是一种交换技术
光纤通道操作速度范围可从 100到 133,200,400和
800Mbps。 FCSI厂商也正在推出未来具有更高速度（ 1,2或
4Gbps） 的光纤通道
光纤通道的价值已被现在的某些千兆位局域网所证实，这些局域网就是基于光纤通道技术的
连网拓扑结构的灵活性是光纤通道的主要财富，它支持点到点、
仲裁环及交换光纤连接
FDDI,
光纤分布式数据接口 FDDI（ Fiber Distributed Data
Interface）
FDDI采用双向光纤令牌环可提供 100-200Mbps数据传输速率
FDDI具有互连大量设备的能力
传统的 FDDI仅以异步方式操作国家高性能计算中心（合肥） 282009-7-24
双向 FDDI环作为主干网文件服务器数据库服务器计算机服务器双向 FDDI环
FD DI 集中器
FDDI 集中器 FDDI 集中器桌面计算机以太网集线器路由器
国家高性能计算中心（合肥） 292009-7-24
标准互联网络（ 4）
ATM（ Asynchronous Transfer Mode）,
由成立于 1991年的 ATM论坛和 ITU标准定义。
ATM是一种独立于介质的消息传输协议，它将消息段变成更短的固定长度为 53字节的报元进行传输。
这种技术是基于报元交换机制。 ATM的目的是将实时和突发数据的传输合并成单一的网络技术。
ATM网络支持从 25到 51,155和 622Mbps不同的速率，其速率越低 ATM交换器和使用的链路价格越低。
国家高性能计算中心（合肥） 302009-7-24
香港大学开发的 Pearl机群
ASX-200BX
LAX-20
HARNET
Power
集线器70 00
IBM
SP2
城市大学的WS 池浸会大学的WS 池
USC的
IMSC
XL 服务器
PC
FDDI
PC
和
WS
去US A
主干因特网
Sun
E-6000
服务器
(8 CPU)
以太网工作站池
HP
服务器
Sun
E-4000
Sun
UltraSPARC
2/1200
Sun SPARC
20/HS14
以太网
T3
T1
155Mb/s
ASX-1000
AT M开 关
T1
T1
155Mb / s
155Mb/ s
SGI Power
Challenge
(8CPU)
32 节点 ）(
国家高性能计算中心（合肥） 312009-7-24
标准互连网络（ 5）
代别类型以太网
10BaseT
快速以太网
100BaseT
千兆位以太网
1GB
引入年代 1982 1994 1997
速度（带宽） 10Mb/s 100Mb/s 1Gb/s
最大距离
UTR（ 非屏蔽双扭对） 100m 100m 25－ 100m
STP（ 屏蔽双扭对）
同轴电缆
500m 100m 25－ 100m
多模光纤 2Km 412m（ 半双工）
2Km（ 全双工）
500m
单模光纤 25Km 20Km 3Km
主要应用领域 文件共享，
打印机共享
COW计算，
C/S结构，
大型数据库存取等大型图像文件，
多媒体，
因特网，
内部网，
数据仓库等国家高性能计算中心（合肥） 322009-7-24
并行计算机结构模型
P/C
LM
NIC
定制网络
(c)MPP
P/C
LM
NIC
MB MB
VP
SM
交叉开关
(a)PVP
VP VP
SMSM
P/C
SM SM I/O
总线或交叉开关
(b)SMP
P/C P/C?
P/C
LM
NIC
DIR
MB
定制网络
(d)DSM
P/C
LM
NIC
DIR
MB
LD
P/C
M
MB
IOB
(e)COW
LD
P/C
M
MB
IOB
商品网络(以太网，A TM,et c,)
Bridge
NICNIC
Bridge
国家高性能计算中心（合肥） 332009-7-24
并行计算机体系合一结构
SMP,MPP,DSM和 COW并行结构渐趋一致。
大量的节点通过高速网络互连起来
节点遵循 Shell结构：用专门定制的 Shell电路将商用微处理器和节点的其它部分（包括板级 Cache,局存,NIC和 DISK）
连接起来。优点是 CPU升级只需要更换 Shell。
C
P
NIC
(a)无共 享
NIC
互连网络
M
D
节点 N
节点 1
Shell
共享磁盘
C
P
NIC
(b)共享 磁盘
NIC
M
互连网络节点 N
节点 1
Shell
C
P
互连网络共享存储器 共享磁盘
(c)共享 存储
C
P
ShellShell
国家高性能计算中心（合肥） 342009-7-24
五种结构特性一览表属性 PVP SMP MPP DSM COW
结构类型 MIMD MIMD MIMD MIMD MIMD
处理器类型 专用定制 商用 商用 商用 商用互连网络 定制交叉开关 总线,交叉开关 定制网络 定制网络 商用网络 （ 以太
ATM）
通信机制 共享变量 共享变量 消息传递 共享变量 消息传递地址空间 单地址空间 单地址空间 多地址空间 单地址空间 多地址空间系统存储器 集中共享 集中共享 分布非共享 分布共享 分布非共享访存模型 UMA UMA NORMA NUMA NORMA
代表机器 Cray C-90，
Cray T-90，
银河 1号
IBM R50，
SGI Power
Challenge，
曙光 1号
Intel Paragon，
IBMSP2,曙光
1000/2000
Stanford DASH，
Cray T 3D
Berkeley NOW，
Alpha Farm
国家高性能计算中心（合肥） 352009-7-24
并行计算机访存模型（ 1)
P
1
P
2
P
n
I/O SM
1
SM
m
共享存储器处理器
（ ）
系统互连总线 交叉开关 多级,,网络
UMA（ Uniform Memory Access） 模型是均匀存储访问模型的简称。其特点是：
物理存储器被所有处理器均匀共享；
所有处理器访问任何存储字取相同的时间；
每台处理器可带私有高速缓存；
外围设备也可以一定形式共享。
国家高性能计算中心（合肥） 362009-7-24
并行计算机访存模型（ 2)
NUMA(Nonuniform Memory Access)模型是 非均匀存储访问 模型的简称 。 特点是：
被共享的存储器在物理上是分布在所有的处理器中的,其所有本地存储器的集合就组成了全局地址空间；
处理器访问存储器的时间是不一样的；访问本地存储器 LM或群内共享存储器 CSM较快,而访问外地的存储器或全局共享存储器 GSM较慢 (此即非均匀存储访问名称的由来 )；
每台处理器照例可带私有高速缓存,外设也可以某种形式共享 。
LM1 P1
LM2 P2
LMn Pn
互连网络
(a)共享本地存储模型全局互连网络
(b)层次式机群模型
GSM GSM GSM
… … …
…
P
C
I
N
CSM
P
P
CSM
CSM
群 1
… …
P
C
I
N
CSM
群 N
P
P
CSM
CSM… …
国家高性能计算中心（合肥） 372009-7-24
并行计算机访存模型（ 3)
COMA(Cache-Only Memory Access)模型是 全高速缓存存储访问 的简称 。 其特点是：
各处理器节点中没有存储层次结构,全部高速缓存组成了全局地址空间；
利用分布的高速缓存目录 D进行远程高速缓存的访问 ;
COMA中的高速缓存容量一般都大于 2级高速缓存容量；
使用 COMA时,数据开始时可任意分配,因为在运行时它最终会被迁移到要用到它们的地方 。
互连网络
D
C
P
D
C
P
D
C
P
国家高性能计算中心（合肥） 382009-7-24
并行计算机访存模型（ 4)
CC-NUMA（ Coherent-Cache Nonuniform Memory
Access） 模型是 高速缓存一致性非均匀存储访问 模型的简称。其特点是：
大多数使用基于目录的高速缓存一致性协议；
保留 SMP结构易于编程的优点，也改善常规 SMP的可扩放性；
CC-NUMA实际上是一个分布共享存储的 DSM多处理机系统；
它最显著的优点是程序员无需明确地在节点上分配数据，系统的硬件和软件开始时自动在各节点分配数据，在运行期间，高速缓存一致性硬件会自动地将数据迁移至要用到它的地方。
I/O NIC,DIR,RC
系统互连网路
MemP/CP/C
I/O NIC,DIR,RC
MemP/CP/C
节点 N节点 1
总线或 交叉 开关 总线或 交叉 开关
国家高性能计算中心（合肥） 392009-7-24
并行计算机访存模型（ 5)
消息传递 互连网络
(网 络，环网，超立方，
立方环等)
P M
P M
M P
M P
M
P
M
P
M
P
P
M
P
M
P
M
...
...
.
.
.
.
.
.
NORMA（ No-Remote Memory Access） 模型是 非远程存储访问 模型的简称 。 NORMA的特点是：
所有存储器是私有的；
绝大数 NUMA都不支持远程存储器的访问；
在 DSM中,NORMA就消失了 。
国家高性能计算中心（合肥） 402009-7-24
构筑并行机系统的不同存储结构
MIMD
多计算机
(多 地址空间非共享存储器)
(IBM SP2,DEC TruCluster
Tandem Hymalaya,HP,
Microsoft Wolfpack,etc)
NORMA
UMA
NUMA
Cluster
MPP (Intel TFLOPS)
紧耦合
PVP (Cray T90)
SMP
(Intel SHV,SunFire,DEC 8400,
SGI PowerChallenge,IBMR60,etc.)
COMA (KSR-1,DDM)
CC-NUMA
(Stanford Dash,
SGI Origin 2000,Sequent NUMA-Q,
HP/Convex Exemplar)
NCC-NUMA (Cray T3E)
DSM
(TreadMarks,
Wind Tunnel,
IVY,Shrimp,
etc.)
（ ）
松散耦合（ ）
中央 存储器分布 存储器多处理机单地址共享
（
）
空间存储器国家高性能计算中心（合肥） 412009-7-24
第二章 当代并行机系统
2.1 共享存储多处理机系统
2.1.1 对称多处理机 SMP结构特性
2.2 分布存储多计算机系统
2.2.1 大规模并行机 MPP结构特性
2.3 机群系统
2.3.1 大规模并行处理系统 MPP机群 SP2
2.3.2 工作站机群 COW
国家高性能计算中心（合肥） 422009-7-24
对称多处理机 SMP(1)
SMP,采用商用微处理器，通常有片上和片外 Cache,基于总线连接，集中式共享存储,UMA结构
例子,SGI Power Challenge,DEC Alpha
Server,Dawning 1
P/C
SM SM I/O
总线或交叉开关
P/C P/C?
国家高性能计算中心（合肥） 432009-7-24
对称多处理机 SMP(2)
优点
对称性
单地址空间，易编程性，动态负载平衡，无需显示数据分配
高速缓存及其一致性，数据局部性，硬件维持一致性
低通信延迟,Load/Store完成
问题
欠可靠,BUS,OS,SM
通信延迟（相对于 CPU）,竞争加剧
慢速增加的带宽（ MB double/3年,IOB更慢）
不可扩放性 ---〉 CC-NUMA
国家高性能计算中心（合肥） 442009-7-24
大规模并行机 MPP
成百上千个处理器组成的大规模计算机系统，规模是变化的。
NORMA结构，高带宽低延迟定制互连。
可扩放性,Mem,I/O,平衡设计
系统成本：商用处理器，相对稳定的结构,SMP,分布
通用性和可用性：不同的应用,PVM,MPI,交互，批处理，互连对用户透明，单一系统映象，故障
通信要求
存储器和 I/O能力
例子,Intel Option Red
IBM SP2 Dawning 1000
P/C
LM
NIC
定制网络
P/C
LM
NIC
MB MB
国家高性能计算中心（合肥） 452009-7-24
典型 MPP系统特性比较
MPP模型 Intel/Sandia ASCI
Option Red
IBM SP2 SGI/Cray
Origin2000
一个大型样机的配置 9072个处理器，
1.8Tflop/s(NSL)
400个处理器，
100Gflop/s(MHPC
C)
128个处理器，
51Gflop/s(NCSA)
问世日期 1996年 12月 1994年 9月 1996年 10月处理器类型 200MHz,
200Mflop/s
Pentium Pro
67MHz，
267Mflop/s
POWER2
200MHz，
400Mflop/s MIPS
R10000
节点体系结构和数据存储器
2个处理器,32到
256MB主存，共享磁盘
1个处理器,64MB
到 2GB本地主存，
1GB到 14.5GB本地磁盘
2个处理器,64MB
到 256MB分布共享主存和共享磁盘互连网络和主存模型 分离两维网孔，
NORMA
多级网络，
NORMA
胖超立方体网络，
CC-NUMA
节点操作系统 轻量级内核
（ LWK）
完全 AIX（ IBM
UNIX）
微内核 Cellular
IRIX
自然编程机制 基于 PUMA
Portals的 MPI
MPI和 PVM Power C,Power
Fortran
其他编程模型 Nx,PVM,HPF HPF,Linda MPI,PVM
国家高性能计算中心（合肥） 462009-7-24
MPP所用的高性能 CPU特性比较属性 Pentium Pro PowerPC
602
Alpha
21164A
Ultra SPARC
II
MIPS
R10000工艺 BiCMOS CMOS CMOS CMOS CMOS
晶体管数 5.5M/15.5M 7M 9.6M 5.4M 6.8M
时钟频率 150MHz 133MHz 417MHz 200MHz 200MHz
电压 2.9V 3.3V 2.2V 2.5V 3.3V
功率 20W 30W 20W 28W 30W
字长 32位 64位 64位 64位 64位
I/O
高速缓存
8KB/8KB 32KB/32KB 8KB/8KB 16KB/16KB 32KB/32K
B2级高速缓存
256KB
(多芯片模块
)
1~128MB
(片外 )
96KB
(片上 )
16MB
(片外 )
16MB
(片外 )
执行单元 5个单元 6个单元 4个单元 9个单元 5个单元超标量 3路 (Way) 4路 4路 4路 4路流水线深度
14级 4~8级 7~9级 9级 5~7级
SPECint 92 366 225 >500 350 300
SPECfp 92 283 300 >750 550 600
SPECint 95 8.09 225 >11 N/A 7.4
SPECfp 95 6.70 300 >17 N/A 15
其它特性 CISC/RISC
混合短流水线长
L1高速缓存最高时钟频率最大片上
2级高速缓存多媒体和图形指令
MP机群总线可支持 4
个 CPU
国家高性能计算中心（合肥） 472009-7-24
机群型大规模并行机 SP2
设计策略：
机群体系结构
标准环境
标准编程模型
系统可用性
精选的单一系统映像
系统结构：
高性能开关 HPS 多级 Ω网络
宽节点、窄节点和窄节点 2
NIC
D
E
节点1
NIC
D
E
节点
S
以太网
P
MCC MCC
P
P
P
N
高性能 Omega,网络开关
I/O 总线I/O 总线
国家高性能计算中心（合肥） 482009-7-24
工作站机群 COW
分布式存储,MIMD,工作站 +商用互连网络，每个节点是一个完整的计算机，有自己的磁盘和操作系统，而 MPP中只有微内核
优点：
投资风险小
系统结构灵活
性能 /价格比高
能充分利用分散的计算资源
可扩放性好
问题
通信性能
并行编程环境
例子,Berkeley NOW,Alpha Farm,FXCOW
P/C
M
MIO MIO
M
P/C
NIC NIC
D DLAN
国家高性能计算中心（合肥） 492009-7-24
典型的机群系统典型的机群系统特点一览表名称 系统特点
Princeton:SHRIMP PC商用组件,通过专用网络接口达到共享虚拟存储,支持有效通信
Karsruhe:Parastation 用于分布并行处理的有效通信网络和软件开发
Rice:TreadMarks 软件实现分布共享存储的工作站机群
Wisconsin:Wind Tunnel 在经由商用网络互连的工作站机群上实现分布共享存储
Chica,Maryl、
Penns:NSCP
国家可扩放机群计划：在通过因特网互连的 3个本地机群系统上进行元计算
Argonne:Globus 在由 ATM连接的北美 17个站点的 WAN上开发元计算平台和软件
Syracuse:WWVM 使用因特网和 HPCC技术,在世界范围的虚拟机上进行高性能计算
HKU:Pearl Cluster 研究机群在分布式多媒体和金融数字库方面的应用
Virgina:Legion 在国家虚拟计算机设施上开发元计算软件国家高性能计算中心（合肥） 502009-7-24
SMP\MPP\机群比较系统特征 SMP MPP 机群节点数量 (N)?O(10) O(100)-O(1000)?O(100)
节点复杂度 中粒度或细粒度 细粒度或中粒度 中粒度或粗粒度节点间通信 共享存储器 消息传递或共享变量（有 DSM时）
消息传递节点操作系统 1 N(微内核 )
和 1个主机 OS(单一 )
N (希望为同构 )
支持单一系统映像 永远 部分 希望地址空间 单一 多或单一（有 DSM时） 多个作业调度 单一运行队列 主机上单一运行队列 协作多队列网络协议 非标准 非标准 标准或非标准可用性 通常较低 低到中 高可用或容错性能 /价格比 一般 一般 高互连网络 总线 /交叉开关 定制 商用国家高性能计算中心（合肥） 512009-7-24
第三章 并行计算性能评测
3.1 并行机的一些基本性能指标
3.2 加速比性能定律
3.2.1 Amdahl定律
3.2.2 Gustafson定律
3.2.3 Sun和 Ni定律
3.3 可扩放性评测标准
3.3.1 并行计算的可扩放性
3.3.2 等效率度量标准
3.3.3 等速度度量标准
3.3.4 平均延迟度量标准国家高性能计算中心（合肥） 522009-7-24
CPU的某些基本性能指标
工作负载
执行时间
浮点运算数
指令数目
并行执行时间 T comput 为计算时间,T paro 为并行开销时间,T comm为相互通信时间
T n = T comput + T paro+ T comm
例：估计 APRAM模型下执行时间
T
n
TTT
n
T
n 11,m ax
国家高性能计算中心（合肥） 532009-7-24
存储器性能
存储器的层次结构 (C,L,B)
估计存储器的带宽
RISC add r1,r2,r3 r 8bytes 100MHz
B = 3*8*100*106 B/s= 2.4GB/s
寄存器
1级高速缓存
2级高速缓存主存 磁盘远程存储器
C<2KB
L=0周 期
B=1-32GB/S
4-256KB
0-2周 期
1-16GB/S
64KB-4MB
2-10周 期
1-4GB/S
16MB-16GB
10-100周 期
0.4-2GB/S
1-100GB
100K-1M周 期
1-16MB/S
1-100GB
100-100K周 期
1-300MB/S
国家高性能计算中心（合肥） 542009-7-24
并行与通信开销
并行和通信开销：相对于计算很大。
PowerPC (每个周期 15ns 执行 4flops;
创建一个进程 1.4ms 可执行 372000flops)
开销的测量：乒 --乓方法（ Ping-Pong Scheme）
节点 0发送 m个字节给节点 1；节点 1从节点 0接收
m个字节后，立即将消息发回节点 0。总的时间除以 2，即可得到点到点通信时间，也就是执行单一发送或接收操作的时间。
可一般化为热土豆法（ Hot-Potato）,也称为救火队法（ Fire-Brigade) 0——1 —— 2 ——
… —— -n-1 —— 0
国家高性能计算中心（合肥） 552009-7-24
Ping-Pong Scheme
if （ my _node _id =0） then /*发送者 */
start _time =second（ ）
send an m-byte message to node 1
receive an m-byte message from node 1
end_time = second（ ）
total_time = end_time – start_time
communication_time[i] = total_time/2
else if （ my_node_id = 1） then /*接收者 */
receive an m-byte message from node 0
send an m-byte message to node 0
endif
国家高性能计算中心（合肥） 562009-7-24
并行开销的表达式：点到点通信
通信开销 t(m) = t0 + m/ r∞
通信启动时间 t0
渐近 带宽 r∞,传送无限长的消息时的通信速率
半 峰值长度 m1/2,达到一半渐近带宽所要的消息长度
特定性能 π0：表示短消息带宽
t0 = m1/2 / r∞ = 1 /π0
国家高性能计算中心（合肥） 572009-7-24
并行开销的表达式：整体通信
典型的整体通信有：
播送（ Broadcasting）,处理器 0发送 m个字节给所有的 n个处理器
收集（ Gather）,处理 0接收所有 n个处理器发来在消息，所以处理器 0最终接收了 m n个字节；
散射（ Scatter）,处理器 0发送了 m个字节的不同消息给所有
n个处理器，因此处理器 0最终发送了 m n个字节；
全交换（ Total Exchange）,每个处理器均彼此相互发送 m个字节的不同消息给对方，所以总通信量为 mn2个字节；
循环移位（ Circular-shift）,处理器 i发送 m个字节给处理器
i+1,处理器 n-1发送 m个字节给处理器 0，所以通信量为 m n个字节。
国家高性能计算中心（合肥） 582009-7-24
机器的成本、价格与性 /价比
机器的成本与价格
机器的性能 /价格比 Performance/Cost Ratio,系指用单位代价（通常以百万美元表示）所获取的性能（通常以 MIPS或 MFLOPS表示）
利用率（ Utilization）,可达到的速度与峰值速度之比国家高性能计算中心（合肥） 592009-7-24
算法级性能评测
加速比性能定律
并行系统的加速比是指对于一个给定的应用，并行算法（或并行程序）
的执行速度相对于串行算法（或串行程序）的执行速度加快了多少倍。
Amdahl 定律
Gustafson定律
Sun Ni定律
可扩放性评测标准
等效率度量标准
等速度度量标准
平均延迟度量标准国家高性能计算中心（合肥） 602009-7-24
Amdahl 定律
P,处理器数；
W,问题规模（ 计算负载、工作负载，给定问题的总计算量 ）；
Ws,应用程序中的串行分量,f是串行分量比例（ f = Ws/W，
Ws=W1）；
WP,应用程序中可并行化部分,1-f为并行分量比例；
Ws +W p =W；
Ts=T1,串行执行时间,T p,并行执行时间；
S,加速比,E,效率；
出发点：
固定不变的计算负载；
固定的计算负载分布在多个处理器上的，
增加处理器加快执行速度，从而达到了加速的目的。
国家高性能计算中心（合肥） 612009-7-24
Amdahl定律（ cont‘d)
固定负载的加速公式：
W s+ W p可相应地表示为 f+（ 1-f）
p→ ∞时，上式极限为,S= 1 / f
W o为额外开销
pWWs
WpWsS
P /?
)1(11
)1(
pf
p
p
f
f
ff
S
WpWpf
p
W
p
fW
fW
W
W
p
W
W
WW
S
OOOPS
PS
/)1(1)1(
国家高性能计算中心（合肥） 622009-7-24
Amdahl’s law (cont’d)
程序中顺序部分的百分比 f
(c)
0% 1% 2% 3% 4% 100%
加速比
S S
1024
=1024/(1+1023 f )
1024x
91x
48x
31x
24x
1x
W
p
W
p
W
p
W
p
W
p
W
p
W
1
W
1
W
1
W
1
W
1
W
1
工作负载
W
处理器数 P
(a)
1 2 3 4 5 6
T
1
T
1
T
p
T
p
T
p
T
p
T
p
T
p
T
1
T
1
T
1
执行时间
T
处理器数 P
(b)
T
1
1 2 3 4 5 6
国家高性能计算中心（合肥） 632009-7-24
Gustafson定律
出发点：
对于很多大型计算，精度要求很高，即在此类应用中精度是个关键因素，而计算时间是固定不变的。此时为了提高精度，必须加大计算量，相应地亦必须增多处理器数才能维持时间不变；
除非学术研究，在实际应用中没有必要固定工作负载而计算程序运行在不同数目的处理器上，增多处理器必须相应地增大问题规模才有实际意义。
Gustafson加速定律,
并行开销 W o,
PS
S
S
S
WW
p W pW
pWppW
p W pWS
/'
) p - f ( p -- p ) f ( p - f ) p ( f S ' 111
WW
fpf
WWW
pWWS
OOPS
PS
/1
1'
国家高性能计算中心（合肥） 642009-7-24
Gustafson定律（ cont‘d)
程序中顺序部分的百分比 f
(c)
S '
1024
=1024-1023 f
0% 1% 2% 3% 4%
1024x
1014x 1004x 993x
983x
加速比
S
'
处理器数 P
工作负载
W
(a)
W
1
W
1
W
1
W
1
W
1
W
1
W
p
W
p
W
p
W
p
W
p
W
p
1 2 3 4 5 6
T
p
T
1
T
1
T
1
T
1
T
1
T
1
执行时间
T
处理器数 P
(b)
1 2 3 4 5 6
T
p
T
p
T
p
T
p
T
p
国家高性能计算中心（合肥） 652009-7-24
Sun 和 Ni定律
基本思想：
只要存储空间许可，应尽量增大问题规模以产生更好和更精确的解
（此时可能使执行时间略有增加）。
假定在单节点上使用了全部存储容量 M并在相应于 W的时间内求解之，
此时工作负载 W= fW + （ 1-f） W。
在 p 个节点的并行系统上，能够求解较大规模的问题是因为存储容量可增加到 pM。 令因子 G（ p） 反应存储容量增加到 p倍时并行工作负载的增加量，所以扩大后的工作负载 W = fW + （ 1-f） G（ p） W。
存储受限的加速公式,
并行开销 W o:
pWpGffW
WpGffWS
/1
1''
ppGff
pGff
/1
1
WWppGff
pGff
WpWpGffW
pWGffWS
OO //1
1
/1
1'
国家高性能计算中心（合肥） 662009-7-24
Sun 和 Ni定律 (cont’d)
G（ p） =1时就是 Amdahl加速定律；
G（ p） =p 变为 f + p（ 1-f）,就是 Gustafson加速定律
G（ p） >p时，相应于计算机负载比存储要求增加得快，
此时 Sun和 N i 加速均比 Amdahl 加速和 Gustafson 加速为高。
T
1
T
p
执行时间
T
处理器数 P
(b)
T
1
T
1
T
1
T
1
T
1 T
p
T
p
T
p
T
pT
p
处理器数 P
工作负载
W
(a)
W
1
W
p
W
p
W
p
W
p
W
p
W
p
W
1
W
1
W
1
W
1
W
1
1 2 3 4 5 6 1 2 3 4 5 6
国家高性能计算中心（合肥） 672009-7-24
加速比讨论
参考的加速经验公式,p/log p≤S≤P
线性加速比：很少通信开销的矩阵相加、内积运算等
p/log p的加速 比：分治类的应用问题
通信密集类的应用问题,S = 1 / C （ p ）
超线性加速
绝对加速：最佳并行算法与串行算法
相对加速：同一算法在单机和并行机的运行时间国家高性能计算中心（合肥） 682009-7-24
可扩放性评测标准
并行计算的可扩放性（ Scalability） 也是主要性能指标
可扩放性最简朴的含意是在确定的应用背景下，计算机系统（或算法或程序等）性能随处理器数的增加而按比例提高的能力
影响加速比的因素：处理器数与问题规模
求解问题中的串行分量
并行处理所引起的额外开销（通信、等待、竞争、冗余操作和同步等）
加大的处理器数超过了算法中的并发程度
增加问题的规模有利于提高加速的因素：
较大的问题规模可提供较高的并发度；
额外开销的增加可能慢于有效计算的增加；
算法中的串行分量比例不是固定不变的（串行部分所占的比例随着问题规模的增大而缩小）。
增加处理器数会增大额外开销和降低处理器利用率，所以对于一个特定的并行系统（算法或程序），它们能否有效利用不断增加的处理器的能力应是受限的，而度量这种能力就是可扩放性这一指标。
国家高性能计算中心（合肥） 692009-7-24
可扩放性评测标准（ cont‘d)
可扩放性,调整什么和按什么比例调整
并行计算要调整的是处理数 p和问题规模 W，
两者可按不同比例进行调整，此比例关系（可能是线性的，多项式的或指数的等）就反映了可扩放的程度。
并行算法和体系结构
可扩放性研究的主要目的：
确定解决某类问题用何种并行算法与何种并行体系结构的组合，
可以有效地利用大量的处理器；
对于运行于某种体系结构的并行机上的某种算法当移植到大规模处理机上后运行的性能；
对固定的问题规模，确定在某类并行机上最优的处理器数与可获得的最大的加速比；
用于指导改进并行算法和并行机体系结构，以使并行算法尽可能地充分利用可扩充的大量处理器
目前无一个公认的、标准的和被普遍接受的严格定义和评判它的标准国家高性能计算中心（合肥） 702009-7-24
等效率度量标准
令 tie 和 t io 分别是并行系统上第 i个处理器的有用计算时间和额外开销时间（包括通信、同步和空闲等待时间等）
T p 是 p个处理器系统上并行算法的运行时间，对于任意 i显然有 T p = tie +t io,且 T e+ T o= pT p
问题的规模 W为最佳串行算法所完成的计算量 W=Te
如果问题规模 W 保持不变，处理器数 p增加，开销 To增大，
效率 E下降。为了维持一定的效率（介于 0与 1之间），当处理数 p增大时，需要相应地增大问题规模 W的值。由此定义函数 f E（ p） 为问题规模 W随处理器数 p变化的函数，为等效率函数（ ISO-efficiency Function）（ Kumar1987）
1
0
p
i
i
ee TstT?
1
0
p
i
i
oo tT
W
T
p
T
T
p
p
TT
T
T
TS
o
e
ooe
e
p
e
11 WTTTP
SE
o
e
o?
1
1
1
1
国家高性能计算中心（合肥） 712009-7-24
等效率度量标准（ cont‘d)
曲线 1表示算法具有很好的扩放性；曲线 2表示算法是可扩放的；曲线 3表示算法是不可扩放的。
优点：简单可定量计算的、少量的参数计算等效率函数
缺点：如果 To无法计算出（在共享存储并行机中）
处理器数 P
工作负载
W
曲线 3
曲线 2
曲线 1
国家高性能计算中心（合肥） 722009-7-24
等速度度量标准
p 表示处理器个数,W表示要求解问题的工作量或称问题规模
（在此可指浮点操作个数）,T为并行执行时间，定义并行计算的速度 V为工作量 W除以并行时间 T
p个处理器的并行系统的平均速度定义为并行速度 V除以处理器个数 p：
W是使用 p个处理器时算法的工作量，令 W’表示当处理数从 p增大到 p’时，为了保持整个系统的平均速度不变所需执行的工作量，则可得到处理器数从 p到 p’时平均速度可扩放度量标准公式
pT
W
p
VV
'
'
'/'
/)',(
pW
Wp
pW
pWpp
国家高性能计算中心（合肥） 732009-7-24
等速度度量标准（ cont’d）
问题规模处理器数执行时间处理器数处理器数平均速度处理器数执行时间
优点：直观地使用易测量的机器性能速度指标来度量
缺点：某些非浮点运算可能造成性能的变化国家高性能计算中心（合肥） 742009-7-24
平均延迟度量标准
Ti为 Pi的执行时间，包括包括延迟 Li,Pi的总延迟时间为,L i+启动时间 +停止时间,。定义系统平均延迟时间为
pTpara =To+ Ts
在 p个处理器上求解工作量为 W问题的平均延迟
在 p’个处理器上求解工作量为 W’问题的平均延迟当处理器数由 p变到 p’,而推持并行执行效率不变，则定义平均延迟可扩放性度量标准为
pLTTpWL p
i
iip a r a?
1
,
pWLpT o,?
pTTpWL s e qp a r a,
',',',,pWL pWLppE
pWL,
',' pWL
国家高性能计算中心（合肥） 752009-7-24
平均延迟度量标准（ Cont’d)
处理器数 P
T
1
T
2
T
3
T
4
T
5
T
6
T
7
T
8
T
5
= T
para
执行时间
T
p
a
r
a
5
4
3
2
1
P
1
P
2
P
3
P
4
P
5
P
6
P
7
P
8
开销延迟 L
i
启动前与结束后空 闲时间 运行时间 T
i
优点：平均延迟能在更低层次上衡量机器的性能
缺点：需要特定的软硬件才能获得平均延迟
——结构?算法?编程国家高性能计算中心（合肥） 22009-7-24
并行计算 ——结构?算法?编程
第一篇 并行计算的基础
第一章 并行计算机系统及其结构模型
第二章 当代并行机系统,SMP,MPP和 Cluster
第三章 并行计算性能评测
第二篇 并行算法的设计
第四章 并行算法的设计基础
第五章 并行算法的一般设计方法
第六章 并行算法的基本设计技术
第七章 并行算法的一般设计过程国家高性能计算中心（合肥） 32009-7-24
并行计算 ——结构?算法?编程
第三篇 并行数值算法
第八章 基本通信操作
第九章 稠密矩阵运算
第十章 线性方程组的求解
第十一章 快速傅里叶变换
第四篇 并行程序设计
第十二章 并行程序设计基础
第十三章 并行程序设计模型和共享存储系统编程
第十四章 分布存储系统并行编程
第十五章 并行程序设计环境与工具国家高性能计算中心（合肥） 42009-7-24
第一章并行计算机系统及结构模型
1.1 并行计算
1.1.1 并行计算与计算科学
1.1.2 当代科学与工程问题的计算需求
1.2 并行计算机系统互连
1.2.1 系统互连
1.2.2 静态互联网络
1.2.3 动态互连网络
1.2.4 标准互联网络
1.3 并行计算机系统结构
1.3.1 并行计算机结构模型
1.3.2 并行计算机访存模型国家高性能计算中心（合肥） 52009-7-24
并行计算
并行计算：并行机上所作的计算，又称高性能计算或超级计算。
计算科学：计算物理、计算化学、计算生物等
科学与工程问题的需求：气象预报、油藏模拟、核武器数值模拟、航天器设计、基因测序等。
需求类型：计算密集、数据密集、网络密集。
美国 HPCC计划：重大挑战性课题,3T性能
美国 Petaflops研究项目,Pflop/s。
美国 ASCI计划：核武器数值模拟。
国家高性能计算中心（合肥） 62009-7-24
高性能计算机
Intel（ Option Red)：
1Tflops,1997,Pentium Pro
SGI(Option Blue Mountain),
3Tflops,1998,MIPS10000
IBM(Option White),
7Tflops,Top4,2001,Power3
日本 Earth Simulator,
35Tflops,Top1,2002,VP
Hewlett-Packard ASCI Q：
7Tflops,Top2,3,2002,Alpha Server
中国联想：
1Tflops,Top43,2002
国家高性能计算中心（合肥） 72009-7-24
系统互连
不同带宽与距离的互连技术,
总线,SAN,LAN,MAN,WAN
局部总线
I/O
总线
SCI
HiPPI
Myrinet
千兆位 以太网光纤通道快速以太网以太网
10 Base T
FDDI
ATM
总线或开关 SAN LAN MAN WAN
100
Gb/s
10
Gb/s
1
Gb/s
100
Mb/s
10
Mb/s IsoEnet
网络带宽交叉开关
MIN 或
100 Base T
国家高性能计算中心（合肥） 82009-7-24
局部总线,I/O总线,SAN和 LAN
P M
I/O
桥磁盘
SAN(e.g.Myrinet)
LAN(e.g.以 太网,FDDI) 系统 I I
I / O 总线,
接口系统 I
处理器总线局部总线,存储器总线
SCSI
节点 2 节点 N
系统总线节点 1
国家高性能计算中心（合肥） 92009-7-24
网络性能指标
节点度（ Node Degree）,射入或射出一个节点的边数。在单向网络中，入射和出射边之和称为节点度。
网络直径（ Network Diameter）,网络中任何两个节点之间的最长距离，即最大路径数。
对剖宽度（ Bisection Width）,对分网络各半所必须移去的最少边数
对剖带宽（ Bisection Bandwidth）,每秒钟内，在最小的对剖平面上通过所有连线的最大信息位（或字节）数
如果从任一节点观看网络都一样，则称网络为对称的
（ Symmetry）
国家高性能计算中心（合肥） 102009-7-24
静态互连网络 与动态互连网络
静态互连网络：处理单元间有着固定连接的一类网络，
在程序执行期间，这种点到点的链接保持不变；典型的静态网络有一维线性阵列、二维网孔、树连接、超立方网络、立方环、洗牌交换网、蝶形网络等
动态网络：用交换开关构成的，可按应用程序的要求动态地改变连接组态；典型的动态网络包括总线、交叉开关和多级互连网络等。
国家高性能计算中心（合肥） 112009-7-24
静态互连网络（ 1）
一维线性阵列（ 1-D Linear Array）：
并行机中最简单、最基本的互连方式，
每个节点只与其左、右近邻相连，也叫二近邻连接，
N个节点用 N-1条边串接之，内节点度为 2，直径为 N-1,对剖宽度为 1
当首、尾节点相连时可构成循环移位器，在拓扑结构上等同于环，环可以是单向的或双向的，其节点度恒为 2，直径或为
（双向环）或为 N-1（ 单向环），对剖宽度为 2
2/N
国家高性能计算中心（合肥） 122009-7-24
静态互连网络（ 2）
二维网孔（ 2-D Mesh）：
每个节点只与其上、下、左、右的近邻相连（边界节点除外），
节点度为 4，网络直径为,对剖宽度为
在垂直方向上带环绕，水平方向呈蛇状，就变成 Illiac网孔了，
节点度恒为 4，网络直径为,而对剖宽度为
垂直和水平方向均带环绕，则变成了 2-D环绕（ 2-D Torus），
节点度恒为 4，网络直径为,对剖宽度为
)1(2?N N
1?N N2
2/2 N N2
NN?
(a)2-D网孔 (b)Illiac网孔 (c)2-D环绕国家高性能计算中心（合肥） 132009-7-24
静态互连网络（ 3）
二叉树：
除了根、叶节点，每个内节点只与其父节点和两个子节点相连。
节点度为 3，对剖宽度为 1，而树的直径为
如果尽量增大节点度为，则直径缩小为 2，此时就变成了星形网络，其对剖宽度为
传统二叉树的主要问题是根易成为通信瓶颈。胖树节点间的通路自叶向根逐渐变宽。
1log2?N
2/N
(a) 二叉树 (b) 星形连接
(c) 二叉胖树国家高性能计算中心（合肥） 142009-7-24
静态互连网络（ 4）
超立方,
一个 n-立方由 个顶点组成,3-立方如图 (a)所示； 4-立方如图 (b)所示，由两个 3-立方的对应顶点连接而成。
n-立方的节点度为 n,网络直径也是 n,而对剖宽度为 。
如果将 3-立方的每个顶点代之以一个环就构成了如图 (d)所示的 3-立方环，此时每个顶点的度为 3，而不像超立方那样节点度为 n。
nN 2?
2/N
(b )4 -立 方(a )3 -立 方
(c )顶 点代之以环 (d )3 -立 方环国家高性能计算中心（合肥） 152009-7-24
嵌入
将网络中的各节点映射到另一个网络中去
用 膨胀 （ Dilation）系数来描述嵌入的质量，它是指被嵌入网络中的一条链路在所要嵌入的网络中对应所需的最大链路数
如果该系数为 1，则称为完美嵌入。
环网可完美嵌入到 2-D环绕网中
超立方网可完美嵌入到 2－ D环绕网中国家高性能计算中心（合肥） 162009-7-24
嵌入
1000 1001 1011 1010
1100 1101 1111 1110
0100 0101 0111 0110
0000 0001 0011 0010
01010100
0000 0001
01110110
0010 0011
11011100
1000 1001
11111110
1010 1011
国家高性能计算中心（合肥） 172009-7-24
网络名称 网络规模 节点度 网络直径 对剖宽度 对称 链路数线性阵列 2 1 非环形 2 （双向）
2 是
2-D网孔 4 非
Illiac网孔 4 非
2-D环绕 4 是二叉树 3 1 非星形 2 非超立方 n n 是立方环 3 是
N
N
N
N
NN?
NN?
NN?
nN 2?
kkN 2
1?N
1?N
2/N
)1(2?N
1?N
2/2 N
1log2?N
2/12 kk
N
N2
N2
2/N
2/N
)2/(kN
1?N
N
)(2 NN?
N2
N2
1?N
1?N
2/nN
2/3N
静态互连网络特性比较国家高性能计算中心（合肥） 182009-7-24
动态互连网络 (1)
总线,PCI,VME,Multics,Sbus,MicroChannel
多处理机总线系统的主要问题包括总线仲裁、中断处理、协议转换、
快速同步、高速缓存一致性协议、分事务、总线桥和层次总线扩展等
LM IOC
本地总线高速缓存
CPU
IF IF
IF
存储器总线存储器单元
IF
IF
CPU板 存储器板
I/O板 通信板系统总线 (底 板上)
数据总线缓冲
CCIOP
数据总线网络
(以 太网等)
磁盘和磁带部件打印机或绘图仪本地外围设备
(S CS I总 线)
MC
IF缓冲国家高性能计算中心（合肥） 192009-7-24
动态互连网络 （ 2）
交叉开关（ Crossbar）：
单级交换网络，可为每个端口提供更高的带宽。象电话交换机一样，交叉点开关可由程序控制动态设置其处于,开,或,关,
状态，而能提供所有（源、目的）对之间的动态连接。
交叉开关一般有两种使用方式：一种是用于对称的多处理机或多计算机机群中的处理器间的通信；另一种是用于 SMP服务器或向量超级计算机中处理器和存储器之间的存取。
国家高性能计算中心（合肥） 202009-7-24
动态互联网络 （ 3）
单级交叉开关级联起来形成多级互连网络 MIN
（ Multistage Interconnection Network）
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
(a) 4种 可能的开关连接
000
001
010
011
100
101
110
111
输入
000
001
010
011
100
101
110
111
输出第0 级 第1 级 第2 级
(b) 一种8输 入的Ome ga网 络国家高性能计算中心（合肥） 212009-7-24
动态互连网络（ 4）
交换开关模块：
一个交换开关模块有 n个输入和 n个输出，每个输入可连接到任意输出端口，但只允许一对一或一对多的映射，不允许多对一的映射，因为这将发生输出冲突
级间互连（ Interstage Connection ）：
均匀洗牌、蝶网、多路均匀洗牌、交叉开关、立方连接
n输入的 Ω网络需要 级 开关，在 Ilinois大学的
Cedar[2]多处理机系统中采用了 Ω网络
Cray Y/MP多级网络，该网络用来支持 8个向量处理器和 256
个存储器模块之间的数据传输。网络能够避免 8个处理器同时进行存储器存取时的冲突。
n2log 22?
国家高性能计算中心（合肥） 222009-7-24
动态互连网络比较
n,节点规模 w,数据宽度动态互连网络的复杂度和带宽性能一览表网络特性 总线系统 多级互连网络 交叉开关硬件复杂度每个处理器带宽
～
报道的聚集带宽 SunFire服务器中的 Gigaplane
总线,2.67GB/s
IBM SP2中的
512节点的 HPS：
10.24GB/s
Digital的千兆开关,3.4GB/s
)( wnO? ))lo g(( wnnO k )( 2wnO
)/( nwfO )(wfO )(wfO )(wfO
国家高性能计算中心（合肥） 232009-7-24
标准互联网络（ 1）
Myrinet:
Myrinet是由 Myricom公司设计的千兆位包交换网络，其目的是为了构筑计算机机群，使系统互连成为一种商业产品。
Myrinet是基于加州理工学院开发的多计算机和 VLSI技术以及在南加州大学开发的 ATOMIC/LAN技术。 Myrinet能假设任意拓扑结构，不必限定为开关网孔或任何规则的结构。
Myrinet在数据链路层具有可变长的包格式，对每条链路施行流控制和错误控制，并使用切通选路法以及定制的可编程的主机接口。在物理层上,Myrinet网使用全双工 SAN链路，最长可达 3米，峰值速率为（ 1.28＋ 1.28） Gbps（ 目前有
2.56+2.56)
Myrinet交换开关,8,12,16端口
Myrinet主机接口,32位的称作 LANai芯片的用户定制的 VLSI
处理器，它带有 Myrinet接口、包接口,DMA引擎和快速静态随机存取存储器 SRAM。
140 of the November 2002 TOP500 use Myrinet,
including 15 of the top 100
国家高性能计算中心（合肥） 242009-7-24
Myrinet连接的 LAN/Cluster
交换开关 交换开关交换开关 交换开关桌面主机机箱内多计算机机群多处理机机群网络R A M 和
VME 单板磁盘国家高性能计算中心（合肥） 252009-7-24
标准互连网络（ 2)
高性能并行接口（ HiPPI）
Los Alamos国家实验室于 1987年提出的一个标准，其目的是试图统一来自不同产商生产的所有大型机和超级计算机的接口。
在大型机和超级计算机工业界,HiPPI作为短距离的系统到系统以及系统到外设连接的高速 I/O通道。
1993年,ANSI X3T9.3委员会认可了 HiPPI标准，它覆盖了物理和数据链路层，但在这两层之上的任何规定却取决于用户。
HiPPI是个单工的点到点的数据传输接口，其速率可达
800Mbps到 1.6Gbps。
开发成功了一种能提供潜在的 6.4Gbps速率，比 HiPPI快 8倍且有很低时延的超级 HiPPI技术，
SGI公司和 Los Alamos国家实验室都开发了用来构筑速率高达
25.6Gbps的 HiPPI交换开关的 HiPPI技术。
HiPPI通道和 HiPPI交换开关被用在 SGI Power Challenge服务器,IBM 390主机,Cray Y/MP,C90和 T3D/T3E等系统国家高性能计算中心（合肥） 262009-7-24
使用 HiPPI通道和开关构筑的
LAN主干网
HiPPI
交换开关超级计算机 帧缓冲器
RGB
显示器
HiPPI
串行文件服务器工作站小型机大规模并行处理系统
25米
300米
25米
25米
HiPPI
串行
300米直至10千米
300米
HiPPI
串行存储器服务器工作站光纤扩展器 光纤扩展器
HiPPI
交换开关国家高性能计算中心（合肥） 272009-7-24
标准互连网络（ 3）
光纤通道 FC（ Fiber Channel）,
通道和网络标准的集成
光纤通道既可以是共享介质，也可以是一种交换技术
光纤通道操作速度范围可从 100到 133,200,400和
800Mbps。 FCSI厂商也正在推出未来具有更高速度（ 1,2或
4Gbps） 的光纤通道
光纤通道的价值已被现在的某些千兆位局域网所证实，这些局域网就是基于光纤通道技术的
连网拓扑结构的灵活性是光纤通道的主要财富，它支持点到点、
仲裁环及交换光纤连接
FDDI,
光纤分布式数据接口 FDDI（ Fiber Distributed Data
Interface）
FDDI采用双向光纤令牌环可提供 100-200Mbps数据传输速率
FDDI具有互连大量设备的能力
传统的 FDDI仅以异步方式操作国家高性能计算中心（合肥） 282009-7-24
双向 FDDI环作为主干网文件服务器数据库服务器计算机服务器双向 FDDI环
FD DI 集中器
FDDI 集中器 FDDI 集中器桌面计算机以太网集线器路由器
国家高性能计算中心（合肥） 292009-7-24
标准互联网络（ 4）
ATM（ Asynchronous Transfer Mode）,
由成立于 1991年的 ATM论坛和 ITU标准定义。
ATM是一种独立于介质的消息传输协议，它将消息段变成更短的固定长度为 53字节的报元进行传输。
这种技术是基于报元交换机制。 ATM的目的是将实时和突发数据的传输合并成单一的网络技术。
ATM网络支持从 25到 51,155和 622Mbps不同的速率，其速率越低 ATM交换器和使用的链路价格越低。
国家高性能计算中心（合肥） 302009-7-24
香港大学开发的 Pearl机群
ASX-200BX
LAX-20
HARNET
Power
集线器70 00
IBM
SP2
城市大学的WS 池浸会大学的WS 池
USC的
IMSC
XL 服务器
PC
FDDI
PC
和
WS
去US A
主干因特网
Sun
E-6000
服务器
(8 CPU)
以太网工作站池
HP
服务器
Sun
E-4000
Sun
UltraSPARC
2/1200
Sun SPARC
20/HS14
以太网
T3
T1
155Mb/s
ASX-1000
AT M开 关
T1
T1
155Mb / s
155Mb/ s
SGI Power
Challenge
(8CPU)
32 节点 ）(
国家高性能计算中心（合肥） 312009-7-24
标准互连网络（ 5）
代别类型以太网
10BaseT
快速以太网
100BaseT
千兆位以太网
1GB
引入年代 1982 1994 1997
速度（带宽） 10Mb/s 100Mb/s 1Gb/s
最大距离
UTR（ 非屏蔽双扭对） 100m 100m 25－ 100m
STP（ 屏蔽双扭对）
同轴电缆
500m 100m 25－ 100m
多模光纤 2Km 412m（ 半双工）
2Km（ 全双工）
500m
单模光纤 25Km 20Km 3Km
主要应用领域 文件共享，
打印机共享
COW计算，
C/S结构，
大型数据库存取等大型图像文件，
多媒体，
因特网，
内部网，
数据仓库等国家高性能计算中心（合肥） 322009-7-24
并行计算机结构模型
P/C
LM
NIC
定制网络
(c)MPP
P/C
LM
NIC
MB MB
VP
SM
交叉开关
(a)PVP
VP VP
SMSM
P/C
SM SM I/O
总线或交叉开关
(b)SMP
P/C P/C?
P/C
LM
NIC
DIR
MB
定制网络
(d)DSM
P/C
LM
NIC
DIR
MB
LD
P/C
M
MB
IOB
(e)COW
LD
P/C
M
MB
IOB
商品网络(以太网，A TM,et c,)
Bridge
NICNIC
Bridge
国家高性能计算中心（合肥） 332009-7-24
并行计算机体系合一结构
SMP,MPP,DSM和 COW并行结构渐趋一致。
大量的节点通过高速网络互连起来
节点遵循 Shell结构：用专门定制的 Shell电路将商用微处理器和节点的其它部分（包括板级 Cache,局存,NIC和 DISK）
连接起来。优点是 CPU升级只需要更换 Shell。
C
P
NIC
(a)无共 享
NIC
互连网络
M
D
节点 N
节点 1
Shell
共享磁盘
C
P
NIC
(b)共享 磁盘
NIC
M
互连网络节点 N
节点 1
Shell
C
P
互连网络共享存储器 共享磁盘
(c)共享 存储
C
P
ShellShell
国家高性能计算中心（合肥） 342009-7-24
五种结构特性一览表属性 PVP SMP MPP DSM COW
结构类型 MIMD MIMD MIMD MIMD MIMD
处理器类型 专用定制 商用 商用 商用 商用互连网络 定制交叉开关 总线,交叉开关 定制网络 定制网络 商用网络 （ 以太
ATM）
通信机制 共享变量 共享变量 消息传递 共享变量 消息传递地址空间 单地址空间 单地址空间 多地址空间 单地址空间 多地址空间系统存储器 集中共享 集中共享 分布非共享 分布共享 分布非共享访存模型 UMA UMA NORMA NUMA NORMA
代表机器 Cray C-90，
Cray T-90，
银河 1号
IBM R50，
SGI Power
Challenge，
曙光 1号
Intel Paragon，
IBMSP2,曙光
1000/2000
Stanford DASH，
Cray T 3D
Berkeley NOW，
Alpha Farm
国家高性能计算中心（合肥） 352009-7-24
并行计算机访存模型（ 1)
P
1
P
2
P
n
I/O SM
1
SM
m
共享存储器处理器
（ ）
系统互连总线 交叉开关 多级,,网络
UMA（ Uniform Memory Access） 模型是均匀存储访问模型的简称。其特点是：
物理存储器被所有处理器均匀共享；
所有处理器访问任何存储字取相同的时间；
每台处理器可带私有高速缓存；
外围设备也可以一定形式共享。
国家高性能计算中心（合肥） 362009-7-24
并行计算机访存模型（ 2)
NUMA(Nonuniform Memory Access)模型是 非均匀存储访问 模型的简称 。 特点是：
被共享的存储器在物理上是分布在所有的处理器中的,其所有本地存储器的集合就组成了全局地址空间；
处理器访问存储器的时间是不一样的；访问本地存储器 LM或群内共享存储器 CSM较快,而访问外地的存储器或全局共享存储器 GSM较慢 (此即非均匀存储访问名称的由来 )；
每台处理器照例可带私有高速缓存,外设也可以某种形式共享 。
LM1 P1
LM2 P2
LMn Pn
互连网络
(a)共享本地存储模型全局互连网络
(b)层次式机群模型
GSM GSM GSM
… … …
…
P
C
I
N
CSM
P
P
CSM
CSM
群 1
… …
P
C
I
N
CSM
群 N
P
P
CSM
CSM… …
国家高性能计算中心（合肥） 372009-7-24
并行计算机访存模型（ 3)
COMA(Cache-Only Memory Access)模型是 全高速缓存存储访问 的简称 。 其特点是：
各处理器节点中没有存储层次结构,全部高速缓存组成了全局地址空间；
利用分布的高速缓存目录 D进行远程高速缓存的访问 ;
COMA中的高速缓存容量一般都大于 2级高速缓存容量；
使用 COMA时,数据开始时可任意分配,因为在运行时它最终会被迁移到要用到它们的地方 。
互连网络
D
C
P
D
C
P
D
C
P
国家高性能计算中心（合肥） 382009-7-24
并行计算机访存模型（ 4)
CC-NUMA（ Coherent-Cache Nonuniform Memory
Access） 模型是 高速缓存一致性非均匀存储访问 模型的简称。其特点是：
大多数使用基于目录的高速缓存一致性协议；
保留 SMP结构易于编程的优点，也改善常规 SMP的可扩放性；
CC-NUMA实际上是一个分布共享存储的 DSM多处理机系统；
它最显著的优点是程序员无需明确地在节点上分配数据，系统的硬件和软件开始时自动在各节点分配数据，在运行期间，高速缓存一致性硬件会自动地将数据迁移至要用到它的地方。
I/O NIC,DIR,RC
系统互连网路
MemP/CP/C
I/O NIC,DIR,RC
MemP/CP/C
节点 N节点 1
总线或 交叉 开关 总线或 交叉 开关
国家高性能计算中心（合肥） 392009-7-24
并行计算机访存模型（ 5)
消息传递 互连网络
(网 络，环网，超立方，
立方环等)
P M
P M
M P
M P
M
P
M
P
M
P
P
M
P
M
P
M
...
...
.
.
.
.
.
.
NORMA（ No-Remote Memory Access） 模型是 非远程存储访问 模型的简称 。 NORMA的特点是：
所有存储器是私有的；
绝大数 NUMA都不支持远程存储器的访问；
在 DSM中,NORMA就消失了 。
国家高性能计算中心（合肥） 402009-7-24
构筑并行机系统的不同存储结构
MIMD
多计算机
(多 地址空间非共享存储器)
(IBM SP2,DEC TruCluster
Tandem Hymalaya,HP,
Microsoft Wolfpack,etc)
NORMA
UMA
NUMA
Cluster
MPP (Intel TFLOPS)
紧耦合
PVP (Cray T90)
SMP
(Intel SHV,SunFire,DEC 8400,
SGI PowerChallenge,IBMR60,etc.)
COMA (KSR-1,DDM)
CC-NUMA
(Stanford Dash,
SGI Origin 2000,Sequent NUMA-Q,
HP/Convex Exemplar)
NCC-NUMA (Cray T3E)
DSM
(TreadMarks,
Wind Tunnel,
IVY,Shrimp,
etc.)
（ ）
松散耦合（ ）
中央 存储器分布 存储器多处理机单地址共享
（
）
空间存储器国家高性能计算中心（合肥） 412009-7-24
第二章 当代并行机系统
2.1 共享存储多处理机系统
2.1.1 对称多处理机 SMP结构特性
2.2 分布存储多计算机系统
2.2.1 大规模并行机 MPP结构特性
2.3 机群系统
2.3.1 大规模并行处理系统 MPP机群 SP2
2.3.2 工作站机群 COW
国家高性能计算中心（合肥） 422009-7-24
对称多处理机 SMP(1)
SMP,采用商用微处理器，通常有片上和片外 Cache,基于总线连接，集中式共享存储,UMA结构
例子,SGI Power Challenge,DEC Alpha
Server,Dawning 1
P/C
SM SM I/O
总线或交叉开关
P/C P/C?
国家高性能计算中心（合肥） 432009-7-24
对称多处理机 SMP(2)
优点
对称性
单地址空间，易编程性，动态负载平衡，无需显示数据分配
高速缓存及其一致性，数据局部性，硬件维持一致性
低通信延迟,Load/Store完成
问题
欠可靠,BUS,OS,SM
通信延迟（相对于 CPU）,竞争加剧
慢速增加的带宽（ MB double/3年,IOB更慢）
不可扩放性 ---〉 CC-NUMA
国家高性能计算中心（合肥） 442009-7-24
大规模并行机 MPP
成百上千个处理器组成的大规模计算机系统，规模是变化的。
NORMA结构，高带宽低延迟定制互连。
可扩放性,Mem,I/O,平衡设计
系统成本：商用处理器，相对稳定的结构,SMP,分布
通用性和可用性：不同的应用,PVM,MPI,交互，批处理，互连对用户透明，单一系统映象，故障
通信要求
存储器和 I/O能力
例子,Intel Option Red
IBM SP2 Dawning 1000
P/C
LM
NIC
定制网络
P/C
LM
NIC
MB MB
国家高性能计算中心（合肥） 452009-7-24
典型 MPP系统特性比较
MPP模型 Intel/Sandia ASCI
Option Red
IBM SP2 SGI/Cray
Origin2000
一个大型样机的配置 9072个处理器，
1.8Tflop/s(NSL)
400个处理器，
100Gflop/s(MHPC
C)
128个处理器，
51Gflop/s(NCSA)
问世日期 1996年 12月 1994年 9月 1996年 10月处理器类型 200MHz,
200Mflop/s
Pentium Pro
67MHz，
267Mflop/s
POWER2
200MHz，
400Mflop/s MIPS
R10000
节点体系结构和数据存储器
2个处理器,32到
256MB主存，共享磁盘
1个处理器,64MB
到 2GB本地主存，
1GB到 14.5GB本地磁盘
2个处理器,64MB
到 256MB分布共享主存和共享磁盘互连网络和主存模型 分离两维网孔，
NORMA
多级网络，
NORMA
胖超立方体网络，
CC-NUMA
节点操作系统 轻量级内核
（ LWK）
完全 AIX（ IBM
UNIX）
微内核 Cellular
IRIX
自然编程机制 基于 PUMA
Portals的 MPI
MPI和 PVM Power C,Power
Fortran
其他编程模型 Nx,PVM,HPF HPF,Linda MPI,PVM
国家高性能计算中心（合肥） 462009-7-24
MPP所用的高性能 CPU特性比较属性 Pentium Pro PowerPC
602
Alpha
21164A
Ultra SPARC
II
MIPS
R10000工艺 BiCMOS CMOS CMOS CMOS CMOS
晶体管数 5.5M/15.5M 7M 9.6M 5.4M 6.8M
时钟频率 150MHz 133MHz 417MHz 200MHz 200MHz
电压 2.9V 3.3V 2.2V 2.5V 3.3V
功率 20W 30W 20W 28W 30W
字长 32位 64位 64位 64位 64位
I/O
高速缓存
8KB/8KB 32KB/32KB 8KB/8KB 16KB/16KB 32KB/32K
B2级高速缓存
256KB
(多芯片模块
)
1~128MB
(片外 )
96KB
(片上 )
16MB
(片外 )
16MB
(片外 )
执行单元 5个单元 6个单元 4个单元 9个单元 5个单元超标量 3路 (Way) 4路 4路 4路 4路流水线深度
14级 4~8级 7~9级 9级 5~7级
SPECint 92 366 225 >500 350 300
SPECfp 92 283 300 >750 550 600
SPECint 95 8.09 225 >11 N/A 7.4
SPECfp 95 6.70 300 >17 N/A 15
其它特性 CISC/RISC
混合短流水线长
L1高速缓存最高时钟频率最大片上
2级高速缓存多媒体和图形指令
MP机群总线可支持 4
个 CPU
国家高性能计算中心（合肥） 472009-7-24
机群型大规模并行机 SP2
设计策略：
机群体系结构
标准环境
标准编程模型
系统可用性
精选的单一系统映像
系统结构：
高性能开关 HPS 多级 Ω网络
宽节点、窄节点和窄节点 2
NIC
D
E
节点1
NIC
D
E
节点
S
以太网
P
MCC MCC
P
P
P
N
高性能 Omega,网络开关
I/O 总线I/O 总线
国家高性能计算中心（合肥） 482009-7-24
工作站机群 COW
分布式存储,MIMD,工作站 +商用互连网络，每个节点是一个完整的计算机，有自己的磁盘和操作系统，而 MPP中只有微内核
优点：
投资风险小
系统结构灵活
性能 /价格比高
能充分利用分散的计算资源
可扩放性好
问题
通信性能
并行编程环境
例子,Berkeley NOW,Alpha Farm,FXCOW
P/C
M
MIO MIO
M
P/C
NIC NIC
D DLAN
国家高性能计算中心（合肥） 492009-7-24
典型的机群系统典型的机群系统特点一览表名称 系统特点
Princeton:SHRIMP PC商用组件,通过专用网络接口达到共享虚拟存储,支持有效通信
Karsruhe:Parastation 用于分布并行处理的有效通信网络和软件开发
Rice:TreadMarks 软件实现分布共享存储的工作站机群
Wisconsin:Wind Tunnel 在经由商用网络互连的工作站机群上实现分布共享存储
Chica,Maryl、
Penns:NSCP
国家可扩放机群计划：在通过因特网互连的 3个本地机群系统上进行元计算
Argonne:Globus 在由 ATM连接的北美 17个站点的 WAN上开发元计算平台和软件
Syracuse:WWVM 使用因特网和 HPCC技术,在世界范围的虚拟机上进行高性能计算
HKU:Pearl Cluster 研究机群在分布式多媒体和金融数字库方面的应用
Virgina:Legion 在国家虚拟计算机设施上开发元计算软件国家高性能计算中心（合肥） 502009-7-24
SMP\MPP\机群比较系统特征 SMP MPP 机群节点数量 (N)?O(10) O(100)-O(1000)?O(100)
节点复杂度 中粒度或细粒度 细粒度或中粒度 中粒度或粗粒度节点间通信 共享存储器 消息传递或共享变量（有 DSM时）
消息传递节点操作系统 1 N(微内核 )
和 1个主机 OS(单一 )
N (希望为同构 )
支持单一系统映像 永远 部分 希望地址空间 单一 多或单一（有 DSM时） 多个作业调度 单一运行队列 主机上单一运行队列 协作多队列网络协议 非标准 非标准 标准或非标准可用性 通常较低 低到中 高可用或容错性能 /价格比 一般 一般 高互连网络 总线 /交叉开关 定制 商用国家高性能计算中心（合肥） 512009-7-24
第三章 并行计算性能评测
3.1 并行机的一些基本性能指标
3.2 加速比性能定律
3.2.1 Amdahl定律
3.2.2 Gustafson定律
3.2.3 Sun和 Ni定律
3.3 可扩放性评测标准
3.3.1 并行计算的可扩放性
3.3.2 等效率度量标准
3.3.3 等速度度量标准
3.3.4 平均延迟度量标准国家高性能计算中心（合肥） 522009-7-24
CPU的某些基本性能指标
工作负载
执行时间
浮点运算数
指令数目
并行执行时间 T comput 为计算时间,T paro 为并行开销时间,T comm为相互通信时间
T n = T comput + T paro+ T comm
例：估计 APRAM模型下执行时间
T
n
TTT
n
T
n 11,m ax
国家高性能计算中心（合肥） 532009-7-24
存储器性能
存储器的层次结构 (C,L,B)
估计存储器的带宽
RISC add r1,r2,r3 r 8bytes 100MHz
B = 3*8*100*106 B/s= 2.4GB/s
寄存器
1级高速缓存
2级高速缓存主存 磁盘远程存储器
C<2KB
L=0周 期
B=1-32GB/S
4-256KB
0-2周 期
1-16GB/S
64KB-4MB
2-10周 期
1-4GB/S
16MB-16GB
10-100周 期
0.4-2GB/S
1-100GB
100K-1M周 期
1-16MB/S
1-100GB
100-100K周 期
1-300MB/S
国家高性能计算中心（合肥） 542009-7-24
并行与通信开销
并行和通信开销：相对于计算很大。
PowerPC (每个周期 15ns 执行 4flops;
创建一个进程 1.4ms 可执行 372000flops)
开销的测量：乒 --乓方法（ Ping-Pong Scheme）
节点 0发送 m个字节给节点 1；节点 1从节点 0接收
m个字节后，立即将消息发回节点 0。总的时间除以 2，即可得到点到点通信时间，也就是执行单一发送或接收操作的时间。
可一般化为热土豆法（ Hot-Potato）,也称为救火队法（ Fire-Brigade) 0——1 —— 2 ——
… —— -n-1 —— 0
国家高性能计算中心（合肥） 552009-7-24
Ping-Pong Scheme
if （ my _node _id =0） then /*发送者 */
start _time =second（ ）
send an m-byte message to node 1
receive an m-byte message from node 1
end_time = second（ ）
total_time = end_time – start_time
communication_time[i] = total_time/2
else if （ my_node_id = 1） then /*接收者 */
receive an m-byte message from node 0
send an m-byte message to node 0
endif
国家高性能计算中心（合肥） 562009-7-24
并行开销的表达式：点到点通信
通信开销 t(m) = t0 + m/ r∞
通信启动时间 t0
渐近 带宽 r∞,传送无限长的消息时的通信速率
半 峰值长度 m1/2,达到一半渐近带宽所要的消息长度
特定性能 π0：表示短消息带宽
t0 = m1/2 / r∞ = 1 /π0
国家高性能计算中心（合肥） 572009-7-24
并行开销的表达式：整体通信
典型的整体通信有：
播送（ Broadcasting）,处理器 0发送 m个字节给所有的 n个处理器
收集（ Gather）,处理 0接收所有 n个处理器发来在消息，所以处理器 0最终接收了 m n个字节；
散射（ Scatter）,处理器 0发送了 m个字节的不同消息给所有
n个处理器，因此处理器 0最终发送了 m n个字节；
全交换（ Total Exchange）,每个处理器均彼此相互发送 m个字节的不同消息给对方，所以总通信量为 mn2个字节；
循环移位（ Circular-shift）,处理器 i发送 m个字节给处理器
i+1,处理器 n-1发送 m个字节给处理器 0，所以通信量为 m n个字节。
国家高性能计算中心（合肥） 582009-7-24
机器的成本、价格与性 /价比
机器的成本与价格
机器的性能 /价格比 Performance/Cost Ratio,系指用单位代价（通常以百万美元表示）所获取的性能（通常以 MIPS或 MFLOPS表示）
利用率（ Utilization）,可达到的速度与峰值速度之比国家高性能计算中心（合肥） 592009-7-24
算法级性能评测
加速比性能定律
并行系统的加速比是指对于一个给定的应用，并行算法（或并行程序）
的执行速度相对于串行算法（或串行程序）的执行速度加快了多少倍。
Amdahl 定律
Gustafson定律
Sun Ni定律
可扩放性评测标准
等效率度量标准
等速度度量标准
平均延迟度量标准国家高性能计算中心（合肥） 602009-7-24
Amdahl 定律
P,处理器数；
W,问题规模（ 计算负载、工作负载，给定问题的总计算量 ）；
Ws,应用程序中的串行分量,f是串行分量比例（ f = Ws/W，
Ws=W1）；
WP,应用程序中可并行化部分,1-f为并行分量比例；
Ws +W p =W；
Ts=T1,串行执行时间,T p,并行执行时间；
S,加速比,E,效率；
出发点：
固定不变的计算负载；
固定的计算负载分布在多个处理器上的，
增加处理器加快执行速度，从而达到了加速的目的。
国家高性能计算中心（合肥） 612009-7-24
Amdahl定律（ cont‘d)
固定负载的加速公式：
W s+ W p可相应地表示为 f+（ 1-f）
p→ ∞时，上式极限为,S= 1 / f
W o为额外开销
pWWs
WpWsS
P /?
)1(11
)1(
pf
p
p
f
f
ff
S
WpWpf
p
W
p
fW
fW
W
W
p
W
W
WW
S
OOOPS
PS
/)1(1)1(
国家高性能计算中心（合肥） 622009-7-24
Amdahl’s law (cont’d)
程序中顺序部分的百分比 f
(c)
0% 1% 2% 3% 4% 100%
加速比
S S
1024
=1024/(1+1023 f )
1024x
91x
48x
31x
24x
1x
W
p
W
p
W
p
W
p
W
p
W
p
W
1
W
1
W
1
W
1
W
1
W
1
工作负载
W
处理器数 P
(a)
1 2 3 4 5 6
T
1
T
1
T
p
T
p
T
p
T
p
T
p
T
p
T
1
T
1
T
1
执行时间
T
处理器数 P
(b)
T
1
1 2 3 4 5 6
国家高性能计算中心（合肥） 632009-7-24
Gustafson定律
出发点：
对于很多大型计算，精度要求很高，即在此类应用中精度是个关键因素，而计算时间是固定不变的。此时为了提高精度，必须加大计算量，相应地亦必须增多处理器数才能维持时间不变；
除非学术研究，在实际应用中没有必要固定工作负载而计算程序运行在不同数目的处理器上，增多处理器必须相应地增大问题规模才有实际意义。
Gustafson加速定律,
并行开销 W o,
PS
S
S
S
WW
p W pW
pWppW
p W pWS
/'
) p - f ( p -- p ) f ( p - f ) p ( f S ' 111
WW
fpf
WWW
pWWS
OOPS
PS
/1
1'
国家高性能计算中心（合肥） 642009-7-24
Gustafson定律（ cont‘d)
程序中顺序部分的百分比 f
(c)
S '
1024
=1024-1023 f
0% 1% 2% 3% 4%
1024x
1014x 1004x 993x
983x
加速比
S
'
处理器数 P
工作负载
W
(a)
W
1
W
1
W
1
W
1
W
1
W
1
W
p
W
p
W
p
W
p
W
p
W
p
1 2 3 4 5 6
T
p
T
1
T
1
T
1
T
1
T
1
T
1
执行时间
T
处理器数 P
(b)
1 2 3 4 5 6
T
p
T
p
T
p
T
p
T
p
国家高性能计算中心（合肥） 652009-7-24
Sun 和 Ni定律
基本思想：
只要存储空间许可，应尽量增大问题规模以产生更好和更精确的解
（此时可能使执行时间略有增加）。
假定在单节点上使用了全部存储容量 M并在相应于 W的时间内求解之，
此时工作负载 W= fW + （ 1-f） W。
在 p 个节点的并行系统上，能够求解较大规模的问题是因为存储容量可增加到 pM。 令因子 G（ p） 反应存储容量增加到 p倍时并行工作负载的增加量，所以扩大后的工作负载 W = fW + （ 1-f） G（ p） W。
存储受限的加速公式,
并行开销 W o:
pWpGffW
WpGffWS
/1
1''
ppGff
pGff
/1
1
WWppGff
pGff
WpWpGffW
pWGffWS
OO //1
1
/1
1'
国家高性能计算中心（合肥） 662009-7-24
Sun 和 Ni定律 (cont’d)
G（ p） =1时就是 Amdahl加速定律；
G（ p） =p 变为 f + p（ 1-f）,就是 Gustafson加速定律
G（ p） >p时，相应于计算机负载比存储要求增加得快，
此时 Sun和 N i 加速均比 Amdahl 加速和 Gustafson 加速为高。
T
1
T
p
执行时间
T
处理器数 P
(b)
T
1
T
1
T
1
T
1
T
1 T
p
T
p
T
p
T
pT
p
处理器数 P
工作负载
W
(a)
W
1
W
p
W
p
W
p
W
p
W
p
W
p
W
1
W
1
W
1
W
1
W
1
1 2 3 4 5 6 1 2 3 4 5 6
国家高性能计算中心（合肥） 672009-7-24
加速比讨论
参考的加速经验公式,p/log p≤S≤P
线性加速比：很少通信开销的矩阵相加、内积运算等
p/log p的加速 比：分治类的应用问题
通信密集类的应用问题,S = 1 / C （ p ）
超线性加速
绝对加速：最佳并行算法与串行算法
相对加速：同一算法在单机和并行机的运行时间国家高性能计算中心（合肥） 682009-7-24
可扩放性评测标准
并行计算的可扩放性（ Scalability） 也是主要性能指标
可扩放性最简朴的含意是在确定的应用背景下，计算机系统（或算法或程序等）性能随处理器数的增加而按比例提高的能力
影响加速比的因素：处理器数与问题规模
求解问题中的串行分量
并行处理所引起的额外开销（通信、等待、竞争、冗余操作和同步等）
加大的处理器数超过了算法中的并发程度
增加问题的规模有利于提高加速的因素：
较大的问题规模可提供较高的并发度；
额外开销的增加可能慢于有效计算的增加；
算法中的串行分量比例不是固定不变的（串行部分所占的比例随着问题规模的增大而缩小）。
增加处理器数会增大额外开销和降低处理器利用率，所以对于一个特定的并行系统（算法或程序），它们能否有效利用不断增加的处理器的能力应是受限的，而度量这种能力就是可扩放性这一指标。
国家高性能计算中心（合肥） 692009-7-24
可扩放性评测标准（ cont‘d)
可扩放性,调整什么和按什么比例调整
并行计算要调整的是处理数 p和问题规模 W，
两者可按不同比例进行调整，此比例关系（可能是线性的，多项式的或指数的等）就反映了可扩放的程度。
并行算法和体系结构
可扩放性研究的主要目的：
确定解决某类问题用何种并行算法与何种并行体系结构的组合，
可以有效地利用大量的处理器；
对于运行于某种体系结构的并行机上的某种算法当移植到大规模处理机上后运行的性能；
对固定的问题规模，确定在某类并行机上最优的处理器数与可获得的最大的加速比；
用于指导改进并行算法和并行机体系结构，以使并行算法尽可能地充分利用可扩充的大量处理器
目前无一个公认的、标准的和被普遍接受的严格定义和评判它的标准国家高性能计算中心（合肥） 702009-7-24
等效率度量标准
令 tie 和 t io 分别是并行系统上第 i个处理器的有用计算时间和额外开销时间（包括通信、同步和空闲等待时间等）
T p 是 p个处理器系统上并行算法的运行时间，对于任意 i显然有 T p = tie +t io,且 T e+ T o= pT p
问题的规模 W为最佳串行算法所完成的计算量 W=Te
如果问题规模 W 保持不变，处理器数 p增加，开销 To增大，
效率 E下降。为了维持一定的效率（介于 0与 1之间），当处理数 p增大时，需要相应地增大问题规模 W的值。由此定义函数 f E（ p） 为问题规模 W随处理器数 p变化的函数，为等效率函数（ ISO-efficiency Function）（ Kumar1987）
1
0
p
i
i
ee TstT?
1
0
p
i
i
oo tT
W
T
p
T
T
p
p
TT
T
T
TS
o
e
ooe
e
p
e
11 WTTTP
SE
o
e
o?
1
1
1
1
国家高性能计算中心（合肥） 712009-7-24
等效率度量标准（ cont‘d)
曲线 1表示算法具有很好的扩放性；曲线 2表示算法是可扩放的；曲线 3表示算法是不可扩放的。
优点：简单可定量计算的、少量的参数计算等效率函数
缺点：如果 To无法计算出（在共享存储并行机中）
处理器数 P
工作负载
W
曲线 3
曲线 2
曲线 1
国家高性能计算中心（合肥） 722009-7-24
等速度度量标准
p 表示处理器个数,W表示要求解问题的工作量或称问题规模
（在此可指浮点操作个数）,T为并行执行时间，定义并行计算的速度 V为工作量 W除以并行时间 T
p个处理器的并行系统的平均速度定义为并行速度 V除以处理器个数 p：
W是使用 p个处理器时算法的工作量，令 W’表示当处理数从 p增大到 p’时，为了保持整个系统的平均速度不变所需执行的工作量，则可得到处理器数从 p到 p’时平均速度可扩放度量标准公式
pT
W
p
VV
'
'
'/'
/)',(
pW
Wp
pW
pWpp
国家高性能计算中心（合肥） 732009-7-24
等速度度量标准（ cont’d）
问题规模处理器数执行时间处理器数处理器数平均速度处理器数执行时间
优点：直观地使用易测量的机器性能速度指标来度量
缺点：某些非浮点运算可能造成性能的变化国家高性能计算中心（合肥） 742009-7-24
平均延迟度量标准
Ti为 Pi的执行时间，包括包括延迟 Li,Pi的总延迟时间为,L i+启动时间 +停止时间,。定义系统平均延迟时间为
pTpara =To+ Ts
在 p个处理器上求解工作量为 W问题的平均延迟
在 p’个处理器上求解工作量为 W’问题的平均延迟当处理器数由 p变到 p’,而推持并行执行效率不变，则定义平均延迟可扩放性度量标准为
pLTTpWL p
i
iip a r a?
1
,
pWLpT o,?
pTTpWL s e qp a r a,
',',',,pWL pWLppE
pWL,
',' pWL
国家高性能计算中心（合肥） 752009-7-24
平均延迟度量标准（ Cont’d)
处理器数 P
T
1
T
2
T
3
T
4
T
5
T
6
T
7
T
8
T
5
= T
para
执行时间
T
p
a
r
a
5
4
3
2
1
P
1
P
2
P
3
P
4
P
5
P
6
P
7
P
8
开销延迟 L
i
启动前与结束后空 闲时间 运行时间 T
i
优点：平均延迟能在更低层次上衡量机器的性能
缺点：需要特定的软硬件才能获得平均延迟
