08-第08章-基本通讯操作-并行数值算法-并行计算(共15章)

并行计算中国科学技术大学计算机科学与技术系中国科学技术大学计算机科学与技术系国家高性能计算中心国家高性能计算中心((合肥合肥))20042004年年1212月月第三篇并行数值算法第八章基本通讯操作第九章稠密矩阵运算第十章线性方程组的求解第十一章快速傅里叶变换第八章并行数值算法8.0预备知识8.1选路方法与开关技术8.2单一信包一到一传输8.3一到多播送8.4多到多播送国家高性能计算中心（合肥）42013/7/24Wednesday预备知识选路选路(Routing)(Routing)又称为选径或路由。产生消息从发源地到目的地所取又称为选径或路由。产生消息从发源地到目的地所取的路径的路径,,要求具有较低通讯延迟、无死锁和容错能要求具有较低通讯延迟、无死锁和容错能力。应用于网络或并行机上的信息交换。力。应用于网络或并行机上的信息交换。消息、信包、片消息、信包、片消息消息(Message)(Message)：是在多计算机系统的处理接点之间：是在多计算机系统的处理接点之间传递包含数据和同步消息的信息包。它是一种逻辑单传递包含数据和同步消息的信息包。它是一种逻辑单位，可由任意数量的包构成。位，可由任意数量的包构成。包包(Packet)(Packet)：包的长度随协议不同而不同，它是信息：包的长度随协议不同而不同，它是信息传送的最小单位，传送的最小单位，6464--512512位。位。片片(Flit)(Flit)：片的长度固定，一般为：片的长度固定，一般为88位。位。国家高性能计算中心（合肥）52013/7/24Wednesday预备知识消息、信包、片消息、信包、片的相互关系的相互关系包消息包据片头片尾片……顺序号数片FFFFFFFF国家高性能计算中心（合肥）62013/7/24Wednesday预备知识一些术语一些术语信道带宽信道带宽bb：每个信道有：每个信道有ww位宽和信号传输率位宽和信号传输率ff=1/t(t=1/t(t是时钟周期是时钟周期),),b=b=wfwfbits/secbits/sec节点和开关的度：与节点和开关相连的信道数目节点和开关的度：与节点和开关相连的信道数目路径：信包在网络中走过的开关和链路路径：信包在网络中走过的开关和链路(link)(link)序列序列路由长度或距离：路由路径中包括的链路路由长度或距离：路由路径中包括的链路(link)(link)数目数目信包传输性能参数信包传输性能参数启动时间启动时间ttss((startupstartuptimetime))：准备包头信息等：准备包头信息等节点延迟时间节点延迟时间tthh((perper--hoptimehoptime))：包头穿越相邻节点的时间：包头穿越相邻节点的时间字传输时间字传输时间ttww((transfertransfertimetime))：传输每个字的时间：传输每个字的时间链路数链路数ll、信包大小、信包大小mm国家高性能计算中心（合肥）72013/7/24Wednesday预备知识选路算法的三种机制选路算法的三种机制基于算术的基于算术的::开关中具有简单的算术运算功能，如开关中具有简单的算术运算功能，如维序选路；维序选路；基于源地址的基于源地址的::在源点时就将沿路径的各个开关的在源点时就将沿路径的各个开关的输出端口地址输出端口地址pp00,p,p11,,……,,ppnn包在信包的头部，每个开包在信包的头部，每个开关只是对信包头的输出端口地址进行剥离；关只是对信包头的输出端口地址进行剥离；基于查表的基于查表的::开关中含有一个选路表，对信包头中开关中含有一个选路表，对信包头中的选路域查出输出端口地址。的选路域查出输出端口地址。国家高性能计算中心（合肥）82013/7/24Wednesday预备知识选路方式选路方式多到多（会议））一到所有（广播、组播一到多（多播）多到一（集中）目的地；每条信包有且仅有一个发送一条信包，每个处理器开始时最多一到一（置换）一到一（单播）事先算好传输路径脱机没有事先计算好的路径联机网络信包可在任意时刻到达动态息都已到达网络在选路开始时所有的信静态用交换机线路）虫孔（）存储－转发（信包::)(:)(:::offlineonlineWormholeForwardandStore第八章并行数值算法8.0预备知识8.1选路方法与开关技术8.2单一信包一到一传输8.3一到多播送8.4多到多播送8.1选路方法与开关技术8.1.1选路方法8.1.2开关技术国家高性能计算中心（合肥）112013/7/24Wednesday选路方法分类分类最短路径最短路径//非最短路径非最短路径((贪心选路贪心选路//随机选路随机选路))，，如维序选路是贪心的，二阶段维序选路是随机的如维序选路是贪心的，二阶段维序选路是随机的确定选路确定选路//自适应选路自适应选路((寻径确定寻径确定//寻径视网络状况寻径视网络状况))维序选路维序选路(Dimension(Dimension--OrderedRouting)OrderedRouting)：：一种确定的最短路径选路一种确定的最短路径选路二维网孔中的维序选路二维网孔中的维序选路:X:X--YY选路选路超立方中的维序选路超立方中的维序选路:E:E--立方选路立方选路国家高性能计算中心（合肥）122013/7/24Wednesday选路方法XX--YY选路算法选路算法算法算法8.18.1：二维网孔上的：二维网孔上的XX--YY选路算法选路算法beginbeginstep1:step1:沿沿XX方向将信包送至目的地处理器方向将信包送至目的地处理器所在的列所在的列step2:step2:沿沿YY方向将信包送至目的地处理器方向将信包送至目的地处理器所在的行所在的行endend国家高性能计算中心（合肥）132013/7/24Wednesday选路方法例例8.18.1(P186)(P186)图8.10,71,72,73,74,75,76,77,70,61,62,63,64,65,66,67,61,50,52,53,54,55,56,57,50,41,42,43,47,44,46,45,46,31,32,33,34,35,30,37,30,21,22,23,27,25,26,24,22,11,10,13,14,15,16,17,10,01,07,03,04,05,06,02,0xyi,jESWN源;目的对:(2,1;7,6)(0,7;4,2)(5,4;2,0)(6,3;1,5)4()国家高性能计算中心（合肥）142013/7/24Wednesday选路方法EE--立方选路算法立方选路算法路由计算：路由计算：ssnn--11ssnn--22……ss11ss00((源地址源地址))异或异或ddnn--11ddnn--22……dd11dd00((目的地目的地址址))rrnn--11rrnn--22……rr11rr00((路由值路由值))路由过程：路由过程：ssnn--11ssnn--22……ss11ss00ssnn--11ssnn--22……ss11ss00rr00ssnn--11ssnn--22……ss11ss00rr11……算法算法8.28.2：超立方网络上的：超立方网络上的EE--立方选路算法立方选路算法(P186)(P186)国家高性能计算中心（合肥）152013/7/24Wednesday选路方法例例8.28.2(P187)(P187)0110(S)0110(S)1101(D)1101(D)1011(R)1011(R)dim2dim3dim1dim4源：S=0110目的：D=1101路径：01100111010111011101010101101111111000001100100110000100011100010010001110101011图8.28.1选路方法与开关技术8.1.1选路方法8.1.2开关技术国家高性能计算中心（合肥）172013/7/24Wednesday开关技术存储转发存储转发(Store(Store--andand--Forward)Forward)选路选路消息被分成基本的传输单位消息被分成基本的传输单位--------信包信包(Packet),(Packet),每个每个信包都含有寻径信息；信包都含有寻径信息；当一个信包到达中间节点当一个信包到达中间节点AA时，时，AA把整个信包放入其通把整个信包放入其通信缓冲器中，然后在选路算法的控制下选择下一个相信缓冲器中，然后在选路算法的控制下选择下一个相邻节点邻节点BB，当从，当从AA到到BB的通道空闲并且的通道空闲并且BB的通信缓冲器可的通信缓冲器可用时，把信包从用时，把信包从AA发向发向BB；；信包的传输时间信包的传输时间::ttcommcomm(SF)=(SF)=ttss+(+(mtmtww++tthh))ll==OO((mlml))缺点：缺点：每个结点必须对整个消息和信包进行缓冲，缓冲器较每个结点必须对整个消息和信包进行缓冲，缓冲器较大；大；网络时延与发送消息所经历的节点数成正比网络时延与发送消息所经历的节点数成正比国家高性能计算中心（合肥）182013/7/24Wednesday开关技术切通切通((CutThroughCutThrough))选路选路在传递一个消息之前，就为它建立一条从源结点到在传递一个消息之前，就为它建立一条从源结点到目的结点的物理通道。在传递的全部过程中，线路目的结点的物理通道。在传递的全部过程中，线路的每一段都被占用，当消息的尾部经过网络后，整的每一段都被占用，当消息的尾部经过网络后，整条物理链路才被废弃。条物理链路才被废弃。传输时间传输时间::ttcommcomm(CT)=(CT)=ttss++mtmtww++ltlthh==OO((m+lm+l))缺点：缺点：物理通道非共享物理通道非共享传输过程中物理通道一直被占用传输过程中物理通道一直被占用国家高性能计算中心（合肥）192013/7/24Wednesday开关技术虫孔虫孔((WormholeWormhole))选路选路DallyDally于于19861986年提出，利用了前二种方法的优点，减少年提出，利用了前二种方法的优点，减少了缓冲区，提高了物理通道的利用。了缓冲区，提高了物理通道的利用。首先把一个消息分成许多很小的片，消息的首先把一个消息分成许多很小的片，消息的头片头片包含包含了这个消息的所有寻径信息。了这个消息的所有寻径信息。尾片尾片是一个其最后包含是一个其最后包含了消息结束符的片。中间的片均为了消息结束符的片。中间的片均为数据片数据片；；片是最小信息单位。每个结点上只需要缓冲一个片就片是最小信息单位。每个结点上只需要缓冲一个片就能满足要求；能满足要求；用一个头片直接牵引一条从输入链路到输出链路的路用一个头片直接牵引一条从输入链路到输出链路的路径的方法来进行操作。每个消息中的片以流水的方式径的方法来进行操作。每个消息中的片以流水的方式在网络中向前在网络中向前““蠕动蠕动””。每个片相当于。每个片相当于WormWorm的一个的一个节，节，““蠕动蠕动””以节为单位顺序地向前爬行。当消息的以节为单位顺序地向前爬行。当消息的尾片向前尾片向前““蠕动蠕动””一步后，它刚才所占用的结点就被一步后，它刚才所占用的结点就被放弃了。放弃了。国家高性能计算中心（合肥）202013/7/24Wednesday开关技术虫孔虫孔((WormholeWormhole))选路选路优点：优点：(1)(1)每个结点的缓冲器的需求量小每个结点的缓冲器的需求量小，易于用，易于用VLSIVLSI实现；实现；(2)(2)较低的网络传输延迟较低的网络传输延迟。存储转发传输延迟基本上正。存储转发传输延迟基本上正