第八章 基本通讯操作

并行计算,第一级,第二级,第三级,第一级,第二级,第三级,国家高性能计算中心（合肥）,*,*,并 行 计 算,第三篇 并行数值算法,第八章,基本通讯操作,第九章 稠密矩阵运算,第十章 线性方程组的求解,第十一章 快速傅里叶变换,第八章 并行数值算法,8.0,预备知识,8.1,选路方法与开关技术,8.2,单一信包一到一传输,8.3,一到多播送,8.4,多到多播送,预备知识,选路,(Routing),又称为选径或路由。产生消息从发源地到目的地所取的路径,要求具有较低通讯延迟、无死锁和容错能力。应用于网络或并行机上的信息交换。,消息、信包、片,消息,(Message),：是在多计算机系统的处理接点之间传递包含数据和同步消息的信息包。它是一种逻辑单位，可由任意数量的包构成。,包,(Packet),：包的长度随协议不同而不同，它是信息传送的最小单位，,64-512,位。,片,(Flit),：片的长度固定，一般为,8,位。,2024/10/1,4,国家高性能计算中心（合肥）,预备知识,消息、信包、片,的相互关系,包,消息,包,据,片,头片,尾片,顺序号,数,片,F,F,F,F,F,F,F,F,2024/10/1,5,国家高性能计算中心（合肥）,预备知识,一些术语,信道带宽,b,：每个信道有,w,位宽和信号传输率,f,=1/t(t,是时钟周期,),b=,wf,bits/sec,节点和开关的度：与节点和开关相连的信道数目,路径：信包在网络中走过的开关和链路,(link),序列,路由长度或距离：路由路径中包括的链路,(link),数目,信包传输性能参数,启动时间,t,s,(,startup,time,),：准备包头信息等,节点延迟时间,t,h,(,per,-hop time,),：包头穿越相邻节点的时间,字传输时间,t,w,(,transfer,time,),：传输每个字的时间,链路数,l,、信包大小,m,2024/10/1,6,国家高性能计算中心（合肥）,预备知识,选路算法的三种机制,基于算术的,:,开关中具有简单的算术运算功能，如维序选路；,基于源地址的,:,在源点时就将沿路径的各个开关的输出端口地址,p,0,p,1,p,n,包在信包的头部，每个开关只是对信包头的输出端口地址进行剥离；,基于查表的,:,开关中含有一个选路表，对信包头中的选路域查出输出端口地址。,2024/10/1,7,国家高性能计算中心（合肥）,预备知识,选路方式,2024/10/1,8,国家高性能计算中心（合肥）,第八章 并行数值算法,8.0,预备知识,8.1,选路方法与开关技术,8.2,单一信包一到一传输,8.3,一到多播送,8.4,多到多播送,8.1,选路方法与开关技术,8.1.1,选路方法,8.1.2,开关技术,选路方法,分类,最短路径,/,非最短路径,(,贪心选路,/,随机选路,),，,如维序选路是贪心的，二阶段维序选路是随机的,确定选路,/,自适应选路,(,寻径确定,/,寻径视网络状况,),维序选路,(Dimension-Ordered Routing),：,一种确定的最短路径选路,二维网孔中的维序选路,:X-Y,选路,超立方中的维序选路,:E-,立方选路,2024/10/1,11,国家高性能计算中心（合肥）,选路方法,X-Y,选路算法,算法,8.1,：二维网孔上的,X-Y,选路算法,begin,step1:,沿,X,方向将信包送至目的地处理器所在的列,step2:,沿,Y,方向将信包送至目的地处理器所在的行,end,2024/10/1,12,国家高性能计算中心（合肥）,选路方法,例,8.1,(P186),2024/10/1,13,国家高性能计算中心（合肥）,选路方法,E-,立方选路算法,路由计算：,s,n-1,s,n-2,s,1,s,0,(,源地址,),异或,d,n-1,d,n-2,d,1,d,0,(,目的地址,),r,n-1,r,n-2,r,1,r,0,(,路由值,),路由过程：,s,n-1,s,n-2,s,1,s,0,s,n-1,s,n-2,s,1,s,0,r,0,s,n-1,s,n-2,s,1,s,0,r,1,算法,8.2,：超立方网络上的,E-,立方选路算法,(P186),2024/10/1,14,国家高性能计算中心（合肥）,选路方法,例,8.2,(P187),0110(S),1101(D),1011(R),2024/10/1,15,国家高性能计算中心（合肥）,8.1,选路方法与开关技术,8.1.1,选路方法,8.1.2,开关技术,开关技术,存储转发,(Store-and-Forward),选路,消息被分成基本的传输单位,-,信包,(Packet),每个信包都含有寻径信息；,当一个信包到达中间节点,A,时，,A,把整个信包放入其通信缓冲器中，然后在选路算法的控制下选择下一个相邻节点,B,，当从,A,到,B,的通道空闲并且,B,的通信缓冲器可用时，把信包从,A,发向,B,；,信包的传输时间,:,t,comm,(SF)=,t,s,+(,mt,w,+,t,h,),l,=,O,(,ml,),缺点：,每个结点必须对整个消息和信包进行缓冲，缓冲器较大；,网络时延与发送消息所经历的节点数成正比,2024/10/1,17,国家高性能计算中心（合肥）,开关技术,切通,(,Cut Through,),选路,在传递一个消息之前，就为它建立一条从源结点到目的结点的物理通道。在传递的全部过程中，线路的每一段都被占用，当消息的尾部经过网络后，整条物理链路才被废弃。,传输时间,:,t,comm,(CT)=,t,s,+,mt,w,+,lt,h,=,O,(,m+l,),缺点：,物理通道非共享,传输过程中物理通道一直被占用,2024/10/1,18,国家高性能计算中心（合肥）,开关技术,虫孔,(,Wormhole,),选路,Dally,于,1986,年提出，利用了前二种方法的优点，减少了缓冲区，提高了物理通道的利用。,首先把一个消息分成许多很小的片，消息的,头片,包含了这个消息的所有寻径信息。,尾片,是一个其最后包含了消息结束符的片。中间的片均为,数据片,；,片是最小信息单位。每个结点上只需要缓冲一个片就能满足要求；,用一个头片直接牵引一条从输入链路到输出链路的路径的方法来进行操作。每个消息中的片以流水的方式在网络中向前,“,蠕动,”,。每个片相当于,Worm,的一个节，,“,蠕动,”,以节为单位顺序地向前爬行。当消息的尾片向前,“,蠕动,”,一步后，它刚才所占用的结点就被放弃了。,2024/10/1,19,国家高性能计算中心（合肥）,开关技术,虫孔,(,Wormhole,),选路,优点：,(1),每个结点的缓冲器的需求量小,，易于用,VLSI,实现；,(2),较低的网络传输延迟,。存储转发传输延迟基本上正比于消息在网络中传输的距离,;Wormhole,与线路开关的网络传输延迟正比于消息包的长度，传输距离对它的影响很小（消息包较长时的情况）；,(3),通道共享性好、利用率高,；,(4),易于实现,Multicast,和,Broadcast,。,2024/10/1,20,国家高性能计算中心（合肥）,开关技术,几种开关技术的时空图,2024/10/1,21,国家高性能计算中心（合肥）,第八章 并行数值算法,8.0,预备知识,8.1,选路方法与开关技术,8.2,单一信包一到一传输,8.3,一到多播送,8.4,多到多播送,单一信包一到一传输,距离,l,的计算：,对于,p,个处理器,一维环形：,带环绕,Mesh(),：,超立方：,t,comm,(SF,),的计算,(,可由,(8.1b),式得到,),一维环形：,带环绕,Mesh,：,超立方：,t,comm,(CT,),的计算,(,可由,(8.2b),式得到,),如果,mp,：,t,comm,(SF,),t,comm,(CT,)=,t,s,+mt,w,2024/10/1,23,国家高性能计算中心（合肥）,第八章 并行数值算法,8.0,预备知识,8.1,选路方法与开关技术,8.2,单一信包一到一传输,8.3,一到多播送,8.4,多到多播送,8.3,一到多播送,8.3.1,SF,模式,8.3.2 CT,模式,一到多播送,SF,模式,环,步骤：,先左右邻近传送,;,再左右二个方向同时播送,示例：,通讯时间：,2024/10/1,26,国家高性能计算中心（合肥）,一到多播送,SF,模式,环绕网孔,步骤：,先完成一行中的播送,;,再同时进行各列的播送,示例：,共,4,步,(2,步行、,2,步列,),通讯时间：,2024/10/1,27,国家高性能计算中心（合肥）,一到多播送,SF,模式,超立方,步骤：从低维到高维，依次进行播送,;,示例：,通讯时间：,2024/10/1,28,国家高性能计算中心（合肥）,8.3,一到多播送,8.3.1 SF,模式,8.3.2,CT,模式,一到多播送,CT,模式,环,步骤：,(1),先发送至,p/2,远的处理器,;,(2),再同时发送至,p/2,2,远的处理器,;,(i),再同时发送至,p/2,i,远的处理器,;,示例：图,8.8,通讯时间：,2024/10/1,30,国家高性能计算中心（合肥）,一到多播送,CT,模式,网孔,步骤：,(1),先进行行播送,;,(2),再同时进行列播送,;,示例：图,8.9,通讯时间：,2024/10/1,31,国家高性能计算中心（合肥）,一到多播送,CT,模式,超立方,步骤：,依次从低维到高维,播送,d-,立方,d=0,1,2,3,4;,通讯时间：,2024/10/1,32,国家高性能计算中心（合肥）,第八章 并行数值算法,8.0,预备知识,8.1,选路方法与开关技术,8.2,单一信包一到一传输,8.3,一到多播送,8.4,多到多播送,8.3,一到多播送,8.3.1,SF,模式,8.3.2 CT,模式,多到多播送,SF,模式,环,步骤：,同时向右,(,或左,),播送,刚接收到的信包,示例：图,8.10,通讯时间：,已有数据,第,2,步传送数据,2,2024/10/1,35,国家高性能计算中心（合肥）,多到多播送,SF,模式,环绕网孔,步骤：,(1),先进行行的播送；,(2),再进行列的播送；,示例：图,8.11,通讯时间：,2024/10/1,36,国家高性能计算中心（合肥）,多到多播送,SF,模式,超立方,步骤：,依次按维进行,多到多的播送；,示例：图,8.12,通讯时间：,2024/10/1,37,国家高性能计算中心（合肥）,8.3,一到多播送,8.3.1 SF,模式,8.3.2,CT,模式,多到多播送,CT,模式,使用一到多的策略会造成链路竞争,2024/10/1,39,国家高性能计算中心（合肥）,