1、第六章 多机系统第一讲 概述一、并行性概念1、单机系统中的并行性 1）当外设采用中断传送方式时，外设的机械动作与CPU的运行可并行执行。 2）在多用户系统中，各用户的入出设备的机械动作也在并行执行。 3）在重叠方式中，多条指令可以在不同的过程段上重叠执行。,2、并行性的意义 1）并行性意味着有多个事件并发进行，可提高运行效率。 2）若有多个相同的事件同时进行着，意味着对某事件有多个装置进行数据处理，可靠性高。3）并行也可意味着须多套装置来完成。,二、从单机系统向多机系统发展的三条途径,单机系统,一条指令多个过程段,以指令为单位构成指令流水线,宏流水线,异构型多机系统,多用户系统分时共享CPU,
2、将单机在不同时间虚拟成不同概念结构,用微小型机来代替虚拟结构,分布式多机系统,多存贮器结构,多处理机结构,同构型、并列式、阵列式,时间重叠,资源重复,资源共享,三、多机系统中的耦合度 1、何谓耦合度 多机间相互通信能力或相互依赖程度称为系统的耦合度。2、几种耦合度 1）最低耦合度。通信能力低，依赖程度小。如两台计算机间仅用两三条线连接通信，无任何性能。2）松散耦合度。通信能力较强，依赖程度较高。如连接在网上的计算机，在高速中主机与处理机之间也属此类。3）紧密耦合。依赖程度最强，如阵列式，并行式处理机与控制部件（CU）之间。,四、多机系统的特点和分类 1、多处理机系统 1）具有多个处理机 2）具
3、有一个指令译码执行部件 3）各处理机共享公共主存与I/O通道 4）各处理机要在统一的操作系统控制下工作 5）它们属于SIMD结构 6）它们属于紧密耦合,2、多计算机系统特点 1）具有多个处理机 2）具有多个指令译码分析部件 3）各处理机有自己的主存与I/O通道 4）各处理机要在统一的操作系统控制下协调工作（如网络操作系统） 5）MIMD结构 6）松散耦合,第二讲 多处理机系统一、多处理机系统分类 1、并行式多处理机系统 各处理机构成地位完全相同，位置可互换，主要用于对向量数据（一维）的计算。 2、阵列式多处理机系统 各处理机的构成完全相同，但处理机排列成矩阵结构，如4*4，8*8等，主要对阵列
4、数据（二维）进行处理。3、分布式多处理机系统 各处理机的构成可以不同，处理地位也可以不同，主要用于对同时产生不同性质的多发事件处理。,其中，1，2属同构系统，3属于分布式处理系统二、阵列式多处理机系统简介（伊）为主 1、伊总体结构 具有两个象限的阵列处理部件,A,A,A,A,CU,CU,CU,CU,MM,I/O通道,D,A为阵列处理部件 每个阵列处理部件由64个PU（阵列处理机）构成 CU是对阵列处理部件A进行控制的阵列控制部件，由它可向A的各PU发出相应的控制命令，CU是A的指令译码分析部件，MM为主存（A,CU共享）,2、阵列结构A 1)由64个8行8列排成阵列的PU来构成 PU0 PU1
5、 PU7 PU8 PU56 PU63 2）横的排列按1的模式，且以64为模进行排列与连接3）纵的排列按8的模式，且也以64为模进行行列连接4）每一个PU可直接和四周的PU进行通信,例：PUI PUI+1 PUI+8 PUI-1 PUI-8,其它PU可通过联网络进行通信,三、阵列式多处理机的算法1、完成有限距离的拉普拉斯方程的求解（它是一个具有二阶偏导数的偏微分方程） 其最后的计算公式如下 U(x,y) = (U(x+h,y) + U(x,y+h)+ U(x-h,y) + U(x,y-h)/4 其中U(x,y) 为某一点的参数，h为有限距离,U(x,y),U(x+h,y),U(x-h,y),U(
6、x,y+h),U(x,y-h),上式意义在于每次计算某点参数值可直接用其四周参数的平均值,按此进行计算，可称为“平滑”或“数字滤波” 而阵列式处理机的每个PU可同时从四周的PU获取参数，因而阵列多处理机很适合于有限差分方程求解。2、完成距阵加运算 1）完成算式C=A+B,.。,a70 a71 a77,A=,.。,b70 b71 b77,B=,a00 a01 a07 a10 a11 a17,b00 b01 b07 b10 b11 b17,.。,c70 c71 c77,C=,c00 c01 c07 c10 c11 c17,cij=aij+bij,2)阵列数据分配 （每个PU除共享公共主存外，还有自
7、己的局部存储器PUM，随PU排列，因此PUM又称阵列存贮器）每个PUM为1K 每个PUM占用三个单元,PUM0, +1 +2,PUM0, +1 +2,PUM0, +1 +2,设其单元地址为 、+1 、+2，其中在单元中有存放A阵列数据aij, +1单元放B阵式数据bij ,+2单元放C阵式数据cij3)当CU取出距阵加指令时，可通过如下操作完成运算 CU向各PU播发公共地址 和读命令，各PU 分别取出 单元中的aij到PU的暂存器中。, CU再向各PU播发公共地址 +1和读命令，使各PU 分别取出 +1单元中的bij到PU的另一暂存器中。 CU再向各PU 下达求和命令（加法），使各PU完成计算
8、cij=aij+bij CU再向各PU 播发第三个公共地址和写命令，使各PU的计算结果存入+2单元中。3、对矩阵乘运算 C=A*B,.。,an0 an1 ann,A=,.。,bn0 bn1 bnn,B=,b00 b01 b0n b10 b11 b1n,a00 a01 a0n a10 a11 a1n,.。,cn0 cn1 cnn,C=,c00 c01 c0n c10 c11 c1n,其中Cij= aikbkj,k=0,n,如C00= a00b00 + a01b10 + a02b20 + + a0nbn0 阵列式多处理机也比较有利于矩阵乘运算，但不如矩阵加,4、可加速累加和运算 1）完成算式S=
9、ai,i=0,7,=a0+a1+a2+a7 a0+a1 a2+ a3 a4+a5 a6+a7 + + +2）当采用一个处理机完成时，需要七步求和完成3）当采用多个处理机计算时，可减少求和时间的次数 第一次求和用4个处理机完成 PU0 PU1 PU2 PU3 a0+a1 a2+ a3 a4+a5 a6+a7 (同时计算）, 第二次求和 PU0 PU1 + + 第三次求和 PU0 +总结：阵列式多处理机最擅长完成有限差分方程求解和矩阵加运算，也比较有利于矩阵乘运算，还可加速累加和完成。四、SIMD互联网络1、概述 1）互联：多处理机之间相互联接进行通信成为互联。 2）互联函数：各处理机之间联结的某
10、种拓扑结构的函数称为互联函数。,如：f(i)=i+1 (i=07,且以8为模） 按此函数实现的连接关系表：0 1，1 2，2 35 6, 6 7, 7 0 3)互联网络：实现处理机之间联结的某种拓扑结构的逻辑电路称为互联网络,出 入,0 1 2 3 4 5 6 7,4）对互联网络的基本要求 有利于实现 可实现多种灵活的连接 要有一定通信频率5）互联网络的分类 从级数来分 ）单级互联网络（仅一级） ）循环互联网络（物理一级，但可实现多级功能） ）多级互联网络（有多级）,按特征性能来分 ）立方体互联网络 ）混洗交换互联网络 ）PM2I互联网络 在立方体和混洗交换互联网络中，处理机（或部件）用编码P
11、表示，其中编码所用二进制位数与部件数相关，如当有8个部件时，需要用三位二进制表示，则用P2P1P0表示部件编码。 设部件数为n，则所用编码二进制位数为log2n，如需要用4位编码时，可用P3P2P1P0表示。,2、单级立方体互联网络（用Cube表示） 1）Cube0（以n=8，用 P2P1P0表示） 互联函数：Cube0 (P2P1P0)= P2P1P0 实现的连接关系表： 0 1 ，1 0 ，2 33 2，4 5，5 4，6 7，7 6,P2P1P0 P2P1P0 000 001 001 000 010 011 011 010 100 101 101 100 110 111 111 110,
12、实现的连接关系图,出 入,0 1 2 3 4 5 6 7,0,1,2,3,4,5,6,7, 当把07共8个部件排成一个立方体时，Cube0可实现8个部件在 X 方向的连接,0,1,5,4,2,3,6,7,Y,X,Z,2）Cube1（以n=8，用 P2P1P0表示） 互联函数：Cube1 (P2P1P0)= P2P1P0, 实现的连接关系表: 0 2 , 1 3 , 2 0,3 1, 4 6, 5 7, 6 4 , 7 5 实现的连接关系图,0,1,2,3,4,5,6,7,出 入,0 1 2 3 4 5 6 7, Cube1可实现8个部件在 Y 方向的连接（见立方图）3）Cube2 互联函数：C
13、ube1 (P2P1P0)= P2P1P0 实现的连接关系表: 0 4，1 5，2 6，3 7，4 0，5 1，6 2，7 3,出 入,0 1 2 3 4 5 6 7,0,1,2,3,4,5,6,7,实现的连接关系图, Cube2可实现8个部件在 Z 方向的连接（见立方图）,4）当有16个部件时，可组成两个立方体，而在两个立方体之间可用Cube3实现两个立方体的连接 互联函数：Cube3 (P3P2P1P0)= P3P2P1P0 连接关系表: 0 8，1 9，2 10，3 11 4 12，5 13，6 14，7 15 8 0，9 1，10 2，11 3 12 4，13 5，14 6，15 7,
14、0,1,5,4,2,3,6,7,8,9,13,12,10,11,14,15,当用Cube4时，可将两个立方体组进行连接,0,1,5,4,2,3,6,7,8,9,12,10,11,14,15,16,17,21,20,18,19,22,23,24,25,28,26,27,30,31,29,13,3、单级混洗交换互联网络 1）混洗互连函数 sh(Pn-1Pn-2P1P0)= Pn-2P1P0Pn-1 利用部件编码循环左移一位，可获得与下个部件相连的编号 2）当n=3时，（共8个部件）可实现如下连接关系,P2P1P0 P1P0P20 0 0 0 0 0 0 00 0 1 0 1 0 2 0 1 0 1
15、 0 0 40 1 1 1 1 0 61 0 0 0 0 1 11 0 1 0 1 1 31 1 0 1 0 1 51 1 1 1 1 1 7,0,1,2,3,4,5,6,7,它将8个部件分为四组，每组之间互不相关,3）在混洗基础上加上Cube(0)的交换时称为混洗交换 Cube(0)为P2P1P0 P2P1P0,0 1 ，1 0 ，2 3,3 2，4 5，5 4，7，7 64）混洗交换互联网络,出 入,0 1 2 3 4 5 6 7,4、单级PM2I互联网络 1）PM2I互联函数 PM2I有两大类 一大类是 PM2 + I = j + 2i（i=0j-1） 另一大类是 PM2 I = j 2
16、i （i=0j-1） 当i=0时，PM2(j)+ 0 = j + 20 = j + 1 若有8个部件，也以8为模时， PM2(j)+ 0 可实现,0,1,2,3,4,5,6,7,当i=1时，PM2(j)+ 1 = j + 21 = j + 2，可实现,0,1,2,3,4,5,6,7, PM2 -I = PM2(j) 2i,当i=0时,有,0,1,2,3,4,5,6,7,当i=1时,有,0,1,2,3,4,5,6,7,2）阵列式处理机所用的PM2I互连函数,0,1,7,8,9,15,56,57,63, 水平方向用PM2+0,PM2 0,水平螺旋连接 垂直方向用PM2+3,PM2-3,垂直螺旋连接
17、 （以64为模）,5、循环互联网络 1）实质：是对单级互联网络的重复使用，它可在一定程度上模拟多级互联网络的性能 2）构成：有单级互联网络、输入寄存器和多路开关构成。结构示意图见P167 图6-276、多级互联网络描述参数 1）交换单元功能,I1,I2,O1,O2, 双功能交换单元，具有直通和交换两种功能,I1,I2,O1,O2,I1,I2,O1,O2,G=0,G=1,直通,交换, 四功能交换单元 除双功能外,在增加上播、下播两种功能,I1,I2,O1,O2,I1,I2,O1,O2,G=00,G=01,直通,交换,I1,O1,O2,I2,O1,O2,G=10,G=11,上播,下播,有了上播与下
18、播功能，可实现广播式通信2）级间连接模式 一般采用级间对号连接 如有两级，第一级为Cube0,第二级为Cube1,0,1,0,1,0,2,0,2,2,3,2,3,1,3,1,3,Cube0,Cube1,3）控制方式 级控制方式：同一级的所有开关只用一个控制信号控制，同时只能处于同一种状态： 单元控制方式：同一级每一个开关都有自己独立的控制信号控制，可各自处于不同的状态； 部分级控制方式：是一、二级的组合。7、多级互联网络的构成与类型 1）构成：由多个同类型的单级互联网络构成（三级和三级以上成为多级）2）类型： 多级 立方体互联网络 多级混洗交换互联网络 多级PM2I互联网络,8、多级 立方体互
19、联网络（先以3级立方体为例，采用双功能交换单元，级间对号连接，级控制方式 1）三级立方体互联网络结构图 （由Cube0,Cube1,Cube2构成）,0,1,0,1,0,2,0,2,2,3,2,3,1,3,1,3,Cube0,Cube1,4,5,4,5,4,6,4,6,6,7,6,7,5,7,5,7,4,0,4,5,1,5,6,2,6,3,7,3,0,1,2,7,Cube2,A,B,C,D,E,F,G,H,I,2）级控制方式下，控制信号与连接关系表，连接关系图和连接关系名称,连接关系图,0 1 2 3 4 5 6 7,0 0 0,0 0 1,0 1 0,0 1 1,连接关系图（续）,0 1 2
20、 3 4 5 6 7,1 0 0,1 1 0,1 0 1,1 1 1,反之,5-0 A交 B直 C交 7-1 D直 E交 F交0-5 G交 H直 F交1-7 G直 H交 I交,能否同时实现,所以，级控制不可能，单元控制可以，但0-5, 1-7不能同时实现,3）级控制与部分级控制相结合方式移数网络 第一级 Cube0 级控 第二级 Cube1 部分级控 G1(E,G) G2(F,H) 第三级 Cube2 部分级控 G3(I),G4(J),G5(K,L) 详见P240表6.2,3）采用四功能交换单元的广播式通信 交换单元与控制信号,I1,I2,O1,O2,I1,I2,O1,O2,G=00,G=01
21、,直通,交换,I1,O1,O2,I2,O1,O2,G=10,G=11,上播,下播, 实现3#与0#7#部件进行广播式通信 B(G0)下播 G0=11 E、F(G1)下播 G1=11 I、J、K、L(G2)上播 G2=10 其控制信号G2G1G0=101111B9、三级PM2I互联网络 1）构成：由PM22, PM21, PM20三级构成 2）每级控制信号用两位二进制数控制 Gi=00,直通 Gi=01，PM2+i( 播下） Gi=10，PM2-i( 播上） 详见P242表6.16,3）利用三级PM2I互联网络，实现1#6#通信时所需控制信号,PM2+2 PM2+1 PM2+0 G0=01 G1
22、=00 G2=01 G2G1G0 =010001B,10、三级混洗互联网络 1）构成：也由Cube0、Cube1、Cube2三级立方体构成，但它与三级立方体互联网络有如下区别（两点） Cube2在第一级，Cube0在第三级 为了使级间连接形式与混洗连接相符合，将Cube1中的中间两个交换单元位置互换。（图见下页）,4,0,4,5,1,5,6,2,6,3,7,3,0,1,2,7,Cube2,0,2,0,2,1,3,1,3,Cube1,4,6,4,6,5,7,5,7,0,1,0,1,2,3,2,3,Cube0,4,5,4,5,6,7,6,7,2）三级混洗互联网络是三级立方体网络的逆网络 在三级立方
23、体网络中，不能同时实现0#5 # 、1 # 7 #的连接，但在混洗互联网络中可同时实现0 # 5 # 、1 # 7 #的连接。反之，5 # 0 # 、1 # 7 #的连接不能完成。能否找到一个互联网络，既可同时实现5 # 0 # 、7 # 1 # ，又可同时实现0 # 5 # ，1 # 7 #的通信？,11、全排列多级互联网络 1）网络构成：由三级混洗互联网络和三级立方体互联网络构成 2）网络结构图,4,0,4,5,1,5,6,2,6,3,7,3,0,1,2,7,Cube2,Cube1,Cube0,2,2,6,4,6,3,1,3,5,7,5,4,1,7,1,1,3,2,3,5,4,5,6,7,
24、6,2,4,7,2,2,6,4,6,3,1,3,5,7,5,4,1,7,4,4,5,1,5,6,2,6,3,7,3,1,2,7,0,0,0,0,0,0,0,0,Cube1,Cube2,A,B,C,D,E,F,G,H,I,J,K,L,M,N,O,P,Q,R,S,T,5# 0# B直 H直 K交 N直 Q交7# 1# D直 H直 L直 P直 R交0# 5# A直 E直 I直 O交 R交1# 7# B交 H直 C直 P直 T直 级控制不行，但单元控制可以12、四级立方体互联网络 由Cube0,Cube1,Cube2，Cube3四级立方体构成,Cube0,1,3,7,2,2,3,5,1,4,5,6,3,7,1,2,0,0,0,Cube1,Cube2,4,6,5,9,11,9,15,10,10,11,14,13,12,12,13,14,11,9,10,8,8,8,12,14,13,8,9,10,3,11,1,2,0,Cube3,12,13,14,7,15,5,6,4,7,4,6,15,15,设由3# 0#5#进行广播式通信G： 00 01 10 11 直通 交换 上播 下播 G3=G2=10上播 G1=G0=11下播 则G3G2G1G0=10 10 11 11,
