计算机系统结构第6章(rev 1)

6.1互连网络6.2

SIMD计算机

6.3MIMD计算机6.4本章小结第6章阵列机•本章重点：常见的静态互连网络和动态互连网络的结构和特点;Omega网络构成和寻径方式、SIMD处理机的基本结构和特点、MIMD处理机的基本结构和特点以及多处理机的Cache一致性问题。6.1SIMD计算机的互连网络6.1.1互连函数

互连网络:是一种由高速开关按照一定的拓扑结构和控制方式构成的网络，用来实现计算机系统内部多个处理机或功能部件之间的相互连接。

在输入结点与输出结点之间建立对应关系，来反映不同互连网络的连接特性

常用的表示方法有两种：第二种方法是互连函数表示法，又称排列函数。第一种是图形表示法。1.方体置换其表达式为：例：节点数N=8时，n=3，则方体互连函数为：方体置换函数共有n=，其中N为节点数。

方体置换主要用于超立方体互连网络中，其互连函数的图形表示法如图6-1所示。（a）C0方体交换函数（b）C1方体交换函数（c）C2方体交换函数图6-1N=8的立方体交换函数2.PM2I函数表达式为：其中：N为节点数，n=，0≤x≤N-1，0≤i≤n-1。

PM2I互连函数有2n个互连函数例：结点数N=8的PM2I函数的图形表示法如图6-2所示（a）i=0（b）i=+1（c）i+2图6-2N=8的PM2I函数3.均匀洗牌函数

表达式为：Shuffle(Xn-1Xn-2…X1X0)=Xn-2…X1X0Xn-1

其中：N为节点数，n=例：结点数N=8的均匀洗牌函数的图形表示法如图6-4所示。

图6-4N=8的均匀洗牌函数

均匀洗牌是一种非常有用的互连函数，以其为代表的链路与以交换置换为代表的开关多级组合起来可构成Omega（Ω）网络。【例6-1】IlliacIV阵列计算机采用PM±0和PM±2四个互连函数构成的移数网络进行16个处理器的连接，如图6-5所示。图6-5用移数函数构成IlliacIV阵列互连函数PM+0

：（012...15）PM-0

：（151413…0）PM±2

：（04）（15）（26）（36）（48）（59）（610）（611）（812）（913）（1014）（1115）（120）（131）（142）（153）解：该网络可用4个PM2I函数表示如下：6.1.2互连网络的性能和特征

⑴网络规模指网络中结点数，它体现网络所能连接的部件数。1．互连网络的性能参数⑵结点度进入结点的边数叫入度，从结点出来的边数叫出度。⑶结点距离从一个结点到另一个结点所经过的最少边数。⑷网络直径指网络中任意两个结点之间距离的最大值，常用D表示。从数据传送的角度来看，网络直径应尽可能的小。2.互连网络的特征参数⑴传送方式传送方式一般分为同步和异步两种：同步方式：在数据传送的过程中采用统一时钟信号。异步方式：不需要统一的时钟信号在各处理机或单元之间进行同步，各处理机或处理单元根据自身需要独立工作。⑵控制策略控制策略：指控制互连开关构成信息通路的方式，可以分为集中控制和分散控制两种。集中控制：由统一的控制器对各个互连开关实施控制。分散控制：由各个开关自身实施控制。⑶交换方法交换方式：指数据传送时的管理方式，可以分为线路交换和分组交换两种。线路交换：在整个传送过程中，在源结点与目的结点之间建立固定的物理通路，适用于成批数据的传送。分组交换：对传送的数据进行分组，分别送入互连网路，各分组可以通过不同的路由到达目标结点，适用于短数据报文传送。拓扑结构：指互连网络中各结点之间的连接关系。⑷拓扑结构按照其控制方式可以分为：静态拓扑结构和动态拓扑结构。静态拓扑结构：指在各结点间有专用的连接通路，在网络运行中其结构不能改变。动态拓扑结构：指在结构中设有有源开关，在网络运行中可以借助于控制信号对各结点的链路重新组合。6.1.3静态互连网络

静态互连网络：指处理单元间有着固定连接的网络，在程序执行期间，点到点的连接保持不变。

下面介绍几种常见的静态互连网络1.线型网和星型网图6-6线性阵列网图6-6星型网内部结点的连接度d=2，两端结点的连接度d=1。网络直径D=N-1。星型网中心结点的连接度d=N-1，外层结点的连接度d=1，网络直径D=2。2.环网和带弦环网图6-8环网图6-9带弦环网环网的结点度均为d=2，单向环网的直径D=N-1，双向环网的直径D=N/2。3.二叉树型网和二叉胖树型网（a）二叉树型网（b）二叉胖树型网5.网格型网络（a）网格型网（b）Illiac网（c）环型网图6-13网格型与环网型结构6.超立方体网络（a）3-立方体（b）2个3-立方体构成的4-立方体

图6-14超立方体结构6.静态互连网络比较表6-1静态互连网络特性汇总r×r网络，r=

与r=的带弦环等效网络类型结点度（d）网络直径（D）链路数l等分宽度B对称性网络规格说明线形阵列2N-1N-11否N个结点环形2[N/2]N2是N个结点全连接N-11N（N-1）/2是N个结点二维网络42（r-1）2N-2rR否Illiac网4r-12N2r否二维环网42[r/2]2N2r是r×r网络，r=

超立方体NnnN/2N/2是N个结点，n=

6.1.4动态互连网络

在动态互连网络中，各结点之间的连接是不固定的，而是在控制信号的作用下，通过网络开关的设置来建立结点之间的间接、可变的连接通路。1.总线互连网络图6-15一种总线连接的多处理机系统2.交叉开关网络图6-16多处理机中处理机-存储器之间的交叉开关网络Fujitsu公司在1992年制造的向量并行处理机VPP500采用224×224的大型交叉开关网络。如图6-16所示。图6-16VPP500向量并行处理机中处理机间的交叉开关网络3.多级互连网络在多级互连网络结构中，由交换开关、拓扑结构和控制方式三个参数描述。⑴交换开关（a）直送（b）交叉（c）下播（d）上播图6-182×2交换开关的四种工作状态⑵拓扑结构

指多级互连网络的各级开关之间链路的互连模式。⑶控制方式控制方式：指对各级交换开关的控制方式。级控：同一级的所有开关用一个信号来控制，所有开关都处于同一种工作状态，n级开关需要n个控制信号。单元控制：每一个开关单独有一个控制信号，同一级的开关可以处于相同的工作状态，也可以处于不同的工作状态。N级网络的输入端和输出端的总数N=2n，所以每一级有N/2个开关，这种方式下共需要nN/2个控制信号。部分级控：对于同一级开关分组，在不同级使用不同数量的控制信号。图6-19所示是一种通用的多级互连网络。接下来以Omega网络为例，介绍多级互连网络的构成和寻径算法。图6-20N=8个结点的Omega网络⑴Omega网络的构成6.2SIMD计算机按照Flynn分类法，将单指令流多数据流结构的计算机称为SIMD计算机。它主要通过硬件资源的重复设置来实现并行性，适用于大量高速的向量或矩阵运算，所以又称为并行处理机和阵列处理机。6.2.1SIMD计算机模型与特点1.SIMD计算机模型图6-23SIMD计算机的操作模型2.SIMD计算机的特点⑴SIMD计算机的工作方式是单指令流多数据流。⑵SIMD计算机依靠的并行措施是资源重复，⑶SIMD计算机采用的互连网络将处理单元进行连接，⑷SIMD计算机以向量处理为主，在SIMD计算机处理短向量时，短向量对其速度的影响虽较小，但会降低处理效率。⑸SIMD计算机是一台向量处理专用计算机。6.2.2SIMD计算机结构

根据存储器的分布方式不同，阵列处理机有分布式存储器和共享式存储器两种基本结构，1.分布式存储器阵列处理机的基本结构图6-24分布式存储器阵列处理机的基本结构2.共享存储器阵列处理机的基本结构图6-25共享存储器的SIMD计算机6.2.3SIMD计算机实例

接下来分别介绍两种典型的SIMD计算机：IlliacIV阵列处理机和BSP计算机。1.IlliacIV阵列处理机图6-26IlliacIV阵列处理机总体框架⑴IlliacIV阵列IlliacIV阵列PU是由64个处理单元（PE）、64个局部存储器（PEM）和存储逻辑部件（MLU）组成。（a）处理单元之间的连接关系（b）IlliacIV处理部件的连接图6-26IlliacIV阵列处理机的阵列连接概括起来，控制器的功能有以下5个方面：对指令流进行控制和译码，包括执行一整套标量操作指令；向各处理单元发出执行数组操作指令所需的控制信号；产生和向所有处理单元广播公共的地址部分；产生和向所有处理单元广播公共的数据；接收和处理由各PE（计算出错时）、系统I/O操作以及B6600所产生的陷阱中断信号。6.2.4SIMD处理机的算法举例⑴矩阵加假定两个8×8的矩阵A和B相加，所得到的结果矩阵C也是一个8×8的矩阵。需用下列3条汇编指令就可一次实现矩阵相加：LDAALPHA

；全部（a）由PEMi送PEi的累加器RGAi中ADRN

ALPHA＋1；全部（a+1）与（RGAi）进行浮点加，结果送RGAiSTAALPHA＋2；全部（RGA）由PEi送PEMi的a+2单元中。图6-29矩阵相加存储器分配⑵矩阵乘

设A、B和C为3个8×8的二维矩阵。若给定A和B，则C＝A×B的64个分量可利用下列公式计算。，0≤i≤6，0≤j≤6。

如果在SIMD计算机上求解这个问题，可执行下列FORTRAN程序：DO

10

I＝0，6C(I,J)=0DO

20

K=0,620

C(I,J)=C(I,J)+A(I,K)*B(K,J)10

CONTINUE图6-30矩阵乘程序执行流程图图6-31矩阵乘存储器分配⑶累加和

假设累加的数为A(I)，其中I的取值范围为0≤I≤7，即共有8个数进行顺序累加。在SIMD计算机上可写成下列FORTRAN程序：C(-1)=0DO10I=0,710C(I)=C(I-1)+A(I)

在SISD计算机上，它需要进行8次加法循环的时间。如果在并行处理机上，采用成对递归相加的算法，则只需要=3次的加法时间。将原始数据A(I)存放在8个PEM的a单元中，求累加和：第1步将全部PEi置为活动状态第2步全部A(I)从PEMi的a单元读到相应PEi的累加寄存器RGAi中，0≤I≤6；第3步令K＝0；第4步全部PEi的(RGAi)转送到传送寄存器RGRi，0≤I≤6；第5步全部PEi的(RGAi）经过互连网络向右传送2k步距，0≤I≤6；第6步令j=2k-1；第6步置PE0至PEj为不活动状态；第8步处于活动状态的PEi执行(RGAi):＝(RGAi)＋(RGRi)操作；第9步

k:=k+1；第10步若k<3，则转回第4步，否则继续往下执行；第11步将全部PEi置为活动状态，0≤I≤6；第12步全部PEi的(RGAi)存入相应PEMi的a+1单元中。上面描述的计算过程如图6-32所示。图6-32阵列处理机上累加和的计算过程6.3MIMD计算机MIMD计算机按照Flynn分类法是指多指令流多数据流计算机，它由多台独立的计算机组成，每台计算机能够独立执行自己的程序。6.3.1MIMD计算机结构MIMD计算机根据存储器组织方式的不同，将MIMD计算机结构分成两类：共享存储器多处理机结构和分布式存储器多处理机结构。（a）共享存储器多处理机结构（b）分布式存储器多处理机结果6-33两种处理机结构MIMD计算机在结构原理上有别于SIMD计算机的主要特点：⑴MIMD计算机有多个控制器，有多个指令部件，可以对各个PE实现单独的控制，并使其相互协调，相互配合。⑵MIMD计算机的外围设备能够被多个PE分别调用，