想网上卖家具怎么做网站,石家庄专业制作网站,app制作需要学什么,个人证书查询网入口免费文章目录 一、互连网络1.1 互连网络概述1.1 互连函数1.1.1 互连函数1.1.2 几种基本的互连函数1.1.2.1 恒等函数1.1.2.2 交换函数1.1.2.3 均匀洗牌函数1.1.2.4 碟式函数1.1.2.5 反位序函数1.1.2.6 移数函数1.1.2.7 PM2I函数 1.2 互连网络的结构参数与性能指标1.2.1 互连网络的结… 文章目录 一、互连网络1.1 互连网络概述1.1 互连函数1.1.1 互连函数1.1.2 几种基本的互连函数1.1.2.1 恒等函数1.1.2.2 交换函数1.1.2.3 均匀洗牌函数1.1.2.4 碟式函数1.1.2.5 反位序函数1.1.2.6 移数函数1.1.2.7 PM2I函数 1.2 互连网络的结构参数与性能指标1.2.1 互连网络的结构参数1.2.2 互连网络的性能指标 1.3 互连网络的结构1.3.1 静态互连网络1.3.1.1 线性阵列1.3.1.2 环和带弦环1.3.1.3 循环移数网络1.3.1.4 树形和星形1.3.1.5.网格形和环网形1.3.1.6 超立方体 1.3.2 动态互连网络1.3.2.1 总线网络1.3.2.2 交叉开关网络1.3.2.3 多级互连网络 二、多处理机2.1 并行计算机系统结构的分类2.1.1 MIMD计算机2.1.2 存储器系统结构和通信机制2.1.2.1 共享地址空间2.1.2.2 采用多个独立地址空间2.1.2.3 通信机制的性能指标2.1.2.4 不同通信机制的优点 2.2 对称式共享存储器系统结构2.2.1 多处理机 Cache 一致性2.2.2 实现一致性的基本方案2.2.2.1 Cache一致性协议2.2.2.2 解决Cache一致性问题的方法 2.2.3 监听协议的实现 2.3 分布式共享存储器系统结构2.3.1 目录协议的基本思想2.3.2 目录协议2.3.3 目录协议存储块的状态2.3.4 本地结点、宿主结点以及远程结点的关系2.3.5 在结点之间发送的消息*2.3.6 目录协议系统Cache块状态图2.3.6.1 响应本地CacheCPU请求2.3.6.2 远程结点Cache块响应来自宿主结点的请求的状态转换图 *2.3.7 目录协议系统目录状态转换图2.3.8 目录的三种结构2.3.8.1 全映象目录2.3.8.2 有限映象目录2.3.8.3 链式目录 2.4 大规模并行处理机MPP2.4.1 并行计算机系统结构2.4.1.1 并行向量处理机(PVP)2.4.1.2 对称式共享存储器多处理机(SMP)2.4.1.3 分布式共享存储器多处理机(DSM)2.4.1.4 大规模并行处理机(MPP)2.4.1.5 工作站机群(Cluster of Workstations) 2.4.2 五种MIMD特征比较 一、互连网络 1.1 互连网络概述
什么是互连网络
互连网络Interconnection Network是一种由开关元件按照一定的拓扑结构和控制方式构成的网络用来实现计算机系统中结点之间的相互连接。
上述定义中
**结点**处理器、存储模块或者其他设备在拓扑上互连网络为输入节点到输出节点之间的一组互连或映像SIMD(单指令流多数据流)计算机和MIMD(多指令流多数据流)计算机的关键组成部分**三大要素**互联结构、开关元件、控制方式
定义是严谨而又枯燥的我们不妨假设目前有若干处理器若干存储器处理器要访问数据那么处理器和存储器之间的就是互连网络 互连网络要快速的根据处理器需求建立与存储器的连接。可以想到总线似乎就有类似的功能假如我们将NetWork换成总线那么自然可以实现数据的访问不过每次只能有一个处理器进行数据访问所以总线可以看作是最简单的互连网络实现方式。
我们将设备用结点来抽象表示分为两部分左部为输入端号右部为输出端号互连网络来建立左部点和右部点的映像就得到了拓扑结构 可以从4个不同的方面来描述互连网络
定时方式有同步和异步两种。 同步系统使用一个统一的时钟。SIMD阵列处理机就属于这一种类型。异步系统没有统一的时钟系统中的各个处理机都是独立地工作。 交换方法有线路交换和分组交换两种 线路交换源结点和目的结点之间的物理通路在整个数据传送期间一直保持连接。就像老式电话机。分组交换把信息分割成许多组(又称为包)将它们分别送入互连网络。 这些数据包可以通过不同的路径传送到达目的结点后再拼合成原来的数据结点之间不存在固定连接的物理通路。 控制策略有集中式和分散式两种 **集中控制方式**有一个全局的控制器接收所有的通信请求并由它设置互连网络的开关连接。**分散控制方式**不存在全局的控制器通信请求的处理和开关的设置由互连网络分散地进行。 拓扑结构有静态和动态两种 静态拓扑结构在各结点之间有专用的连接通路且在运行过程中不能改变。动态拓扑结构可根据需要设置互连网络中的开关从而对结点之间的连接通路进行重新组合实现所要求的通信模式。 1.1 互连函数
1.1.1 互连函数
互连网络是输入结点到输出结点之间的一组互连这种互连可以用互连函数来表示。假设互连网络有N个输入端和N个输出端分别用0…N - 1来表示则互连函数表示了输入端号和输出端号的连接关系。
互连函数反映了网络输入端数组和输出端数组之间对应的置换关系或排列关系所以互连函数有时也称为置换函数(Permutation)或排列函数。
互连函数f (x)有时可以采用循环表示即 ( x 0 , x 1 , … … x j − 1 ) (x_{0}, x_{1}, …… x_{j-1}) (x0,x1,……xj−1) 表示 f ( x 0 ) x 1 , f ( x 1 ) x 2 , … … f ( x j − 1 ) x 0 f(x_{0}) x_{1}, f(x_{1}) x_{2}, ……f(x_{j-1}) x_{0} f(x0)x1,f(x1)x2,……f(xj−1)x0 j称为该循环的长度
设nlogN则可以用 n 位二进制来表示N 个输入端和输出端的二进制地址互连函数表示为: f ( x n − 1 x n − 2 … … x 1 x 0 ) f(x_{n-1} x_{n-2} …… x_{1}x_{0}) f(xn−1xn−2……x1x0)
1.1.2 几种基本的互连函数
1.1.2.1 恒等函数
恒等函数实现同号输入端和输出端之间的连接。 I ( x n − 1 x n − 2 … … x 1 x 0 ) x n − 1 x n − 2 … … x 1 x 0 I (x_{n-1} x_{n-2} ……x_{1} x_{0}) x_{n-1} x_{n-2} ……x_{1} x_{0} I(xn−1xn−2……x1x0)xn−1xn−2……x1x0
1.1.2.2 交换函数
交换函数实现二进制地址编码中第k位互反的输入端与输出端之间的连接。 E ( x n − 1 x n − 2 … … x k 1 x k x k − 1 … … x 1 x 0 ) x n − 1 x n − 2 … … x k 1 x ˉ k x k − 1 … … x 1 x 0 E(x_{n-1} x_{n-2} …… x_{k1} x_{k} x_{k-1} …… x_{1}x_{0}) x_{n-1} x_{n-2} …… x_{k1} \bar x_{k} x_{k-1} …… x_{1}x_{0} E(xn−1xn−2……xk1xkxk−1……x1x0)xn−1xn−2……xk1xˉkxk−1……x1x0 主要用于构造立方体互连网络和各种超立方体互连网络。
它共有n logN种互连函数。N为结点个数
当N 8n 3可得到常用的立方体互连函数 C u b e 0 ( x 2 x 1 x 0 ) x 2 x 1 x ˉ 0 C u b e 1 ( x 2 x 1 x 0 ) x 2 x ˉ 1 x 0 C u b e 2 ( x 2 x 1 x 0 ) x ˉ 2 x 1 x 0 Cube_{0}(x_{2}x_{1}x_{0}) x_{2}x_{1} \bar x_{0} \\ Cube_{1}(x_{2}x_{1}x_{0}) x_{2}\bar x_{1} x_{0} \\ Cube_{2}(x_{2}x_{1}x_{0}) \bar x_{2}x_{1}x_{0} Cube0(x2x1x0)x2x1xˉ0Cube1(x2x1x0)x2xˉ1x0Cube2(x2x1x0)xˉ2x1x0 变换图形如下 结构如下 还是比较好理解的交换函数实现二进制地址编码中第k位互反。那么对于Cube0而言只有第0位互反的输入输出端号会建立连接
000 - 001 010 - 011 100 - 101 110 - 111这是变换图形的解释
对于结构图形三个坐标轴的方向代表了三个位互反的连接端号交换函数还是很巧妙的。Cube1的解释如下 1.1.2.3 均匀洗牌函数
均匀洗牌函数Shuffle将输入端分成数目相等的两半前一半和后一半按类似均匀混洗扑克牌的方式交叉地连接到输出端输出端相当于混洗的结果。也称为混洗函数置换 。
函数关系如下 σ ( x n − 1 x n − 2 … x 1 x 0 ) x n − 2 x n − 3 … x 1 x 0 x n − 1 \sigma(x_{n-1}x_{n-2}…x_{1}x_{0})x_{n-2}x_{n-3}…x_{1}x_{0}x_{n-1} σ(xn−1xn−2…x1x0)xn−2xn−3…x1x0xn−1 即输入端的二进制编号循环左移一位
原输入上下均分为两半交替往右边放我们发现左边输入和自己循环左移一位的输出端号建立连接 既然可以循环左移一位我们自然也可以通过循环右移一位来构造互连函数我们称之为逆均匀洗牌函数显然它是均匀洗牌函数的逆函数。 σ ( x n − 1 x n − 2 … x 1 x 0 ) x 1 x n − 1 x n − 2 … x 2 x 1 \sigma(x_{n-1}x_{n-2}…x_{1}x_{0})x_{1}x_{n-1}x_{n-2}…x_{2}x_{1} σ(xn−1xn−2…x1x0)x1xn−1xn−2…x2x1
1.1.2.4 碟式函数
蝶式互连函数把输入端的二进制编号的最高位与最低位互换位置便得到了输出端的编号。 B ( x n − 1 x n − 2 . . . x 1 x 0 ) x 0 x n − 2 . . . x 1 x n − 1 B(x_{n-1}x_{n-2}...x_{1}x_{0}) x_{0}x_{n-2}...x_{1}x_{n-1} B(xn−1xn−2...x1x0)x0xn−2...x1xn−1
解释000 - 000 001 - 100 010 - 010 - 011 - 110 100 - 001 101 - 101 110 - 011 111 - 111
1.1.2.5 反位序函数
反位序函数将输入端二进制编号的位序颠倒过来求得相应输出端的编号。 ρ ( x n − 1 x n − 2 . . . x 1 x 0 ) x 0 x 1 . . . x n − 2 x n − 1 \rho(x_{n-1}x_{n-2}...x_{1}x_{0})x_{0}x_{1}...x_{n-2}x_{n-1} ρ(xn−1xn−2...x1x0)x0x1...xn−2xn−1
N 8时碟式函数和反位序函数结构表示相同。
1.1.2.6 移数函数
**移数函数**将各输入端都错开一定的位置模N后连到输出端 α ( x ) ( x ± k ) m o d N , 1 ≤ N − 1 , 1 ≤ k ≤ N − 1 \alpha(x) (x\pm k) mod N,1\le N-1 , 1 \le k \le N-1 α(x)(x±k)modN,1≤N−1,1≤k≤N−1
1.1.2.7 PM2I函数
P和M分别表示加和减2I表示2i。该函数又称为**”加减2i“函数**。
**PM2I函数**一种移数函数将各输入端都错开一定的位置模N后连到输出端。 $$ PM2_{i}(x)x2_{}^{i} \space mod \space N \
PM2_{-i}(x)x-2_{}^{i} \space mod \space N \ 其中0 \le x \le N-1, 0\le i\le n-1, n \log_{2}N,N为结点数 $$ PM2I互连网络共有2 n 个互连函数。 举例-阵列计算机ILLIAC Ⅳ 1.2 互连网络的结构参数与性能指标
1.2.1 互连网络的结构参数
互连网络通常是用有向边或无向边连接有限个结点的图来表示的其主要结构参数包含以下6个。
网络规模N网络规模(NetworkSize)是指互连网络中结点的个数。它表示该网络所能连接的部件的数量。网络规模越大则这个互连网络的连接能力越强就能连接更多的部件。结点度结点度(Node Degree)d是指互连网络中结点所连接的边数(通道数)包括入度(InDegree)和出度(Out Degree)。进入结点的边数叫入度从结点出来的边数叫出度。结点距离对于互连网络中的任意两个结点其距离是指从一个结点出发到另一个结点终止所需要跨越的边数的最小值。网络直径D可以类比数据结构中树的直径网络直径(Network Diameter)D是指互连网络中任意两个结点之间距离的最大值。网络中任意两个结点之间传送的信息通过的边数都不会大于网络直径。显然网络直径应当尽可能的小。等分宽度b可以类比网络流种的最小割把由N个结点构成的网络切成结点数相同(N/2)的两半在各种切法中沿切口边数的最小值称为该网络的等分宽度(BisectionWidth)用b表示。而线等分宽度为Bb × w。其中w为通道宽度(用位数表示)。该参数主要反映了网络的最大流量。对称性如果从任意结点来看网络的结构都是相同的则称该网络为**对称网络(Symmetric Network)。**对称网络实现比较容易编程也比较容易。
1.2.2 互连网络的性能指标
**时延(Latency)和带宽(Bandwidth)**是用来评估互连网络性能的两个基本指标。
1.通信时延
通信时延是指从源结点到目的结点传送一条消息所需的总时间它由以下4部分构成。
软件开销。在源结点和目的结点用于收发消息的软件所需的执行时间。通道时延。通过通道传送消息所花的时间。通路时延 消息长度/通道带宽。选路时延。消息在传送路径上所需的一系列选路决策所需的时间开销。竞争时延。多个消息同时在网络中传送时会发生争用网络资源的冲突。为避免或解决争用冲突所需的时间就是竞争时延。
软件开销主要取决于两端结点处理消息的软件内核。通道时延通常由瓶颈链路的通道带宽决定。选路时延与传送路径上的结点数成正比。竞争时延很难预测它取决于网络的传输状态。
2.网络时延
网络时延是指通道时延与选路时延的和。它是由网络硬件特征决定的与程序行为和网络传输状态无关。而软件开销和竞争时延则与程序的行为有关。
3.端口带宽
对于互连网络中的任意一个端口来说其端口带宽是指单位时间内从该端口传送到其他端口的最大信息量。
在对称网络中端口带宽与端口位置无关。网络的端口带宽与各端口的端口带宽相同。而非对称网络的端口带宽则是指所有端口带宽的最小值。
4.聚集带宽
网络的聚集带宽(Aggregate Bandwidth)是指网络从一半结点到另一半结点单位时间内能够传送的最大信息量。例如HPS是一种对称网络网络规模N的上限是512端口带宽是40MB/S因此HPS的聚集带宽是(40MB/s×512)/210.24GB/s。
5.等分带宽
与等分宽度对应的切平面中所有边合起来单位时间所能传送的最大信息量称为该网络的等分带宽(Bisection Bandwidth)。
1.3 互连网络的结构
互连网络通常可以分为两大类静态互连网络(Static Interconnection Network)和动态互连网络(Dynamic Interconnection Network)。
静态互连网络是指各结点之间有固定的连接通路、且在运行中不能改变的网络。而动态互连网络则是指由交换开关构成、可按运行程 序的要求动态改变连接状态的网络。
1.3.1 静态互连网络
静态互连网络比较适合于构造通信模式可预测或可用静态连接实现的计算机。线性阵列结构是一维的静态互连网络二维的有环状、星状、树状、网格状等三维的有立方体等三维以上的有超立方体等。下面介绍几种静态互连网络其中N表示网络的规模即结点的个数
1.3.1.1 线性阵列
一种一维的线性网络其中N个结点用N - 1个链路连成一行。
端结点的度1其余结点的度2直径N1等分宽度b 1 线性阵列与总线的区别 总线是通过切换与其连接的许多结点来实现时分特性的 线性阵列允许不同的源结点和目的结点对并行地使用其不同的部分
1.3.1.2 环和带弦环
环
用一条附加链路将线性阵列的两个端点连接起来而构成。可以单向工作也可以双向工作。
对称结点的度2双向环的直径N/2单向环的直径N环的等分宽度 b 2 带弦环
在环的基础上给每个结点增加一条或两条链路便可得到带弦环增加的链路愈多结点度愈高网络直径就愈小。 全连接网络
结点度15
直径最短为1 1.3.1.3 循环移数网络
通过在环上每个结点到所有与其距离为2的整数幂的结点之间都增加一条附加链而构成。
N16结点度7直径2 一般地如果j - i 2^rr012…n-1n logN则结点 i 与结点 j 连接。
结点度2n1直径n / 2网络规模N 2^n
1.3.1.4 树形和星形
树形
一棵5层31个结点的二叉树 一般说来一棵k层完全平衡的二又树有N 2^k - 1个结点。
最大结点度3直径2(k-1)等分宽度b 1
星形
星状网络是一种两层的树
结点度较高为N - 1。直径较小是一常数2。等分宽度b - [N / 2]可靠性比较差只要中心结点出故障整个系统就会瘫痪。
胖树形 1985年Leiserson提出将计算机科学中所用的一般树结构修改为胖树状。树状网络的一个主要缺点是其根部结点以及连到根部的链路上的负载比较重有可能会成为整个系统的瓶颈。胖树的提出使该问题得到了缓解。 胖树的通道宽度从叶节点到根节点的宽度逐渐增宽它更像真实的树越靠近树根树干就越粗。此结构已经在CM-5计算机上得到应用。
1.3.1.5.网格形和环网形
网格形
网格状是一种比较流行的结构它已经以各种变体形式在Illiac IV、CM-2和IntelParagon等机器中得到了实现。如下图是一个3x3的二维网格状网络。
对于一个规模为N n × n 的二维网格状网络来说
其内部结点的度d4边结点的度d 3角结点的度d 2网络直径D 2 ( n一1 )等分宽度b n这个网络是不对称的q一个由Nn^k 个结点构成的 k 维网格形网络每维 n 个结点的内部结点度d 2k网络直径D k(n-1) 。
环网形 可看作是直径更短的另一种网格 把2维网格形网络的每一行的两个端结点连接起来把每一列的两个端结点也连接起来。 将环形和网格形组合在一起并能向高维扩展。 一个n×n的环网形网 结点度4 网络直径2 x [ n / 2 ] 等分宽度b 2n
1.3.1.6 超立方体
这是一种二元n-立方体结构它已在iPSC、nCUBE和CM-2等计算机系统中得到了实现。一般来说一个二元n-立方体由N 2 ^ n个结点组成它们分布在n维上每维有两个结点。 如我们可以用两个3-立方体对应结点相连来得到一个4-立方体如上图。
为实现一个n-立方体只要把两个(n-1)立方体中相对应的结点用链路连接起来即可。共需要2^n-1条链路。
n-立方体中结点的度都是n直径也是n等分宽度为b N / 2 1.3.2 动态互连网络
动态互连网络设置有有源开关因而能够根据需要借助控制信号对连接通路加以重新组合实现所要求的通信模式。下面介绍总线网络、交叉开关网络和多级互连网络。
1.3.2.1 总线网络
总线网络由一组导线和插座构成经常被用来实现计算机系统中处理机模块、存储模块和外围设备等之间的互连。
每一次总线只能用于一个源主部件到一个或多个目的从部件之间的数据传送。多个功能模块之间的争用总线Contention Bus或时分总线Time-sharing Bus。
特点
结构简单、实现成本低、带宽较窄
下图为一种由总线连接的多处理机系统示意图 系统总线在处理机、I/O子系统、主存储器以及辅助存储设备磁盘、磁带机等之间提供了一条公用通路系统总线通常设置在印刷电路板底板上。处理器板、存储器板和设备接口板都通过插座或电缆插入底板
解决总线带宽较窄问题采用多总线或多层次的总线
多总线是设置多条总线 有两种做法 为不同的功能设置专门的总线重复设置相同功能的总线 多层次的总线总是按层次的架构设置速度不同的总线使得不同速度的模块有比较适合的总线连接。
1.3.2.2 交叉开关网络
可以把交叉开关网络(Crossbar)看作一个单级开关网络。
交叉点开关能在对偶源、目的之间形成动态连接同时实现多个对偶之间的无阻塞连接。带宽和互连特性最好。一个n×n的交叉开关网络可以无阻塞地实现n!种置换。对一个n×n的交叉开关网络来说需要n^2套交叉点开关以及大量的连线。n很大时交叉开关网络所需要的硬件数量非常巨大。因此一般只有n 16的小型交叉开关网络用在商品化机器中。
我们以C.mmp多处理机的交叉开关网络为例 用16×16的交叉开关网络把16台PDP-11处理机与16个存储模块连在一起最多可同时实现16台处理机对16个不同存储模块的并行访问 每个存储模块一次只能满足一台处理机的请求当多个请求要同时访问同一存储模块时交叉开关就必须分解所发生的冲突每一列只能接通一个交叉点开关。为了支持并行或交叉存储器访问可以在同一行中接通几个交叉点开关。
处理机之间的交叉开关可以实现处理机之间的置换连接但这只是一对一的连接。所以n×n交叉开关网络一次最多可实现n个“源-目的”对的连接。
1.3.2.3 多级互连网络
MIMD 和 SIMD计算机一般都采用多级互连网络(Multistage Interconnection NetworkMIN)。
下面是一种通用的多级互连网络 由a×b开关模块和级间连接构成的通用多级互连网络结构每一级都用了多个a×b开关 a个输入和b个输出在理论上a和b不一定相等然而实际上a和b经常选为2的整数幂即ab2^kk ≥ 1 相邻各级开关之间都有固定的级间连接
下表列出了几种常用的开关模块2x2,4X4,8X8。这些块中。每个输人可与一个或多个输出相连但是在输出端不许发生冲突。换句话说,一对一和一对多的映射是允许的但不允许有多对一映射否则输出端将发生冲突。 我们以最简单的开关模块2×2开关 为例四种连接方式 各种多级互连网络的区别在于所用开关模块、控制方式和级间互连模式的不同。
控制方式对各个开关模块进行控制的方式。 级控制每一级的所有开关只用一个控制信号控制只能同时处于同一种状态。**单元控制**每一个开关都有一个独立的控制信号可各自处于不同的状态。**部分级控制**第 i 级的所有开关分别用i1个信号控制0 ≤ i ≤ n1n为级数。 常用的级间互联模式均匀洗牌、蝶式、多路洗牌、纵横交叉、立方体连接等
多级立方体网络
多级立方体网络包括STARAN网络和间接二进制n方体网络等。
两者仅在控制方式上不同在其他方面都是一样的。都采用二功能直送和交换的2×2开关。当第 i 级0 ≤ i ≤ n - 1交换开关处于交换状态时实现的是Cubei 互连函数。
一个N输入的多级立方体网络有logN级每级用N/2个2×2开关模块共需要logN × N/2个开关。
下面是一个8个入端的多级立方体网络
不难看出级间互连分别为交换、均匀洗牌逆均匀洗牌 STARAN网络采用级控制和部分级控制
采用级控制时所实现的是交换功能采用级控制时所实现的是交换功能
间接二进制n方体网络则采用单元控制
具有更大的灵活性
交换将有序的一组元素头尾对称地进行交换。
例如对于由8个元素构成的组各种基本交换的图形 3级STARAN网络在各种级控制信号的情况下所实现的入出端连接以及所实现的交换函数和功能。
其中
K2k1k0控制信号ki(i 012)为第i级的级控制信号。从表中可以看出下面的4行中每一行所实现的功能可以从级控制信号为其反码的一行中所实现的功能加上1组8元变换来获得。
例如级控制信号为110所实现的功能是其反码001所实现的4组2元交换再加上1组8元交换来获得。 当STARAN网络用作移数网络时采用部分级控制控制信号的分组和控制结果。 Omega网络
一个8×8的Omega网络
每级由4个4功能的2 x 2开关构成级间互连采用均匀洗牌连接方式 一个N输入的Omega网络
有logN级每级用N/2个2x2开关模块共需要logN * N/2个开关。每个开关模块均采用单元控制方式。不同的开关状态组合可实现各种置换、广播或从输入到输出的其它连接。假设上图是画在玻璃上的那么从正面看是Omega网络如果到玻璃的背后看过来就是下图所示的三级立方体网络。所以如果mega网络也采用2功能交换开关那么〇mega网络和间接二进制n方体网络就互为逆网络。 动态互连网络的比较 二、多处理机 自20世纪80年代中期以来随着微处理器的发展单处理机的性能达到了前所未有的高速增长。然而从2003年开始单处理机的性能的年增长率下降到了约20%。
Intel于2004年宣布放弃了其高性能单处理器项目转向多核multi-core的研究和开发。IBM、Sun、AMD等公司也纷纷采用了这一途径。
如今并行计算机应用软件已有了稳定的发展。这些计算机能够充分利用商品化微处理器所具有的高性能价格比的优势。
接下来主要介绍多处理机设计的主流——中小规模的计算机(处理器的个数32)。
2.1 并行计算机系统结构的分类
按照Flynn分类法可把计算机分为SISD、SIMD、MISD和MIMD四类单/多指令流、单/多数据流。
很多早期并行计算机为SIMD计算机但近年来MIMD已经成为了通用多处理机系统结构的选择。
SIMD是一个指令程序控制多个数据流的运算它比较适合数组运算那样大量的相同运算而MIMD具有更好的灵活性每个处理机可以执行自己的程序处理自己的数据MIMD可以充分利用商品化微处理器在性能价格比方面的优势市场上有大量可用的CPU且这些CPU更新换代快如果是SIMD很可能遇到市场上缺少所需CPU还要自己设计。计算机机群系统Cluster是一类被广泛采用的MIMD计算机。采用标准组件和标准网络技术这样可以尽可能地采用已经商业化了的技术而不是专门技术。
2.1.1 MIMD计算机
现有的MIMD计算机分为两类每一类代表了一种存储器的结构和互连策略。
1、集中式共享存储器结构Centralized Shared-Memory Architecture
这类多处理机目前最多由几十个处理器构成由于处理器数目较少所以它们共享一个集中式的物理存储器。
由于只有单一主存且该主存相较于各处理器的关系为对称的所以这类机器经常被称为对称式共享存储器多处理机Symmetric shared-memory Multi ProcessorSMP。这种系统结构也被称为UMAUniform Memory Access这是因为从各处理器访问存储器所花的时间相同。SMP结构是当前最流行的结构。
2、分布式存储器多处理机 这类机器中存储器在物理上是分布的存储器分布到各个处理器上否则如果使用集中式存储器则不能满足因处理器个数过多而导致的带宽要求。每个结点包括 处理器及Cache存储器I/O互连网络接口 在许多情况下分布式存储器结构优于集中式共享存储器结构
存储器分布到各个结点有两个优点
如果大多数的访存都是针对本地结点的存储器进行的就可以降低存储器和互连网络对于带宽的要求对本地存储器的访问延迟时间小。分布式存储器系统结构最主要的缺点是处理器之间的通信较为复杂且各处理器之间的访问延迟大。
通常情况下I/O和存储器一样也分布于多处理机的各结点当中。每个结点内还可能包含个数较少如2~8个的处理器这些处理器之间可采用另一种互连技术例如总线相互连接形成簇这样形成的结点叫做超级节点。
2.1.2 存储器系统结构和通信机制
如上所述在大规模的多处理机中存储器在物理上是分布于各个处理结点中的。但在逻辑地址空间的组织方式以及处理器之间通信的实现方法上有以下两种方案。
2.1.2.1 共享地址空间
把物理上分离的所有存储器作为一个统一的共享逻辑空间进行编址这样任何一个处理器就都可以访问该共享空间中的任何一个单元如果有访问权的话不同处理器上的同一个物理地址指向的是同一个存储单元。
这类计算机被称为 分布式共享存储器系统Distributed Shared-MemoryDSM。注意这里的共享指的是地址空间上的共享而非共享同一个存储器。与UMA相反DSM计算机被称为 NUMA(Non-Uniform Memory Access)计算机因为其访问时间取决于数据在存储器中的存放位置。
共享地址空间计算机系统采用共享存储器通信机制处理器之间的通信是通过用load 和 store 指令对相同存储器地址进行读写操作来实现的。
2.1.2.2 采用多个独立地址空间
把每个结点中的存储器编址为一个独立的地址空间不同结点的地址空间之间是相互独立的。
整个系统的地址空间是由多个独立的地址空间构成的每个结点中的存储器只能由本地的存储器进行访问远程的处理器不能直接对其进行访问每一个”处理器-存储器“模块实际上是一台单独的计算机现在这种计算机系统多以机群的方式存在
采用多个独立地址空间计算机系统采用消息传递通信机制数据通信要通过在处理器之间显式地传递消息来完成这称为消息传递通信机制。
消息传递多处理机中处理器之间是通过发送消息来进行通信的这些消息请求进行某些操作或者传送数据。
例如一个处理器要对远程存储器上的数据进行访问或操作
发送消息请求传送数据或对数据进行操作远程进程调用RPCRemote Process Call目的处理器接收到消息后执行相应的操作或代替远程处理器进行访问并发送一个应答消息将结果返回。
这里又引出两种消息传递方式
同步消息传递 请求处理器发送一个消息后一直要等到应答结果才继续运行。
异步消息传递 数据发送方知道别的处理器需要数据通信也可以从数据发送方来开始数据可以不经请求就直接送往数据接受方。这种消息传递往往是可以异步地进行发送方在发出消息后可立即继续执行原来的程序。
2.1.2.3 通信机制的性能指标
通信带宽 理想状态下的通信带宽受限于处理器、存储器和互连网络的带宽。 通信延迟 理想状态下通信延迟应尽可能地小。通信延迟 发送开销 跨越时间 传输延迟 接收开销
通信延迟的隐藏
如何才能较好地将通信和计算或多次通信之间重叠起来以实现通信延迟的隐藏。如接收一个数据后紧接着接收下一个数据这样在上一个数据处理完毕后可以直接拿到下一个数据。通常的原则只要可能就隐藏延迟通信延迟隐藏是一种提高性能的有效途径但它对操作系统和编程者来讲增加了额外的负担。
2.1.2.4 不同通信机制的优点
共享存储器通信的主要优点
与常用的对称式多处理机使用的通信机制兼容。易于编程同时在简化编译器设计方面也占有优势。采用大家所熟悉的共享存储器模型开发应用程序而把重点放到解决对性能影响较大的数据访问上。当通信数据量较小时通信开销较低带宽利用较好。可以通过采用Cache技术来减少远程通信的频度减少了通信延迟以及对共享数据的访问冲突。
消息传递通信机制的主要优点
硬件较简单通信是显式的因此更容易搞清楚何时发生通信以及通信开销是多少显式通信可以让编程者重点注意并行计算的主要通信开销使之有可能开发出结构更好、性能更高的并行程序。同步很自然地与发送消息相关联能减少不当的同步带来错误的可能性。
2.2 对称式共享存储器系统结构
在之前的缓存优化部分提到过多级cache可以降低处理器对存储器带宽的要求。
如果每个处理器对存储器的带宽需求都降低了那么多个处理器就可以共享一个存储器当处理机规模较小时这种计算机十分经济以往这种计算机一般是CPU和cache做在一块板上然后插入底板总线。近些年能在一个单独的芯片上实现28个处理器核。 如Sun公司 2006年 T1 8核的多处理器 对称式共享存储器系统结构 支持对共享数据和私有数据的Cache缓存 私有数据供一个单独的处理器使用而共享数据则是供多个处理器使用。 共享数据进入Cache也带来了一个新的问题即Cache的一致性问题
2.2.1 多处理机 Cache 一致性
如果允许共享数据进入Cache就可能出现多个处理器的Cache中都有同一存储块的副本的情况当其中某个处理器对其Cache中数据进行修改后就会导致其Cache中数据和其它处理器中Cache数据不同。这就是多处理机的Cache一致性Cache Coherence问题。
以下面动图中情况为例
CPUA 和CPUB 的Cache中都有存储单元X的副本其值都是1假设两个Cache都采用写直达方式。
当A对X进行写入更改为0此时A的Cache和存储器中的X都变为了0而BCache中X为1这就出现了问题。 存储器的一致性非正式定义如果对某个数据项的任何读操作均可得到其最新写入的值则认为这个存储系统是一致的。
存储系统行为的两个不同方面
What读操作得到的是什么值When什么时候才能将已写入的值返回给读操作。
需满足以下条件
处理器P对单元X进行一次写之后又对单元X进行读读和写之间没有其它处理器对单元X进行写则P读到的值总是前面写进去的值。处理器P对单元X进行写之后另一处理器Q对单元X进行读读和写之间无其它写则Q读到的值应为P写进去的值对同一单元的写是串行化的即任意两个处理器对同一单元的两次写从各个处理器的角度来看顺序都是相同的。写串行化
在后面的讨论中我们假设
直到所有处理器均看到了写的结果这个写操作才算是完成处理器的任何访问均不能改变写的顺序。即允许处理器对读进行重排序但必须以程序规定的顺序执行。
2.2.2 实现一致性的基本方案
2.2.2.1 Cache一致性协议
在一致的多处理机中Cache提供两种功能
1、共享数据的迁移
减少了对远程共享数据的访问延迟也减少了对共享存储器带宽的要求
2、共享数据的复制
不仅减少了访问共享数据的延迟也减少了访问共享数据所产生的冲突。
在多个处理器中用来维护一致性的协议称为Cache一致性协议Cache-coherent Protocol。
关键跟踪共享数据块的状态。
目前有两类协议
目录式协议directory。 物理存储器中数据块的共享状态被保存在一个称为目录的地方。 监听式协议snooping。 每个Cache除了包含物理存储器中块的数据拷贝之外也保存着各个块的共享信息。Cache通常连接在共享存储器的总线上当某个Cache需要访问存储器它会把请求放到总线上广播出去其它各个Cache控制器通过监听总线它们一直在监听来判断它们是否有总线上请求的数据块。如果有就进行响应操作。
2.2.2.2 解决Cache一致性问题的方法
1、写作废协议
在处理器对某个数据项进行写入之前保证它拥有对该数据项的唯一的访问权即作废其它的副本让其它Cache的该数据块失效。
我们给出一个例子监听总线、写作废协议采用写直达法
初始状态CPU A、CPU B、CPUC都有X的副本。在CPU A要对X进行写入时需先通过监听总线作废CPU B和CPU C中的副本然后再将p写入Cache A中的副本同时用该数据更新主存单元X。 2、写更新协议
当一个处理器对某数据项进行写入时通过广播使其它Cache中所有对应于该数据项的副本进行更新。
给出监听总线、写更新协议的例子采用写直达法
假设3个Cache都有X的副本当CPUA将数据p写入CacheA中的副本时将p广播给所有的Cache这些Cache用p更新其中的副本。 由于这里是采用写直达法所以CPUA还要将p写入存储器中的X。如果采用写回法则不需要写入存储器 写更新和写作废协议性能上的差别:
在对同一个数据进行多次写操作而中间无读操作的情况下写更新协议需进行多次写广播操作而写作废协议只需一次作废操作。在对同一Cache块的多个字进行写操作的情况下写更新协议对于每一个写操作都要进行一次广播而写作废协议仅在对该块的第一次写时进行作废操作即可。写作废是针对Cache块进行操作而**写更新则是针对字(或字节)**进行。考虑从一个处理器A进行写操作后到另一个处理器B能读到该写入数据之间的延迟时间。写更新协议的延迟时间较小。
2.2.3 监听协议的实现 实现监听协议的关键有3个方面 处理器之间通过一个可以实现广播的互连机制相连。通常采用的是总线。 当一个处理器的Cache响应本地CPU的访问时如果它涉及到全局操作其Cache控制器就要在获得总线的控制权后在总线上发出相应的消息。 所有处理器都一直在监听总线它们检测总线上的地址在它们的Cache中是否有副本。若有则响应该消息并进行相应的操作。 写操作的串行化由总线实现 获取总线控制权的顺序性
Cache发送到总线上的消息主要有以下两种
RdMiss——读不命中WtMiss——写不命中
此时都需要通过总线找到相应数据块的最新副本然后调入本地Cache中。
写直达Cache因为所有写入的数据都同时被写回主存所以从主存中总可以取到其最新值。写回Cache得到数据的最新值会困难一些因为最新值可能在某个Cache中也可能在主存中后面的讨论中只考虑写回法
有的监听协议还增设了一条Invalidate消息用来通知其它处理器作废其Cache中响应的副本。
与WtMiss的区别Invalidate不引起调块
Cache的标识tag可直接用来实现监听作废一个块只需将其有效位置为无效。
给每个Cache块增设一个共享位
为“1”该块是被多个处理器共享为“0”仅被某个处理器所占
**块的拥有者**拥有该数据块的唯一副本的处理器。
实现监听协议通常是在每个结点内嵌入一个有限状态控制器该控制器根据来自处理器或总线的请求以及Cache块的状态做出相应的响应。
每个数据块的状态取以下三种状态中的一种
无效简称ICache中该块的内容为无效共享简称S该块可能处于共享状态 在多个处理器中都有副本。这些副本都相同且与存储器中相应的块相同。 已修改简称M该块已经被修改过并且还没写入存储器 块中的内容是最新的系统中唯一的最新版本
监听协议举例
写作废、写回法。
为简单起见对 Write hit 和 Write miss 不加区分都按 Write miss 处理
现有CPU P CPU QCPU P可释放三种信号CPU Q的Cache中数据块有三种状态 情况一请求来自处理器
则有状态机 状态转换解释如下 情况二请求来自总线
则有状态机 状态转换解释如下 2.3 分布式共享存储器系统结构
监听协议直接利用系统中的总线和Cache中的状态位易于实现成本较低但当系统规模变大大量总线广播会使得总线成为系统瓶颈。广播和监听的机制使得监听一致性协议的可扩放性很差。
2.3.1 目录协议的基本思想
广播和监听的机制使得监听一致性协议的可扩放性很差。寻找替代监听协议的一致性协议。采用目录协议
2.3.2 目录协议
目录一种集中的数据结构。对于存储器中的每一个可以调入Cache的数据块在目录中设置一条目录项用于记录该块的状态以及哪些Cache中有副本等相关信息。
特点对于任何一个数据块都可以快速地在唯一的一个位置中找到相关信息。这使一致性协议避免了广播操作。
**位向量**记录哪些Cache中有副本
每一位对应于一个处理器长度与处理器的个数成正比由位向量指定的处理机的集合称为共享集S
分布式目录
目录与存储器一起分布到各结点中从而对于不同目录内容的访问可以在不同的结点进行。 目录法最简单的实现方案对于存储器中每一块都在目录中设置一项。目录中的信息量与M * N成正比。
其中
M存储器中存储块的数量N处理器的个数由于M K * NK是每个处理机中存储块的数量所以如果K保持不变则目录中的信息量就与N^2成正比
2.3.3 目录协议存储块的状态
在目录协议中存储块的状态有3种
**未缓冲**该块尚未被调入Cache。所有处理器的Cache中都没有这个块的副本。**共享**该块在一个或多个处理机上都有这个块的副本且这些副本与存储器中的该块相同。**独占**仅有一个处理机有这个块的副本且该处理机已经对其进行了写操作所以其内容是最新的而存储器中该块的数据已经过时 该处理机被称为该块的拥有者
2.3.4 本地结点、宿主结点以及远程结点的关系
本地结点发出访问请求的结点
宿主结点包含所访问的存储单元及其目录项的结点远程结点可以和宿主结点是同一个结点也可以不是同一个结点。 2.3.5 在结点之间发送的消息 本地结点发给宿主结点(目录)的消息 说明括号中的内容表示所带参数。P发出请求的处理机编号 K所要访问的地址 RdMiss(PK) 处理机P读取地址为A的数据时不命中请求宿主结点提供数据(块)并要求把P加入共享集。 WtMiss(PK) 处理机P对地址A进行写入时不命中请求宿主结点提供数据并使P成为所访问数据块的独占者。 Invalidate(K) 请求向所有拥有响应数据块副本包含地址K的远程Cache发Invalidate消息作废这些副本 宿主节点目录发送给远程结点的消息 Invalidate(K) 作废远程Cache包含地址K的数据块 Fetch(K) 从远程中取出包含地址K的数据块并将之送到宿主结点。把远程Cache中那个块的状态改为“共享”。 FetchInv(K) 从远程Cache中取出包含地址K的数据块并将之送到宿主结点。然后作废远程Cache中的那个块。 宿主结点发送给本地结点的消息 Reply(D) D表示数据内容。把从宿主存储器获得的数据返回给本地Cache。 远程结点发送给宿主结点的消息 WtBack(K, D) 把远程Cache中包含地址K的数据块写回到宿主结点中 **该消息是远程结点对宿主结点发来的“取数据”或“取作废”消息的响应。 ** 本地结点发送给被替换块的宿主结点的消息 MdSharer(P, K) 用于当本地Cache中需要替换一个包含地址K的块、且该块未被修改过的情况。这个消息发给该块的宿主结点请求它将P从共享集中删除。如果删除后共享集变为空集则宿主结点还要将该块的状态改变为“未缓存”(U) WtBack2(PKD) 用于当本地Cache中需要替换一个包含地址K的块、且该块已被修改过的情况。这个消息发给该块的宿主结点完成两步操作①把该块写回②进行与MdSharer相同的操作。 了解这些后就可以看几张dio图了bushi
*2.3.6 目录协议系统Cache块状态图
2.3.6.1 响应本地CacheCPU请求
M: Modified IInvalid SShared 2.3.6.2 远程结点Cache块响应来自宿主结点的请求的状态转换图 *2.3.7 目录协议系统目录状态转换图
先前已经提过
目录中存储器块的状态有3种
未缓存共享独占
位向量记录拥有其副本的处理器的集合。这个集合称为共享集合。
对于从本地结点发来的请求目录所进行的操作包括
向远程结点发送消息以完成相应的操作。这些远程结点由共享集合指出修改目录中该块的状态更新共享集合。
**目录可能接收到3种不同的请求 **假设这些操作是原子的
读不命中写不命中数据写回 我们对上图进行解释
块处于共享状态数据是当前最新接收到的请求及处理操作 RdMiss 将存储器数据送往请求方处理机并将其加入共享集合 WtMiss 将数据送往请求方处理机对共享集合中所有的处理机发送作废消息且将共享集合改为仅含有该处理机该块的状态变为独占。 块处于独占状态最新值保存在唯一拥有者处理机接收到的请求及处理操作 RdMiss 将“取数据”的消息发往拥有者处理机将它所返回给宿主结点的数据写入存储器并进而把该数据送回请求方处理机将请求方处理机加入共享集合。此时共享集合中仍保留原拥有者处理机(因为它仍有一个可读的副本)将该块的状态变为共享。 WtMiss 该块将有一个新的拥有者给旧的拥有者处理机发送消息要求它将数据块送回宿主结点写入存储器然后再从该结点送给请求方处理机。同时还要把旧拥有者处理机中的该块作废。把请求处理机加入共享者集合使之成为新的拥有者。该块的状态仍旧是独占。 WtBack写回 当一个块的拥有者处理机独占态要从其Cache中把该块替换出去时必须将该块写回其宿主结点的存储器中从而使存储器中相应的块中存放的数据是最新的(宿主结点实际上成为拥有者)该块的状态变成未缓冲其共享集合为空。
2.3.8 目录的三种结构
不同目录协议的主要区别主要有两个
所设置的存储器块的状态及其个数不同同目录的结构
根据目录的结构可以将目录协议分为三类全映象(Full mapped)目录、有限映象(Limited-mapped)目录、链式(Chained)目录
2.3.8.1 全映象目录
全映象目录每一个目录项都包含一个N位N为处理机的个数的位向量其每一位对应于一个处理机. 优点处理比较简单速度也比较快。
缺点
存储空间的开销很大。目录项的数目与处理机的个数N成正比而目录项的大小(位数)也与N成正比因此目录所占用的空间与N成正比。可扩放性很差处理机数目一旦改变就很难维护。当位向量中的值为“1”时就表示它所对应的处理机有该数据块的副本否则就表示没有。在这种情况下共享集合由位向量中值为“1”的位所对应的处理机构成。
2.3.8.2 有限映象目录
有限映象目录提高其可扩放性和减少目录所占用的空间。 核心思想采用位数固定的目录项目
限制同一数据块在所有Cache中的副本总数。限定为常数m。则目录项中用于表示共享集合所需的二进制位数为:m * logN。目录所占用的空间与N * [1og2N]成正比。
缺点
当同一数据的副本个数大于m时必须做特殊处理。当目录项中的m个指针都已经全被占满而某处理机又需要新调入该块时就需要在其m个指针中选择一个将之驱逐以便腾出位置存放指向新调入块的处理机的指针。
2.3.8.3 链式目录
用一个目录指针链表来表示共享集合。当一个数据块的副本数增加(或减少)时其指针链表就跟着变长(或变短)由于链表的长度不受限制因而带来了以下优点既不限制副本的个数又保持了可扩展性。
链式目录的两种实现方法
单链法
当Cache中的块被替换出去时需要对相应的链表进行操作——把相应的链表元素(假设是链表中的第i个)删除。实现方法有以下两种:
沿着链表往下寻找第i个元素找到后修改其前后的链接指针跳过该元素。找到第i个元素后作废它及其后的所有元素所对应的Cache副本。 双链法
在替换时不需要遍历整个链表。节省了处理时间但其指针增加了一倍而且一致性协议也更复杂了。
2.4 大规模并行处理机MPP
2.4.1 并行计算机系统结构
目前流行的高性能并行计算机系统结构通常可以分成以下5类
并行向量处理机(PVP)对称式共享存储器多处理机(SMP)分布式共享存储器多处理机(DSM)大规模并行处理机(MPP)工作站机群(Cluster of Workstations) 接下来的图片中的缩写含义如上图
2.4.1.1 并行向量处理机(PVP) 典型的 PVP 的结构如上图。
PVP 系统一般由若干台高性能向量处理机(VP)构成这些向量处理机是专门设计和定制的每个至少有 1G flops的处理能力存储器以兆字节每秒的速度向处理器提供数据向量处理器 VP 和共享存储模块通过高带宽的交叉开关网络互连这样的机器通常不使用高速缓存而是使用大量的向量寄存器和指令缓冲器
如Cray90、NECSX-4和我国的银河一号都是 PVP
2.4.1.2 对称式共享存储器多处理机(SMP)
SMP在前面已经详细讨论过了也介绍了监听协议解决cache一致性问题。 SMP系统使用商品微处理器具有片上或外置高速缓存它们经由高速总线或交叉开关连向共享存储器和 I/O这种机器主要用于商务例如数据库、在线事物处理系统和数据仓库等因为存储器唯一其相对个各个CPU而言关系对称访问时间相同所以称为对称但是处理器不能太多一般少于64个否则存储器带宽压力太大总线和交叉开关网络一旦作成也难以扩展
例如IBM R50、SGI Power Challenge、DEC Alpha 服务器 8400 和我国的曙光 1 号等都是这种类型的机器。
2.4.1.3 分布式共享存储器多处理机(DSM)
DSM我们也进行了详细介绍还介绍了目录协议 物理上有分布在各节点中的局部存储器但是对用户而言系统硬件和软件提供了逻辑上单地址的编程空间。高速缓存目录 DIR用以支持分布高速缓存的一致性。DSM 相对于 MPP的优越性是编程较容易。
例如:Stanford DASH、Cray T3D 和SGI/Cray 0rigin 2000等。
2.4.1.4 大规模并行处理机(MPP) MPP往往是超大规模的计算机系统它具有以下特点
处理结点使用商用微处理器而且每个结点可以有多个微处理器具有较好的可扩放性能扩展成具有成百上千个处理器的系统系统中采用分布非共享的存储器各结点有自己的地址空间。采用专门设计和定制的高性能互连网络是一种异步的MIMD机器程序系由多个进程组成采用消息传递的通信机制。MPP的主要应用是科学计算、工程模拟和信号处理等以计算为主的领域。
例如Intel Paragon、Cray T3E、IntelOption Red和我国的曙光-1000等都是这种类型的机器。
2.4.1.5 工作站机群(Cluster of Workstations) 在有些情况下集群往往是低成本的变形的MPPCOW的重要界线和特征是 COW的每个节点都是一个完整的工作站(不包括监视器、键盘、鼠标等)这样的节点有时叫作“无头工作站”一个节点也可以是一台PC或SMP;各节点通过一种低成本的商品(标准)网络(如以太网、FDDI和 ATM 开关等)互连(有的商用机群也使用定做的网络);各节点内总是有本地磁盘而MPP节点内却没有节点内的网络接口是松散耦合到I/O总线上的而 MPP内的网络接口是连到处理节点的存储总线上的因而可谓是紧耦合式的;一个完整的操作系统驻留在每个节点中而MPP中通常只是个微核COW的操作系统是工作站UNIX加上一个附加的软件层以支持单一系统映像并行度、通信和负载平衡等。
Berkeley NOW、Alpha Farm、Digital Truclster等都是 COW 结构。
2.4.2 五种MIMD特征比较
