第八章基本通讯操作精选文档.ppt

《第八章基本通讯操作精选文档.ppt》由会员分享，可在线阅读，更多相关《第八章基本通讯操作精选文档.ppt（39页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第八章基本通讯操作本讲稿第一页，共三十九页第三篇 并行数值算法 第八章 基本通讯操作 第九章 稠密矩阵运算 第十章 线性方程组的求解 第十一章 快速傅里叶变换 本讲稿第二页，共三十九页第八章 并行数值算法 8.0 预备知识 8.1 选路方法与开关技术 8.2 单一信包一到一传输 8.3 一到多播送 8.4 多到多播送 本讲稿第三页，共三十九页 预备知识选路(Routing)又称为选径或路由。产生消息从发源地到目的地所取的又称为选径或路由。产生消息从发源地到目的地所取的路径路径,要求具有较低通讯延迟、无死锁和容错能力。应用要求具有较低通讯延迟、无死锁和容错能力。应用于网络或并行机上的信息交换。于

2、网络或并行机上的信息交换。消息、信包、片 消息消息(Message)(Message)：是在多计算机系统的处理接点之间传递包含数：是在多计算机系统的处理接点之间传递包含数据和同步消息的信息包。它是一种逻辑单位，可由任意数量的据和同步消息的信息包。它是一种逻辑单位，可由任意数量的包构成。包构成。包包(Packet)(Packet)：包的长度随协议不同而不同，它是信息传送的最小：包的长度随协议不同而不同，它是信息传送的最小单位，单位，64-51264-512位。位。片片(Flit)(Flit)：片的长度固定，一般为：片的长度固定，一般为8 8位。位。本讲稿第四页，共三十九页预备知识消息、信包、片的

3、相互关系包包消息消息包包据据片片头片头片尾片尾片 顺序号顺序号数数片片F F F F F F F F F F F F F F F F本讲稿第五页，共三十九页 预备知识一些术语 信道带宽信道带宽b b：每个信道有：每个信道有w w位宽和信号传输率位宽和信号传输率f f=1/t(t=1/t(t是时钟周是时钟周期期),),b=wf bits/secb=wf bits/sec 节点和开关的度：与节点和开关相连的信道数目节点和开关的度：与节点和开关相连的信道数目 路径：信包在网络中走过的开关和链路路径：信包在网络中走过的开关和链路(link)(link)序列序列 路由长度或距离：路由路径中包括的链路路由

4、长度或距离：路由路径中包括的链路(link)(link)数目数目信包传输性能参数 启动时间启动时间t ts s(startup timestartup time)：准备包头信息等：准备包头信息等 节点延迟时间节点延迟时间t th h(per-hop timeper-hop time)：包头穿越相邻节点的时间：包头穿越相邻节点的时间 字传输时间字传输时间t tw w(transfer timetransfer time)：传输每个字的时间：传输每个字的时间 链路数链路数l l、信包大小、信包大小mm本讲稿第六页，共三十九页 预备知识选路算法的三种机制 基于算术的基于算术的:开关中具有简单的算术运

5、算功能，如维序开关中具有简单的算术运算功能，如维序选路；选路；基于源地址的基于源地址的:在源点时就将沿路径的各个开关的输出端口在源点时就将沿路径的各个开关的输出端口地址地址p p0 0,p,p1 1,p,pn n包在信包的头部，每个开关只是对信包包在信包的头部，每个开关只是对信包头的输出端口地址进行剥离；头的输出端口地址进行剥离；基于查表的基于查表的:开关中含有一个选路表，对信包头中的选开关中含有一个选路表，对信包头中的选路域查出输出端口地址。路域查出输出端口地址。本讲稿第七页，共三十九页 预备知识 选路方式选路方式 本讲稿第八页，共三十九页第八章 并行数值算法 8.0 预备知识 8.1 选路

6、方法与开关技术 8.2 单一信包一到一传输 8.3 一到多播送 8.4 多到多播送 本讲稿第九页，共三十九页8.1 选路方法与开关技术 8.1.1 选路方法 8.1.2 开关技术本讲稿第十页，共三十九页 选路方法分类 最短路径最短路径/非最短路径非最短路径(贪心选路贪心选路/随机选路随机选路)，如维序选路是贪心的，二阶段维序选路是随机的如维序选路是贪心的，二阶段维序选路是随机的 确定选路确定选路/自适应选路自适应选路(寻径确定寻径确定/寻径视网络状况寻径视网络状况)维序选路(Dimension-Ordered Routing)(Dimension-Ordered Routing)：一种确定的最

7、短路径选路一种确定的最短路径选路 二维网孔中的维序选路二维网孔中的维序选路:X-Y:X-Y选路选路 超立方中的维序选路超立方中的维序选路:E-:E-立方选路立方选路 本讲稿第十一页，共三十九页 选路方法X-Y选路算法 算法算法8.18.1：二维网孔上的：二维网孔上的X-YX-Y选路算法选路算法 beginbegin step1:step1:沿沿X X方向将信包送至目的地处理器所在的列方向将信包送至目的地处理器所在的列 step2:step2:沿沿Y Y方向将信包送至目的地处理器所在的行方向将信包送至目的地处理器所在的行 end end本讲稿第十二页，共三十九页 选路方法例8.1(P186)(P

8、186)本讲稿第十三页，共三十九页 选路方法E-立方选路算法 路由计算：路由计算：s sn-1n-1s sn-2n-2ss1 1s s0 0(源地址源地址)异或异或 d dn-1n-1d dn-2n-2dd1 1d d0 0(目的地址目的地址)r rn-1 n-1 r rn-2 n-2 rr1 1 r r0 0(路由值路由值)路由过程：路由过程：s sn-1n-1s sn-2n-2ss1 1s s0 0 s sn-1n-1s sn-2n-2ss1 1s s0 0 r r0 0 s sn-1n-1s sn-2n-2ss1 1s s0 0 r r1 1 算法算法8.2 8.2：超立方网络上的：超立

9、方网络上的E-E-立方选路算法立方选路算法(P186)(P186)本讲稿第十四页，共三十九页 选路方法例8.2(P187)(P187)0110(S)0110(S)1101(D)1101(D)1011(R)1011(R)本讲稿第十五页，共三十九页8.1 选路方法与开关技术 8.1.1 选路方法 8.1.2 开关技术本讲稿第十六页，共三十九页 开关技术存储转发(Store-and-Forward)(Store-and-Forward)选路 消息被分成基本的传输单位消息被分成基本的传输单位-信包信包(Packet),(Packet),每个信包都含每个信包都含有寻径信息；有寻径信息；当一个信包到达中间

10、节点当一个信包到达中间节点A A时，时，A A把整个信包放入其通信缓冲器把整个信包放入其通信缓冲器中，然后在选路算法的控制下选择下一个相邻节点中，然后在选路算法的控制下选择下一个相邻节点B B，当从，当从A A到到B B的通道空闲并且的通道空闲并且B B的通信缓冲器可用时，把信包从的通信缓冲器可用时，把信包从A A发向发向B B；信包的传输时间信包的传输时间:t tcommcomm (SF)=(SF)=t ts s+(+(mtmtww+t+th h)l=Ol=O(mlml)缺点：缺点：每个结点必须对整个消息和信包进行缓冲，缓冲器较大；每个结点必须对整个消息和信包进行缓冲，缓冲器较大；网络时延与

11、发送消息所经历的节点数成正比网络时延与发送消息所经历的节点数成正比本讲稿第十七页，共三十九页 开关技术切通(Cut Through)(Cut Through)选路 在传递一个消息之前，就为它建立一条从源结点到目的结点在传递一个消息之前，就为它建立一条从源结点到目的结点的物理通道。在传递的全部过程中，线路的每一段都被占用，的物理通道。在传递的全部过程中，线路的每一段都被占用，当消息的尾部经过网络后，整条物理链路才被废弃。当消息的尾部经过网络后，整条物理链路才被废弃。传输时间传输时间:t tcommcomm (CT)=(CT)=t ts s+mtmtww+lt+lth h=O=O(m+lm+l)缺

12、点：缺点：物理通道非共享物理通道非共享 传输过程中物理通道一直被占用传输过程中物理通道一直被占用本讲稿第十八页，共三十九页 开关技术虫孔(Wormhole)(Wormhole)选路 DallyDally于于19861986年提出，利用了前二种方法的优点，减少了缓冲年提出，利用了前二种方法的优点，减少了缓冲区，提高了物理通道的利用。区，提高了物理通道的利用。首先把一个消息分成许多很小的片，消息的首先把一个消息分成许多很小的片，消息的头片头片包含了这个包含了这个消息的所有寻径信息。消息的所有寻径信息。尾片尾片是一个其最后包含了消息结束是一个其最后包含了消息结束符的片。中间的片均为符的片。中间的片均

13、为数据片数据片；片是最小信息单位。每个结点上只需要缓冲一个片就能满足要求；片是最小信息单位。每个结点上只需要缓冲一个片就能满足要求；用一个头片直接牵引一条从输入链路到输出链路的路径的方法用一个头片直接牵引一条从输入链路到输出链路的路径的方法来进行操作。每个消息中的片以流水的方式在网络中向前来进行操作。每个消息中的片以流水的方式在网络中向前“蠕蠕动动”。每个片相当于。每个片相当于WormWorm的一个节，的一个节，“蠕动蠕动”以节为单位顺以节为单位顺序地向前爬行。当消息的尾片向前序地向前爬行。当消息的尾片向前“蠕动蠕动”一步后，它刚才所一步后，它刚才所占用的结点就被放弃了。占用的结点就被放弃了。

14、本讲稿第十九页，共三十九页 开关技术虫孔(Wormhole)(Wormhole)选路 优点：优点：(1)(1)每个结点的缓冲器的需求量小每个结点的缓冲器的需求量小，易于用，易于用VLSIVLSI实现；实现；(2)(2)较低的网络传输延迟较低的网络传输延迟。存储转发传输延迟基本上正比。存储转发传输延迟基本上正比于消息在网络中传输的距离于消息在网络中传输的距离;Wormhole;Wormhole与线路开关的网与线路开关的网络传输延迟正比于消息包的长度，传输距离对它的影响络传输延迟正比于消息包的长度，传输距离对它的影响很小（消息包较长时的情况）；很小（消息包较长时的情况）；(3)(3)通道共享性好、

15、利用率高通道共享性好、利用率高；(4)(4)易于实现易于实现MulticastMulticast和和BroadcastBroadcast。本讲稿第二十页，共三十九页 开关技术几种开关技术的时空图 本讲稿第二十一页，共三十九页第八章 并行数值算法 8.0 预备知识 8.1 选路方法与开关技术 8.2 单一信包一到一传输 8.3 一到多播送 8.4 多到多播送 本讲稿第二十二页，共三十九页 单一信包一到一传输距离l的计算：对于p个处理器 一维环形：一维环形：带环绕带环绕Mesh()Mesh()：超立方：超立方：t tcommcomm(SF)(SF)的计算(可由可由(8.1b)(8.1b)式得到式得

16、到)一维环形：一维环形：带环绕带环绕MeshMesh：超立方：超立方：t tcommcomm(CT)(CT)的计算(可由可由(8.2b)(8.2b)式得到式得到)如果mpmp：t tcommcomm(SF)t(SF)tcommcomm(CT)=t(CT)=ts s+mt+mtww本讲稿第二十三页，共三十九页第八章 并行数值算法 8.0 预备知识 8.1 选路方法与开关技术 8.2 单一信包一到一传输 8.3 一到多播送 8.4 多到多播送 本讲稿第二十四页，共三十九页8.3 一到多播送 8.3.1 SF模式 8.3.2 CT模式本讲稿第二十五页，共三十九页 一到多播送SF模式环 步骤：步骤：先

17、左右邻近传送先左右邻近传送;再左右二个方向同时播送再左右二个方向同时播送 示例：示例：通讯时间：通讯时间：本讲稿第二十六页，共三十九页 一到多播送SF模式环绕网孔 步骤：步骤：先完成一行中的播送先完成一行中的播送;再同时进行各列的播送再同时进行各列的播送 示例：示例：共共4 4步步(2(2步行、步行、2 2步列步列)通讯时间：通讯时间：本讲稿第二十七页，共三十九页 一到多播送SF模式超立方 步骤：从低维到高维，依次进行播送步骤：从低维到高维，依次进行播送;示例：示例：通讯时间：通讯时间：本讲稿第二十八页，共三十九页8.3 一到多播送 8.3.1 SF模式 8.3.2 CT模式本讲稿第二十九页，

18、共三十九页 一到多播送CT模式环 步骤：步骤：(1)(1)先发送至先发送至p/2p/2远的处理器远的处理器;(2)(2)再同时发送至再同时发送至p/2p/22 2远的处理器远的处理器;(i)(i)再同时发送至再同时发送至p/2p/2i i远的处理器远的处理器;示例：图示例：图8.88.8 通讯时间：通讯时间：本讲稿第三十页，共三十九页 一到多播送CT模式网孔 步骤：步骤：(1)(1)先进行行播送先进行行播送;(2)(2)再同时进行列播送再同时进行列播送;示例：图示例：图8.98.9 通讯时间：通讯时间：本讲稿第三十一页，共三十九页 一到多播送CT模式超立方 步骤：步骤：依次从低维到高维播送依次

19、从低维到高维播送,d-,d-立方立方,d=0,1,2,3,4;,d=0,1,2,3,4;通讯时间：通讯时间：本讲稿第三十二页，共三十九页第八章 并行数值算法 8.0 预备知识 8.1 选路方法与开关技术 8.2 单一信包一到一传输 8.3 一到多播送 8.4 多到多播送 本讲稿第三十三页，共三十九页8.3 一到多播送 8.3.1 SF模式 8.3.2 CT模式本讲稿第三十四页，共三十九页 多到多播送SF模式环 步骤：步骤：同时向右同时向右(或左或左)播送播送 刚接收到的信包刚接收到的信包 示例：图示例：图8.108.10 通讯时间：通讯时间：已有数据已有数据第第2步传送数据步传送数据2本讲稿第三十五页，共三十九页 多到多播送SF模式环绕网孔 步骤：步骤：(1)(1)先进行行的播送；先进行行的播送；(2)(2)再进行列的播送；再进行列的播送；示例：图示例：图8.118.11 通讯时间：通讯时间：本讲稿第三十六页，共三十九页 多到多播送SF模式超立方 步骤：步骤：依次按维进行依次按维进行 多到多的播送；多到多的播送；示例：图示例：图8.128.12 通讯时间：通讯时间：本讲稿第三十七页，共三十九页8.3 一到多播送 8.3.1 SF模式 8.3.2 CT模式本讲稿第三十八页，共三十九页 多到多播送CT模式 使用一到多的策略会造成链路竞争 本讲稿第三十九页，共三十九页