并 行 计 算中国科学技术大学计算机科学与技术系国家高性能计算中心 (合肥 )
2003年 9月第三篇 并行数值算法第八章 基本通讯操作第九章 稠密矩阵运算第十章 线性方程组的求解第十一章 快速傅里叶变换第八章 并行数值算法
8.0 预备知识
8.1 选路方法与开关技术
8.2 单一信包一到一传输
8.3 一到多播送
8.4 多到多播送国家高性能计算中心（合肥） 42009-7-24
预备知识
选路 (Routing)
又称为选径或路由。产生消息从发源地到目的地所取的路径,要求具有较低通讯延迟、无死锁和容错能力。
应用于网络或并行机上的信息交换。
消息、信包、片
消息 (Message)：是在多计算机系统的处理接点之间传递包含数据和同步消息的信息包。它是一种逻辑单位，可由任意数量的包构成。
包 (Packet)：包的长度随协议不同而不同，它是信息传送的最小单位,64-512位。
片 (Flit)：片的长度固定，一般为 8位。
国家高性能计算中心（合肥） 52009-7-24
预备知识
消息、信包、片 的相互关系包消息包 据 片头片 尾片…… 顺序号数片 F F F F F F F F
国家高性能计算中心（合肥） 62009-7-24
预备知识? 一些术语
信道带宽 b：每个信道有 w位宽和信号传输率 f = 1/t (t
是时钟周期 ),b = wf bits/sec
节点和开关的度：与节点和开关相连的信道数目
路径：信包在网络中走过的开关和链路 (link)序列
路由长度或距离：路由路径中包括的链路 (link)数目
信包传输性能参数
启动时间 ts(startup time)：准备包头信息等
节点延迟时间 th(per-hop time)：包头穿越相邻节点的时间
字传输时间 tw(transfer time)：传输每个字的时间
链路数 l,信包大小 m
国家高性能计算中心（合肥） 72009-7-24
预备知识
选路算法的三种机制
基于算术的,开关中具有简单的算术运算功能，如维序选路；
基于源地址的,在源点时就将沿路径的各个开关的输出端口地址 p0,p1,…,pn包在信包的头部，每个开关只是对信包头的输出端口地址进行剥离；
基于查表的,开关中含有一个选路表，对信包头中的选路域查出输出端口地址。
国家高性能计算中心（合肥） 82009-7-24
预备知识
选路方式
多到多（会议）
）一到所有（广播、组播一到多（多播）
多到一（集中）
目的地；每条信包有且仅有一个发送一条信包，每个处理器开始时最多一到一（置换）
一到一（单播）
事先算好传输路径脱机没有事先计算好的路径联机网络信包可在任意时刻到达动态息都已到达网络在选路开始时所有的信静态用交换机线路
）虫孔（
）存储－转发（
信包
:
:)(
:)(
:
:
:
o f f l i n e
o n l i n e
W o r m h o l e
F o r w a r dandS t o r e
第八章 并行数值算法
8.0 预备知识
8.1 选路方法与开关技术
8.2 单一信包一到一传输
8.3 一到多播送
8.4 多到多播送
8.1 选路方法与开关技术
8.1.1 选路方法
8.1.2 开关技术国家高性能计算中心（合肥） 112009-7-24
选路方法
分类
最短路径 /非最短路径 (贪心选路 /随机选路 )，
如维序选路是贪心的，二阶段维序选路是随机的
确定选路 /自适应选路 (寻径确定 /寻径视网络状况 )
维序选路 (Dimension-Ordered Routing)：
一种确定的最短路径选路
二维网孔中的维序选路,X-Y选路
超立方中的维序选路,E-立方选路国家高性能计算中心（合肥） 122009-7-24
选路方法
X-Y选路算法
算法 8.1：二维网孔上的 X-Y选路算法
begin
step1,沿 X方向将信包送至目的地处理器所在的列
step2,沿 Y方向将信包送至目的地处理器所在的行
end
国家高性能计算中心（合肥） 132009-7-24
选路方法
例 8.1 (P186)
图8.1
0,7 1,7 2,7 3,7 4,7 5,7 6,7 7,7
0,6 1,6 2,6 3,6 4,6 5,6 6,6 7,6
1,50,5 2,5 3,5 4,5 5,5 6,5 7,5
0,4 1,4 2,4 3,4 7,44,4 6,45,4
6,31,3 2,3 3,3 4,3 5,30,3 7,3
0,2 1,2 2,2 3,2 7,25,2 6,24,2
2,11,10,1 3,1 4,1 5,1 6,1 7,1
0,0 1,0 7,03,0 4,0 5,0 6,02,0
x
y
i,j
E
S
W
N
源; 目的 对,(2,1;7,6)
(0,7;4,2)
(5,4;2,0)
(6,3;1,5)
4( )
国家高性能计算中心（合肥） 142009-7-24
选路方法
E-立方选路算法
路由计算,sn-1sn-2… s1s0(源地址 )
异或 dn-1dn-2… d1d0(目的地址 )
rn-1 rn-2 … r1 r0 (路由值 )
路由过程：
sn-1sn-2… s1s0? sn-1sn-2… s1s0 r0?
sn-1sn-2… s1s0 r1?…
算法 8.2,超立方网络上的 E-立方选路算法 (P186)
国家高性能计算中心（合肥） 152009-7-24
选路方法
例 8.2 (P187)
0110(S)
1101(D)
1011(R)
dim2
dim3
dim1
dim4
源,S=0110
目的,D=1101
路径：
0110 0111 0101 1101
11010101
0110 11111110
0000
1100
10011000
0100
0111
0001
0010
0011
1010
1011
图8,2
8.1 选路方法与开关技术
8.1.1 选路方法
8.1.2 开关技术国家高性能计算中心（合肥） 172009-7-24
开关技术
存储转发 (Store-and-Forward)选路
消息被分成基本的传输单位 ----信包 (Packet),每个信包都含有寻径信息；
当一个信包到达中间节点 A时,A把整个信包放入其通信缓冲器中，然后在选路算法的控制下选择下一个相邻节点 B，当从 A到 B的通道空闲并且 B的通信缓冲器可用时，把信包从 A发向 B；
信包的传输时间,tcomm (SF) = ts + (mtw + th)l=O(ml)
缺点：
每个结点必须对整个消息和信包进行缓冲，缓冲器较大；
网络时延与发送消息所经历的节点数成正比国家高性能计算中心（合肥） 182009-7-24
开关技术
切通 (Cut Through)选路
在传递一个消息之前，就为它建立一条从源结点到目的结点的物理通道。在传递的全部过程中，线路的每一段都被占用，当消息的尾部经过网络后，整条物理链路才被废弃。
传输时间,tcomm (CT) = ts + mtw + lth = O(m+l)
缺点：
物理通道非共享
传输过程中物理通道一直被占用国家高性能计算中心（合肥） 192009-7-24
开关技术
虫孔 (Wormhole)选路
Dally于 1986年提出，利用了前二种方法的优点，减少了缓冲区，提高了物理通道的利用。
首先把一个消息分成许多很小的片，消息的 头片 包含了这个消息的所有寻径信息。 尾片 是一个其最后包含了消息结束符的片。中间的片均为 数据片 ；
片是最小信息单位。每个结点上只需要缓冲一个片就能满足要求；
用一个头片直接牵引一条从输入链路到输出链路的路径的方法来进行操作。每个消息中的片以流水的方式在网络中向前,蠕动,。每个片相当于 Worm的一个节，
,蠕动,以节为单位顺序地向前爬行。当消息的尾片向前,蠕动,一步后，它刚才所占用的结点就被放弃了。
国家高性能计算中心（合肥） 202009-7-24
开关技术
虫孔 (Wormhole)选路优点：
(1)每个结点的缓冲器的需求量小,易于用 VLSI实现；
(2)较低的网络传输延迟 。存储转发传输延迟基本上正比于消息在网络中传输的距离 ; Wormhole与线路开关的网络传输延迟正比于消息包的长度，传输距离对它的影响很小（消息包较长时的情况）；
(3)通道共享性好、利用率高 ；
(4)易于实现 Multicast和 Broadcast。
国家高性能计算中心（合肥） 212009-7-24
开关技术
几种开关技术的时空图
l
t (SF)comm
1
P
2
P
3
P
4
P
mtw
头 信包数据
T
(a)
l
1
P
2
P
3
P
4
P
mtw
T
(b)
图8,4
t (CT)comm
第八章 并行数值算法
8.0 预备知识
8.1 选路方法与开关技术
8.2 单一信包一到一传输
8.3 一到多播送
8.4 多到多播送国家高性能计算中心（合肥） 232009-7-24
单一信包一到一传输
距离 l的计算,对于 p个处理器
一维环形：
带环绕 Mesh( )：
超立方：
tcomm(SF)的计算 (可由 (8.1b)式得到 )
一维环形：
带环绕 Mesh：
超立方：
tcomm(CT)的计算 (可由 (8.2b)式得到 )
如果 m>>p,tcomm(SF)≈ t comm(CT) = ts+mtw
2/pl?
pp2/2 pl?
pl log?
2/)( pmttSFt wsc om m
2/2)( pmttSFt wsc o m m
pmttSFt wsc om m lo g)(
wsc om m mttCTt)(
第八章 并行数值算法
8.0 预备知识
8.1 选路方法与开关技术
8.2 单一信包一到一传输
8.3 一到多播送
8.4 多到多播送
8.3 一到多播送
8.3.1 SF模式
8.3.2 CT模式国家高性能计算中心（合肥） 262009-7-24
一到多播送 — SF模式
环
步骤,① 先左右邻近传送 ;② 再左右二个方向同时播送
示例：
通讯时间：
7 5
0
6 4
1 2 3
3 4
1 2 3
2 4
图8.5
2/)()( pmttSFt wsal ltoone
国家高性能计算中心（合肥） 272009-7-24
一到多播送 — SF模式
环绕网孔
步骤,① 先完成一行中的播送 ;② 再同时进行各列的播送
示例：
共 4步 (2步行,2步列 )
通讯时间：
98
54 7
10 3
12 13 14 15
10 11
4444
3
4
333
444
21
2
图 8,6
6
2
2)(2)(
pmttSFt
wsal ltoone
国家高性能计算中心（合肥） 282009-7-24
一到多播送 — SF模式
超立方
步骤：从低维到高维，依次进行播送 ;
示例：
通讯时间：
2 3
0 1
6 7
54
( 0 1 0 )
( 0 0 0 ) ( 0 0 1 )
( 0 1 1 )
( 1 1 0 ) ( 1 1 1 )
( 1 0 1 )
( 1 0 0 )
3
3
3
3
2
2
1
pmttSFt wsal ltoon e lo g)()(
8.3 一到多播送
8.3.1 SF模式
8.3.2 CT模式国家高性能计算中心（合肥） 302009-7-24
一到多播送 — CT模式
环
步骤：
(1)先发送至 p/2远的处理器 ;
(2)再同时发送至 p/22远的处理器 ;
……
(i)再同时发送至 p/2i远的处理器 ;
示例：图 8.8
通讯时间：
)(lo g)(
)1(lo glo g
)2/()(
l og
1
)2.8(
可忽略时hws
hws
p
i
i
hwsal ltoon e
tpmtt
ptpmtpt
ptmttCTt
7 456
0 321
3
2
3
1
2
3 3
图 8,8
国家高性能计算中心（合肥） 312009-7-24
一到多播送 — CT模式
网孔
步骤：
(1)先进行行播送 ;
(2)再同时进行列播送 ;
示例：图 8.9
通讯时间：
)1(lo glo g// ptpmtpt hws
3 7
62
51
4
9
80
4 4 4 4
4 4 4 4
2 2
3 333
1
11
12
13
14
15
10
图 8,9
)1(lo glo g// ptpmtpt hws
)1(2l o g)(
))1(l o gl o g(2)(
ptpmtt
ptpmtptCTt
hws
hwsa l ltoo n e
国家高性能计算中心（合肥） 322009-7-24
一到多播送 — CT模式
超立方
步骤：
依次从低维到高维播送,d-立方,d=0,1,2,3,4… ;
通讯时间,pmttCTt
wsal ltoone lo g)()(
第八章 并行数值算法
8.0 预备知识
8.1 选路方法与开关技术
8.2 单一信包一到一传输
8.3 一到多播送
8.4 多到多播送
8.3 一到多播送
8.3.1 SF模式
8.3.2 CT模式国家高性能计算中心（合肥） 352009-7-24
多到多播送 — SF模式
环
步骤：
同时向右 (或左 )播送刚接收到的信包
示例：图 8.10
通讯时间：
7 6 5 4
0 1 2 3
1(6) 1(5) 1(4)
1(0) 1(1) 1(2)
1(7) 1(3)
(0) (1) (2) (3)
(7) (6) (5) (4)
第1通信步
7 6 5 4
0 1 2 3
2(5) 2(4) 2(3)
2(7) 2(0) 2(1)
2(6) 2(2)
(0,7) (1,0) (2,1)
(3,2)
(7,6) (6,5) (5,4)
(4,3)
第2通信步
7 6 5 4
0 1 2 3
7(0) 7(7) 7(6)
7(2) 7(3) 7(4)
7(1) 7(5)
(7,6,5,4,3,2,1)
第7通信步
(6,5,4,3,2,1,0)
(5,4,3,2,1,0,7)
(4,3,2,1,0,7,6)
(0,7,6,5,4,3,2)
(1,0,7,6,5,4,3)
(2,1,0,7,6,5,4)
(3,2,1,0,7,6,5)
图8,1 0
.
.
.
.
.
.
已有数据第 2步传送数据 2
)1)(()( pmttSFt wsal ltoal l
国家高性能计算中心（合肥） 362009-7-24
多到多播送 — SF模式
环绕网孔
步骤：
(1)先进行行的播送；
(2)再进行列的播送；
示例：图 8.11
通讯时间：
)1()1(2
)1)(()1)(()(
pmtpt
ptpmtpmttSFt
ws
wswsa l ltoa l l
6 7 8
543
0 1 2
6 7 8
543
0 1 2
(6) (7) (8)
(0) (1) (2)
(6,7,8) (6,7,8) (6,7,8)
(0,1,2) (0,1,2) (0,1,2)
(3) (4) (5)
(3,4,5) (3,4,5) (3,4,5)
(a) (b)
图8,1 1
国家高性能计算中心（合肥） 372009-7-24
多到多播送 — SF模式
超立方
步骤：
依次按维进行多到多的播送；
示例：图 8.12
通讯时间：
2
4
0
6
1
5
7
3
(0) (1)
(2) (3)
(7)(6)
(5)(4)
(a)
2
4
0
6
1
5
7
3
(6,7)
(b)
(0,1)
(2,3)
(0,1)
(2,3)
(4,5) (5,6)
(6,7)
(4,5)
2
4
0
6
1
5
7
3
(0,1,2,3)
(c)
(0,1,2,3)
(0,1,2,3)
(0,1,2,3)
(4,5,6,7) (4,5,6,7)
(4,5,6,7)(4,5,6,7)
2
4
0
6
1
5
7
3
(0,...,7)
(d)
(0,...,7)
(0,...,7)
(0,...,7)
(0,...,7) (0,...,7)
(0,...,7)(0,...,7)
图8,1 2)1(lo g
)2()(
l o g
1
1
pmtpt
mttSFt
ws
p
i
w
i
sa lltoa ll
8.3 一到多播送
8.3.1 SF模式
8.3.2 CT模式国家高性能计算中心（合肥） 392009-7-24
多到多播送 — CT模式
使用一到多的策略会造成链路竞争
)()( SFtCTt al ltoal lal ltoal l
7 6 5 4
0 1 2 3
多条信包图8,1 3
竞争一 通道
2003年 9月第三篇 并行数值算法第八章 基本通讯操作第九章 稠密矩阵运算第十章 线性方程组的求解第十一章 快速傅里叶变换第八章 并行数值算法
8.0 预备知识
8.1 选路方法与开关技术
8.2 单一信包一到一传输
8.3 一到多播送
8.4 多到多播送国家高性能计算中心（合肥） 42009-7-24
预备知识
选路 (Routing)
又称为选径或路由。产生消息从发源地到目的地所取的路径,要求具有较低通讯延迟、无死锁和容错能力。
应用于网络或并行机上的信息交换。
消息、信包、片
消息 (Message)：是在多计算机系统的处理接点之间传递包含数据和同步消息的信息包。它是一种逻辑单位，可由任意数量的包构成。
包 (Packet)：包的长度随协议不同而不同，它是信息传送的最小单位,64-512位。
片 (Flit)：片的长度固定，一般为 8位。
国家高性能计算中心（合肥） 52009-7-24
预备知识
消息、信包、片 的相互关系包消息包 据 片头片 尾片…… 顺序号数片 F F F F F F F F
国家高性能计算中心（合肥） 62009-7-24
预备知识? 一些术语
信道带宽 b：每个信道有 w位宽和信号传输率 f = 1/t (t
是时钟周期 ),b = wf bits/sec
节点和开关的度：与节点和开关相连的信道数目
路径：信包在网络中走过的开关和链路 (link)序列
路由长度或距离：路由路径中包括的链路 (link)数目
信包传输性能参数
启动时间 ts(startup time)：准备包头信息等
节点延迟时间 th(per-hop time)：包头穿越相邻节点的时间
字传输时间 tw(transfer time)：传输每个字的时间
链路数 l,信包大小 m
国家高性能计算中心（合肥） 72009-7-24
预备知识
选路算法的三种机制
基于算术的,开关中具有简单的算术运算功能，如维序选路；
基于源地址的,在源点时就将沿路径的各个开关的输出端口地址 p0,p1,…,pn包在信包的头部，每个开关只是对信包头的输出端口地址进行剥离；
基于查表的,开关中含有一个选路表，对信包头中的选路域查出输出端口地址。
国家高性能计算中心（合肥） 82009-7-24
预备知识
选路方式
多到多（会议）
）一到所有（广播、组播一到多（多播）
多到一（集中）
目的地；每条信包有且仅有一个发送一条信包，每个处理器开始时最多一到一（置换）
一到一（单播）
事先算好传输路径脱机没有事先计算好的路径联机网络信包可在任意时刻到达动态息都已到达网络在选路开始时所有的信静态用交换机线路
）虫孔（
）存储－转发（
信包
:
:)(
:)(
:
:
:
o f f l i n e
o n l i n e
W o r m h o l e
F o r w a r dandS t o r e
第八章 并行数值算法
8.0 预备知识
8.1 选路方法与开关技术
8.2 单一信包一到一传输
8.3 一到多播送
8.4 多到多播送
8.1 选路方法与开关技术
8.1.1 选路方法
8.1.2 开关技术国家高性能计算中心（合肥） 112009-7-24
选路方法
分类
最短路径 /非最短路径 (贪心选路 /随机选路 )，
如维序选路是贪心的，二阶段维序选路是随机的
确定选路 /自适应选路 (寻径确定 /寻径视网络状况 )
维序选路 (Dimension-Ordered Routing)：
一种确定的最短路径选路
二维网孔中的维序选路,X-Y选路
超立方中的维序选路,E-立方选路国家高性能计算中心（合肥） 122009-7-24
选路方法
X-Y选路算法
算法 8.1：二维网孔上的 X-Y选路算法
begin
step1,沿 X方向将信包送至目的地处理器所在的列
step2,沿 Y方向将信包送至目的地处理器所在的行
end
国家高性能计算中心（合肥） 132009-7-24
选路方法
例 8.1 (P186)
图8.1
0,7 1,7 2,7 3,7 4,7 5,7 6,7 7,7
0,6 1,6 2,6 3,6 4,6 5,6 6,6 7,6
1,50,5 2,5 3,5 4,5 5,5 6,5 7,5
0,4 1,4 2,4 3,4 7,44,4 6,45,4
6,31,3 2,3 3,3 4,3 5,30,3 7,3
0,2 1,2 2,2 3,2 7,25,2 6,24,2
2,11,10,1 3,1 4,1 5,1 6,1 7,1
0,0 1,0 7,03,0 4,0 5,0 6,02,0
x
y
i,j
E
S
W
N
源; 目的 对,(2,1;7,6)
(0,7;4,2)
(5,4;2,0)
(6,3;1,5)
4( )
国家高性能计算中心（合肥） 142009-7-24
选路方法
E-立方选路算法
路由计算,sn-1sn-2… s1s0(源地址 )
异或 dn-1dn-2… d1d0(目的地址 )
rn-1 rn-2 … r1 r0 (路由值 )
路由过程：
sn-1sn-2… s1s0? sn-1sn-2… s1s0 r0?
sn-1sn-2… s1s0 r1?…
算法 8.2,超立方网络上的 E-立方选路算法 (P186)
国家高性能计算中心（合肥） 152009-7-24
选路方法
例 8.2 (P187)
0110(S)
1101(D)
1011(R)
dim2
dim3
dim1
dim4
源,S=0110
目的,D=1101
路径：
0110 0111 0101 1101
11010101
0110 11111110
0000
1100
10011000
0100
0111
0001
0010
0011
1010
1011
图8,2
8.1 选路方法与开关技术
8.1.1 选路方法
8.1.2 开关技术国家高性能计算中心（合肥） 172009-7-24
开关技术
存储转发 (Store-and-Forward)选路
消息被分成基本的传输单位 ----信包 (Packet),每个信包都含有寻径信息；
当一个信包到达中间节点 A时,A把整个信包放入其通信缓冲器中，然后在选路算法的控制下选择下一个相邻节点 B，当从 A到 B的通道空闲并且 B的通信缓冲器可用时，把信包从 A发向 B；
信包的传输时间,tcomm (SF) = ts + (mtw + th)l=O(ml)
缺点：
每个结点必须对整个消息和信包进行缓冲，缓冲器较大；
网络时延与发送消息所经历的节点数成正比国家高性能计算中心（合肥） 182009-7-24
开关技术
切通 (Cut Through)选路
在传递一个消息之前，就为它建立一条从源结点到目的结点的物理通道。在传递的全部过程中，线路的每一段都被占用，当消息的尾部经过网络后，整条物理链路才被废弃。
传输时间,tcomm (CT) = ts + mtw + lth = O(m+l)
缺点：
物理通道非共享
传输过程中物理通道一直被占用国家高性能计算中心（合肥） 192009-7-24
开关技术
虫孔 (Wormhole)选路
Dally于 1986年提出，利用了前二种方法的优点，减少了缓冲区，提高了物理通道的利用。
首先把一个消息分成许多很小的片，消息的 头片 包含了这个消息的所有寻径信息。 尾片 是一个其最后包含了消息结束符的片。中间的片均为 数据片 ；
片是最小信息单位。每个结点上只需要缓冲一个片就能满足要求；
用一个头片直接牵引一条从输入链路到输出链路的路径的方法来进行操作。每个消息中的片以流水的方式在网络中向前,蠕动,。每个片相当于 Worm的一个节，
,蠕动,以节为单位顺序地向前爬行。当消息的尾片向前,蠕动,一步后，它刚才所占用的结点就被放弃了。
国家高性能计算中心（合肥） 202009-7-24
开关技术
虫孔 (Wormhole)选路优点：
(1)每个结点的缓冲器的需求量小,易于用 VLSI实现；
(2)较低的网络传输延迟 。存储转发传输延迟基本上正比于消息在网络中传输的距离 ; Wormhole与线路开关的网络传输延迟正比于消息包的长度，传输距离对它的影响很小（消息包较长时的情况）；
(3)通道共享性好、利用率高 ；
(4)易于实现 Multicast和 Broadcast。
国家高性能计算中心（合肥） 212009-7-24
开关技术
几种开关技术的时空图
l
t (SF)comm
1
P
2
P
3
P
4
P
mtw
头 信包数据
T
(a)
l
1
P
2
P
3
P
4
P
mtw
T
(b)
图8,4
t (CT)comm
第八章 并行数值算法
8.0 预备知识
8.1 选路方法与开关技术
8.2 单一信包一到一传输
8.3 一到多播送
8.4 多到多播送国家高性能计算中心（合肥） 232009-7-24
单一信包一到一传输
距离 l的计算,对于 p个处理器
一维环形：
带环绕 Mesh( )：
超立方：
tcomm(SF)的计算 (可由 (8.1b)式得到 )
一维环形：
带环绕 Mesh：
超立方：
tcomm(CT)的计算 (可由 (8.2b)式得到 )
如果 m>>p,tcomm(SF)≈ t comm(CT) = ts+mtw
2/pl?
pp2/2 pl?
pl log?
2/)( pmttSFt wsc om m
2/2)( pmttSFt wsc o m m
pmttSFt wsc om m lo g)(
wsc om m mttCTt)(
第八章 并行数值算法
8.0 预备知识
8.1 选路方法与开关技术
8.2 单一信包一到一传输
8.3 一到多播送
8.4 多到多播送
8.3 一到多播送
8.3.1 SF模式
8.3.2 CT模式国家高性能计算中心（合肥） 262009-7-24
一到多播送 — SF模式
环
步骤,① 先左右邻近传送 ;② 再左右二个方向同时播送
示例：
通讯时间：
7 5
0
6 4
1 2 3
3 4
1 2 3
2 4
图8.5
2/)()( pmttSFt wsal ltoone
国家高性能计算中心（合肥） 272009-7-24
一到多播送 — SF模式
环绕网孔
步骤,① 先完成一行中的播送 ;② 再同时进行各列的播送
示例：
共 4步 (2步行,2步列 )
通讯时间：
98
54 7
10 3
12 13 14 15
10 11
4444
3
4
333
444
21
2
图 8,6
6
2
2)(2)(
pmttSFt
wsal ltoone
国家高性能计算中心（合肥） 282009-7-24
一到多播送 — SF模式
超立方
步骤：从低维到高维，依次进行播送 ;
示例：
通讯时间：
2 3
0 1
6 7
54
( 0 1 0 )
( 0 0 0 ) ( 0 0 1 )
( 0 1 1 )
( 1 1 0 ) ( 1 1 1 )
( 1 0 1 )
( 1 0 0 )
3
3
3
3
2
2
1
pmttSFt wsal ltoon e lo g)()(
8.3 一到多播送
8.3.1 SF模式
8.3.2 CT模式国家高性能计算中心（合肥） 302009-7-24
一到多播送 — CT模式
环
步骤：
(1)先发送至 p/2远的处理器 ;
(2)再同时发送至 p/22远的处理器 ;
……
(i)再同时发送至 p/2i远的处理器 ;
示例：图 8.8
通讯时间：
)(lo g)(
)1(lo glo g
)2/()(
l og
1
)2.8(
可忽略时hws
hws
p
i
i
hwsal ltoon e
tpmtt
ptpmtpt
ptmttCTt
7 456
0 321
3
2
3
1
2
3 3
图 8,8
国家高性能计算中心（合肥） 312009-7-24
一到多播送 — CT模式
网孔
步骤：
(1)先进行行播送 ;
(2)再同时进行列播送 ;
示例：图 8.9
通讯时间：
)1(lo glo g// ptpmtpt hws
3 7
62
51
4
9
80
4 4 4 4
4 4 4 4
2 2
3 333
1
11
12
13
14
15
10
图 8,9
)1(lo glo g// ptpmtpt hws
)1(2l o g)(
))1(l o gl o g(2)(
ptpmtt
ptpmtptCTt
hws
hwsa l ltoo n e
国家高性能计算中心（合肥） 322009-7-24
一到多播送 — CT模式
超立方
步骤：
依次从低维到高维播送,d-立方,d=0,1,2,3,4… ;
通讯时间,pmttCTt
wsal ltoone lo g)()(
第八章 并行数值算法
8.0 预备知识
8.1 选路方法与开关技术
8.2 单一信包一到一传输
8.3 一到多播送
8.4 多到多播送
8.3 一到多播送
8.3.1 SF模式
8.3.2 CT模式国家高性能计算中心（合肥） 352009-7-24
多到多播送 — SF模式
环
步骤：
同时向右 (或左 )播送刚接收到的信包
示例：图 8.10
通讯时间：
7 6 5 4
0 1 2 3
1(6) 1(5) 1(4)
1(0) 1(1) 1(2)
1(7) 1(3)
(0) (1) (2) (3)
(7) (6) (5) (4)
第1通信步
7 6 5 4
0 1 2 3
2(5) 2(4) 2(3)
2(7) 2(0) 2(1)
2(6) 2(2)
(0,7) (1,0) (2,1)
(3,2)
(7,6) (6,5) (5,4)
(4,3)
第2通信步
7 6 5 4
0 1 2 3
7(0) 7(7) 7(6)
7(2) 7(3) 7(4)
7(1) 7(5)
(7,6,5,4,3,2,1)
第7通信步
(6,5,4,3,2,1,0)
(5,4,3,2,1,0,7)
(4,3,2,1,0,7,6)
(0,7,6,5,4,3,2)
(1,0,7,6,5,4,3)
(2,1,0,7,6,5,4)
(3,2,1,0,7,6,5)
图8,1 0
.
.
.
.
.
.
已有数据第 2步传送数据 2
)1)(()( pmttSFt wsal ltoal l
国家高性能计算中心（合肥） 362009-7-24
多到多播送 — SF模式
环绕网孔
步骤：
(1)先进行行的播送；
(2)再进行列的播送；
示例：图 8.11
通讯时间：
)1()1(2
)1)(()1)(()(
pmtpt
ptpmtpmttSFt
ws
wswsa l ltoa l l
6 7 8
543
0 1 2
6 7 8
543
0 1 2
(6) (7) (8)
(0) (1) (2)
(6,7,8) (6,7,8) (6,7,8)
(0,1,2) (0,1,2) (0,1,2)
(3) (4) (5)
(3,4,5) (3,4,5) (3,4,5)
(a) (b)
图8,1 1
国家高性能计算中心（合肥） 372009-7-24
多到多播送 — SF模式
超立方
步骤：
依次按维进行多到多的播送；
示例：图 8.12
通讯时间：
2
4
0
6
1
5
7
3
(0) (1)
(2) (3)
(7)(6)
(5)(4)
(a)
2
4
0
6
1
5
7
3
(6,7)
(b)
(0,1)
(2,3)
(0,1)
(2,3)
(4,5) (5,6)
(6,7)
(4,5)
2
4
0
6
1
5
7
3
(0,1,2,3)
(c)
(0,1,2,3)
(0,1,2,3)
(0,1,2,3)
(4,5,6,7) (4,5,6,7)
(4,5,6,7)(4,5,6,7)
2
4
0
6
1
5
7
3
(0,...,7)
(d)
(0,...,7)
(0,...,7)
(0,...,7)
(0,...,7) (0,...,7)
(0,...,7)(0,...,7)
图8,1 2)1(lo g
)2()(
l o g
1
1
pmtpt
mttSFt
ws
p
i
w
i
sa lltoa ll
8.3 一到多播送
8.3.1 SF模式
8.3.2 CT模式国家高性能计算中心（合肥） 392009-7-24
多到多播送 — CT模式
使用一到多的策略会造成链路竞争
)()( SFtCTt al ltoal lal ltoal l
7 6 5 4
0 1 2 3
多条信包图8,1 3
竞争一 通道
