ch3-第三章互连与通信讲解.ppt

第三章 互连与通信 3.1 互连网络的作用 3.2 静态网络 3.3 动态网络 3.4 通信问题 3.1 互连网络的作用 定义：由开关元件按一定拓扑结构和控制方式构成的网络以实现计算机系统内部多个处理机或多个功能部件间的相互连接。 操作方式： 同步通信（Synchronous Communication) 异步通信(Asynchronous Communication) 控制策略： 集中控制(Centralized control) 分布控制(Distributed control) 第三章 互连与通信 3.1 互连网络的作用 3.2 静态网络 3.2.1 静态网络的特点与指标 3.2.2 典型的静态网络 3.3 动态网络 3.4 通信问题 第三章 互连与通信 3.1 互连网络的作用 3.2 静态网络 3.3 动态网络 3.3.1 互连函数 3.3.2 多级互联网络 3.4 通信问题 第三章 互连与通信 3.1 互连网络的作用 3.2 静态网络 3.3 动态网络 3.4 通信问题 3.4.1 基本术语与性能指标 3.4.2 寻径算法 3.4.3 虚拟通道与死锁 3.4.4 包冲突的解决 3.4.5 维序寻径 3.4.6 通信模式 3.传输时延与吞吐量 一个消息的传输时延：从它在源结点进行发送初始化到它在目的结点完整的被接收所耗费的时间。 一个网络的传输时延：在一定条件下发送消息的平均时延。 网络的吞吐量：单位时间内网络所能传输的消息数目或长度。 4.传输时延的公式 其中，Ts称为建立时延，Tn称为网络时延，Tb称为阻塞时延。 它们具体定义如下： 建立时延Ts：一个消息在源结点和目的结点上装配和分解、从存储器拷贝到通信缓冲区以及正确性验证等所耗费的时间。它和机器本身的硬件、软件技术有关。 其中： Tss称为源结点时延：从发送进程开始消息发送初始化到消息的头部进入网络所经历的时间。 Tsd称为目的结点时延：从消息的尾部到达目的结点到消息完全被接收进程接收所经历的时间。 网络时延Tn：消息头部从源结点进入网络到消息的尾部到达目的结点的时间间隔。 其中： Tp?D称为结点时延：其中Tp是消息在它所经过的路径上的每个中间结点上的平均时延， D为中间结点或源结点与目的结点之间的距离。 L/B称为线路时延：其中L为消息长度， B为结点之间的通道带宽。 阻塞时延Tb：消息传递过程中其他所有可能的时延（主要原因是资源冲突）。 5.网络的拓扑结构 第一代并行计算机：HyperCube 第二代并行计算机：n—Mesh 6.网络的寻径算法 决定发送一个消息到其目的地所经过的路径。 可以分为： 最短路径算法 非最短路径算法 或者： 确定性算法：路径的选择只依赖于它所发送的消息的源结点和目的结点。 可适应算法：消息从结点A到结点B可以由几条不同的路径。 7.网络的流控制 当一个消息在网络中沿着某条路径传送时，互连网络如何来为它分配通道和缓冲器。 3.4.2寻径算法 我们介绍四种寻径方式： 存储转发（Store-and-Forward） 虚拟直通（Virtual cut through） 线路交换（Circuit Switching） Wormhole交换（Wormhole Switching) 1.存储转发 当一个消息到达中间结点A时，A把整个消息放入其通信缓冲器中，然后在寻径算法的控制下选择下一个相邻结点B，当从A到B的通道空闲并且B的通信缓冲器可用时，把消息从A发向B。 缺点： 每个结点必须对整个消息进行缓冲，缓冲器较大。 网络时延与发送消息所经历的结点数成正比 2.虚拟直通 中间结点没有必要等到整个消息全部被缓冲后再作出路由选择，只要消息的目的信息域可用后，就可以作出路由选择。 其中，Lh为消息头部开始到其目的信息域的长度，显然有L Lh，所以D的影响比较小。 而当通向下一结点的通道忙或结点的缓冲器非空闲时，必须把整个消息缓冲起来，这时和存储转发一样。 3.线路开关 在传递一个消息之前，就为它建立一条从源结点到目的结点的物理通道。在传递的全部过程中，线路的每一段都被占用，当消息的尾部经过网络后，整条物理链路才被废弃。 其中，Lc是为消息建立物