计算机系统结构6.pptVIP

第六章 阵列处理机 6.1 阵列处理机的原理 6.2 SIMD计算机的互连网络 6.3 共享主存构形的阵列处理机中并行存储器的无冲突访问 6.4 脉动阵列流水处理机 6.1.1阵列处理机的构形和特点 阵列处理机(Array Processor)也称并行处理机(Parallel Processor)通过重复设置大量相同的处理单元PE(Processing Element)，将它们按一定方式互连成阵列,在单一控制部件CU(Control Unit)控制下，对各自所分配的不同数据并行执行同一组指令规定的操作，操作级并行的SIMD计算机，它适用于矩阵运算。 7.3.5 Omega网络 采用全混洗函数和交换函数，又称混洗交换网络。 1、N个输入的Omega网络有log2N级，每级有N/2个2×2的四功能交换开关 2、每级的拓扑结构相同 3、采用单元控制 4、能够实现任意一个输入端到任意一个输出端的连接。但不能同时实现多个输入端到多个输出端的连接。 5、能够实现从任意一个输入端到所有输出端的广播。 如果采用级控制，是STARAN交换网的逆网 如果采用部分级控制，是STARAN移数网的逆网 因此，Omega网的许多性质与多级立方体网相反，如发生冲突的情况 Omega网属于多级互连网 当有N个输入端时，共有N^(N/2)个变换 要同时实现任意一个输入端到任意一个输出端的连接，共需N!个变换 8个输入端的Omega网络实际上只能实现全部变换的10%(8^4/8! = 4096/40320=0.1016)，有90%的变换将引起阻塞 Omega网络是一种阻塞网络，采用多次通过来解决冲突 有N个输入端时，实现连接的通过次数最多为log2N N=8的多级立方体网络和Omega网络的关系 这是一个三维的情形。立方体的每一个顶点(网络的节点)代表一个处理单元，共有 8 个处理单元，用zyx三位二进制码编号。它所能实现的入、出端连接如同立方体各顶点间能实现的互连一样，即每个处理单元只能直接连到其二进制编号的某一位取反的其他 3 个处理单元上。如 010 只能连到 000、 011、110，不能直接连到对角线上的 001、100、101、111。 所以，三维的立方体单级网络有 3 种互连函数：Cube0、 Cube1和Cube2。其连接方式如图 6.10 中的实线所示。Cubei函数表示相连的入端和出端的二进制编号只在右起第i位(i=0, 1, 2)上有差别，即仅在该位上的代码“0”、“1”互反，其余各位代码都相同。 立方体单级网络连接图 与i结点最近的距离就是在立方体中有直线连通的结点，只需1步就可到达；次近的是面对角线另一端的结点，至少需要2步到达；最远的是体对角线另一端的结点，需要3(n=3)步。 推广到n维的情形，N个节点的立方体单级网络共有n=log2N种互连函数， 即 式中，0≤i≤n-1，Pi为入端号二进制码的第i位。当维数n＞3时，称为超立方体(Hyper Cube)网络。 2) PM2I单级网络 PM2I单级网络是“加减2i”(Plus-Minus 2i)单级网络的简称。能实现与j号处理单元直接相连的是号为j±2i的处理单元， 即 式中，0≤j≤N-1, 0≤i≤n-1, n=log2N。因此，它共有2n个互连函数。由于总存在PM2+(n-1)=PM2-(n-1)，所以实际上，PM2I互连网络只有2n-1种不同的互连函数。 对于N=8的三维PM2I互连网络的互连函数有PM2+0、 PM2-0、PM2+1、PM2-1、PM2±2等 5 个不同的互连函数，它们分别为： PM2+0: (0 1 2 3 4 5 6 7) PM2-0: (7 6 5 4 3 2 1 0) PM2+1: (0 2 4 6)(1 3 5 7) PM2-1: (6 4 2 0)(7 5 3 1) PM2±2: (0 4)(1 5)(2 6)(3 7) 图 6.11 PM2I互连网络的部分连接图 有的阵列处理机采用单向环网或双向环网实现处理器的互连，可以看成是PM2I网络的特例，它仅使用了其中的PM2+0、 PM2-0或PM2±0互连函数。不难看出，ILLIAC Ⅳ处理单元的互连也是PM2I互连网络的特例，只采用了其中的PM2±0和 (即PM2±3)4 个互连函数。 PM2I单级网络的最大距离为［n/2］。以上面的三维PM2I互连网络的例子就可以看出，最多只要二次使用，即可实现任意一对入、 出端号之间的连接。 3) 混洗交换单级网络 图 6.12