Download presentation
Presentation is loading. Please wait.
1
第六章 互连网络
2
第一节 互连网络基本概念 一、互连网络的互连特性 1、互连网络(Interconnection Network)
*概念:由开关元件按一定拓扑结构和控制方式构成的网络,实现节点间的互连 互连网络IN ··· 软件接口 硬件接口 节点 … N-1 IN有单向和双向之分。 *互连特性:多个端口对(同时)、多种端口对组合(分时) *应用:根据需要,可用于P→P及P←→M的并行连接 互连网络IN ··· P PM 回下页
3
*互连函数:出端编码是入端编码的排列、组合、移位、取反等操作的结果,表示所有出端与入端的连接关系
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的出端连接(非对称的) *互连特性的表示:用一组 互连函数表示 *互连特性的选择:用控制信号实现选择(网络控制) 转上页
4
①节点间需同时互连(互连函数需同时实现),如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页
5
二、互连网络的组成 1、网络主要器件 (1)链路 --又称通道或电缆 属性有长度、宽度、定时机制3种
(1)链路 又称通道或电缆 属性有长度、宽度、定时机制3种 *长/短链路:指同一时刻传递多/单个逻辑值(链路上) *宽/窄链路:指信号并行/串行传送 *同步/异步链路:指源端、目标端是/否用公共时钟握手 (2)交叉开关(Crossbar) *组成:N2个交叉点开关[2态] (N个入-出任意连接) 不同拓扑结构实现互连的复杂程度和延时不同。 …… *控制:用信号控制(个数由功能决定) (最多为N2个、常为Nlog2N个) 回下页
6
(3)交换开关(Switch) —又称交换机或路由器 *组成:交叉开关、缓冲区、接收器/发送器、寻径器
入 端 出 交叉 开关 接收器 缓冲区 发送器 寻径器(路由、调度、控制) *控制:由控制信号(外部)、或数据包(内部)控制 *交换开关的度:输入/输出端口的数量(N) 特点—部件部分成本~kN, 即~端口数量×端口宽度 内部连接成本~cN2,即~交换开关度2 转上页 回下页 转4页
7
(4)网络接口电路(Network Interface Circuitry) --又称网卡 *组成:链路接口、缓冲区、DMA通道、控制逻辑等
节点MEM总线或I/O总线 说明: ①实线部分为动态网络NIC一般结构 ②虚线部分为静态网络NIC增加部分,数量由网络拓扑结构决定 节点DMA请求 发送DMA 链路接口 接收DMA 网络接口 电路NIC 交换 开关 总线 接口 *功能:数据包组织、路由构造、数据包发送/接收、 一致性检查、流量和错误控制等 *成本:由端口规模、处理能力和控制电路决定 *设计:软硬件分配取决于IN和节点的特性及性能要求 回下页 转上页
8
节点间的连接在运行期间固定不变,又称直接网络 └→节点直接连接
2、静态互连网络组成 节点间的连接在运行期间固定不变,又称直接网络 └→节点直接连接 *组成:链路、拓扑结构、NIC P100 P101 P110 P111 P000 P001 P010 P011 MB 节点 M NIC P C *拓扑结构:有线性阵列、网格、立方体等多种 *互连特性: 互连函数种类—有限几种(由拓扑结构决定) 互连函数选择—控制NIC 转上页 回下页 回11页 回12页
9
节点间的连接由程序动态地改变,有共享介质、交叉开关、多级互连3种,后2种又称间接网络(节点仅与交换开关连接)
3、动态互连网络组成 节点间的连接由程序动态地改变,有共享介质、交叉开关、多级互连3种,后2种又称间接网络(节点仅与交换开关连接) (1)共享介质网络 同时只存在一个节点对连接(N个节点对连接需分时实现) *组成:链路、拓扑结构、NIC P0 P1 PN-1 … M NIC P MB 节点 C *拓扑结构:总线 *互连特性: 互连函数种类—零个(多个节点对连接只能分时实现) 节点对选择—各NIC自行判别地址 回下页 转上页
10
同时存在N个节点对的任意连接,又称非阻塞网络
(2)交叉开关网络 同时存在N个节点对的任意连接,又称非阻塞网络 *组成:链路、交叉开关(拓扑结构)、NIC M NIC P MB 节点 C … P0 PN-1 *拓扑结构:交叉开关 *互连特性: 互连函数种类—常为Nlog2N种(可为NN种) 互连函数选择—控制交叉开关 转上页 回下页
11
单级互连网络—只有一种互连函数,常为链路+拓扑结构
(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页 转上页 回下页
12
*互连特性:互连函数种类—多种(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页 转上页
13
三、互连网络的性能指标 1、时延 指网络无负载时的传输时延,即网络时延 通信时延=额外开销+网络时延+竞争时延
额外开销—收/发方的软/硬件开销,与节点内核、NIC有关 竞争时延—传输竞争导致的时延,与网络状况、程序行为有关 发送开销 路由时延 接收开销 网络时延 发送方 互连网络 接收方 t 通道时延 软件开销、竞争开销受程序行为影响 网络时延=路由时延+消息长度/通道带宽 路由时延—消息停顿在各交换开关的时间,与拓扑结构有关 通道带宽—消息占用通道导致的时延,与链路带宽及路径有关 回26页
14
目标—反映端口最小带宽 (非对称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页
15
四、互连网络实现的相关问题 主要指网络层的实现,包括控制方式、交换方式、拓扑结构、路由算法、流控机制等 1、控制方式
指互连函数同时/分时实现,对应方式有集中式和分布式2种 *集中式控制: 程序在IN外部同时控制所有交换开关(或NIC)状态, IN保持状态、直到再次控制为止 指令译码器 PE控制器 计算指令 通信指令 网络控制指令 并行 程序 … PEN-1 PE0 PE1 IN控制器 ISC(0) ISC(n-1) 回下页
16
数据分组在IN内部分时控制相关交换开关(或NIC)状态, IN保持状态、直到分组通过或通信完成为止
*分布式控制: 数据分组在IN内部分时控制相关交换开关(或NIC)状态, IN保持状态、直到分组通过或通信完成为止 (取决于交换方式) … PN-1 ISC(0) ISC(n-1) P0 P1 分布式控制的互连网络结构 分布式控制的交换开关结构 入 端 出 交叉 开关 接收器 缓冲区 发送器 寻径器(路由、调度、控制功能) *控制方式的应用: 集中式控制—适合于SIMD系统 分布式控制—适合于MIMD系统 SIMD并行算法需要结点对同时连接,MIMD并行算法无此要求。 转上页 回44页
17
指分布式IN中,消息的传递方式(含寻径及传输) *交换类型:线路交换、包交换
2、交换方式 指分布式IN中,消息的传递方式(含寻径及传输) *交换类型:线路交换、包交换 (1)线路交换 (先寻径,后传输) 先建立物理通路(又称虚电路),再传递消息,最后撤销通路 时间t N1 N2 N3 N4 D 说明:本图忽略了链路传输时延 寻径 寻径 消息 消息 消息 消息 消息3 交换类型是网络层的实现技术,寻径方式是链路层的实现技术 *与集中式控制的差别:仅控制一条路径(非所有路径) *特点:适于成批传送,网络冲突较大(静态占用) 回19页 回下页
18
①消息分解成若干分组独立传送,目标结点再整合成消息 ②IN中相关结点选择路径,保持状态(直至分组通过)
(2)分组(包)交换 (边寻径,边传输) ①消息分解成若干分组独立传送,目标结点再整合成消息 ②IN中相关结点选择路径,保持状态(直至分组通过) └→根据数据包中寻径信息 *数据包的组织: 消息分解为分组,分组封装成数据包(帧), 数据包包含导径、顺序号、数据片等信息 注:数据包和数据片大小固定,未标出帧头/尾 消息 分组 分组 数据包 片 R S D R:导径信息 S:顺序号 D:数据片 网络层的交换单元为分组,链路层的交换单元为数据包(帧) 线路交换实现的是面向连接的服务,包交换实现的是无连接服务 *特点:传输延迟略大,网络冲突较小 转上页
19
*寻径方式:存储-转发(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页
20
3、拓扑结构 是实现互连函数的主要机构 ←交换开关为辅助机构 *拓扑结构种类: 1D—线性阵列 2D—环、树型、胖树型、星型、2D网格等 nD—带弦环、nD网格、立方体、超立方体等 *拓扑结构与互连函数: 拓扑结构的并行链路数,影响互连函数的种类 拓扑结构的链路连接特性,影响互联函数的功能 *控制方式与拓扑结构: 集中式控制—对拓扑结构要求较高 (→常用nD结构) 分布式控制—对拓扑结构要求一般
21
*算法:算术路由、源路由、查表路由、自适应路由等 *目标:避免死锁、均匀负载、维持低时延、容错等
3、路由算法 交换开关决定分组移动方向的算法 └→入→出路径 *算法:算术路由、源路由、查表路由、自适应路由等 *目标:避免死锁、均匀负载、维持低时延、容错等 4、流控机制 流量控制—控制分组发送速度、以适应接收端吸收能力 *流控机制种类:链路级流控、端到端流控 (基于反馈) (基于速率) 流量控制面向某对发送端-接收端,拥塞控制面向整个网络; 链路层流控面向路由器/交换机、采用基于反馈的方法,端到端流控面向主机、采用基于速率的方法 ※拥塞控制—控制分组的传送、以保持网络的承载流量 拥塞控制方法—警告位、抑制分组、绕道、扬弃(NACK)
22
第二节 互连网络与拓扑结构 一、互连函数与拓扑结构 *单级互连网络:只具有一种互连函数的互连网络 即一种互连函数所实现的互连结构
第二节 互连网络与拓扑结构 一、互连函数与拓扑结构 *单级互连网络:只具有一种互连函数的互连网络 即一种互连函数所实现的互连结构 *拓扑结构:由(多个)单级互连网络构成 1、恒等置换 *互连函数:I(b2b1b0)=(b2b1b0) 000 001 010 011 100 101 110 111 N=8恒等置换互连 *互连特性:互连函数可逆,只有一种变换
23
*互连函数:Exchange(b2b1b0)=(b2b1b0)
2、交换置换 编码末位取反 *互连函数:Exchange(b2b1b0)=(b2b1b0) 000 001 010 011 100 101 110 111 N=8交换置换互连 *互连特性:互连函数可逆,只有一种变换 *应用:2×2交换开关可实现恒等、交换变换等功能 恒等 交换 上播 下播 (a)1位控制信号 (b)2位控制信号
24
*互连函数: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 回下页
25
*互连函数: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页
26
*互连函数:β(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页
27
*互连函数:α(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 回下页
28
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页
29
二、互连实现与拓扑结构 *IN互连需求:IN中的节点均可与任意节点连接 *IN实现方法:IN具有多个互连函数,不同互连函数可叠加
1、静态互连网络与拓扑结构 *网络组成:链路、拓扑结构、节点NIC MEM NIC MEM Bus 节点 CPU Cache P100 P101 P110 P111 P000 P001 P010 P011 *互连实现:源→目标节点需穿过多个节点 *拓扑结构:拓扑结构实现互连函数(多个), NIC实现函数选择、函数叠加 *互连性能:由中间节点数决定(与拓扑结构相关) 回下页
30
*网络组成:链路、拓扑结构、交换开关、节点NIC
2、动态互连网络与拓扑结构 *网络组成:链路、拓扑结构、交换开关、节点NIC P0 P1 PN-1 … M NIC P MB 节点 C ISC(0) ISC(n-1) *互连实现:源→目标节点需穿过多个交换开关 *拓扑结构:拓扑结构(单级网络)实现互连函数(多个), 交换开关实现恒等/交换函数、函数叠加 *互连性能:由单级网络、交换开关功能决定 △小结:拓扑结构决定了互连网络的功能及性能! 转上页
31
*连接度:接入或射出节点的连线数(单向网络为两者之和) *网络直径:任意两个节点间互连的最大步数
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页
32
三、网络控制方式与拓扑结构 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—源→目标步数 回下页
33
2、分布控制方式与拓扑结构 --MIMD方式 *互连特性:互连函数中的互连可分时实现
*控制实现: (以静态网络为例) 数据分组从IN内部分时控制相关NIC通道,直到分组通过 说明: ①缓冲队列—级跳传输所需 ②相关通道—分组入→出路径 ③分组通过—分组离开NIC或 穿过交叉开关 入 端 出 4×4交叉 开关 接收器 缓冲 寻径器(路由、调度、控制) 缓冲 发送器 *通信性能:Tcomm=max{(t0+d(th+tc)+m/B)} 其中,tc—竞争导致的时延,max—不同源→目标导致 △小结:集中式控制—拓扑结构影响IN的功能、性能 分布式控制—拓扑结构不影响IN功能、但影响性能 转上页
34
级控制、部分级控制--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方体网络(更复杂的功能)
35
级控制、开关二功能--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移数网络的逆网络 单元控制、开关二、四功能--更强大的功能
Similar presentations