南京大学：《并行处理技术——分布式与并行计算 Distributed and Parallel computing（并行计算——结构、算法、编程）》课程教学资源（课件讲稿）第八章 并行数值算法（基本通信操作）

第八章并行数值算法 8.0预备知识 8.1选路方法与开关技术 8.2单一信包一到一传输 8.3一到多播送 8.4多到多播送

第八章 并行数值算法 8.0 预备知识 8.1 选路方法与开关技术 8.2 单一信包一到一传输 8.3 一到多播送 8.4 多到多播送

预备知识 *选路(Routing 又称为选径或路由。产生消息从发源地到目的地所取 的路径，要求具有较低通讯延迟、无死锁和容错能力。 应用于网络或并行机上的信息交换。 *消息、信包、片 *消息Messag©)：是在多计算机系统的处理接，点之间传 递包含数据和同步消息的信息包。它是一种逻辑单位， 可由任意数量的包构成。 * 包Packet):包的长度随协议不同而不同，它是信息传 送的最小单位，64-512位。 *片Fid:片的长度固定，一般为8位。 4 2011/11/14

 选路(Routing)  又称为选径或路由。产生消息从发源地到目的地所取 的路径, 要求具有较低通讯延迟、无死锁和容错能力。 应用于网络或并行机上的信息交换。  消息、信包、片  消息(Message)：是在多计算机系统的处理接点之间传 递包含数据和同步消息的信息包。它是一种逻辑单位， 可由任意数量的包构成。  包(Packet)：包的长度随协议不同而不同，它是信息传 送的最小单位，64-512位。  片(Flit)：片的长度固定，一般为8位。 4 2011/11/14 预备知识

预备知识 *消息、信包、片的相互关系 消息 包 包 头片数据片 顺序号尾片 片 FFFFFFFF 5 2011/11/14

 消息、信包、片的相互关系 5 2011/11/14 预备知识 消息 包 包 头片 数 据 片 …… 顺序号 尾片 片 F F F F F F F F

预备知识 一些术语 *信道带宽b:每个信道有w位宽和信号传输率f=1/t(t是 时钟周期)，b=wf bits/sec *节点和开关的度：与节点和开关相连的信道数目 *路径：信包在网络中走过的开关和链路ink)序列 *路由长度或距离：路由路径中包括的链路ik)数目 *信包传输性能参数 *启动时间t(startup time):准备包头信息等 米 节，点延迟时间t(per-hop time):包头穿越相邻节，点的时间 米 字传输时间t(transfer time)):传输每个字的时间 *链路数1、信包大小m 6 2011/11/14

 一些术语  信道带宽b：每个信道有w位宽和信号传输率f = 1/t (t是 时钟周期), b = wf bits/sec  节点和开关的度：与节点和开关相连的信道数目  路径：信包在网络中走过的开关和链路(link)序列  路由长度或距离：路由路径中包括的链路(link)数目  信包传输性能参数  启动时间ts(startup time)：准备包头信息等  节点延迟时间th(per-hop time)：包头穿越相邻节点的时间  字传输时间tw(transfer time)：传输每个字的时间  链路数l 、信包大小m 6 2011/11/14 预备知识

预备知识 *选路算法的三种机制 *基于算术的：开关中具有简单的算术运算功能，如维 序选路； *基于源地址的：在源点时就将沿路径的各个开关的输 出端口地址pP1,…Pn包在信包的头部，每个开关只是 对信包头的输出端口地址进行剥离； *基于查表的：开关中含有一个选路表，对信包头中的 选路域查出输出端口地址。 > 2011/11/14

 选路算法的三种机制  基于算术的: 开关中具有简单的算术运算功能，如维 序选路；  基于源地址的: 在源点时就将沿路径的各个开关的输 出端口地址p0,p1,…,pn包在信包的头部，每个开关只是 对信包头的输出端口地址进行剥离；  基于查表的: 开关中含有一个选路表，对信包头中的 选路域查出输出端口地址。 7 2011/11/14 预备知识

预备知识 选路方式 信包 存储-转发(Store and Forward) 虫孔(Wormhole) 线路：用交换机 「静态：在选路开始时所有的信息都己到达网络 动态：信包可在任意时刻到达网络 联机(online):没有事先计算好的路径 脱机(offline):事先算好传输路径 到一（单播） 到一（置换）：每个处理器开始时最多发送一条信包， 每条信包有且仅有一个目的地： 多到一（集中） 到多（多播） 到所有（广播、组播） 多到多（会议） 2011/11/14 8

预备知识  选路方式                          多到多（会议） 一到所有（广播、组播 ） 一到多（多播） 多到一（集中） 每条信包有且仅有一个目的地； 一到一（置换）每个处理器开始时最多发送一条信包， 一到一（单播） 脱机 事先算好传输路径 联机 没有事先计算好的路径 动态 信包可在任意时刻到达网络 静态 在选路开始时所有的信息都已到达网络 线路 用交换机 虫孔（ ） 存储－转发（ ） 信包 : ( ): ( ): : : : offline online Wormhole Store and Forward 8 2011/11/14

第八章并行数值算法 8.0预备知识 8.1选路方法与开关技术 8.2单一信包一到一传输 83一到多播送 8.4多到多播送

第八章 并行数值算法 8.0 预备知识 8.1 选路方法与开关技术 8.2 单一信包一到一传输 8.3 一到多播送 8.4 多到多播送

8.1选路方法与开关技术 8.1.1选路方法 8.1.2开关技术

8.1 选路方法与开关技术 8.1.1 选路方法 8.1.2 开关技术

选路方法 *分类 *最短路径/非最短路径（贪心选路随机选路）， 如维序选路是贪心的，二阶段维序选路是随机的 *确定选路/自适应选路（寻径确定/寻径视网络状况） *维序选路(Dimension-Ordered Routing): 一种确定的最短路径选路 *二维网孔中的维序选路：X-Y选路 *超立方中的维序选路：E-立方选路 11 2011/11/14

 分类  最短路径/非最短路径(贪心选路/随机选路)， 如维序选路是贪心的，二阶段维序选路是随机的  确定选路/自适应选路(寻径确定/寻径视网络状况)  维序选路(Dimension-Ordered Routing)： 一种确定的最短路径选路  二维网孔中的维序选路: X-Y选路  超立方中的维序选路: E-立方选路 11 2011/11/14 选路方法

选路方法 *X-Y选路算法 *算法8.1：二维网孔上的X-Y选路算法 begin step1:沿X方向将信包送至目的地处理器所在的列 step2:沿Y方向将信包送至目的地处理器所在的行 end 12 2011/11/14

X-Y选路算法  算法8.1：二维网孔上的X-Y选路算法 begin step1: 沿X方向将信包送至目的地处理器所在的列 step2: 沿Y方向将信包送至目的地处理器所在的行 end 12 2011/11/14 选路方法