第六章 并行处理机和相联处理机
6.1 并行处理机原理
6.1.1 并行处理机构形与特点
1.并行处理机的基本构形
分类及依据依据,存储器的组成方式分类,分布式 存储器并行处理机集中式 存储器并行处理机
1.并行处理机的基本构形
分布式存储器并行处理机组成,阵列处理单元 PE0- PEN-1
局部存储器,PEM0- PEMN-1
控制部件 CU (Control Unit)
主存储器 CUM
管理计算机 SC(Supervisory Computer)
互连网络 ICN (Interconnection Network)
外部设备与接口实例,ILLIAC Ⅳ,MPP,DAP
1.并行处理机的基本构形
集中式共享存储器并行处理机组成,阵列处理单元 PE0- PEN-1
多存储体存储器,MM0- MMK-1
控制部件 CU (Control Unit)
管理计算机 SC (Supervisory Computer)
互连网络 ICN (Interconnection Network)
外部设备与接口实例,BSP
2.并行处理机的特点
资源重复的 SIMD型计算机
互连网络
结构灵活,性能高于流水线处理机
与并行算法密切相关
专用性的特殊要求及结构向量处理与标量处理的关系
6.1.2 并行处理机的算法
1.ILLIAC Ⅳ 的处理单元阵列结构
阵列的构成
PU的组成、功能及操作特点
PU之间的连接通路结构,闭合螺线 (Closed Spiral)结构特点,PU间的最短路径不超过 7步一般情况,当 N=NN?时,任意两个处理单元之间的最短距离不会超过 N?-1步
PU0
PU9PU8 PU15
PU7
PU63PU57PU56
PU1
PU55PU49PU48
PU56 PU57 PU63
PU63
PU7
PU47
PU55
PU8
PU16
PU56
PU0
PU0 PU1 PU7
6.1.2 并行处理机的算法
2.并行处理机的算法
有限差分问题
矩阵加
矩阵乘
累加和有限差分问题描述与解决矩阵加矩阵乘
A0
A1
A2
A3
A4
A5
A6
A7
0
0,1
1,2
2,3
3,4
4,5
5,6
6,7
0
0,1
0~2
0~3
1~4
2~5
3~6
4~7
0
0,1
0~2
0~3
0~4
0~5
0~6
0~7
PE0
PE1
PE2
PE3
PE4
PE5
PE6
PE7
循环 k=0 k=1 k=2
累加和
6.1.3 SIMD计算机的互连网络
1,互连网络的设计目标及互连函数
互连网络的必要性
SIMD互连网络的设计目标结构不过分复杂互连灵活单元之间的信息传输路径要尽可能短
互连网络的主要设计问题操作方式 控制策略 交换方式 拓扑结构与分类
1,互连网络的设计目标及互连函数
互连函数定义,对于互连网络所有的入端 0,1,……,N-1,
同时存在入端 j 连至出端 f(j) 的函数对应关系,我们称这种对应关系为互连网络互连函数,
实际应用方法二进制编码
2,基本的单级互连网络
立方体单级互连网络（ Cube）
三维情况一般情况（ n维）
超级立方体 （ Hyper Cube）
特点,可逆性 连通性 容错性强
PM2I 单级互连网络定义,PM2+i （ j） =j+2i mod N
PM2-i （ j） =j-2i mod N
N=8时的 5个互连函数
PM2I 单级网络的最大距离?n/2?
2,基本的单级互连网络
混洗交换单级网络（ Shuffle-Exchange）
互连函数的构成：全混洗 交换全混洗的定义,
Shuffle（ Pn-1 Pn-2… P1 P0 )= Pn-2… P1 P0 Pn-1
函数的不可逆性循环性
混洗交换单级网络（ Shuffle-Exchange）
Cube0交换函数的引入,解决两个全,0”
和 全,1” 的特殊结点与其它结点的 任何连接最远距离,全,0” 结点和全,1” 结点的距离 2n-1
其中混洗 n-1次，交换 n次。
6.1.4 并行存储器的无冲突访问
1,一维数组的无冲突访问
一维数组的访问分析
基本要求,多分体存储器的体数 m 应取为为质数,使变址跳距 (错开距离）与 m 互质,则可避免存储器的访问冲突
2,二维数组的无冲突访问
二维数组的访问分析
访问冲突的解决方法
2,二维数组的无冲突访问
访问冲突的解决方法错位存放方法分体数量大于一次访问的向量元素个数二维数组无冲突访问的充要条件互连网络的作用之一：恢复处理的顺序
3,多维数组的无冲突访问
处理方法
BSC的实现方法
6.2 实际的并行处理机系统
6.2.1 ILLIAC Ⅳ 阵列处理机
性能指标,2亿次运算 /秒
组成阵列处理单元,PE PEM 64个运算类别桶状开关 (Barrel Switch)
CU
SC B6500:前端机磁盘
I/O 开关
6.2 实际的并行处理机系统
6.2.2 BSC科学处理机
速度,5000万次浮点运算 /秒 (50MFLOPS)
组成并行处理单元,16个共享多体存储器,17个模块对准网络,2个
流水线结构结构形式,5级流水线结构特点,资源重复与时间重叠相结合
BSC科学处理机组成
6.2 实际的并行处理机系统
6.2.3 位平面阵列 处理机
6.2.4 CM连接机
6.3 相联处理机
6.1 并行处理机原理
6.1.1 并行处理机构形与特点
1.并行处理机的基本构形
分类及依据依据,存储器的组成方式分类,分布式 存储器并行处理机集中式 存储器并行处理机
1.并行处理机的基本构形
分布式存储器并行处理机组成,阵列处理单元 PE0- PEN-1
局部存储器,PEM0- PEMN-1
控制部件 CU (Control Unit)
主存储器 CUM
管理计算机 SC(Supervisory Computer)
互连网络 ICN (Interconnection Network)
外部设备与接口实例,ILLIAC Ⅳ,MPP,DAP
1.并行处理机的基本构形
集中式共享存储器并行处理机组成,阵列处理单元 PE0- PEN-1
多存储体存储器,MM0- MMK-1
控制部件 CU (Control Unit)
管理计算机 SC (Supervisory Computer)
互连网络 ICN (Interconnection Network)
外部设备与接口实例,BSP
2.并行处理机的特点
资源重复的 SIMD型计算机
互连网络
结构灵活,性能高于流水线处理机
与并行算法密切相关
专用性的特殊要求及结构向量处理与标量处理的关系
6.1.2 并行处理机的算法
1.ILLIAC Ⅳ 的处理单元阵列结构
阵列的构成
PU的组成、功能及操作特点
PU之间的连接通路结构,闭合螺线 (Closed Spiral)结构特点,PU间的最短路径不超过 7步一般情况,当 N=NN?时,任意两个处理单元之间的最短距离不会超过 N?-1步
PU0
PU9PU8 PU15
PU7
PU63PU57PU56
PU1
PU55PU49PU48
PU56 PU57 PU63
PU63
PU7
PU47
PU55
PU8
PU16
PU56
PU0
PU0 PU1 PU7
6.1.2 并行处理机的算法
2.并行处理机的算法
有限差分问题
矩阵加
矩阵乘
累加和有限差分问题描述与解决矩阵加矩阵乘
A0
A1
A2
A3
A4
A5
A6
A7
0
0,1
1,2
2,3
3,4
4,5
5,6
6,7
0
0,1
0~2
0~3
1~4
2~5
3~6
4~7
0
0,1
0~2
0~3
0~4
0~5
0~6
0~7
PE0
PE1
PE2
PE3
PE4
PE5
PE6
PE7
循环 k=0 k=1 k=2
累加和
6.1.3 SIMD计算机的互连网络
1,互连网络的设计目标及互连函数
互连网络的必要性
SIMD互连网络的设计目标结构不过分复杂互连灵活单元之间的信息传输路径要尽可能短
互连网络的主要设计问题操作方式 控制策略 交换方式 拓扑结构与分类
1,互连网络的设计目标及互连函数
互连函数定义,对于互连网络所有的入端 0,1,……,N-1,
同时存在入端 j 连至出端 f(j) 的函数对应关系,我们称这种对应关系为互连网络互连函数,
实际应用方法二进制编码
2,基本的单级互连网络
立方体单级互连网络（ Cube）
三维情况一般情况（ n维）
超级立方体 （ Hyper Cube）
特点,可逆性 连通性 容错性强
PM2I 单级互连网络定义,PM2+i （ j） =j+2i mod N
PM2-i （ j） =j-2i mod N
N=8时的 5个互连函数
PM2I 单级网络的最大距离?n/2?
2,基本的单级互连网络
混洗交换单级网络（ Shuffle-Exchange）
互连函数的构成：全混洗 交换全混洗的定义,
Shuffle（ Pn-1 Pn-2… P1 P0 )= Pn-2… P1 P0 Pn-1
函数的不可逆性循环性
混洗交换单级网络（ Shuffle-Exchange）
Cube0交换函数的引入,解决两个全,0”
和 全,1” 的特殊结点与其它结点的 任何连接最远距离,全,0” 结点和全,1” 结点的距离 2n-1
其中混洗 n-1次，交换 n次。
6.1.4 并行存储器的无冲突访问
1,一维数组的无冲突访问
一维数组的访问分析
基本要求,多分体存储器的体数 m 应取为为质数,使变址跳距 (错开距离）与 m 互质,则可避免存储器的访问冲突
2,二维数组的无冲突访问
二维数组的访问分析
访问冲突的解决方法
2,二维数组的无冲突访问
访问冲突的解决方法错位存放方法分体数量大于一次访问的向量元素个数二维数组无冲突访问的充要条件互连网络的作用之一：恢复处理的顺序
3,多维数组的无冲突访问
处理方法
BSC的实现方法
6.2 实际的并行处理机系统
6.2.1 ILLIAC Ⅳ 阵列处理机
性能指标,2亿次运算 /秒
组成阵列处理单元,PE PEM 64个运算类别桶状开关 (Barrel Switch)
CU
SC B6500:前端机磁盘
I/O 开关
6.2 实际的并行处理机系统
6.2.2 BSC科学处理机
速度,5000万次浮点运算 /秒 (50MFLOPS)
组成并行处理单元,16个共享多体存储器,17个模块对准网络,2个
流水线结构结构形式,5级流水线结构特点,资源重复与时间重叠相结合
BSC科学处理机组成
6.2 实际的并行处理机系统
6.2.3 位平面阵列 处理机
6.2.4 CM连接机
6.3 相联处理机
