第13章

第13章内容摘要：

态网络中的连接不固定，在程序执行过程中可根据需要改变。  网络的开关元件有源，链路可通过设置这些开关的状态来重构。  只有在网络边界上的开关元件才能与处理机相连。  动态网络主要有 总线、交叉开关、多级交换网络。 41 动态互连网络 总线（ Bus）  总线实际上是连接处理器、存储器和 I/O等外围设备的一组导线和插座。  它在某一时刻只能用于一对 源和目的 之间传输数据。  当有多对源和目的请求使用总线时，要进行总线仲裁。 当 CPU数目较多时对总线争用严重（ =32个）。 线性阵列与总线的区别  线性阵列 ：允许不同的源结点和目的结点对并发使用系统的不同部分。  总线 ：通过切换与其相连的许多结点来实现时分特性，同一时刻只有一对结点在传送数据。 42 C 局部总线 CA IF P M CPU板 I/O总线 … 存储器总线 IF C 存储器 存储器板 C 局部总线 CA IF P M CPU板 I/O总线 存储器总线 IF C 存储器 存储器板 … 系统总线（在底板上 ） IF 局部总线 缓存器 IF IOP I/O板 磁盘 打印机 C 局部总线 缓存器 IF IF 网络接口卡 以太网 IF:专用逻辑接口 C:专用控制器 P:处理器 M:局部存储器 CA:高速缓存 IOP:I/O处理器 43 动态互连网络 交叉开关（ Crossbar Switcher）  交叉开关是一种高带宽网络，它可以在输入端和输出端之间建立动态连接  在每个输入端和输出端的交叉点上都有交叉点开关。 该开关可以根据需要置为 “ 开 ” 或 “ 关 ”状态，从而使不同的输入端和输出端导通。  交叉开关的硬件复杂性为 n2数量级，造价昂贵。 但是其带宽和寻径性能在这三种动态网络中最好。 如果网络规模小，它是一种理想的选择（ =64个）。 44 交叉开关 0 0 00 0 10 1 00 1 11 0 01 0 11 1 01 1 10 0 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1内 存C P U图 1 3 . 2 1 8 8 的 交 叉 开 关交 叉 开 关 打 开交 叉 开 关 闭 合45 动态互连网络 多级交换网络  开关单元： a个输入 a个输出的开关单元记作 aa的开关单元，其中， a是 2的整数倍。 常见的有 2 488等。  根据开关单元功能的多少， 22又可以分为 两功能 和四功能 开关。 直通 交换 上播 下播 46 动态互连网络 多级交换网络  级间互连模式  均匀洗牌、蝶式、多路洗牌、纵横开关及立方体连结等  控制方式  级控制：每级只有一个控制信号  单元控制：每个开关一个控制信号  部分级控制：几个开关合用一个控制信号  多级交换网络是总线和交叉开关的折衷。 它的主要优点在于采用模块结构，可扩展性好（ 64） 47 Ω多级交换网络 0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7 第 0级 第 1级 第 2级 计算机原理及系统结构 第五十五讲 主讲教师：赵 宏伟 学时： 64 49 互连网络的寻径方式 多种不同的设计方案  电路交换：预约资源（端口和缓冲区），预先建立固定交换结点链路，分组能够全速发送。  存储转发分组交换：不预约资源，各个交换结点缓存整个分组。 需要有缓存策略：  输入缓存、输出缓存、公共缓冲区  虚拟直通寻径：当分组第一个单元不能移动时，分组的其余单元可以继续向第一个单元所在的结点传送。  虫蚀寻径：当第一个单元不能移动时，通知源结点，源结点就停止传送，因此分组就像一条虫子一样停留在两个或者更多个交换结点中。 P339 50 互连网络的寻径方式 四个交换结点的方型互连网络输 入 端 口输 出 端 口4 端 口 交 换 结 点分 组 的 前 部分 组 的 中 部分 组 的 后 部C P U 1C P U 251 互连网络的寻径方式 存 储 转 发 分 组 交 换C P U1C P U2( a ) ( b ) ( c )完 整 的 分 组 完 整 的 分 组完 整 的 分 组输 入 端 口输 出 端 口4 端 口 交 换 结 点52 互连网络的寻径算法 源寻径和分布式寻径  在源寻径中，源结点预先决定穿过互连网络的完整的路径，使用路径中每个结点的端口号的列表来表示。  在分布式寻径算法中，每个交换结点自己决定把到达的分组发送到哪个输出端口。 一般来说在各个交换结点都设立一个路径表，而分组的头部含有一个寻径字段说明分组的目的地址和选择路径的依据。 静态寻径算法和自适应寻径算法  算法对所有到相同目的结点的分组都做出相同的决策，那么这样的寻径算法就称为静态的。  算法在做路径选择时考虑了当前情况，该算法就是自适应的。 P341 53 本章主要内容 并行计算机系统结构概述 并行计算机系统的设计问题  并行计算机系统的互连网络  并行计算机系统的性能问题  并行计算机系统的软件问题 SIMD计算机简介 MIMD多处理机简介 MIMD多计算机简介 54 并行计算机系统的性能问题 硬件性能指标  重要的性能指标是 CPU和输入 /输出的速度以及互连网络的性能。  互连网络的性能有两个重要的指标：延时（ Latency）和带宽（ Bandwidth）。  延迟时间是指从 CPU发送分组至接收到响应的时间间隔。  对分带宽、聚集带宽和平均带宽（按照 CPU能力计算 ）。 软件性能指标  最关键的性能指标是加速比（ speedup）：一个程序在有 n个处理器的计算机上运行和在只有一个处理器的计算机上运行相比快多少倍。 P342 55 并行计算机系统的性能问题 图 1 3 . 1 0 实 际 程 序 获 得 的 加 速 比 总 是 低 于 线 性 加 速 比P342 56 并行计算机系统的性能问题 理想的加速比不可能达到的部分原因是几乎所有的程序都有串行部分。  假定一个程序在单处理器计算机上运行需要 T秒，其中一部分是串行代码，所占比例记为 f，那么剩余的（ 1－ f）就是可以并行的。  后一部分代码运行在 n个 CPU上而且没有任何其它开销，那么在最理想的情况下，执行时间可以从（ 1－ f） T减少到（ 1－ f） T/n。  串行部分加并行部分的整个执行时间就是 fT＋（ 1－ f） T/n。  加速比就是原来程序的执行时间除以新的程序的执行时间： )f( n nn f ) T(fTTS p e e d u p11/1 57 本章主要内容 并行计算机系统结构概述 并行计算机系统的设计问题  并行计算机系统的互连网络  并行计算机系统的性能问题  并行计算机系统的软件问题 SIMD计算机简介 MIMD多处理机简介 MIMD多计算机简介 58 并行计算机软件的四种设计方法 第一种方法是为普通的串行语言增加特殊的函数库。 这种方法的问题在于只是在很少的库函数中实现了并行性，而大量的程序代码仍然是串行的。 第二种方法是为编程语言增加包括通信和控制原语的库函数。 程序员仍然使用传统的编程语言编程，但是程序员需要使用这些原语来创建和管理并行性。 第三种方法是为现有的编程语言增加一些特殊的结构，比如可以很容易地创建新的并行进程的能力，并行执行循环的能力和同时对一个向量的所有元素执行算术运算的能力。 第四种方法是发明一种全新的用于并行处理的语言。 使用新语言的一个显而易见的优势是这样的语言肯定很适合于并行处理，但是缺点也同样明显，程序员必须学习一种新语言。 P344 59 本章主要内容 并行计算机系统结构概述 并行计算机系统的设计问题。