静态互连网络
(5)金字塔连接(Pyramid)
(6)超立方连接HC (Hypercube Connected) 3－立方， 4－立方
(7)立方环连接CCC (Cube Connected-Cycles) (8)洗牌交换连接SE(Shuffle Exchange) (9)蝶形连接(Butterfly Connected)
0000
0001
0011
0010
0110 0100 0101
0111 1100
1110 1101
1111
0010 0000 0001

《并行算法》 2 / Ch1
1.1 并行计算机的体系结构: 并行计算机分类

Flynn分类（1966年）
(1)单指令流单数据流机SISD，即传统的单处理机 (2)单指令流多数据流机SIMD
(3)多指令流单数据流机MISD，实际中不存在的机器
(4)多指令流多数据流机MIMD

并行机的结构模型－实际的机器体系结构
(3)树形连接TC(Tree Connected) 二叉树， 胖树
2019/2/16
《并行算法》 10 / Ch1
1.1 并行计算机的体系结构: 互连方式

静态互连网络
(4)树网连接MT(Mesh of tree)
2019/2/16
《并行算法》 11 / Ch1
1.1 并行计算机的体系结构: 互连方式
2019/2/16
《并行算法》 12 / Ch1
1.1 并行计算机的体系结构: 互连方式

静态互连网络: 嵌入 将网络中的各节点映射到另一个网络中去 用膨胀（Dilation）系数来描述嵌入的质量，它
是指被嵌入网络中的一条链路在所要嵌入的网络 中对应所需的最大链路数
如果该系数为1，则称为完美嵌入。
SAN/LAN (g) DSM-Cluster
SM SMP
LM MPP
DSM
…
WAN
MPP
(h) Grid (Cluster of Clusters)
2019/2/16
《并行算法》 8 / Ch1
1.1 并行计算机的体系结构: 互连方式

静态互连网络(固定连接)
connected graph vertices = processing nodes edges = communication links
Parallel Algorithms
Chapter 1
Foundation of Parallel Algorithms
Spring, 2018
2019/2/16
《并行算法》 1 / Ch1
主要内容
1.1 并行计算机体系结构 并行计算机的分类 并行计算机的互连方式 1.2 并行计算模型 PRAM模型 异步APRAM模型 BSP模型 LogP模型 1.3 并行算法的一般概念 并行算法的定义和分类 相关性与可并行化 并行算法的表示 并行算法的复杂度 并行算法的WT表示 加速比性能定律 并行算法的同步和通讯 2019/2/16
(1)一维线性连接LA(1-D Linear Array)—一维阵列 不带环绕的1-D LA，带环绕的1-D LA (2)网孔连接MC (Mesh Connected)—二维阵列
不带环绕的MC，带环绕的MC
2019/2/16
《并行算法》 9 / Ch1
1.1 并行计算机的体系结构: 互连方式

静态互连网络
－COW (Cluster of Workstation,
工作站机群)
－DSM (Distributed Shared Memory, 分布共享存储多处理机) 注：SIMD是专用并行机，后5种属于MIMD并行机。
2019/2/16 《并行算法》 并行计算机分类
SISD computer -Von Neumann's model
SIMD computer
2019/2/16
《并行算法》 4 / Ch1
1.1 并行计算机的体系结构: 并行计算机分类
Symmetric multiprocessor – MIMD-SM
Massively parallel processor – MIMD-DM
(c) MPP, 物理/逻辑上多地址空间
2019/2/16
(e) Cluster/COW, 物理/逻辑上多地址空间
《并行算法》 7 / Ch1
1.1 并行计算机的体系结构: 并行计算机分类
结构模型－物理机模型
SM
SMP
SM
SMP
SM
DSM
MPP
DSM
MPP
DSM
…
SMP
…
MPP
SAN/LAN (f) SMP-Cluster
环网可完美嵌入到2-D环绕网中 超立方网可完美嵌入到2－D环绕网中
2019/2/16
《并行算法》 13 / Ch1
1.1 并行计算机的体系结构: 互连方式

静态互连网络: 嵌入
1000 1001 1011 1010
1100
1101
1111
1110
0100
0101
0111
0110
Ring onto 2-D torus Hypercube onto 2-D torus
2019/2/16
《并行算法》 5 / Ch1
1.1 并行计算机的体系结构: 并行计算机分类
Cluster of workstations – MIMD-DM
2019/2/16
《并行算法》 6 / Ch1
1.1 并行计算机的体系结构: 并行计算机分类
结构模型－物理机模型
VP VP
虚拟分布共享存储(DSM) P/C P/C
－SIMD (Single Instruction Multiple Data, 单指令流多数据流机) －PVP (Parallel Vector Processor, －SMP (Symmetric Multiprocessor, 并行向量机) 对称多处理机)
－MPP (Massively Parallel Processor, 大规模并行处理机)
…
VP
…
P/C
LM P/C
LM P/C
LM
交叉开关 SM (a) PVP
总线或交叉开关 SM (b) SMP, 物理上单一地址空间
…
P/C
定制网络 (d) DSM (MPP/Cluster), 逻辑上单一地址空间
LM P/C
LM P/C
LM
LM P/C
LM P/C
LM
…
P/C
…
P/C
定制网络
定制/标准网络