哈尔滨工业大学计算机科学与技术学院
并行处理与体系结构
哈尔滨工业大学计算机科学与技术学院
第 6章系统的互联和千兆位网络
??1 互连网络基础
??2 静态连接网络
??3 动态连接网络
??4 消息传递机制
??5 千兆位网络技术
??6 ATM交换器和网络
哈尔滨工业大学计算机科学与技术学院
?3 动态连接网络
?目的和种类,
?按照价格和性能增加的顺序，动
态连接网络的排队次序为,
?多处理机的总线；
?交叉开关网络。
?多级互连网络 (MIN)；
哈尔滨工业大学计算机科学与技术学院
?动态网络的性能,
?可用网络带宽
? 通过网络的最大数据传输率，用 M字节／秒表示
?数据传输速率
?网络时延
? 单位消息通过网络传送时最坏情况下的时间
延迟
?所用的通信模式
哈尔滨工业大学计算机科学与技术学院
? 一,多处理机的总线
? 定义,
? 特点,
?数字总线已被称为多个功能模块间
的争用总线 (contention bus)或时
分总线 (time-sharing bus)。
哈尔滨工业大学计算机科学与技术学院
哈尔滨工业大学计算机科学与技术学院
哈尔滨工业大学计算机科学与技术学院
?二,开关模块
1.一个 a× b开关模块有 a个输入和 b
个输出。
一个二元开关则与 a＝ b＝ 2 的 2X2
开关模块相对应
哈尔滨工业大学计算机科学与技术学院
哈尔滨工业大学计算机科学与技术学院
?2X2交叉开关可有两种连接模
式,
?直送
?交叉
哈尔滨工业大学计算机科学与技术学院
哈尔滨工业大学计算机科学与技术学院
?2,4X4的交叉开关的模块
哈尔滨工业大学计算机科学与技术学院
?3.交叉开关网络
?特点,
? 交叉开关网络的带宽和互连特性最好。
? 可看作是一个单级开关网络。
? 交叉点开关能在对偶 (源、目的 )之间形
成动态连接，每个交叉点开关在对偶间
提供一条专用连接通路，开关可根据程
序的要求动态地设置, 开, 或, 关, 。
哈尔滨工业大学计算机科学与技术学院
? 例题：下图所示两种交叉开关网络
?(1) C.mmp多处理机可以在处理机和
存储模块之间用交叉开关网络构成一
个共享存储型多处理机，实际上这是
一个存储器访问网络
?C.mmp多处理机已实现了一个 16X16交
叉开关网络
哈尔滨工业大学计算机科学与技术学院
哈尔滨工业大学计算机科学与技术学院
?(2) Fujitsu公司 (1992)制造的向量
并行处理机
? 还有一种交叉开关网络可用于处理机
间通信，如下图所示。 (VPP500)实际
上就是采用了这种大型交叉开关网络
(224X224)
? 其中 PE为接有存储器的处理机,
?CP代表控制处理机，用来监控整个系统，
包括交叉开关网络的运行。
哈尔滨工业大学计算机科学与技术学院
哈尔滨工业大学计算机科学与技术学院
? 交叉开关网络的局限性
? 每台处理机可以向多个存储模块发出请求。
nXn的交叉开关网络在每个存储周期最多
可为 n台处理机发送 n个存储字。
? 交叉开关网络每个存储周期可以实现 n个
数据传输,与每个总线周期只传一个数据
相比，它的频宽最高。
? 由于所有必要的开关和解决冲突的逻辑都
做在交叉点开关中,所以处理机接口和存
储器端口的逻辑就变得比较简单，因而也
比较便宜。
哈尔滨工业大学计算机科学与技术学院
? 交叉开关网络 对只有几台处理机访问几个
存储器模块的小型多处理机系统来说性能
价格比比较高。 单级交叉开关网络一旦构
成后将不能扩充
? 冗余或奇偶校验线可以做在每个交叉点开
关中,以便增强交叉开关网络的容错性和
可靠性
? 除了用电子元件构造交叉开关网络外，科
研机构正在研究用光电元件构造较大较快
的网络。
哈尔滨工业大学计算机科学与技术学院
? 三,多级网络
? 一种通用多级网络如下图所示；
? 各种 MIN的区别就在于,
① 所用开关模块和级间连接 (ISC)模式
的不同。最简单的开关模块是 2× 2
开关。
② 常用的 ISC模式包括有均匀洗牌、蝶
式、多路洗牌、纵横交叉、立方体
连接等。
哈尔滨工业大学计算机科学与技术学院
哈尔滨工业大学计算机科学与技术学院
?四, ?网络
?1,?网络的构造
? 下图所示的是一个 16X16 ?网络，共
需 4级 2X2开关。
? 网络左侧有 16个输入，右侧有 16个输
出
?ISC是对 16个对象的均匀洗牌模式
哈尔滨工业大学计算机科学与技术学院
哈尔滨工业大学计算机科学与技术学院
? 一个 n输入的 ?网络需要 log2n级 2X2
开关，每级要用 n／ 2个开关模块,
?网络共需 nlog2n／ 2个开关。
? 每个开关模块采用单元控制方式。
? 不同的开关状态组合可实现各种置
换、广播或从输入到输出的其它连
接
哈尔滨工业大学计算机科学与技术学院
? 2,?网络寻径控制
?8个输入端的 Omega网络如下图所示。
? 通常,n个输入端的 Omega网络有 logan
级 (开关输入 a个）
? 从输入级到输出级依次编号为,
?0到 log2n-1
哈尔滨工业大学计算机科学与技术学院
? 控制方法,
? 目的地址控制法 ;
?通过检查二进制目的地址编码来控
制数据路径。
?目的地址编码从高位开始的第 i位
为 0时，第 i级的 2X2开关的输入端
与 上 输出端连接
?否则输入端与 下 输出端连接。
哈尔滨工业大学计算机科学与技术学院
? 例题,
? 下图的开关设置对应于置换
?1=(0,7,6,4,2)(1,3)(5)
? 中的开关设置,?1的映射为 0— 7,7— 6，
6— 4,4— 2,2— 0,1— 3,3— 1,5— 5。
? 观察一个消息从输入端 001到输出端 011
的路径。它使用了开关 A,B和 C。
? 实现 ?1的置换所要求的开关设置，不存在
冲突。
哈尔滨工业大学计算机科学与技术学院
哈尔滨工业大学计算机科学与技术学院
?置换 ?2＝ (0,6,4,7,3)(1，
5)(2)。
?现在再来考察 8个输入端口的
Omega网络实现置换 ?2的情况。
?开关 F,G和 H的设置发生了冲突
哈尔滨工业大学计算机科学与技术学院
哈尔滨工业大学计算机科学与技术学院
?F冲突 ---由 000→110 和 100→111 引
起；
?G冲突 ---由 011→000 和 111→011 引
起；
?H冲突 ---由 101→001 和 011→000 引
起
哈尔滨工业大学计算机科学与技术学院
? Omega网络是一种阻塞网络。当出现阻塞时，
可以采用几次通过的方法解决冲突。
? 例如 ?2,
? 在第一次通过时实现连接 000— 110，
001→ 101,010→ 010,101→ 001，
110→ 100。
? 在第二次通过时实现连接 011→ 000，
100→ 111,111→ 011。
哈尔滨工业大学计算机科学与技术学院
? 讨论,
? 如果采用 2X2开关元件,n个输入端 Omega
网络一次通过可以实现 n n／ 2个置换，但
总共有 n!个置换。
? n个输入端的 Omega网络一次通过只能实
现全部置换的 n n／ 2/ n!
? 一般来说,n个输入端的 Omega网络实现
非阻塞连接最多需要通过的次数为 log2n。
? 在任何多级网络中都不希望出现阻塞，阻
塞将降低有效频宽。
哈尔滨工业大学计算机科学与技术学院
? 例题,n＝ 8时,
① 8个输入端的 Omega网络一次通过
只能实现全部置换的 10,16％,
② 即 84／ 8！＝ 4096／ 40320＝
0,1016＝ 10,16％。
③ 所有其它置换将引起阻塞。实现
这些置换需要三次通过。
哈尔滨工业大学计算机科学与技术学院
?例题
?如下图所示，采用上播或下播开
关设置,Omega网络也可以从一
个源将数据广播给多个目的地。
?在输人端 001的消息通过二进制
树的连接广播到所有 8个输出端。
哈尔滨工业大学计算机科学与技术学院
哈尔滨工业大学计算机科学与技术学院
?例题,
?下图是用 4X4开关元件作为构成块
的 Omega网络，级间是 4路洗牌连
接，而不是 2路洗牌连接。
?16个输入端的 Omega网络的级数为,
log416＝ 2
哈尔滨工业大学计算机科学与技术学院
?4路洗牌相当于把 16个输人端平
均地分成 4个子组，然后 4个子组
均匀地洗牌。
?当采用是 kXk开关元件时，则可
以定义 k路洗牌函数来构造更大
的级数为 logkn的 Omega网络。
哈尔滨工业大学计算机科学与技术学院
哈尔滨工业大学计算机科学与技术学院
? 五,基准网络
? Wu和 Feng(1980)研究过多级互连网络之
间的关系。基准网络可如下图所示递归生
成。
? 第一级为一个 N× N模块；
? 第二级为两个 (N／ 2)X(N／ 2)子模块，以
C0和 C1表示。
? 以上构成方法可递归用于子模块，直至得
到 2× 2的 N／ 2子模块为止。
? 每个块有两个合法状态：两个输出和输入
的直送和交叉。
哈尔滨工业大学计算机科学与技术学院
哈尔滨工业大学计算机科学与技术学院
?总结,
? 总线的造价最低
? 其缺点是每台处理机可用的带宽较窄。
总线所存在的另一个问题是容易产生故
障。
? 交叉开关
? 硬件复杂性以 n2上升，所以其造价最为
昂贵。但是，交叉开关的带宽和寻径性
能最好。如网络的规模较小，它是一种
理想的选择。
哈尔滨工业大学计算机科学与技术学院
?多级网络,
?则是两个极端之间的折衷。它
的主要优点在于采用模块结构，
因而可扩展性较好。然而，其
时延随网络的级数 log2n而上升。
哈尔滨工业大学计算机科学与技术学院
并行处理与体系结构
哈尔滨工业大学计算机科学与技术学院
第 6章系统的互联和千兆位网络
??1 互连网络基础
??2 静态连接网络
??3 动态连接网络
??4 消息传递机制
??5 千兆位网络技术
??6 ATM交换器和网络
哈尔滨工业大学计算机科学与技术学院
?3 动态连接网络
?目的和种类,
?按照价格和性能增加的顺序，动
态连接网络的排队次序为,
?多处理机的总线；
?交叉开关网络。
?多级互连网络 (MIN)；
哈尔滨工业大学计算机科学与技术学院
?动态网络的性能,
?可用网络带宽
? 通过网络的最大数据传输率，用 M字节／秒表示
?数据传输速率
?网络时延
? 单位消息通过网络传送时最坏情况下的时间
延迟
?所用的通信模式
哈尔滨工业大学计算机科学与技术学院
? 一,多处理机的总线
? 定义,
? 特点,
?数字总线已被称为多个功能模块间
的争用总线 (contention bus)或时
分总线 (time-sharing bus)。
哈尔滨工业大学计算机科学与技术学院
哈尔滨工业大学计算机科学与技术学院
哈尔滨工业大学计算机科学与技术学院
?二,开关模块
1.一个 a× b开关模块有 a个输入和 b
个输出。
一个二元开关则与 a＝ b＝ 2 的 2X2
开关模块相对应
哈尔滨工业大学计算机科学与技术学院
哈尔滨工业大学计算机科学与技术学院
?2X2交叉开关可有两种连接模
式,
?直送
?交叉
哈尔滨工业大学计算机科学与技术学院
哈尔滨工业大学计算机科学与技术学院
?2,4X4的交叉开关的模块
哈尔滨工业大学计算机科学与技术学院
?3.交叉开关网络
?特点,
? 交叉开关网络的带宽和互连特性最好。
? 可看作是一个单级开关网络。
? 交叉点开关能在对偶 (源、目的 )之间形
成动态连接，每个交叉点开关在对偶间
提供一条专用连接通路，开关可根据程
序的要求动态地设置, 开, 或, 关, 。
哈尔滨工业大学计算机科学与技术学院
? 例题：下图所示两种交叉开关网络
?(1) C.mmp多处理机可以在处理机和
存储模块之间用交叉开关网络构成一
个共享存储型多处理机，实际上这是
一个存储器访问网络
?C.mmp多处理机已实现了一个 16X16交
叉开关网络
哈尔滨工业大学计算机科学与技术学院
哈尔滨工业大学计算机科学与技术学院
?(2) Fujitsu公司 (1992)制造的向量
并行处理机
? 还有一种交叉开关网络可用于处理机
间通信，如下图所示。 (VPP500)实际
上就是采用了这种大型交叉开关网络
(224X224)
? 其中 PE为接有存储器的处理机,
?CP代表控制处理机，用来监控整个系统，
包括交叉开关网络的运行。
哈尔滨工业大学计算机科学与技术学院
哈尔滨工业大学计算机科学与技术学院
? 交叉开关网络的局限性
? 每台处理机可以向多个存储模块发出请求。
nXn的交叉开关网络在每个存储周期最多
可为 n台处理机发送 n个存储字。
? 交叉开关网络每个存储周期可以实现 n个
数据传输,与每个总线周期只传一个数据
相比，它的频宽最高。
? 由于所有必要的开关和解决冲突的逻辑都
做在交叉点开关中,所以处理机接口和存
储器端口的逻辑就变得比较简单，因而也
比较便宜。
哈尔滨工业大学计算机科学与技术学院
? 交叉开关网络 对只有几台处理机访问几个
存储器模块的小型多处理机系统来说性能
价格比比较高。 单级交叉开关网络一旦构
成后将不能扩充
? 冗余或奇偶校验线可以做在每个交叉点开
关中,以便增强交叉开关网络的容错性和
可靠性
? 除了用电子元件构造交叉开关网络外，科
研机构正在研究用光电元件构造较大较快
的网络。
哈尔滨工业大学计算机科学与技术学院
? 三,多级网络
? 一种通用多级网络如下图所示；
? 各种 MIN的区别就在于,
① 所用开关模块和级间连接 (ISC)模式
的不同。最简单的开关模块是 2× 2
开关。
② 常用的 ISC模式包括有均匀洗牌、蝶
式、多路洗牌、纵横交叉、立方体
连接等。
哈尔滨工业大学计算机科学与技术学院
哈尔滨工业大学计算机科学与技术学院
?四, ?网络
?1,?网络的构造
? 下图所示的是一个 16X16 ?网络，共
需 4级 2X2开关。
? 网络左侧有 16个输入，右侧有 16个输
出
?ISC是对 16个对象的均匀洗牌模式
哈尔滨工业大学计算机科学与技术学院
哈尔滨工业大学计算机科学与技术学院
? 一个 n输入的 ?网络需要 log2n级 2X2
开关，每级要用 n／ 2个开关模块,
?网络共需 nlog2n／ 2个开关。
? 每个开关模块采用单元控制方式。
? 不同的开关状态组合可实现各种置
换、广播或从输入到输出的其它连
接
哈尔滨工业大学计算机科学与技术学院
? 2,?网络寻径控制
?8个输入端的 Omega网络如下图所示。
? 通常,n个输入端的 Omega网络有 logan
级 (开关输入 a个）
? 从输入级到输出级依次编号为,
?0到 log2n-1
哈尔滨工业大学计算机科学与技术学院
? 控制方法,
? 目的地址控制法 ;
?通过检查二进制目的地址编码来控
制数据路径。
?目的地址编码从高位开始的第 i位
为 0时，第 i级的 2X2开关的输入端
与 上 输出端连接
?否则输入端与 下 输出端连接。
哈尔滨工业大学计算机科学与技术学院
? 例题,
? 下图的开关设置对应于置换
?1=(0,7,6,4,2)(1,3)(5)
? 中的开关设置,?1的映射为 0— 7,7— 6，
6— 4,4— 2,2— 0,1— 3,3— 1,5— 5。
? 观察一个消息从输入端 001到输出端 011
的路径。它使用了开关 A,B和 C。
? 实现 ?1的置换所要求的开关设置，不存在
冲突。
哈尔滨工业大学计算机科学与技术学院
哈尔滨工业大学计算机科学与技术学院
?置换 ?2＝ (0,6,4,7,3)(1，
5)(2)。
?现在再来考察 8个输入端口的
Omega网络实现置换 ?2的情况。
?开关 F,G和 H的设置发生了冲突
哈尔滨工业大学计算机科学与技术学院
哈尔滨工业大学计算机科学与技术学院
?F冲突 ---由 000→110 和 100→111 引
起；
?G冲突 ---由 011→000 和 111→011 引
起；
?H冲突 ---由 101→001 和 011→000 引
起
哈尔滨工业大学计算机科学与技术学院
? Omega网络是一种阻塞网络。当出现阻塞时，
可以采用几次通过的方法解决冲突。
? 例如 ?2,
? 在第一次通过时实现连接 000— 110，
001→ 101,010→ 010,101→ 001，
110→ 100。
? 在第二次通过时实现连接 011→ 000，
100→ 111,111→ 011。
哈尔滨工业大学计算机科学与技术学院
? 讨论,
? 如果采用 2X2开关元件,n个输入端 Omega
网络一次通过可以实现 n n／ 2个置换，但
总共有 n!个置换。
? n个输入端的 Omega网络一次通过只能实
现全部置换的 n n／ 2/ n!
? 一般来说,n个输入端的 Omega网络实现
非阻塞连接最多需要通过的次数为 log2n。
? 在任何多级网络中都不希望出现阻塞，阻
塞将降低有效频宽。
哈尔滨工业大学计算机科学与技术学院
? 例题,n＝ 8时,
① 8个输入端的 Omega网络一次通过
只能实现全部置换的 10,16％,
② 即 84／ 8！＝ 4096／ 40320＝
0,1016＝ 10,16％。
③ 所有其它置换将引起阻塞。实现
这些置换需要三次通过。
哈尔滨工业大学计算机科学与技术学院
?例题
?如下图所示，采用上播或下播开
关设置,Omega网络也可以从一
个源将数据广播给多个目的地。
?在输人端 001的消息通过二进制
树的连接广播到所有 8个输出端。
哈尔滨工业大学计算机科学与技术学院
哈尔滨工业大学计算机科学与技术学院
?例题,
?下图是用 4X4开关元件作为构成块
的 Omega网络，级间是 4路洗牌连
接，而不是 2路洗牌连接。
?16个输入端的 Omega网络的级数为,
log416＝ 2
哈尔滨工业大学计算机科学与技术学院
?4路洗牌相当于把 16个输人端平
均地分成 4个子组，然后 4个子组
均匀地洗牌。
?当采用是 kXk开关元件时，则可
以定义 k路洗牌函数来构造更大
的级数为 logkn的 Omega网络。
哈尔滨工业大学计算机科学与技术学院
哈尔滨工业大学计算机科学与技术学院
? 五,基准网络
? Wu和 Feng(1980)研究过多级互连网络之
间的关系。基准网络可如下图所示递归生
成。
? 第一级为一个 N× N模块；
? 第二级为两个 (N／ 2)X(N／ 2)子模块，以
C0和 C1表示。
? 以上构成方法可递归用于子模块，直至得
到 2× 2的 N／ 2子模块为止。
? 每个块有两个合法状态：两个输出和输入
的直送和交叉。
哈尔滨工业大学计算机科学与技术学院
哈尔滨工业大学计算机科学与技术学院
?总结,
? 总线的造价最低
? 其缺点是每台处理机可用的带宽较窄。
总线所存在的另一个问题是容易产生故
障。
? 交叉开关
? 硬件复杂性以 n2上升，所以其造价最为
昂贵。但是，交叉开关的带宽和寻径性
能最好。如网络的规模较小，它是一种
理想的选择。
哈尔滨工业大学计算机科学与技术学院
?多级网络,
?则是两个极端之间的折衷。它
的主要优点在于采用模块结构，
因而可扩展性较好。然而，其
时延随网络的级数 log2n而上升。
哈尔滨工业大学计算机科学与技术学院
