预备知识 选路方式 信包 存储-转发(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 选路方法