• 互联网络，由开关元件按照一定拓扑结构核控制方式构成的网络，实现计算机系统中节点之间的相互连接
• 节点：处理器、存储模块或其他设备
• 互联网络已成为并行处理系统的核心组成部分
• 互联网对整个计算机系统的性能价格比有决定性的影响
• 三个要素：互联网结构、开关元件、控制模式

• 互联函数表示 输入端号与输出端号一对应， f(x)
• 设 n = l o g 2 N n = log_2N n=log2N，N个输入端和输出端的二进制地址用n位二进制数表示，互联函数表示 f ( x n ? 1 x n ? 2 . . . x 1 x 0 ) f(x_{n-1}x_{n-2}...x_1x_0) f(xn?1 xn−2​...x1​x0​)

恒等函数 交换函数：实现二进制地址编码中第k位互反的输入端和输出端之间的连接

均匀洗牌函数 shuffle：移动最高位到第0位，实现效果为前后分两半，交叉连接到输出端。

• 子洗牌（子混洗）：之后第 k位进行洗牌

• 超洗牌（超混洗）：只有高k位混洗 蝶式互联函数 Butterfly：输入端二进制编号最高位和最低为互换位置

• 子蝶式： 只在低k位进行互换

• 超蝶式：只在高k位进行互换 反序位函数 Bit Reversal： 将输入二年禁止编号位序颠倒

• 子反序位：即把输入端的二进制编号的低k位中各位的次序颠倒过来

• 超反序位： 将二进制编号高k位颠倒 移位函数： 将输入端都错开一定位置后连接到输出端 PM2I函数： P和M分别代表加和减，2I表示 2 i 2^i 2i,又称加减 2 i 2^i 2i函数

• 将输入端都错开一定位置后连接到输出端。

总延时 = 发送方开销 + 飞行时间 + 消息长度/频带宽度 + 接受方开销

• 静态互联网络： 给节点之间有固定的连接通路、且在运行中不能改变的网络
• 动态互联网络：由交换开关组成、可按运行程序的要求动态地改变连接状态的网络

一种一维的线性网络，其中N个节点传一行

• 端点的度： 1
• 其余节点度：2
• 直径： N-1
• 等分宽度：b=1

• 对称
• 节点的度：2
• 双向环的直径：N/2
• 单向环直径：N
• 环的等分宽度 b = 2

全连接环

• 再换上每个节点到与其距离为2的整数幂的节点之间加一条链

星形：

• 可靠性比较低,征信节点出故障，整个系统会瘫痪。

MIN multistafe interconnection network

ISC 级间连接是固定的

MIN 的区别在于 开关模块、控制方式、级间互联模式

控制方式：

• 级控制： 每级的所有开关只用一个控制信号控制，同时处在同一种状态
• 单元控制： 每个开关都有独立的控制信号
• 部分控制： 第i级所有开关，分别用 i+1个信号控制

级间互联： 均匀洗牌、蝶式、多路洗牌、纵横交叉、立方体连接等

多级立方体网络包括 STRAN网络 和 间接二进制n立方体网络

• 两者不同： 仅控制方式 不同，STRAN 网络采用级控制和部分级控制，而间接二进制n立方体网络采用单元控制，具有更大灵活性。
• 共同点： 都是用二功能（直送、交换）的 2*2开关；当第 i 级 （0 ≤ i≤ n − 1）交换开关处于交换状态时 第 i 级间采用 C u b e i Cube_i Cubei​互联函数

一个N输入的多级立方体网络有log2N级，每级用N/2个2×2开关模 块，共需要log2N×N/2个开关

• 88 的Omega网络，每级有 4个4功能的22开关，级间互联采用均匀洗牌的连接方式。

• 可以提供冗余路径，便于电路继承，提高可靠性

• 控制三种连接线的信号分别被称为 平控H、下控D和 上控U

• 各处理单元设有剧本存储器PEM，存放被分布的数据；只能被本处理单元直接访问
• 控制部件CU设有存放程序和数据的主存储器
• 整个系统在CU控制下运行用户程序和部分系统程序
• 处理单元之间可通过互联网络ICN
• 目前大部分真累处理及是基于分布式存储器模型的系统

• 存储器由K个存储体集中组成，经互联网络ICN为全部N个处理单元共享
• 互联网络用于处理单元和存储体分体之间进行转接而构成数据通路

共享主存构形的阵列处理机中并行存储器的无冲突访问

• 脉动阵列结构有一组吹单元（PE）构成的阵列
• 每个PE内部就够相同
• 震雷内所有PE的数据所存收一个时钟控制
• 运算时，市局在阵列结构中各个PE间沿各自方向同步向前推进

• 各个PE只接受前一组PE传来的数据，并向后一组PE发送数据
• 只有位于阵列边缘的处理单元，才与存储器或I/O端口进行数据交互

• 结构简单、规整，速度快，可扩充，适合超大规模集成电路实现
• PE见数据通信距离短、规则，施舍拘留和控制流的设计、同步控制简单规则
• 计算并行性高，通过流水获得很高的运算效率和吞吐率。
• 减轻了阵列和外界的I/O通信量
• 脉动阵列的构型与特定计算任务和算法密切相关
• 通用脉动阵列结构， 关键因素：受阵列结构的通用性及I/O带宽约束所限制的阵列结构的规模大小

源节点和目的节点之间没有直接相连的时候，消息需要经过中间节点的转发。寻径，也叫路由。

消息：节点之间进行通信的逻辑单位

• 包是包含寻径所需目的地址的基本单位，不同的包可能异步道道目的节点。每个包都分配一个序号，一百年报道大目的节点候能重新组装出消息
• 包进一步分成更小的长度固定的片，寻径信息和包秀娥好形成包头片，其余为数据片。

• 先建立一条物理通路，在传递信息

• 优点： 传输带宽大，平均传输延迟较小，使用缓冲区性较小，适合于具有动态和突发性的大规模并行处理数据的传送
• 缺点：需要频繁地建立源节点到目的节点的物理通路，时间开销会很大

• 包是信息传递的基本单位，从源节点经过一系列中介按揭带你到达目的节点
• 当一个包到达一个中间结点时，它首先被存放到缓冲区，当所要求的的输出通道和接收结点的包缓冲区可用时，再将它传送给下一个结点
• 优点： 占用物理通路的时间比较短
• 缺点：包缓冲区打，时延大

• 为减少时延，没有必要等到整个消息全部缓冲后再进行路由选择，只接收到 用作寻径的消息头部即可判断

• 优点：每个结点的缓冲区较小；较低的网络传输时延；通道共享性好，利用率高；易于实现选播和广播通信方式。 主要是信道利用率高了，所以快
• 缺点：当消息的一个片被阻塞时，整个消息都被阻塞。

• 确定性寻径： 通信路径完全由源节点地址和目的地址来决定，即寻径路径是预先唯一地确定好了的，而与网络的状况无关
• 自适应寻径：通信的通路每一次都要根据资源或者网络的情况来选择。 可以避开拥挤的或者有故障的节点，是网络的利用率得到改善

两种确定性寻径算法

• 在维序概念上，按照特定的顺序线则后继通道
• 在二维网格中，称为 X-Y寻径，在超立方体网格中称为E立方体寻径
• 二维网格中，先沿X轴方向前进，再沿Y轴方向前进

也就是说，从 i =0 到 n-1，判断 S = ( s n − 1 s n − 2 . . . s 1 s 0 ) d = d n − 1 d n − 2 . . . d 1 d 0 S = (s_{n-1}s_{n-2}...s_1s_0) \quad d={d_{n-1}d_{n-2}...d_1d_0} S=(sn−1​sn−2​...s1​s0​)d=dn−1​dn−2​...d1​d0​ 第 i 位 是否相等，不相等则 变第 i 位 都得到路径下一个节点 v

• 单播： 一对一
• 选拨：一对多
• 广播：一到全体
• 会议：多对多

两个参数

• 通道流量： 传输消息有关的通道数
• 通信时延：包的最大传输时间

优化的寻径网络应能以最小流量和最小时延实现相关的通信模式