第一节 互连网络基本概念 一、互连网络功能 1、互连网络 定义：互连网络是由开关元件按照一定拓扑结构和控制方 式构成的网络，实现多个结点对之间的相互连接。 结点 结点 结点 软件接口 硬件接口 软件接口 硬件接口 · · · 软件接口 硬件接口 互连网络IN 互连应用：根据处理单元PE与存储单元PM的结构特征， IN可PE→PE和PE←→PM的连接。 PE · · · 互连网络IN PE PE · · · 互连网络IN PE PM · · · PM 2、互连网络功能-设计目标 空间特性：能够实现某结点到任意结点的互连； 时间特性：同一时刻能够实现多个结点对的互连。 0 0 … 0 0 … N-1 互连网络功能的应用： 空间特性满足并行算法的并行性需求； 时间特性满足并行算法的同步、异步需求。 互连网络与总线比较： 互连网络同时有多个不相关通道存在； 互连网络的通道具有方向性(可为非对称)。 … … N-1 N-1 N-1 3、互连函数 主要用于表示互连网络互连的空间特性。 互连函数定义： 是入端编码的排列、组合、移位、取反等操作的结果。 入端编码表示：x=（bn-1…b0) n=log2N 出端编码表示：f(x)=基于(bn-1…b0)的操作的结果。 并行算法与互连函数： 并行算法--在不同时刻按照不同规则实现不同结点间 的连接与通信； 互连函数—可表示并行算法的连接规则； 并行算法的连接规则可通过一组互连函数表示。 互连函数与互连网络： 不同的互连函数可通过互连网络不同控制信号实现。 二、互连网络种类 1、静态互连网络 结点到结点的连接在运行期间不改变，又称直接网络。 组成：由链路、拓扑结构及网络接口电路NIC组成。 PE010 PE011 M P C MB M P C 结点 MB PE100 PE111 PE000 PE001 NIC 结点 Bridge I/OB NIC PE100 PE100 拓扑结构：有线性阵列、网格、立方体等多种结构。 互连功能实现： 互连空间特性通过NIC的数据寻径功能实现； 互连时间特性由拓扑结构及网络控制方式决定。 2、动态互连网络 结点到结点的连接由程序动态地改变，包括共享介质、非 阻塞、基于开关的三种子类型网络。 （1）共享介质网络 同时只允许一个结点对连接，即多个结点对分时互连。 组成：由链路、拓扑结构及NIC组成。 PE0 PE1 … PEN-1 PE0 PE1 … PE N-1 拓扑结构：包括总线、环状结构。 互连功能实现：互连空间特性通过NIC的地址判别实现； 互连时间特性是分时互连。 与环状静态网络区别：链路中同时存在的结点对数量不同。 （2）非阻塞网络 同时允许所有结点对连接，即所有结点对可同时互连，又 称交叉开关网络。 组成：由链路、交叉开关及NIC组成。 交叉开关--由N2个交叉点开关组成， 每个交叉点开关只有两个状态(通/断)； 拓扑结构—无。 PE0 … PEN-1 PE0 … PEN-1 互连功能实现： 通过控制N2个开关状态可实现无阻塞的互连空间特性 和时间特性。 （3）基于开关的网络 结点到结点通过交换开关进行连接(无直接相连通道)，即 结点只与交换开关连接，又称间接网络。 0 组成：由链路、交换开关(交换机)、 NIC NIC1 … ISC(n-l) … … … ISC(O) NIC0 NIC1 … NICN-1 各级间拓扑结构(ISC)、 NIC组成。 思考：为什么要用多级拓扑结构？ … NICN-1 拓扑结构：可为静态网络的各种结构。 互连功能实现： 互连空间特性通过交换开关和拓扑结构实现； 互连时间特性由交换开关的控制方式决定，集中/分布 控制实现多个结点对连接的同时/分式实现。 3、混合互连网络 为静态互连网络和动态互连网络的混合体，即网络中包含 了多种网络。 混合网络的可扩展性较强。 例如：以基于开关的超立方体网络为主干网； 主干网中每个结点为一个静态网格网络； 网格网络中每个结点为一个共享介质的总线个处理单元。 三、互连网络相关问题 有控制方式、交换策略、拓扑结构、路由算法、流控机制 等几个方面。 1、控制方式 控制方式用于实现网络互连时间特性(同时或分时)。 控制方式分集中控制和分布控制两种。 集中控制：程序在网络外部同时控制所有NIC寻径器或交换 开关状态，直到再次控制为止。即先控制(先寻径)、后传输。 指令译码器 ALU控制器 PEN-1 PE0 PE1 … ISC(n-l) … PE0 PE1 ISC(O) … … … … PEN-1 IN控制器 分布控制：消息在网络内部分时控制相关NIC寻径器或交换 开关状态，直到消息通过或传输完成为止。即边控制(边寻径)、 边传输。 PE0 PE1 … ISC(n-l) … … … ISC(O) PE0 PE1 … PEN-1 … PEN-1 输 入 端 口 接收器 缓冲区 缓冲区 发送器 交叉 开关 路由、调度、控制 输 出 端 口 应用： 集中控制适合于SIMD系统，采用同步并行算法； 分布控制适合于MIMD系统，采用异步并行算法。 2、交换策略 交换策略有线路交换和包交换两种。 （1）线路交换 程序在源和目的结点间建立一条路径，直到传输完成(消息 全部通过)为止。（先寻径，后传输） D N1 N2 N3 N4 说明：本图传输时忽略了链路时延。 消息1 消息2 T 应用： 线路交换一般与集中控制配对，应用于SIMD系统； 线路交换也可与分布控制配对，应用于MIMD系统，如 面向连接的通信。 （2）数据包交换 将消息分成一系列数据包独立发出，各NIC或交换开关根据 目的结点地址，在当前节点与下级节点间选择一条路径传输数 据包，目的结点整合各数据包成为消息。（边寻径，边传输） 消息格式— 消息由数据包组成，数据包由数据片组成。 消息大小可变，数据包和数据片大小固定。 消息 包 片 D D D D S R R：导径信息 S：顺序号 D：数据片 传输方式—分为存储-转发、虫孔寻径两种。 存储-转发—传输单位为数据包，寻径、传输串行进行， 中间节点需缓冲整个数据包。 D 数据包1 N1 N2 N3 N4 数据包2 R T 虫孔寻径—传输单位为数据片，寻径、传输流水进行， 中间节点需缓冲数据片。 D 数据包1 N1 N2 N3 N4 数据包2 T 应用—包交换只能与分布控制配对，应用于MIMD系统。 转上二页 回17页 3、拓扑结构 是实现互连功能的主要机构，反映互连函数实现的复杂度。 拓扑结构与互连函数： 网络拓扑结构不同，实现互连函数的效率不同。 如：高维拓扑结构实现移位函数效率总比低维结构好； 又如：对称拓扑结构实现交换函数效率总比非对称结 构好。 互连函数与并行算法： 不同的并行算法需要不同的互连函数支持； 同一系统的应用需要支持多种并行算法。 集中控制方式对拓扑结构的要求较高，直接影响并行算法 的实现效果(同时连接的结点对数量)； 分布控制方式对拓扑结构的要求一般。 4、路由算法 决定消息在网络图中如何移动(选择路径)的算法。 采用分布控制的互连网络才涉及到路由问题。 路由算法：算术路由、源路由、查表路由、自适应路由等。 路由算法目标：避免死锁、维持低时延、均匀分布负载、 容错等。 4、流控机制 在资源使用冲突时控制各通道流量(带宽)的机制。 流控机制层次： 有链路级流控、端到端流控两个层次。 四、互连网络基本性能 时延和带宽是评价互连网络性能的两个基本指标。 1、时延 发送方 互连网络 接收方 发送方 开销 传输时间 飞行时间 传输时延 传输时间 接收方 开销 通信时延=额外开销+飞行时间+消息长度/通道带宽 额外开销—指收/发双方软/硬件开销，与结点内核及 NIC结构有关； 飞行时间—与结点间距离(拓扑结构)及通道带宽有关； 通道带宽—与链路带宽和通道竞争情况有关。 2、带宽 可通过端口带宽、聚集带宽和等分带宽表示网络带宽特性。 端口带宽：结点或交换机每个端口(输入和输出)的带宽。 聚集带宽：网络的前一半节点(与结点不同含义)与后一半 节点间传输的带宽，一般指网络内部带宽的总和。 等分带宽(对剖带宽)：将网络按结点均匀切成两个子网， 子网间的通信带宽。 输出带宽+输入带宽=端口带宽b 结点0 结点N/2-1 结点N/2 结点N-1 回28页 回30页 … … … 结点0 等分带宽B=lwb/2 说明：l、l’为穿过剖面链路数； w为每条链路连线数。 聚集带宽l’wb/2 … 结点N/2-1 结点N/2 … … 节点 (交换开关) … … 结点N-1 第二节 互连网络与拓扑结构 一、互连函数与拓扑结构 互连函数是并行算法与硬件互连的结合点。 拓扑结构是硬件互连实现互连函数的有效机构。 互连函数也可称为单级互连网络。 1、恒等置换 互连函数：I(b2b1b0)=(b2b1b0) 000 001 010 011 100 101 110 111 N=8恒等置换 000 001 010 011 100 101 110 111 互连特性：互连函数可逆；只有一种变换功能。 2、交换置换 互连函数：Exchange(b2b1b0)=(b2b1b0) 000 001 010 011 100 101 110 111 000 001 010 011 100 101 110 111 N=8交换置换 互连特性：互连函数可逆；只有一种变换功能。 应用：2×2交换开关可实现恒等置换与交换置换功能，功 能控制可通过外部信号或内部消息译码实现。 恒等 交换 上播 下播 3、立方体置换 互连函数：Cubek(bn-1…bk…b0)=(bn-1…bk…b0) 000 001 010 011 100 101 110 111 000 001 010 011 100 101 110 111 000 001 010 011 100 101 110 111 N=8 Cube1置换 000 001 010 011 100 101 110 111 000 001 010 011 100 101 110 111 000 001 010 011 100 101 110 111 N=8 Cube0置换 N=8 Cube2置换 y 010 110 000 100 z 111 011 001 互连特性：互连函数可逆； n位编码有n种(Cube0，…， Cuben-1)变换功能。 应用：n立方体结构可实现n种立方 体变换，功能控制可通过各端点的外部 x 101 信号或内部消息译码实现。 4、混洗置换 互连函数：Shuffle(bn-1bn-2…b1b0)=(bn-2…b1b0bn-1)； 000 001 010 011 100 101 110 111 N=8 混洗置换 000 001 010 011 100 101 110 111 互连特性：互连函数不可逆(全0、全1编码的结点除外)； 只有一种变换功能。 应用：混洗变换与交换变换的多次组合，可实现某结点到 任意结点的连接。 0 回32页 1 2 3 4 5 6 7 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 000 001 010 011 100 101 110 111 000 001 010 011 100 101 110 111 N=8 β(1)子蝶式置换 子蝶式和超蝶式置换： β (k)(bn-1…bk+1bkbk-1…b0)=(bn-1…bk+1b0bk-1…b1bk)； β (k)(bn-1…bn-kbn-k-1bn-k-2…b0)=(bn-k-1bn-2…bn-kbn-1bn-k-2…b0)； 互连特性：互连函数可逆； n位编码有2n-2种(子、超各为n-1)变换功能。 应用：蝶式与子蝶式变换实现分组功能，加上交换变换， 可实现某结点到任意结点的连接。 6、移数置换 互连函数：α (X)=(X+k) mod N，0≤k≤N-1； 000 001 010 011 100 101 110 111 000 001 010 011 100 101 110 111 000 001 010 011 100 101 110 111 k=2移数置换 000 001 010 011 100 101 110 111 k=1移数置换 互连特性：互连函数不可逆(k=0除外)； n位编码有2n个移数变换功能。 应用：单向带弦环可实现移数置换功能(内弦连接不同实现 的间隔不同)，双向带弦环可实现两个移数置换。 7、加减2i置换 --移数置换的特例 互连函数：PM2I+i(j)=(j+2i) mod N PM2I-i(j)=(j-2i) mod N 其中 0≤i≤log2N-1, 0≤j≤N-1 互连特性：互连函数不可逆(i=±n除外)； n位编码有2n-1种变换功能。 应用：几种PM2I变换的组合，可实现某结 点到任意结点的连接，组合不同效率不同。 例：闭合螺旋结构为PM2I+0(横向)及 1 2 3 4 5 0 7 6 PM2I±n/2(纵向)互连函数。 二、静态互连网络 特点：结点到结点的连接在运行期间不改变。 互连实现过程： 源→目标结点的连接一般需要穿过几个中间结点； 当前中间结点的NIC负责转发消息到下个结点。 结点NIC组成： 一般有多个输入/输出通道，其中一对连接本结点CPU； 所有通道有外部信号和内部信号控制两种控制方式。 网络集中控制：控制器根据同时通信的所有消息源、目标 结点地址和拓扑结构类型，生成所有NIC的所有通道的外部控制 信号； 网络分布控制：当前NIC根据当前消息源、目标结点地址和 拓扑结构类型，生成当前NIC的部分通道的内部控制信号。 1、网络结构性能参数 连接度：结点与其它结点的直接连接程度，即结点NIC直接 连接的结点数。 距 直 带 离：两个结点互连的最少步数。 静态网络=1，动态网络＞1。 径：两个结点互连的最大步数。 与连接度和拓扑结构有关。 宽：可同时连接的结点对数。 与连接度和拓扑结构有关。 2、静态网络拓扑结构与性能 常见网络拓扑结构及相关性能参数： 维数 拓扑结构 最大连接度 直径 链路数 等分带宽 一维 二维 线性 环状 网格 星形 二叉树 2 2 4 N-1 3 log2N N-1 N-1 N 2N - 2 N 1 2 N ?N / 2? 2( N ? 1) 2 2[log2N1] log2N N-1 N-1 N/2×log2 N ?N / 2? 1 N/2 多维 超立方体 拓扑结构与性能参数间相互关系： N-1 1 N 全互连 N！ 拓扑结构以结点连接度为基础； 相同连接度时，拓扑结构不同，网络直径与带宽不同。 转18页 三、动态互连网络 特点：结点到结点的连接由程序动态地改变。 互连实现过程： 源→目标结点的连接不穿过中间结点，可能需穿过多 个交换开关； 交换开关根据外部/内部信号控制消息的转发。 结点NIC组成： 只有一对输入/输出通道；无转发功能。 网络集中控制：控制器根据同时通信的所有消息源、目标 结点地址和拓扑结构类型，生成所有开关的外部控制信号； 网络分布控制：当前开关根据当前消息源、目标结点地址 和拓扑结构类型，生成当前开关的部分通道的内部控制信号。 1、总线 互连控制：只能采用集中方式实现控制； 控制机构--总线仲裁机构。 总线与线性阵列比较： 总线； 线； 线性阵列的性能优于总线页 2、交叉开关 互连控制：可采用集中、分布方式实现控制； 通过N2个交叉开关组合完成控制。 带宽：等分带宽=(N/2)N/2，聚集带宽=(N/2)N/2。 2×2开关模块： 恒等 交换 上播 下播 根据置换和播送功能，控制信号可为1位或2位。 3、多级网络—单级互连循环网络 组成：单级互连函数拓扑 结构+多路选择器。 控制：循环次数根据入-出 结点编码要求决定。 单级互连函数拓扑结构： 循环 PE0来 去PE0 PEN-1来 去PEN-1 DTR … MUX MUX 单 个 互 连 函 数 拓 扑 DTR ①经过循环能够实现某结点到任意结点的互连； ②经过循环能够改变同时连接的结点对间相互关系。 如：单级混洗交换函数、移数函数等构成的拓扑结构。 网络带宽：等分带宽=N/2，聚集带宽=N/2。 转22页 4、多级网络—多级互连网络 组成：交换开关+级间拓扑结构。 控制：可采用集中、分布控制方式对交换开关进行控制。 0 1 2 3 4 5 6 7 2×2 2×2 2×2 2×2 ISC 0 2×2 2×2 2×2 2×2 ISC 1 2×2 2×2 2×2 2×2 ISC 2 0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7 A B C D 0级 E F G H 1级 I J K L 2级 0 1 2 3 4 5 6 7 0级 1级 2级 各级拓扑结构(ISCi)： 组合后能实现网络的空间、时间特性。 要求较单级循环互连要低得多。 网络带宽：等分带宽=N/2，聚集带宽=N/2。 四、SIMD多级互连网络 1、多级立方体网络 0 1 2 3 4 5 6 7 A B C D 0级 E F G H 1级 I J K L 2级 0 1 2 3 交换开关：二功能(恒等和交换)； 4 5 6 7 拓扑结构：β (1)+β +逆Shuffle； 互连函数：0级--f(b2b1b0)=b2b0b1 1级--f(b2b0b1)=b1b0b2 2级--f(b1b0b2)=b2b1b0 开关组合控制： 级控制、部分级控制--STARAN网络(交换、移数功能)； 单元控制--间接二进制n方体网络(更复杂的功能)。 （1）交换功能 开关组合控制方式：级控制。 0 1 000 0 1 2 3 4 5 6 7 001 1 0 3 2 5 4 7 6 010 2 3 0 1 6 7 4 5 级控制信号（k2k1k0） 011 3 2 1 0 7 6 5 4 100 4 5 6 7 0 1 2 3 101 5 4 7 6 1 0 3 2 110 6 7 4 5 2 3 0 1 111 7 6 5 4 3 2 1 0 入 端 2 3 4 5 6 7 i 功 能 Cube0 Cube1 Cube0 + Cube1 Cube2 Cube0 Cube1 Cube0 + + + Cube2 Cube2 Cube1 + Cube2 分组交换功能：组间次序不变，组内元素镜像。 Cube0--4组2元交换；Cube1--2组4元交换+4组2元交换； Cube2--1组8元交换+2组4元交换。 （2）移位功能 开关组合控制方式：部分级控制(第i级有i+1种控制信号) 2级 K,L J I F,H E,G A,B,C,D 功 能 0 0 1 0 1 1 0 1 1 1 1 0 1 1 1 0 0 0 0 0 0 0 1 1 0 0 0 1 1 0 0 0 0 0 0 1 0 0 0 0 0 0 1级 0级 移1 Mod 8 移2 Mod 8 移4 Mod 8 移1 Mod 4 移2 Mod 4 移1 Mod 2 不移 衡等 Mod的作用：不同Mod可用于不同的分组操作。 （3）应用 交换功能很适合于双向互连等要求的实现； 移数功能很适合于累加求和等要求的实现。 （4）带宽问题 STARAN可同时多对结点连接，尚不能同时任意组合。 （5）例题 例1：16个PE采用STARAN网络互连时，实现相当于4组4元交 换，然后2组8元交换，再1组16元交换功能。写出互连函数一般 式、各级交换开关状态。 答：因需实现交换功能，故选择STARAN的交换功能(级控制 方式）。 4组4元交换 2组8元交换 1组16元交换 Cube0+Cube1 Cube0+Cube1+Cube2 Cube0+Cube1+Cube2+Cube3 相加 Cube0+Cube1 +Cube3 互连函数：f(b3b2b1b0)=(b3b2b1b0) 各级开关状态：k3k2k1k0=(1011) 例2：编号0~F的PE间，要实现下列通信配对：(7,D),(6,C), (5,F),(4,E),(3,9),(2,8),(1,B),(0,A)。请画出互连网络结构 图，写出控制方式及各开关状态。 答：因需实现双向交换功能，选择STARAN网络的交换功能 (级控制方式)可满足要求。 网络拓扑结构： 因共有16个结点，编码需要4位，所以开关共4级。 0级—开关+β 1级--开关+β (1)，f(b3b2b1b0)=b3b2b0b1 (2)，f(b3b2b0b1)=b3b1b0b2 2级--开关+β ， f(b3b1b0b2)=b2b1b0b3 3级--开关+逆Shuffle，f(b2b1b0b3)=b3b2b1b0 回下页 0 1 2 3 4 5 6 7 8 9 A B C D E F 0 1 2 3 4 5 6 7 8 9 A B C D E F 级 k0 k1 k2 k3 转上页 配对要求：(7,D),(6,C),(5,F),(4,E),(3,9),(2,8),(1,B),(0,A) 开关控制： 因≤7的结点与＞7的结点配对，故需1组16元交换； 因0~3的结点与8~B的结点配对，故需2组8元交换； 因0~1的结点与A~B的结点配对，故需4组4元交换； 因0结点与A结点配对，故需8组2元交换。 1组16元交换 2组8元交换 4组4元交换 8组2元交换 Cube0+Cube1+Cube2+Cube3 Cube0+Cube1+Cube2 Cube0+Cube1 Cube0 Cube3 相加 Cube1+ 各级开关状态：k3k2k1k0=(1010) 2、多级混洗交换网络（ω 网络） 0 1 2 3 A B C D 2级 E F G H 1级 I J K 0 1 2 3 4 5 6 7 交换开关：四功能； 拓扑结构：多级Shuffle； 互连函数：2级--f(b2b1b0)=b1b0b2 1级--f(b1b0b2)=b0b2b1 0级--f(b0b2b1)=b2b1b0 4 5 6 7 L 0级 开关组合控制： 级控制、开关二功能--STARAN交换网络的逆网络； 部分级控制、开关二功能—STARAN移数网络的逆网络； 单元控制、开关二、四功能--更强大的功能。 3、全排列网络 （1）多级网络比较 灵活性(低→高)：STARAN、间接二进制n方体、 Omega(ω )、ADM(混洗四功能) 成本(低→高)：同上 用途： STARAN、Omega PE←→M 间接二进制n方体 PE→PE 功能：只能实现同时部分多对多功能。 （2）全排列网络 定义：所有入端、出端的连接均不发生冲突的网络，又称 非阻塞型网络，即：N入→N出有N！种排列。 常规多级网络(如STARAN、ω 等)属于阻塞型网络。 证明：对n=log2N级网络，开关数=N/2×n。 排列数 ? 2 ( N / 2?log 2 N ) N ?2 log 2 N N / 2 ? N N /2 ? N 全排列网络实现： ? N !? N N 思想：N!＜NN/2×NN/2＜NN。 方法：a.原有多级网络通过锁存器运行两次即可； b.两个log2N网络背靠背串联。 五、MIMD互连网络 互连组合与互连时间要求： 要求实现结点与任意结点互连，但不要求同时。 P2→P3 P0→P1 应用需求 t P2→P3 P0→P1 SIMD互连 t P2→P3 P0→P1 MIMD互连 t 控制方式： 采用分布控制方式，即各NIC或交换开关只根据消息的 源和目的地址控制本身的状态(不能影响已连接的通道)。 拓扑结构： 拓扑结构不影响互连函数的实现，只影响互连函数实 现的效率或性能。 第三节 1、线 消息传递机制 一、消息寻径方式与传输性能 --面向连接 消息1 消息2 传递消息前，先建立源到目的结点的物理通路。 T 说明：本图传输时忽略了链路时延。 网络时延：Tcs(n,d)=dnt/b+n/b≈n/b，其中ntn 寻径阻塞处理：放弃寻径消息nt，等待通道空闲时重发。 回下页 2、包交换 --面向无连接 （1）存储-转发寻径 整个数据包到达中间结点后，再寻径和转发。 D 数据包1 N1 N2 N3 N4 数据包2 R T 网络时延：Tsf(n’,d)=dnt/b+dn’/b=d(nt+n’)/b 对单个消息，存储-转发比线路交换时延大； 对整个网络，存储-转发比线路交换利用率高。 寻径阻塞处理：中间结点需要缓冲整个数据包，等待通道 空闲时转发。 转上页 回下页 （2）虚拟直通寻径 包的寻径头部到达中间结点后即可寻径、传输。 D 数据包1 N1 N2 N3 N4 T 网络时延：Tvd(n’,d)=dnt/b+n’/b≈n’/b 网络状态较好时，虚拟直通与线路交换时延相当； 网络状态不好时，虚拟直通与存储-转时延相当。 寻径阻塞处理：中间结点需要缓冲几个数据片(最多为整个 数据包)，等待通道空闲时转发。 转上页 回下页 （3）虫孔寻径 将数据包分成很小的数据片，各片以流水方式传输。 D 数据包1 N1 N2 N3 N4 数据包2 T 网络时延：Twh(n’,d)=dnt/b+n’/b≈n’/b 网络状态较好时，虫孔寻径与线路交换时延相当； 网络状态不好时，虫孔寻径不如存储-转时延。 寻径阻塞处理：中间结点只需缓冲一个数据片(非消息或数 据包)，所有中间结点全部停顿(流水占用一连串资源)。 转上页 中间结点流水状态表示：用一根就绪/请求线实现相邻结点 间的握手协议。 前一结点 R/A 后一结点 路由S（发送方） 路由D（接收方） 状态 发送准备好 正在发送 R/A线 低→高 高 状态 可接收片 正在接收 R/A线 高→低，低 不驱动 物理通道 禁止接收 不驱动 寻径阻塞处理的优化：采用虚拟通道方法，使一个物理通 道为多个数据包传输所共享。 2×2 交换 开关 2 ×2 交换 开关 ) R/A 物理通道( 前一结点 后一结点 回54页 二、路由算法 所有的路由算法都是根据网络拓扑结构的特征而设计的。 路由算法有确定性路由算法和自适应路由算法两大类。 确定性路由算法：路由只与源和目的地址有关； 自适应路由算法：路由除与源和目的地址有关外，还与网 络传输状态(路径上的其他流量)有关。 1、确定性路由算法 一般有算术路由法、源路由法、查表路由法三种。 （1）算术路由法 各交换开关根据消息中源与目的地址、拓扑结构中的当前 开关位置来计算到下级开关的所选路径。 如：2D网格的X-Y路由算法、3D立方体的E立方路由算法等。 特点：当前开关需知道自己在网络中的位置。 （2）源路由法 源结点根据源与目的地址计算出沿途各交换开关的输出端 口号插入消息中；各开关根据消息中相关信息选择开关状态。 特点：降低了开关的复杂度，源结点需知道全部网络拓扑 结构。 （3）查表路由法 源结点根据目的地址计算出路由域i插入消息中；各交换机 维护一个路由表R(包含输出端口o及下一跳路由域i’)，以消息 中路由域i为索引查表R，得o=R[i]及i’，修改i=i’，将消息从端 口o转发出去。 特点：当前交换机(交换开关)只需知道下级交换机路由域 即可。适合复杂的网络连接。 回下页 2、自适应路由算法 一般为确定性路由算法的扩展算法，即可根据网络传输状 况在几条路径中选择一条。 扩展算术路由算法：数据包头中增加控制信息，由交换机 识别并控制(需改变交换机设计)； 扩展源路由算法：源结点从多条路径中选(根据历史信息) 一条到数据包头中(不改变交换机设计)； 扩展查表路由算法：路由表项中包含多条路由域i’，交换 机根据网络状态选择并控制。 应用：不广泛(交换机时延的增加抵消了带宽的增加，可通 过其他方法解决负载不均匀问题)。 转上页 三、死锁解决 1、死锁产生原因 迎面死锁：两个结点相互以同步方式发送消息时会发生。 消 息 处 理 ① ④ 结点A ③ ② 结点B 消 息 处 理 结点A-结点B迎面死锁示意图 路由死锁：资源为非抢占式、网 络中通道缓冲区已满时，各消息路径 构成闭环时会产生。 路由死锁示意图 回下页 2、死锁的避免 （1）迎面死锁解决 NIC无法发送消息时仍可接收 消息。即可从接收队列中优先处理 已发送消息的应答。 只接收①的应答 消 息 处 理 只接收②的应答 ① ④ 结点A ③ ② 结点B 消 息 处 理 （2）路由死锁解决之一—虚拟通道技术 当某虚拟通道被阻塞时，总可选择其他虚拟通道传输，打 破闭环。 C4 C1 C2 C3 C4 V4 V3 C1 C3 C2 只需在部分通道上设置虚拟通道，即可打破闭环。 转上页 转49页 （3）路由死锁解决之二—转弯路由技术 通过限制转弯的种类来避免产生通道闭环。 以2D网格网络为例进行分析： 基本方法--沿x方向路由时转弯无限制，沿y方向路由时不 允许向x方向转弯。 算法对路径的限制分析： -x→-y +x→-y 16种转弯中禁止了4种； +x→+y -x→+y 限制越多，阻塞概率越大。 方法扩充—16种转弯中只禁止2种已经可避免死锁。 西优先算法 北最后算法 负优先算法 3、死锁的解决 --流控机制的部分功能 主要是解决两个消息同时争用一个物理通道的问题。 解决方法：缓冲法、阻塞法、扬弃并重发、绕道法。 包1 包2 包缓冲区 片缓 输出 冲区 通道 包1 包2 门 控制 方法1：缓冲法 包1 包2 方法2：阻塞法 绕其它通道 包2 包1 应答包2：NACK 方法3：扬弃并重发 方法4：阻塞后绕道 采用方案：一般选择2种左右。
