第八章 基本通讯操作

1、并行计算，第3章并行数值算法，第8章基本通信操作，第9章密集矩阵操作，第10章求解线性方程，第11章快速傅立叶变换，第8章并行数值算法，第8.0章初步知识，第8.1章路由方法和交换技术，第8.2章单包一对一传输，第8.3章一对多广播，第8.4章多对多广播，国家高性能计算中心(合肥)，第4，2020/8/4章初步知识，要求具有低通信延迟，无死锁和容错能力，以生成消息从适用于网络或并行计算机上的信息交换。报文、数据包和消息：它是指在多计算机系统的处理节点之间传输的包含数据和同步消息的信息包。它是一个逻辑单元，可以由任意数量的包组成。数据包：数据包的长度因协议不同而不同，它是信息传输的最小单位，为6

2、4-512位。片：片的长度是固定的，通常是8位。国家高性能计算中心(合肥)，5，2020/8/4，初步知识，消息、数据包和电影之间的关系，国家高性能计算中心(合肥)，6，2020/8/4，初步知识，某些术语信道带宽B:每个信道具有w位宽和信号传输速率f=1/t (t B=wf比特/秒节点和交换机的度数：连接到节点和交换机的信道数；路径：数据包在网络中传输的交换和链接序列；路由长度或距离：路由路径中包含的链路数量；分组传输性能参数启动时间ts(启动时间) :准备分组报头信息等。节点延迟时间th(每跳时间):数据包报头经过相邻节点的时间字传输时间tw(传输时间):用于传输每个字的时间链路号l，数据

3、包大小m，国家高性能计算中心(合肥)，7，2020/8/4，初步知识，路由算法的三种机制：交换机基于算术具有简单的算术运算功能。基于源地址的：将每个交换机的输出端口地址P0、P1、PN沿路径打包在源点的数据包报头中，每个交换机只剥离出数据包报头的输出端口地址；基于查找表的：交换机包含一个路由表，用于在报头的路由字段中找出输出端口的地址。，国家高性能计算中心(合肥)，2020年8月4日，初步知识，路由模式，第8章并行数值算法8.0初步知识8.1路由方法和交换技术8.2单包一对一传输8.3一对多广播8.4多对多广播8.1路由方法和交换技术8.1.1路由方法8.1.2交换技术，国家高性能计算中心(合

4、肥)，11，2020/8/4，路由方法，最短路径/非最短路径分类两阶段维有序路由是随机确定性路由/自适应路由(路由是确定性的/路由取决于网络条件):确定性最短路径路由，二维网格中的维有序路由， X-Y路由，超立方体中的维有序路由，3360e立方路由，国家高性能计算中心(合肥)，2020年8月12日4日，路由方法， X-Y路由算法算法8.1:二维网格上的X-Y路由算法开始步骤1:将数据包发送到目的处理器沿X方向所在的列，步骤2:将数据包发送到目的处理器沿Y方向末端所在的行，国家高性能计算中心(合肥)，2020年8月13日/。 例8.1 (P186)，国家高性能计算中心(合肥)，14，2020/8

5、/4，路由方法，e-cube路由算法的路由计算：sn-1sn-2s1s0(源地址)异或dn-1dn-2d1d0(目的地址)rn-1 rn-2 r1 r0(路由值)路由过程：sn-1sn-2s s0sn-1sn-2s 1s 0 r0 sn-1sn-2s 1s 0 R1算法8.2:超立方体网络上的e-cube路由算法(P188) 存储转发路由消息被划分为基本的传输单元数据包，当数据包到达中间节点A时，A将整个数据包放入其通信缓冲区，然后在路由算法的控制下选择下一个相邻的节点B。 当甲到乙的信道空闲且乙的通信缓冲区可用时，甲向乙发送数据包；该数据包的传输时间为：命令(SF)=ts (mtw th)l

6、=O(ml)。缺点：每个节点必须缓冲整个消息和数据包，而且缓冲区很大；网络延迟与发送消息的节点数成正比。国家高性能计算中心(合肥)，18，2020/8/4，交换技术，直通路由，在传输消息之前建立从源节点到目的节点的物理信道。在整个传输过程中，线路的每一段都被占用，整个物理链路在消息尾部通过网络后被丢弃。传输时间： tcomm (CT)=ts mtw lth=O(m l)缺点：在物理信道的非共享传输过程中，物理信道总是被占用。国家高性能计算中心(合肥)，2020年8月4日，19日，交换技术，虫洞路由磨利在1986年提出，使用前两种方法。首先，一条消息被分成许多小段，消息的头段包含消息的所有路由信

7、息。预告片是在结尾包含消息终止符的预告片。中间的切片都是数据切片；切片是最小的信息单位。每个节点上只需要缓冲一个切片就可以满足要求；标头用于直接将路径从输入链接拉至输出链接。每个消息中的片段以流水线方式在网络中“爬行”。每个切片相当于一个Worm部分，“爬行”以部分为单位按顺序向前爬行。当消息的尾部“向前爬行”时，它刚才占用的节点被放弃。国家高性能计算中心(合肥)，20，2020/8/4，交换技术，虫洞路由优势：(1)每个节点的缓冲需求小，易于用超大规模集成电路实现；(2)降低网络传输延迟。存储转发传输延迟基本上与网络中消息传输的距离成正比；虫洞与线路交换机之间的网络传输时延与报文长度成正比，

8、传输距离对其影响很小(报文较长时)；(3)渠道共享性好，利用率高；(4)易于实现组播和广播。国家高性能计算中心(合肥)，21，2020/8/4，交换技术，时空图的几种交换技术，第8章并行数值算法8.0先决知识8.1路由方法和交换技术8.2单个数据包的一对一传输8.3一对多广播8.4多对多广播，国家高性能计算中心(合肥)，23，2020/8/4距离l的计算：对于p处理器，一维环的计算：带环绕的网格():超立方体：tcomm 一维环的计算：带环绕的网格：超立方体：tcomm(CT)(可由公式(8.2b)得到)如果MP: tcomm (SF) tcomm，第8章并行数值算法8.0初步知识8.1路由方

9、法和交换技术8.2单包一对一传输8.3一对多广播8.4多对多广播8.3一对多广播8.3.1 SF模式8.3.2 CT模式，国家高性能计算中心(合肥) 循环步骤：第一个左右相邻的左右方向同时广播示例：通信时间：国家高性能计算中心(合肥)，2020年8月4日，一对多广播SF模式，环绕网格步骤：首先完成一行广播； 然后同时广播每一列的例子：共4步(2步，2步)通信时间：国家高性能计算中心(合肥)，28，2020/8/4，一对多广播SF模式，超立方体步骤：从低维到高维，依次广播；示例：通信时间：8.3一对多广播8.3.1 SF模式，8.3.2 CT模式，国家高性能计算中心(合肥)，30，2020/8/

10、4，一对多广播CT模式，循环步骤：(1)发送到远离p/2的处理器；(2)同时将其发送到远离p/22的处理器；(I)同时将其发送到远离p/2i的处理器；示例：图8.8通信时间：国家高性能计算中心(合肥)，2020年8月4日31日，一对多广播CT模式，网状步骤：(1)高级线对线广播；(2)同时进行栏目播出；示例：图8.9通信时间：国家高性能计算中心(合肥)，2020年8月4日，32日，一对多广播CT模式，超立方体步骤：从低维到高维依次广播，d- cube，d=0，1，2，3，4；通信时间：第8章并行数值算法8.0初步知识8.1路由方法和交换技术8.2单包一对一传输8.3一对多广播8.4多对多广播8.3一对多广播8.3.1 SF模式8.3.2 CT模式，国家高性能计算中心(合肥)，35，2020/8/4，多对多广播SF模式，振铃步骤：同时向右侧(或左侧)广播新接收的包。示例：图8.10通信时间：现有数据，步骤2，数据传输2，国家高性能计算中心(合肥)，36，2020/8/4，多对多广播SF模式，围绕网格步骤：(1)高级线路广播；(2)再次广播