中国料学火计算机科学与波术系 niversity of Science and Technolo ogy of China DEAT三 NT OF C口 MPUTER SCIENGE AND TECHNOLOr 第三篇并行数值算法 第八章基本通讯操作 第九章稠密矩阵运算 第十章线性方程组的求解 第十一章快速傅里叶变换
第三篇 并行数值算法 第八章 基本通讯操作 第九章 稠密矩阵运算 第十章 线性方程组的求解 第十一章 快速傅里叶变换
中国料学火计算机科学与波术系 niversity of Science and Technolo ogy of China DEAT三 NT OF C口 MPUTER SCIENGE AND TECHNOLOr 第八章并行数值算法 80预备矢 81选路方法与开关技术 8.2单一信包一到一传输 8.3一到多播送 84多到多播送
第八章 并行数值算法 8.0 预备知识 8.1 选路方法与开关技术 8.2 单一信包一到一传输 8.3 一到多播送 8.4 多到多播送
中国料学火计算机科学与波术系 niversity of Science and Technology of China DEAT三 NT OF C口 MPUTER SCIENGE AND TECHNOLOr 预备知 选路( Routing) 又称为选径或路由。产生消息从发源地到目的地所取 的路径,要求具有较低通讯延迟、无死锁和容错能力。 应用于网络或并行机上的信息交换。 消息、信包、片 消息( Message):是在多计算机糸统的处理接点之问 传递包含数据和同步消息的信息包。宅是一种逻辑单 位,可由任意数量的包构成。 包( Packet):包的长度随协议不同而不同,宅是信息 传送的最小单位,64-512位。 片(Flit):片的长度固定,一般为8位。 国家高性能计算中心(合肥 2021/2/19
国家高性能计算中心（合肥） 4 2021/2/19 预备知识 ▪ 选路(Routing) ▪ 又称为选径或路由。产生消息从发源地到目的地所取 的路径, 要求具有较低通讯延迟、无死锁和容错能力。 应用于网络或并行机上的信息交换。 ▪ 消息、信包、片 ▪ 消息(Message)：是在多计算机系统的处理接点之间 传递包含数据和同步消息的信息包。它是一种逻辑单 位，可由任意数量的包构成。 ▪ 包(Packet)：包的长度随协议不同而不同，它是信息 传送的最小单位，64-512位。 ▪ 片(Flit)：片的长度固定，一般为8位
中国料学火计算机科学与波术系 niversity of Science and Technolo ogy of China DEAT三 NT OF C口 MPUTER SCIENGE AND TECHNOLOr 预备知炽 ■消息、信包、片的相互关糸 消息 头片数据「片 顺序号尾片 片 IFIFIFFFFIFIF 国家高性能计算中心(合肥 2021/2/19
国家高性能计算中心（合肥） 5 2021/2/19 预备知识 ▪ 消息、信包、片的相互关系 消息 包 包 头片 数 据 片 …… 顺序号 尾片 片 F F F F F F F F
中国料学火计算机科学与波术系 niversity of Science and Technology of China DEAT三 NT OF C口 MPUTER SCIENGE AND TECHNOLOr 预备知识 ■一些术语 信道带宽b:每个信道有W位宽和信号传输率f=1/(t 是肘钟周期),b= wf bits/sec 节点和开关的度:与节点和开关相连的信道数目 ■路径:信包在网络中走过的开关和链路(ink)序列 ■路由长度或距离:路由路径中包括的链路(link)数教目 ■信包传输性能参数 启动时间t( startup time):准备包头信息等 ■节点延迟时间t(per- hop time):包头穿越相邻节点的时间 字传输肘间t( transfer time):传输每个字的时间 ■链路数1、信包大小m 国家高性能计算中心(合肥 2021/2/19
国家高性能计算中心（合肥） 6 2021/2/19 预备知识 ▪ 一些术语 ▪ 信道带宽b：每个信道有w位宽和信号传输率f = 1/t (t 是时钟周期), b = wf bits/sec ▪ 节点和开关的度：与节点和开关相连的信道数目 ▪ 路径：信包在网络中走过的开关和链路(link)序列 ▪ 路由长度或距离：路由路径中包括的链路(link)数目 ▪ 信包传输性能参数 ▪ 启动时间ts(startup time)：准备包头信息等 ▪ 节点延迟时间th(per-hop time)：包头穿越相邻节点的时间 ▪ 字传输时间tw(transfer time)：传输每个字的时间 ▪ 链路数l 、信包大小m
中国料学火计算机科学与波术系 niversity of Science and Technology of China DEAT三 NT OF C口 MPUTER SCIENGE AND TECHNOLOr 预备知 ■选路算法的三种机制 ■基于算术的:开关中具有简单的算术远算功能,如维 序选路; ■基于源地址的:在源点肘就将沿路径的各个开关的输 出端口地址PP1,…,Pn包在信包的头部,每个开关只 是对信包头的输出端口地址进行剥离 ■基于查表的:开关中合有一个选路表,对信包头中的 选路堿查出输岀端口地址。 国家高性能计算中心(合肥 2021/2/19
国家高性能计算中心（合肥） 7 2021/2/19 预备知识 ▪ 选路算法的三种机制 ▪ 基于算术的: 开关中具有简单的算术运算功能，如维 序选路； ▪ 基于源地址的: 在源点时就将沿路径的各个开关的输 出端口地址p0 ,p1 ,…,pn包在信包的头部，每个开关只 是对信包头的输出端口地址进行剥离； ▪ 基于查表的: 开关中含有一个选路表，对信包头中的 选路域查出输出端口地址
中国料学火计算机科学与波术系 niversity of Science and Technology of China DEAT三 NT OF C口 MPUTER SCIENGE AND TECHNOLOr 预备知识 选路方式」信包(存储一转发 Store and for 虫孔( Wormhe l e 线路:用交换机 静态:在选路开始时所有的信息都已到达网络 动态信包可在任意时刻到达网络 联机( online):没有事先计算好的路径 脱机(o〃ine):事先算好传输路径 到一(单播) 到一(置换):每个处理器开始时最多发送一条信包, 每条信包有且仅有一个目的地; 多到一(集中) 到多(多播) 到所有(广播、组播) 多到多(会议) 国家高性能计算中心(合肥 2021/2/19
国家高性能计算中心（合肥） 8 2021/2/19 预备知识 ▪ 选路方式 多到多（会议） 一到所有（广播、组播） 一到多（多播） 多到一（集中） 每条信包有且仅有一个目的地； 一到一（置换）每个处理器开始时最多发送一条信包， 一到一（单播） 脱机 事先算好传输路径 联机 没有事先计算好的路径 动态 信包可在任意时刻到达网络 静态 在选路开始时所有的信息都已到达网络 线路 用交换机 虫孔（ ） 存储－转发（ ） 信包 : ( ): ( ): : : : offline online Wormhole Store and Forward
中国料学火计算机科学与波术系 niversity of Science and Technolo ogy of China DEAT三 NT OF C口 MPUTER SCIENGE AND TECHNOLOr 第八章并行数值算法 80预备知识 81选路方法与开关技术 8.2单一信包一到一传输 8.3一到多播送 84多到多播送
第八章 并行数值算法 8.0 预备知识 8.1 选路方法与开关技术 8.2 单一信包一到一传输 8.3 一到多播送 8.4 多到多播送
中国料学火计算机科学与波术系 niversity of Science and Technolo ogy of China DEAT三 NT OF C口 MPUTER SCIENGE AND TECHNOLOr 81选路方法与开关技术 8.1.1选路方法 812开关技术
8.1 选路方法与开关技术 8.1.1 选路方法 8.1.2 开关技术
中国料学火计算机科学与波术系 niversity of Science and Technology of China DEAT三 NT OF C口 MPUTER SCIENGE AND TECHNOLOr 选路方法 分类 最短路徑/非最短路径(贪心选路/随机选路), 如维序选路是贪心的,三阶段维序选路是随机的 ■确定选路/自适应选路(寻径确定/寻径视网络状况) 维序选路 Dimension-Ordered routing: 种确定的最短路径选路 二维网孔中的维序选路:XY选路 ■超立方中的维序选路:E立方选路 国家高性能计算中心(合肥 2021/2/19
国家高性能计算中心（合肥） 11 2021/2/19 选路方法 ▪ 分类 ▪ 最短路径/非最短路径(贪心选路/随机选路)， 如维序选路是贪心的，二阶段维序选路是随机的 ▪ 确定选路/自适应选路(寻径确定/寻径视网络状况) ▪ 维序选路(Dimension-Ordered Routing)： 一种确定的最短路径选路 ▪ 二维网孔中的维序选路: X-Y选路 ▪ 超立方中的维序选路: E-立方选路