高级计算机体系结构第5章1

1第五章互连网络2第一节互连网络基本概念一、互连网络的互连特性1、互连网络(InterconnectionNetwork)

*概念：由开关元件按一定拓扑结构和控制方式构成的网络，实现节点间的互连

*应用：根据需要，可用于P→P及P←→M的并行连接回下页互连网络IN···软件接口硬件接口节点软件接口硬件接口节点软件接口硬件接口节点0…N-10N-1互连网络IN···P互连网络INPPMPPPM······

*互连特性：多个端口对(同时)、多种端口对组(分时)32、互连特性的表示

*互连函数：出端编码是入端编码的排列、组合、移位、取反等操作的结果，用于表示所有出端与入端的连接关系

入端编码表示—

x＝bn-1…b0，n=log2N

出端编码表示—f(x)＝基于bn-1…b0的操作结果

例2—互连函数f(bn-1…b0)=bn-2…b0bn-1，表示IN的前一半入端与其编码×2的出端连接、后一半入端与其编码÷2的出端连接(非对称的)

例1—互连函数f(bn-1…b0)=bn-1…b0，表示IN的所有端口分为N/2个组，组内入端与出端交叉连接(对称的)

*互连特性的表示：可用一组

互连函数表示转上页

*互连特性的选择：用控制信号实现选择(网络控制)43、应用需求与互连实现方式

*应用需求种类：

①节点互连需同时完成(互连函数需同时实现)，如SIMD②节点互连可分时完成(互连函数可分时实现)，如MIMD

*互连实现方式：应用需求①应用需求②节点互连表示软件指令指明互连目标(程序通知IN)消息内地址指明互连目标(IN解析消息)互连函数实现IN同时控制所有部件

(满足需求)IN分时控制相关部件

(提高效率)P0→P1P4→P5P8→P9P0→P4P4→P8P8→P4P0→P1P4→P5P8→P9P0→P2P4→P6P8→P0P4→P8同时互连示例分时互连示例节点P0节点P4节点P8P0→P2P4→P6P8→P0回6页51、网络主要器件(1)链路--又称通道或电缆

属性有长度、宽度、定时机制3种

*长/短链路：指同一时刻可传递多/单个逻辑值

*宽/窄链路：指数据及控制信号可并行/串行传送

*同步/异步链路：指源端、目的端是/否使用公共时钟握手二、互连网络的组成(2)交叉开关(Crossbar)

*组成：N2个交叉点开关[2态]，(建立N个入-出连接)

*控制：用控制信号控制，控制信号数由功能决定(最多为N2个、常为Nlog2N个)……回下页6(3)交换开关(Switch)—又称交换机或路由器

*组成：交叉开关、缓冲区、接收器/发送器、寻径器

*控制：由控制信号(外部)、或数据包(内部)控制

*交换开关的度：输入/输出端口的数量(N)特点—部件部分成本～kN，即～端口数量×端口宽度内部连接成本～cN2，即～交换开关度2入端出端交叉开关接收器缓冲区缓冲区发送器寻径器(路由、调度、控制)转上页回下页转4页7(4)网络接口电路(NetworkInterfaceCircuitry)--又称网卡

*组成：链路接口、缓冲区、DMA通道、控制逻辑等*设计：软硬件分配取决于IN和节点的特性及性能要求*功能：数据包组织、路由构造、数据包发送/接收、

一致性检查、流量和错误控制等*成本：由端口规模、处理能力和控制电路决定转上页节点MEM总线或I/O总线说明：①实线部分为动态网络NIC一般结构；②虚线部分为静态网络NIC增加部分，数量由网络拓扑结构决定节点DMA请求发送DMA链路接口接收DMA网络接口电路NIC链路接口交换开关发送DMA接收DMA总线接口回下页82、静态互连网络组成

节点间的连接在运行期间固定不变，又称直接网络

└→节点直接连接

*组成：链路、拓扑结构、NIC

*拓扑结构：有线性阵列、网格、立方体等多种

*互连特性：

互连函数种类—有限几种(由拓扑结构决定)

互连函数选择—控制NIC转上页P100P101P110P111P000P001P010P011MB节点MNICPCNIC回下页回11页回12页93、动态互连网络组成

节点间的连接由程序动态地改变，有共享介质、交叉开关、多级互连3种，后2种又称间接网络(节点仅与交换开关连接)(1)共享介质网络

同时只存在一个节点对连接(N个节点对连接需分时实现)

*组成：链路、拓扑结构、NIC

*拓扑结构：总线

*互连特性：

互连函数种类—零个(多个节点对连接只能分时实现)

节点对选择—各NIC自行判别地址

*与线性阵列静态网络的区别：通道数量、互连方向性P0P1PN-1…MNICPMB节点C转上页回下页10(2)交叉开关网络

同时存在N个节点对的任意连接，又称非阻塞网络

*组成：链路、交叉开关(拓扑结构)、NIC

*互连特性：

互连函数种类—常为Nlog2N种(可为NN种)

互连函数选择—控制交叉开关

*拓扑结构：交叉开关MNICPMB节点C…P0PN-1…P0PN-1转上页回下页11(3)多级互连网络

单级互连网络—只有一种互连函数，常为链路＋拓扑结构

*组成：链路、交换开关、单级网络、NIC

*拓扑结构：可为静态网络的各种结构，各ISC(i)可不同

*互连特性：

互连函数种类—多种(可为N!种，数量由拓扑结构决定)

互连函数选择—控制交换开关ISC(O)P0P1…PN-1…………………ISC(n-1)P0P1…PN-1ISC(1)…MNICPMB节点C

多级互连网络—用交换开关级联多个单级网络，

实现N个节点对的有限连接转上页转8页回下页124、混合互连网络的组成

*组成示例：(可扩展性较强)

*互连特性：互连函数种类—多种(M×N×L)

互连函数选择—组合控制各个网络

共享介质网络：总线动态网络交叉开关网络：n×n交叉开关(非阻塞)

多级互连网络：单向多级、双向多级、单向环1D网络：线性阵列静态网络

2D网络：环、树型、胖树型、星型、2D网格等

nD网络：带弦环、nD网格、立方体、超立方体等主干网(超立方体网络)主干节点0主干节点N-1…主干节点网(静态网格网络)网格节点0网格节点M-1…网格节点网(总线网络)叶节点0(2个P)叶节点L-1…

※IN组成小结：转8页转上页13三、互连网络的性能指标1、时延

指网络无负载时的传输时延，即网络时延

通信时延＝额外开销＋网络时延＋竞争时延额外开销—收/发方的软/硬件开销，与节点内核及NIC有关

竞争时延—网络传输竞争导致的时延，与网络状况及程序行为有关回26页发送开销路由时延接收开销网络时延发送方互连网络接收方t通道时延

网络时延＝路由时延＋消息长度/通道带宽路由时延—消息停顿在各交换开关的时间，与拓扑结构有关

通道带宽—消息占用通道导致的时延，与链路带宽及路径有关14回30页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’为最大等分平面链路数15四、互连网络的实现要点主要指网络层的实现，包括控制方式、传输机制、拓扑结构、路由算法、流控机制等1、控制方式

指互连函数同时/分时实现，方式有集中式和分布式2种

*集中式控制：

程序在IN外部同时控制所有交换开关(或NIC)状态，IN保持状态、直到再次控制为止回下页指令译码器PE控制器计算指令通信指令网络控制指令并行程序…PEN-1PE0PE1…PEN-1PE0PE1IN控制器ISC(0)………………ISC(n-1)…回31页16

*分布式控制：

数据分组在IN内部分时控制相关交换开关(或NIC)状态，IN保持状态、直到分组通过或通信完成为止（交换方式不同）

*控制方式的应用：

集中式控制—适合于SIMD系统

分布式控制—适合于MIMD系统转上页…PN-1ISC(0)………………ISC(n-1)P0P1…PN-1P0P1…分布式控制的互连网络结构分布式控制的交换开关结构入端出端交叉开关接收器缓冲区缓冲区发送器寻径器(路由、调度、控制功能)回32页17

*传输机制(寻径技术)种类：

存储-转发(Store-and-Forward)、切通(Cut-Through)回下页2、传输机制

指分组在分布式控制IN中的传送方式

*分组的传输组织：网络层交换单元是分组，链路层交换单元是数据包(帧)；

数据包可分解成若干个数据片消息分组分组包片RSDDDDR：导径信息S：顺序号D：数据片注：数据包和数据片大小固定，未标出帧头/尾18*存储-转发传输方式：

数据包串行传输，缓冲数据包*切通传输方式：

数据包流水传输(Δt＝数据片)，正常时缓冲数据片，

阻塞时缓冲数据包(虚拟直通方式)、或数据片(虫蚀方式)

*比较：前者拥塞的代价小、后者时延与距离无关RtR1R2R3R4交换开关tR1R2R3R4交换开关转上页T＝t0＋d(th＋m/B)T＝t0＋dth＋m/B≈t0＋m/B193、拓扑结构

是实现互连函数的主要机构

←交换开关为辅助机构

*拓扑结构种类：1D—线性阵列2D—环、树型、胖树型、星型、2D网格等nD—带弦环、nD网格、立方体、超立方体等

*控制方式与拓扑结构：

集中式控制—对拓扑结构要求较高

(→常用nD结构)

分布式控制—对拓扑结构要求一般

*拓扑结构与互连函数：

并行链路数量—影响互连函数的种类

链路连接特性—影响互连函数的功能203、路由算法

交换开关决定分组移动方向的算法

└→入→出路径

*算法：算术路由、源路由、查表路由、自适应路由等

*目标：避免死锁、均匀负载、维持低时延、容错等4、流控机制

流量控制—控制分组发送速度、以适应接收端吸收能力*流控机制种类：链路级流控、端到端流控(基于反馈)(基于速率)

※拥塞控制—控制分组的传送、以保持网络的承载流量拥塞控制方法—警告位、抑制分组、绕道、扬弃(NACK)21第二节拓扑结构1、恒等置换

*互连函数：I(b2b1b0)=(b2b1b0)000001010011100101110111N=8恒等置换互连000001010011100101110111

*互连特性：互连函数可逆，只有一种变换一、互连函数与拓扑结构

*单级互连网络：只具有一种互连函数的互连网络

即互连函数所实现的互连结构

*拓扑结构：由(多个)单级互连网络构成222、交换置换

--编码末位取反

*互连函数：Exchange(b2b1b0)=(b2b1b0)000001010011100101110111N=8交换置换互连000001010011100101110111

*互连特性：互连函数可逆，只有一种变换

*应用：2×2交换开关可实现恒等和交换变换、及其它功能，

需1位或2位控制信号恒等交换上播下播(a)1位控制信号(b)2位控制信号恒等交换233、立方体置换

--编码某位取反

*互连函数：Cubek(bn-1…bk…b0)=(bn-1…bk…b0)000001010011100101110111N=8Cube0置换互连000001010011100101110111000001010011100101110111N=8Cube1置换互连000001010011100101110111000001010011100101110111N=8Cube2置换互连000001010011100101110111

*互连特性：互连函数可逆，有n种(Cube0，…，Cuben-1)变换

*应用：n立方体结构可实现n种Cube变换，zyx010011110111000001101100NICCPUXYZCPUXYZ每个节点需n位控制信号回下页244、混洗置换

--编码最高位移位

*互连函数：Shuffle(bn-1bn-2…b1b0)=(bn-2…b1b0bn-1)000001010011100101110111N=8混洗置换互连000001010011100101110111

*互连特性：互连函数不可逆(首尾节点只连接自身)，

只有一种变换

*应用：混洗与交换结构可实现任意节点间互连01234567特征—多级网络ISCi可只有一种互连(混洗)转上页255、蝶式置换

--编码位交换位置

*互连函数：β(bn-1bn-2…b1b0)=(b0bn-