燕山大学研一计算机专业 并行处理与体系结构PC2-网络互联部分.ppt

2.3.4包冲突的解决 1.问题的提出 两个相邻结点间要传送包，必须具备下列三个条件： （1）源缓冲区已存该包 （2）通道已分配好 （3）接收缓冲区准备接收 当两个包到达同一个结点时，可能请求同一个接收缓冲区或用同一个输出通道： （1）把通道分配给哪个包？ （2）没有分配到通道的包怎么办？ 2.四种解决方法 （1）用缓冲实现虚拟直通寻径 包缓冲区 包2 包1 输出通道 片缓冲区 将通道分配给包1，缓冲包2 好处：不会浪费已经分配的资源 缺点：需要一个能存放整个包的缓冲区，包缓冲区不可能做在寻径芯片上，要用存储器作为缓冲区，会有较大的存储延迟。 （2）阻塞流控制（Wormhole寻径） 包2 包1 输出通道 片缓冲区 第二个包被阻塞不再前进，但没有被扬弃 控制 门 （3）扬弃并重发 包2 包1 输出通道 片缓冲区 第二个包被扬弃 （3）阻塞后绕道 包2 包1 输出通道 片缓冲区 第二个包绕道：被转发到其它的寻径器 绕道通道 2.3.5维序寻径 1.寻径方式 确定寻径（deterministic routing）： 通信路径完全由源和目的地址确定。（换句话说，寻找的路径是预先唯一确定的，与网络的状况无关）。 自适应寻径（adaptive routing）： 与网络的状况有关，可能会有几条路径。（需要消除死锁的算法）。 2.两种确定寻径算法（维序寻径） （1）二维网格中的X-Y寻径： 首先沿着X维方向确定路径，然后沿着Y维方向选择路径。 假定从任意源结点s = ( X1 Y1 )到任意目的结点 d = ( X2 Y2 )。寻径从s开始，首先沿着X方向前进一直到d所在的第X2列为止，然后沿Y方向前进直到d。 四种模式： 东—北，东—南，西—北，西—南。 下面是一个例子： 0,7 1,7 2,7 3,7 4,7 4,6 7,6 1,5 4,5 7,5 1,4 2,4 3,4 4,4 5,4 7,4 1,3 2,3 3,3 4,3 5,3 6,3 7,3 2,2 4,2 7,2 2,1 3,1 4,1 5,1 6,1 7,1 2,0 Y X 东—北：( 2 , 1 ) ? ( 7 , 6 ) 西—南：( 5 , 4 ) ? ( 2 , 0 ) 东—南：( 0 , 7 ) ? ( 4 , 2 ) 西—北：( 6 , 3 ) ? ( 1 , 5 ) 特点： 总是先沿X维方向寻径，然后再沿Y维方向寻径，寻径不会出现死锁或循环等待现象。 可以扩充到n维网络，如X-Y-Z等等。 可用于存储转发或Wormhole寻径网络，在源和目的结点之间形成一条距离最短的路径。 第2章 互连与通信 2.3 通信问题 2.3.1 基本术语与性能指标 2.3.2 寻径算法 2.3.3 虚拟通道与死锁 2.3.4 包冲突的解决 2.3.5 维序寻径 2.3.6 通信模式 2.3 通信问题 2.3.1基本术语与性能指标 1.消息、包和片 消息（Message）：是在多计算机系统的处理结点之间传递包含数据和同步消息的信息包。它是一种逻辑单位，可由任意数量的包构成。 包（Packet）：包的长度随协议不同而不同，它是信息传送的最小单位，64-512位。 片（Flit）：片的长度固定，一般为8位。 它们的相互关系如下图： 包 …… 消息 包 片 据 片 头片 尾片 …… 顺序号 数 b b b b b b b b 2.互连网络 互连网络用来在多计算机系统的处理结点之间传递消息。互连网络的描述： 拓扑（Topology） 寻径算法（Routing） 流控制（Flow Control） 互连网络性能的两个重要指标： 传输时延（Transmission Latency） 吞吐量（Throughput） 3.传输时延与吞吐量 一个消息的传输时延：从它在源结点进行发送初始化到它在目的结点完整的被接收所耗费的时间。 一个网络的传输时延：在一定条件下发送消息的平均时延。 网络的吞吐量：单位时间内网络所能传输的消息数目或长度。 4.传输时延的公式 其中，Ts称为建立时延，Tn称为网络时延，Tb称为阻塞时延。 它们具体定义如下： 网络时延Tn：消息头部从源结点进入网络到消息的尾部到达目的结点的时间间隔。 其中： Tp?D称为结点时延：其中Tp是消息在它所经过的路径上的每个中间结点上的平均时延， D为中间结点