第六章 互连网络

第一节 互连网络基本概念 一、互连网络的互连特性 1、互连网络(Interconnection Network) *概念：由开关元件按一定拓扑结构和控制方式构成的网络，实现节点间的互连 互连网络IN ··· 软件接口 硬件接口 节点 … N-1 IN有单向和双向之分。 *互连特性：多个端口对(同时)、多种端口对组合(分时) *应用：根据需要，可用于P→P及P←→M的并行连接 互连网络IN ··· P PM 回下页

*互连函数：出端编码是入端编码的排列、组合、移位、取反等操作的结果，表示所有出端与入端的连接关系 2、互连特性的表示 *互连函数：出端编码是入端编码的排列、组合、移位、取反等操作的结果，表示所有出端与入端的连接关系 入端编码表示— x＝bn-1…b0，n=log2N 出端编码表示— f(x)＝基于bn-1…b0的操作结果 例1—互连函数f(bn-1…b0)=bn-1…b0，表示IN的所有端口分为N/2个组，组内入端与出端交叉连接(对称的) 例2—互连函数f(bn-1…b0)=bn-2…b0bn-1，表示IN的前一半入端与其编码×2的出端连接、后一半入端与其编码÷2的出端连接(非对称的) *互连特性的表示：用一组 互连函数表示 *互连特性的选择：用控制信号实现选择(网络控制) 转上页

①节点间需同时互连(互连函数需同时实现)，如SIMD ②节点间可分时互连(互连函数可分时实现)，如MIMD 3、应用需求与互连实现方式 *应用需求种类： ①节点间需同时互连(互连函数需同时实现)，如SIMD ②节点间可分时互连(互连函数可分时实现)，如MIMD P0→P1 P4→P5 P8→P9 P0→P4 P4→P8 P8→P4 P0→P2 P4→P6 P8→P0 同时互连示例 分时互连示例 节点P0 节点P4 节点P8 *互连实现方式： 应用需求① 应用需求② 节点互连表示 软件指令指明互连目标 (程序通知IN) 消息内地址指明互连目标 (IN解析消息) 互连函数实现 IN同时控制所有部件 (满足需求) IN分时控制相关部件 (提高效率) 回6页

二、互连网络的组成 1、网络主要器件 (1)链路 --又称通道或电缆 属性有长度、宽度、定时机制3种 (1)链路 --又称通道或电缆 属性有长度、宽度、定时机制3种 *长/短链路：指同一时刻传递多/单个逻辑值(链路上) *宽/窄链路：指信号并行/串行传送 *同步/异步链路：指源端、目标端是/否用公共时钟握手 (2)交叉开关(Crossbar) *组成：N2个交叉点开关[2态] (N个入-出任意连接) 不同拓扑结构实现互连的复杂程度和延时不同。 …… *控制：用信号控制(个数由功能决定) (最多为N2个、常为Nlog2N个) 回下页

(3)交换开关(Switch) —又称交换机或路由器 *组成：交叉开关、缓冲区、接收器/发送器、寻径器 入 端 出 交叉 开关 接收器 缓冲区 发送器 寻径器(路由、调度、控制) *控制：由控制信号(外部)、或数据包(内部)控制 *交换开关的度：输入/输出端口的数量(N) 特点—部件部分成本～kN， 即～端口数量×端口宽度 内部连接成本～cN2，即～交换开关度2 转上页 回下页 转4页

(4)网络接口电路(Network Interface Circuitry) --又称网卡 *组成：链路接口、缓冲区、DMA通道、控制逻辑等 节点MEM总线或I/O总线 说明： ①实线部分为动态网络NIC一般结构 ②虚线部分为静态网络NIC增加部分，数量由网络拓扑结构决定 节点DMA请求 发送DMA 链路接口 接收DMA 网络接口 电路NIC 交换 开关 总线 接口 *功能：数据包组织、路由构造、数据包发送/接收、 一致性检查、流量和错误控制等 *成本：由端口规模、处理能力和控制电路决定 *设计：软硬件分配取决于IN和节点的特性及性能要求 回下页 转上页

节点间的连接在运行期间固定不变，又称直接网络 └→节点直接连接 2、静态互连网络组成 节点间的连接在运行期间固定不变，又称直接网络 └→节点直接连接 *组成：链路、拓扑结构、NIC P100 P101 P110 P111 P000 P001 P010 P011 MB 节点 M NIC P C *拓扑结构：有线性阵列、网格、立方体等多种 *互连特性： 互连函数种类—有限几种(由拓扑结构决定) 互连函数选择—控制NIC 转上页 回下页 回11页 回12页

节点间的连接由程序动态地改变，有共享介质、交叉开关、多级互连3种，后2种又称间接网络(节点仅与交换开关连接) 3、动态互连网络组成 节点间的连接由程序动态地改变，有共享介质、交叉开关、多级互连3种，后2种又称间接网络(节点仅与交换开关连接) (1)共享介质网络 同时只存在一个节点对连接(N个节点对连接需分时实现) *组成：链路、拓扑结构、NIC P0 P1 PN-1 … M NIC P MB 节点 C *拓扑结构：总线 *互连特性： 互连函数种类—零个(多个节点对连接只能分时实现) 节点对选择—各NIC自行判别地址 回下页 转上页

同时存在N个节点对的任意连接，又称非阻塞网络 (2)交叉开关网络 同时存在N个节点对的任意连接，又称非阻塞网络 *组成：链路、交叉开关(拓扑结构)、NIC M NIC P MB 节点 C … P0 PN-1 *拓扑结构：交叉开关 *互连特性： 互连函数种类—常为Nlog2N种(可为NN种) 互连函数选择—控制交叉开关 转上页 回下页

单级互连网络—只有一种互连函数，常为链路＋拓扑结构 (3)多级互连网络 单级互连网络—只有一种互连函数，常为链路＋拓扑结构 多级互连网络—用交换开关级联多个单级网络， 实现N个节点对的有限连接 *组成：链路、交换开关、单级网络(拓扑结构)、NIC ISC(O) P0 P1 … PN-1 ISC(n-1) ISC(1) M NIC P MB 节点 C ISC(Interstage Connect) *拓扑结构：静态网络拓扑结构，各ISC(i)可不同 *互连特性： 互连函数种类—多种(可为N!种，种数由拓扑结构决定) 互连函数选择—控制交换开关 转8页 转上页 回下页

*互连特性：互连函数种类—多种(M×N×L) 互连函数选择—组合控制各个网络 4、混合互连网络 *组成示例：(可扩展性较强) 主干网 (超立方体网络) 主干 节点0 主干节 点N-1 … 主干节点网 (静态网格网络) 网格 网格节 点M-1 网格节点网 (总线网络) 叶节点0 (2个P) 叶节点L-1 *互连特性：互连函数种类—多种(M×N×L) 互连函数选择—组合控制各个网络 ※IN组成小结： 共享介质网络：总线 动态网络 交叉开关网络：n×n交叉开关(非阻塞) 多级互连网络：单向多级、双向多级、单向环 1D网络：线性阵列 静态网络 2D网络：环、树型、胖树型、星型、2D网格等 nD网络：带弦环、nD网格、立方体、超立方体等 转8页 转上页

三、互连网络的性能指标 1、时延 指网络无负载时的传输时延，即网络时延 通信时延＝额外开销＋网络时延＋竞争时延 额外开销—收/发方的软/硬件开销，与节点内核、NIC有关 竞争时延—传输竞争导致的时延，与网络状况、程序行为有关 发送开销 路由时延 接收开销 网络时延 发送方 互连网络 接收方 t 通道时延 软件开销、竞争开销受程序行为影响 网络时延＝路由时延＋消息长度/通道带宽 路由时延—消息停顿在各交换开关的时间，与拓扑结构有关 通道带宽—消息占用通道导致的时延，与链路带宽及路径有关 回26页

目标—反映端口最小带宽 (非对称IN指min) 2、带宽 有端口带宽、等分带宽和聚集带宽3种类型 *端口带宽：任意一个端口的带宽 目标—反映端口最小带宽 (非对称IN指min) *等分带宽(对剖带宽)：最小等分平面上连线的总带宽 等分平面—n节点网络分为两个n/2节点网络的一组连线 目标—反映网络最小带宽 └→不要求节点连续 *聚集带宽：一半节点到另一半节点的最大带宽 目标—反映网络最大带宽 端口带宽b 节点0 互连网络IN ··· 节点i 节点i+1 节点j 节点k 节点j+1 节点N-1 节点k+1 等分带宽=lb，l为最小等分平面链路数 聚集带宽=l’b，l’为最大等分平面链路数 回29页

四、互连网络实现的相关问题 主要指网络层的实现，包括控制方式、交换方式、拓扑结构、路由算法、流控机制等 1、控制方式 指互连函数同时/分时实现，对应方式有集中式和分布式2种 *集中式控制： 程序在IN外部同时控制所有交换开关(或NIC)状态， IN保持状态、直到再次控制为止 指令译码器 PE控制器 计算指令 通信指令 网络控制指令 并行 程序 … PEN-1 PE0 PE1 IN控制器 ISC(0) ISC(n-1) 回下页

数据分组在IN内部分时控制相关交换开关(或NIC)状态， IN保持状态、直到分组通过或通信完成为止 *分布式控制： 数据分组在IN内部分时控制相关交换开关(或NIC)状态， IN保持状态、直到分组通过或通信完成为止 （取决于交换方式） … PN-1 ISC(0) ISC(n-1) P0 P1 分布式控制的互连网络结构 分布式控制的交换开关结构 入 端 出 交叉 开关 接收器 缓冲区 发送器 寻径器(路由、调度、控制功能) *控制方式的应用： 集中式控制—适合于SIMD系统 分布式控制—适合于MIMD系统 SIMD并行算法需要结点对同时连接，MIMD并行算法无此要求。 转上页 回44页

指分布式IN中，消息的传递方式(含寻径及传输) *交换类型：线路交换、包交换 2、交换方式 指分布式IN中，消息的传递方式(含寻径及传输) *交换类型：线路交换、包交换 (1)线路交换 (先寻径，后传输) 先建立物理通路(又称虚电路)，再传递消息，最后撤销通路 时间t N1 N2 N3 N4 D 说明：本图忽略了链路传输时延 寻径 寻径 消息 消息1 消息 消息2 消息3 交换类型是网络层的实现技术，寻径方式是链路层的实现技术 *与集中式控制的差别：仅控制一条路径(非所有路径) *特点：适于成批传送，网络冲突较大(静态占用) 回19页 回下页

①消息分解成若干分组独立传送，目标结点再整合成消息 ②IN中相关结点选择路径，保持状态(直至分组通过) (2)分组(包)交换 (边寻径，边传输) ①消息分解成若干分组独立传送，目标结点再整合成消息 　 ②IN中相关结点选择路径，保持状态(直至分组通过) └→根据数据包中寻径信息 *数据包的组织： 消息分解为分组，分组封装成数据包(帧)， 数据包包含导径、顺序号、数据片等信息 注：数据包和数据片大小固定，未标出帧头/尾 消息 分组 分组 数据包 片 R S D R：导径信息 S：顺序号 D：数据片 网络层的交换单元为分组，链路层的交换单元为数据包(帧) 线路交换实现的是面向连接的服务，包交换实现的是无连接服务 *特点：传输延迟略大，网络冲突较小 转上页

*寻径方式：存储-转发(Store-and-Forward)、切通(Cut-Through) 存储-转发方式—数据包串行传输，缓冲一个数据包 R t R1 R2 R3 R4 交换开关 T＝t0＋d(th＋m/B) 切通方式—数据包流水传输(Δt＝数据片)， 正常时缓冲：数据片， 阻塞时缓冲：数据包(虚拟直通方式)、或数据片(虫蚀方式) t R1 R2 R3 R4 交换开关 T＝t0＋dth＋m/B ≈t0＋m/B 比较—前者拥塞代价小、后者时延与距离无关 转17页

3、拓扑结构 是实现互连函数的主要机构 ←交换开关为辅助机构 *拓扑结构种类： 1D—线性阵列 2D—环、树型、胖树型、星型、2D网格等 nD—带弦环、nD网格、立方体、超立方体等 *拓扑结构与互连函数： 拓扑结构的并行链路数，影响互连函数的种类 拓扑结构的链路连接特性，影响互联函数的功能 *控制方式与拓扑结构： 集中式控制—对拓扑结构要求较高 (→常用nD结构) 分布式控制—对拓扑结构要求一般

*算法：算术路由、源路由、查表路由、自适应路由等 *目标：避免死锁、均匀负载、维持低时延、容错等 3、路由算法 交换开关决定分组移动方向的算法 └→入→出路径 *算法：算术路由、源路由、查表路由、自适应路由等 *目标：避免死锁、均匀负载、维持低时延、容错等 4、流控机制 流量控制—控制分组发送速度、以适应接收端吸收能力 *流控机制种类：链路级流控、端到端流控 (基于反馈) (基于速率) 流量控制面向某对发送端-接收端，拥塞控制面向整个网络； 链路层流控面向路由器/交换机、采用基于反馈的方法，端到端流控面向主机、采用基于速率的方法 ※拥塞控制—控制分组的传送、以保持网络的承载流量 拥塞控制方法—警告位、抑制分组、绕道、扬弃(NACK)

第二节 互连网络与拓扑结构 一、互连函数与拓扑结构 *单级互连网络：只具有一种互连函数的互连网络 即一种互连函数所实现的互连结构 第二节 互连网络与拓扑结构 一、互连函数与拓扑结构 *单级互连网络：只具有一种互连函数的互连网络 即一种互连函数所实现的互连结构 *拓扑结构：由(多个)单级互连网络构成 1、恒等置换 *互连函数：I(b2b1b0)=(b2b1b0) 000 001 010 011 100 101 110 111 N=8恒等置换互连 *互连特性：互连函数可逆，只有一种变换

*互连函数：Exchange(b2b1b0)=(b2b1b0) 2、交换置换 --编码末位取反 *互连函数：Exchange(b2b1b0)=(b2b1b0) 000 001 010 011 100 101 110 111 N=8交换置换互连 *互连特性：互连函数可逆，只有一种变换 *应用：2×2交换开关可实现恒等、交换变换等功能 恒等 交换 上播 下播 (a)1位控制信号 (b)2位控制信号

*互连函数：Cubek(bn-1…bk…b0)=(bn-1…bk…b0) 3、立方体置换 --编码某位取反 *互连函数：Cubek(bn-1…bk…b0)=(bn-1…bk…b0) 000 001 010 011 100 101 110 111 N=8 Cube0置换互连 N=8 Cube1置换互连 N=8 Cube2置换互连 *互连特性：互连函数可逆，有n种(Cube0，…，Cuben-1)变换 *应用：n立方体结构可实现n种Cube变换， z y x 010 011 110 111 000 001 101 100 每个节点需n位控制信号 NIC CPU X Y Z 回下页

*互连函数：Shuffle(bn-1bn-2…b1b0)=(bn-2…b1b0bn-1) 4、混洗置换 --编码最高位移位 *互连函数：Shuffle(bn-1bn-2…b1b0)=(bn-2…b1b0bn-1) 000 001 010 011 100 101 110 111 N=8 混洗置换互连 *互连特性：互连函数不可逆(首尾节点只连接自身)， 只有一种变换 *应用：混洗与交换结构可实现任意节点间互连 混洗是扩散，逆混洗是收敛 为控制方便，一次混洗紧接一次交换 1 2 3 4 5 6 7 特征—多级网络ISCi可只有一种互连(混洗) 转上页 回33页

*互连函数：β(bn-1bn-2…b1b0)=(b0bn-2…b1bn-1) 5、蝶式置换 --编码位交换位置 *互连函数：β(bn-1bn-2…b1b0)=(b0bn-2…b1bn-1) 000 001 010 011 100 101 110 111 N=8蝶式置换互连 000 001 010 011 100 101 110 111 N=8 β(1)子蝶式置换互连 *子蝶式和超蝶式置换： β(k)(bn-1…bkbk-1…b0)=(bn-1…bk+1b0bk-1…b1bk) β(k)(bn-1…bn-kbn-k-1…b0)=(bn-k-1bn-2…bn-kbn-1bn-k-2…b0) *互连特性：互连函数可逆，有2n-2种(子/超各为n-1)变换 *应用：子蝶式结构可实现分组互连(＋交换＝组内全互连) 蝶式结构可实现组间互连(步长＞1的组内互连) 回33页

*互连函数：α(X)=(X+k) mod N，0≤k≤N-1 6、移数置换 --编码值移位 *互连函数：α(X)=(X+k) mod N，0≤k≤N-1 000 001 010 011 100 101 110 111 k=1移数置换互连 k=2移数置换互连 *互连特性：互连函数不可逆(k=0除外)，有2n个移数变换 *应用：带弦环结构可实现多种移数变换 结构特性—间隔k决定内弦连接 变换种类决定内弦数 4 1 7 2 6 3 5 回下页

7、加减2i置换 --移数置换的特例(k=2i) *互连函数：PM2I+i(j)=(j+2i) mod N 4 1 7 2 6 3 5 000 001 010 011 100 101 110 111 PM2I+1置换互连 PM2I+2置换互连 *互连特性：互连函数不可逆(i=±n除外)，有2n-1种变换 *应用：闭合螺旋结构可实现PM2I±0及 PM2I±n/2变换 △小结：互连函数可用拓扑结构实现 互联函数选择可用拓扑结构选择实现 转上页 回33页

二、互连实现与拓扑结构 *IN互连需求：IN中的节点均可与任意节点连接 *IN实现方法：IN具有多个互连函数，不同互连函数可叠加 1、静态互连网络与拓扑结构 *网络组成：链路、拓扑结构、节点NIC MEM NIC MEM Bus 节点 CPU Cache P100 P101 P110 P111 P000 P001 P010 P011 *互连实现：源→目标节点需穿过多个节点 *拓扑结构：拓扑结构实现互连函数(多个)， NIC实现函数选择、函数叠加 *互连性能：由中间节点数决定(与拓扑结构相关) 回下页

*网络组成：链路、拓扑结构、交换开关、节点NIC 2、动态互连网络与拓扑结构 *网络组成：链路、拓扑结构、交换开关、节点NIC P0 P1 PN-1 … M NIC P MB 节点 C ISC(0) ISC(n-1) *互连实现：源→目标节点需穿过多个交换开关 *拓扑结构：拓扑结构(单级网络)实现互连函数(多个)， 交换开关实现恒等/交换函数、函数叠加 *互连性能：由单级网络、交换开关功能决定 △小结：拓扑结构决定了互连网络的功能及性能！ 转上页

*连接度：接入或射出节点的连线数(单向网络为两者之和) *网络直径：任意两个节点间互连的最大步数 3、拓扑结构性能参数 *连接度：接入或射出节点的连线数(单向网络为两者之和) *网络直径：任意两个节点间互连的最大步数 (与连接度及连接方式有关) *常见拓扑结构性能参数： 维数 拓扑结构 最大连接度 网络直径 链路数 等分宽度 一维 线性 2 N-1 1 二维 环状 N 网格 4 星形 二叉树 3 2[log2N-1] (N/2-1)×3 多维 超立方体 log2N N/2×log2N N/2 全互连 N2 (N/2)2 转14页

三、网络控制方式与拓扑结构 1、集中控制方式与拓扑结构 --SIMD方式 *互连特性：互连函数中的互连须同时实现 *控制实现： (以静态网络为例) 程序从IN外部同时控制所有NIC通道，直到再次控制 PE控制器 计算指令 通信指令 网络控制指令 并行程序指令 PE100 PE101 PE110 PE111 PE000 PE001 PE010 PE011 互连网络控制器 系统控制器(CU) MB SM I/O DISK PE LM NIC ALUs *通信性能：Tcomm＝Nstep×(t0＋dth＋m/B) 其中，Nstep—需求对应C/N指令数，d—源→目标步数 回下页

2、分布控制方式与拓扑结构 --MIMD方式 *互连特性：互连函数中的互连可分时实现 *控制实现： (以静态网络为例) 数据分组从IN内部分时控制相关NIC通道，直到分组通过 说明： ①缓冲队列—级跳传输所需 ②相关通道—分组入→出路径 ③分组通过—分组离开NIC或 穿过交叉开关 入 端 出 4×4交叉 开关 接收器 缓冲 寻径器(路由、调度、控制) 缓冲 发送器 *通信性能：Tcomm＝max{(t0＋d(th＋tc)＋m/B)} 其中，tc—竞争导致的时延，max—不同源→目标导致 △小结：集中式控制—拓扑结构影响IN的功能、性能 分布式控制—拓扑结构不影响IN功能、但影响性能 转上页

级控制、部分级控制--STARAN网络(交换、移数功能) 单元控制--间接二进制n方体网络(更复杂的功能) 3、多级互连网络示例(集中式) (1)多级立方体网络 0级 1 2 3 4 5 6 7 1级 2级 A B C D E F G H I J K L 交换开关：二功能(恒等和交换) 拓扑结构：β(1)+β+逆Shuffle 互连函数：0级--f(b2b1b0)=b2b0b1 1级--f(b2b0b1)=b1b0b2 2级--f(b1b0b2)=b2b1b0 开关组合控制方式： (仍是集中控制) 级控制、部分级控制--STARAN网络(交换、移数功能) 单元控制--间接二进制n方体网络(更复杂的功能)

级控制、开关二功能--STARAN交换网络的逆网络 部分级控制、开关二功能—STARAN移数网络的逆网络 2、多级混洗交换网络（ω网络） A B C D E F G H I J K L 1 2 3 4 5 6 7 2级 1级 0级 交换开关：四功能； 拓扑结构：多级Shuffle 互连函数：2级--f(b2b1b0)=b1b0b2 1级--f(b1b0b2)=b0b2b1 0级--f(b0b2b1)=b2b1b0 开关组合控制： 级控制、开关二功能--STARAN交换网络的逆网络 部分级控制、开关二功能—STARAN移数网络的逆网络 单元控制、开关二、四功能--更强大的功能