1
并行处理与体系结构
2
第一章 并行计算机模型
? ?1 计算技术的现状
??2 多处理机和多计算机
? ?3 多向量机和 SIMD计算机
? ?4 并行计算机的抽象模型
? ?5 可扩展的范围和设计
3
?2 多处理机和多计算机
?一、共享存储型多处理机
?1,UMA模型
?UMA --Uniform Memory Access
?结构和特点,
4
5
? 紧耦合系统 (tightly coupled
system)
? 多处理机由于高度资源共享
? 系统的互连采用总线、交叉开关、或多
级网络形式
?对称 (symmetric)多处理机
?当所有处理机都能同样访问所有外
围设备时。
6
? 例 Fortran程序可在单处理机上顺序执
行,分析 CPU的运行时间,假设条件,
? 所有数组 A(I),B(I),C(I)都有 N个
元素；
? 分析：求和 Fortran程序
7
? L1,Do 10 I＝ 1,N
? L2,A(I)＝ B(I)+C(I)
? L3:10 Continue
? L4,SUM＝ 0
? L5,Do 20 J＝ 1,N
? L6,SUM＝ SUM+A(J)
? L7:20 Continue
? 假定取指令和加载数据的开销可以忽略不
计；
? 所有数组已经装人主存储器，并且短程序段
已经装入高速缓冲存储器。
? 忽略总线争用或存储器存取冲突问题。
8
?再假设,
? 执行代码行 L2,L4和 L6，每行要用一个
机器周期。
? 执行程序控制语句 L1,L3,L5和 L7所需
的时间可以忽略。
? 假定经过共享存储器的处理机之间的每
次通信操作需要 k个周期。
?结论,CPU用 2N个周期
9
串行程序并行化
?在 M— 处理机系统上执行程序
?将循环操作 划分 成 M段，每段有
L＝ N／ M个元素。
?假设经过共享存储器的处理机
之间的每次通信操作需要,
? k个周期 。
10
?Doall表示所有 M段在 M台处理机上
并行执行
? Doall k＝ 1,M
? Do 10 I＝ L(k-1)+1,kL。
? A(I)＝ B(I)+C(I)
? 10 Continue
? SUM(k)＝ 0
? Do 20 J＝ 1,L
? SUM(k) = SUM(k) + A(L(k-1)+ J)
? 20 Continue
? ENDall
11
? 分析,
? 循环 1是 L个周期；循环 2是 L个周期
? 总时间,
? 2L+ h(k+1)=2N/M+(k+1) log2M
12
2,NUAM模型
13
? 3.COMA模型
? 概念：只使用高速缓存的多处理机
14
?实现的机器,
?瑞典计算机科学研究所的数据扩
散机 (DDM,Hagersten等,1990)
?KendallSquareReserch公司的
KSR— 1机器 (Burkhart等,1992)。
15
?特点,
? COMA模型是 NUMA机的一种特例，将 NUMA
中分布主存储器换成了高速缓存；
? 全部高速缓冲存储器组成了全局地址空
间；
? 远程高速缓存访问则借助于分布高速缓
存目录进行，分级目录往往可用来寻找
高速缓存块的副本，这与所用的互连网
络有关；
? 数据的初始位置并不重要，因为它最终
将会迁移到要用到它的地方。
16
?模型的演变,
? 例如，高速缓存一致性非均匀存储存取
(CC— NUMA)模型。
?可以用分布共享存储器和高速缓存目
录来描述。
?CC— NUMA模型的实例
? 斯坦福大学的 Dash系统 (Lenosh等,1990)
和麻省理工学院的 Alewife系统 (Agarwal
等,1990)；
? 这些将在后面讨论。
17
4.典型的多处理机
18
? 二、分布存储型多计算机系统
? 1.概念
? 由多个计算机结点，通过消息传递网络
互相连接而成，每个结点是一台由处理
机、本地存储器和有时接有磁盘或 I／ 0
外围设备组成的自治的计算机。
19
20
? 2.特点,
? 消息传递网络提供结点之间的点到点 静态连接
? 传统的多计算机已被称为近地存储访问 (NORMA)
机
? 所有本地存储器是私用的，而且只有本地处
理机才能访问；
? 私用存储器逐渐在分布共享存储器的多计算机
中将被逐步取消。
21
? 3,多计算机的换代
? 现代多计算机用硬件寻径器来传送信息；
? 计算机结点与寻径器相连，边界上的寻
径器与 I／ O和外围设备连接；
? 任何两结点间的消息传递会涉及一连串
的寻径器和通道。
? 在异构多计算机系统中，可以有多种类
型的结点，结点间的通信是通过可兼容
的数据表示和消息传递协议来实现的。
22
? 消息传递型多计算机的发展换代
? 第一代 (1983— 1987)是基于处理机板技术，
采用了超立方体结构和软件控制的消息交换
方法。
? 加州理工学院的 Cosmic和 InteliPSC／ 1是
这一代研制的代表。
? 第二代 (1988— 1992)是用网格连接的系统结
构、硬件消息寻径和中粒度分布计算的软件
环境实现的；
? IntelParagon和 ParsysSuperNodel000可
作为代表性产品。
23
? 现在面临的第三代 (1993— )预期是细粒
度计算机
?麻省理工学院的 J-Machine和加州工
学院的 Mosaic,VLSI片上实现处理机
和通讯工具 。
24
示例,
IBM POWER4体系结构特点
?PowerPC 64位体系结构
?单芯片双处理器,MCM八处理器
?集成多处理器互连接口
?集成 I/O控制器
?集成 L3Cache控制器
?集成存储控制器
25
26
IBM POWER4 (MCM结构 )
27
IBM POWER4 (32CPU)
28
?4.典型多计算机
?多计算机的可编程性取决于,
?高效编译器实用
?高效的分布式操作系统实用
29
30
?总结,
? 本节区分了多处理机和多计算机的主
要差别和分类。
31
?3 多向量机和 SIMD计算机
?一、向量超级计算机
?1.早期的超级计算机可分为,
?流水线向量机；
?SIMD计算机两类。
32
33
? 执行过程,
? 当译出的指令为向量操作；
? 它将被送至向量控制器，控制器将监
督主存储器与向量功能流水线之间的
向量数据流，向量数据流由控制器协
调控制；
? 向量处理机则装有若干条向量功能流
水线。
34
?2.寄存器 — 寄存器的系统结构
? 如 1976年推出的 Cray 1。
35
36
?向量寄存器用来保存向量操作
数、中间和最终的向量结果 ;
?向量功能流水线从向量寄存器
检索操作数，并将结果放入寄
存器。
37
? 3.存储器 — 存储器结构
?这种结构比较早，与寄存器 — 寄存
器结构的区别就在于采用向量流水
部件代替了向量寄存器。
?例如,
38
39
40
二,SIMD超级计算机
41
? 1,SIMD的操作模型
? 可用五元组表示 M＝ <N,C,I,M，
R>
? N为机器的处理单元 (PE)数。
?例如,illiac IV有 64个 PE，而连接机
(ConnectionMachine)CM— 2采用 65
536个 PE。
? C为由控制部件 (CU)直接执行的指令集；
?包括标量和程序流控制指令。
42
? I为由 CU广播至所有 PE进行并行执行的指令
集；
? 它包括算术运算、逻辑运算、数据寻径、
屏蔽以及其它由每个活动的 PE对它的数据
所执行的局部操作。
? M为屏蔽方案集
? 其中每种屏蔽将 PE集划分为允许操作和禁
止操作两种子集。
? R是数据寻径功能集
? 说明互连网络中 PE间通信所需要的各种设
置模式。
43
?示例,
?描述具体的 SIMD机器 MasParMP— 1计
算机的操作特性 --五元组特性,
?MP— 1是一种 SIMD机器，其 PE数 N＝
1024至 16 384。 PE数目与机器配置有
关。
?CU执行标量指令，将译码后的向量指
令播送到 PE阵列，并控制 PE间的通信。
44
? 每个 PE都是基于寄存器的加载／存储
RISC处理机，能执行不同数据量的整数
运算和标准浮点运算。各 PE从 CU接受指
令。
? 屏蔽方案设在每个 PE中，并由 CU连续监
控，它能在运行时动态地使每个 PE处于
置位或复位状态。
? 例如,
? MP— 1有一个 X— Net网格网络和一个全
局多级交叉开关寻径器，以实现 CU— PE
之间,X— Net的 8个近邻之间和全局寻
径器的通信。
45
? 2.SIMD的实施模型
? （ 1）分布式存储器模型
46
? 存储器分布的 SIMD特点,
? SIMD计算机开发的是 PE之间的空间并行性。
? 存储器分布的 SIMD计算机由同一阵列控制
部件控制的 PE阵列组成。
? 程序和数据通过主机装入控制存储器。
? 指令是送到控制部件进行译码。
? 标量操作或控制操作，则将直接由与控制部件
相连的标量处理机执行。
? 向量操作，则将它广播到所有 PE并行地执行。
47
? 划分后的数据集合通过向量数据总线广播到
所有 PE的本地存储器。
? PE通过数据寻径网络互连。数据寻径网络执
行 PE间的通信，如移数、置换和其它寻径操
作。控制部件通过执行程序来控制数据寻径
网络。 PE的同步由控制部件的硬件实现。
? 所有 PE在同一个周期执行同一条指令。
? 可以用屏蔽逻辑来决定任何一个 PE在给定的
指令周期执行或不执行指令。
48
? （ 2） 共享存储器模型
? 是一种 PE使用共享存储器的 SIMD计算机。
PE和存储器之间的通信网络是一个对准
网络，它也受控制部件控制。
49
并行处理与体系结构
2
第一章 并行计算机模型
? ?1 计算技术的现状
??2 多处理机和多计算机
? ?3 多向量机和 SIMD计算机
? ?4 并行计算机的抽象模型
? ?5 可扩展的范围和设计
3
?2 多处理机和多计算机
?一、共享存储型多处理机
?1,UMA模型
?UMA --Uniform Memory Access
?结构和特点,
4
5
? 紧耦合系统 (tightly coupled
system)
? 多处理机由于高度资源共享
? 系统的互连采用总线、交叉开关、或多
级网络形式
?对称 (symmetric)多处理机
?当所有处理机都能同样访问所有外
围设备时。
6
? 例 Fortran程序可在单处理机上顺序执
行,分析 CPU的运行时间,假设条件,
? 所有数组 A(I),B(I),C(I)都有 N个
元素；
? 分析：求和 Fortran程序
7
? L1,Do 10 I＝ 1,N
? L2,A(I)＝ B(I)+C(I)
? L3:10 Continue
? L4,SUM＝ 0
? L5,Do 20 J＝ 1,N
? L6,SUM＝ SUM+A(J)
? L7:20 Continue
? 假定取指令和加载数据的开销可以忽略不
计；
? 所有数组已经装人主存储器，并且短程序段
已经装入高速缓冲存储器。
? 忽略总线争用或存储器存取冲突问题。
8
?再假设,
? 执行代码行 L2,L4和 L6，每行要用一个
机器周期。
? 执行程序控制语句 L1,L3,L5和 L7所需
的时间可以忽略。
? 假定经过共享存储器的处理机之间的每
次通信操作需要 k个周期。
?结论,CPU用 2N个周期
9
串行程序并行化
?在 M— 处理机系统上执行程序
?将循环操作 划分 成 M段，每段有
L＝ N／ M个元素。
?假设经过共享存储器的处理机
之间的每次通信操作需要,
? k个周期 。
10
?Doall表示所有 M段在 M台处理机上
并行执行
? Doall k＝ 1,M
? Do 10 I＝ L(k-1)+1,kL。
? A(I)＝ B(I)+C(I)
? 10 Continue
? SUM(k)＝ 0
? Do 20 J＝ 1,L
? SUM(k) = SUM(k) + A(L(k-1)+ J)
? 20 Continue
? ENDall
11
? 分析,
? 循环 1是 L个周期；循环 2是 L个周期
? 总时间,
? 2L+ h(k+1)=2N/M+(k+1) log2M
12
2,NUAM模型
13
? 3.COMA模型
? 概念：只使用高速缓存的多处理机
14
?实现的机器,
?瑞典计算机科学研究所的数据扩
散机 (DDM,Hagersten等,1990)
?KendallSquareReserch公司的
KSR— 1机器 (Burkhart等,1992)。
15
?特点,
? COMA模型是 NUMA机的一种特例，将 NUMA
中分布主存储器换成了高速缓存；
? 全部高速缓冲存储器组成了全局地址空
间；
? 远程高速缓存访问则借助于分布高速缓
存目录进行，分级目录往往可用来寻找
高速缓存块的副本，这与所用的互连网
络有关；
? 数据的初始位置并不重要，因为它最终
将会迁移到要用到它的地方。
16
?模型的演变,
? 例如，高速缓存一致性非均匀存储存取
(CC— NUMA)模型。
?可以用分布共享存储器和高速缓存目
录来描述。
?CC— NUMA模型的实例
? 斯坦福大学的 Dash系统 (Lenosh等,1990)
和麻省理工学院的 Alewife系统 (Agarwal
等,1990)；
? 这些将在后面讨论。
17
4.典型的多处理机
18
? 二、分布存储型多计算机系统
? 1.概念
? 由多个计算机结点，通过消息传递网络
互相连接而成，每个结点是一台由处理
机、本地存储器和有时接有磁盘或 I／ 0
外围设备组成的自治的计算机。
19
20
? 2.特点,
? 消息传递网络提供结点之间的点到点 静态连接
? 传统的多计算机已被称为近地存储访问 (NORMA)
机
? 所有本地存储器是私用的，而且只有本地处
理机才能访问；
? 私用存储器逐渐在分布共享存储器的多计算机
中将被逐步取消。
21
? 3,多计算机的换代
? 现代多计算机用硬件寻径器来传送信息；
? 计算机结点与寻径器相连，边界上的寻
径器与 I／ O和外围设备连接；
? 任何两结点间的消息传递会涉及一连串
的寻径器和通道。
? 在异构多计算机系统中，可以有多种类
型的结点，结点间的通信是通过可兼容
的数据表示和消息传递协议来实现的。
22
? 消息传递型多计算机的发展换代
? 第一代 (1983— 1987)是基于处理机板技术，
采用了超立方体结构和软件控制的消息交换
方法。
? 加州理工学院的 Cosmic和 InteliPSC／ 1是
这一代研制的代表。
? 第二代 (1988— 1992)是用网格连接的系统结
构、硬件消息寻径和中粒度分布计算的软件
环境实现的；
? IntelParagon和 ParsysSuperNodel000可
作为代表性产品。
23
? 现在面临的第三代 (1993— )预期是细粒
度计算机
?麻省理工学院的 J-Machine和加州工
学院的 Mosaic,VLSI片上实现处理机
和通讯工具 。
24
示例,
IBM POWER4体系结构特点
?PowerPC 64位体系结构
?单芯片双处理器,MCM八处理器
?集成多处理器互连接口
?集成 I/O控制器
?集成 L3Cache控制器
?集成存储控制器
25
26
IBM POWER4 (MCM结构 )
27
IBM POWER4 (32CPU)
28
?4.典型多计算机
?多计算机的可编程性取决于,
?高效编译器实用
?高效的分布式操作系统实用
29
30
?总结,
? 本节区分了多处理机和多计算机的主
要差别和分类。
31
?3 多向量机和 SIMD计算机
?一、向量超级计算机
?1.早期的超级计算机可分为,
?流水线向量机；
?SIMD计算机两类。
32
33
? 执行过程,
? 当译出的指令为向量操作；
? 它将被送至向量控制器，控制器将监
督主存储器与向量功能流水线之间的
向量数据流，向量数据流由控制器协
调控制；
? 向量处理机则装有若干条向量功能流
水线。
34
?2.寄存器 — 寄存器的系统结构
? 如 1976年推出的 Cray 1。
35
36
?向量寄存器用来保存向量操作
数、中间和最终的向量结果 ;
?向量功能流水线从向量寄存器
检索操作数，并将结果放入寄
存器。
37
? 3.存储器 — 存储器结构
?这种结构比较早，与寄存器 — 寄存
器结构的区别就在于采用向量流水
部件代替了向量寄存器。
?例如,
38
39
40
二,SIMD超级计算机
41
? 1,SIMD的操作模型
? 可用五元组表示 M＝ <N,C,I,M，
R>
? N为机器的处理单元 (PE)数。
?例如,illiac IV有 64个 PE，而连接机
(ConnectionMachine)CM— 2采用 65
536个 PE。
? C为由控制部件 (CU)直接执行的指令集；
?包括标量和程序流控制指令。
42
? I为由 CU广播至所有 PE进行并行执行的指令
集；
? 它包括算术运算、逻辑运算、数据寻径、
屏蔽以及其它由每个活动的 PE对它的数据
所执行的局部操作。
? M为屏蔽方案集
? 其中每种屏蔽将 PE集划分为允许操作和禁
止操作两种子集。
? R是数据寻径功能集
? 说明互连网络中 PE间通信所需要的各种设
置模式。
43
?示例,
?描述具体的 SIMD机器 MasParMP— 1计
算机的操作特性 --五元组特性,
?MP— 1是一种 SIMD机器，其 PE数 N＝
1024至 16 384。 PE数目与机器配置有
关。
?CU执行标量指令，将译码后的向量指
令播送到 PE阵列，并控制 PE间的通信。
44
? 每个 PE都是基于寄存器的加载／存储
RISC处理机，能执行不同数据量的整数
运算和标准浮点运算。各 PE从 CU接受指
令。
? 屏蔽方案设在每个 PE中，并由 CU连续监
控，它能在运行时动态地使每个 PE处于
置位或复位状态。
? 例如,
? MP— 1有一个 X— Net网格网络和一个全
局多级交叉开关寻径器，以实现 CU— PE
之间,X— Net的 8个近邻之间和全局寻
径器的通信。
45
? 2.SIMD的实施模型
? （ 1）分布式存储器模型
46
? 存储器分布的 SIMD特点,
? SIMD计算机开发的是 PE之间的空间并行性。
? 存储器分布的 SIMD计算机由同一阵列控制
部件控制的 PE阵列组成。
? 程序和数据通过主机装入控制存储器。
? 指令是送到控制部件进行译码。
? 标量操作或控制操作，则将直接由与控制部件
相连的标量处理机执行。
? 向量操作，则将它广播到所有 PE并行地执行。
47
? 划分后的数据集合通过向量数据总线广播到
所有 PE的本地存储器。
? PE通过数据寻径网络互连。数据寻径网络执
行 PE间的通信，如移数、置换和其它寻径操
作。控制部件通过执行程序来控制数据寻径
网络。 PE的同步由控制部件的硬件实现。
? 所有 PE在同一个周期执行同一条指令。
? 可以用屏蔽逻辑来决定任何一个 PE在给定的
指令周期执行或不执行指令。
48
? （ 2） 共享存储器模型
? 是一种 PE使用共享存储器的 SIMD计算机。
PE和存储器之间的通信网络是一个对准
网络，它也受控制部件控制。
49
