计算机体系结构(金星)第六章阵列处理机

第六章阵列处理机,一、阵列处理机的原理,阵列处理机也称并行处理机，它将大量重复设置的处理单元PE按一定方式互连成阵列，在单一控制部件CU控制下对各自所分配的不同数据并行执行同一指令规定的操作，是操作并行的SIMD计算机。处理单元是不带指令控制部件的算术逻辑运算单元用于向量、数组要求高速运算的场合。,1、SIMD基本构形,(1)分布式存储器(2)集中式存储器,分布式存储器,集中式存储器,2、阵列处理机与流水线机比较,二、并行算法,1、ILLIACIV的处理单元阵列结构,ILLIACIV的处理单元阵列结构特点,N=64处理单元数构成8*8阵列第i个处理单元PUi与以下四个单元连接上:(i8)mod64下:(i+8)mod64左:(i-1)mod64右:(i+1)mod64网络直径：网络中任意两个结点间最短路径长度的最大值。对于n*n的阵列，网络直径为n-1,2、并行算法举例,矩阵加：C=A+B，其中A，B，C为8*8的矩阵并行算法对数据存储的要求：不同向量相同位置的元素放在同一个存储器内，同一向量的各元素放在不同存储器的同一地址单元中。,aa+1a+2,PEM0PEM1PEM63,LDAALPHAADRNALPHA+1STAALPHA+2,三、SIMD计算机的互连网络,1、基本概念(1)互连网络的定义互连网络是一种由开关元件按照一定的拓扑结构和控制方式构成的网络，用于实现计算机系统内部多个处理机或多个功能部件之间的相互连接。,(2)互连网络的设计目标,结构简单，降低成本互连灵活，满足应用要求步距小，提高速度结构规整，扩充性好,(3)互连网络的分类,静态连接网络：使用直接链路连接各结点，并且构成后结点间的连接方式就固定不变的网络。用于构造通信模式可预测或可用静态连接实现的计算机系统。动态连接网络：结点之间的连接不固定，使用开关或仲裁器实现结点之间的互连，根据程序要求动态连接开关，常用于集中式共享存储器多处理系统。,(4)互连函数,互连函数(路由函数)：N个输入端的结点号与N个输出端的结点号的一种对应关系可以用一个映射函数表示，称为互连函数。它是处理单元集合对于自身的双射映射，所以又称为“置换”，或者“循环”。把互连网络的n个结点用0,n-1表示，则f(x)表示以结点x为入端的通道的出端。,互连函数有多种表示方式，如下例所示：,f(0)=1f(1)=2f(2)=0f(3)=3a.枚举法,b.开关状态图,f=(0,1,2)(3)d.循环函数,一个网络通过开关切换可以形成多个映射关系，所以要用“互连函数族”来定义一个网络。,2基本的单级互连网络,立方体PM2I混洗交换,立方体网络,连接规律：每个处理单元只能直接连接到它的二进制编号某位取反的处理单元上。,Cube0:(01)(23)(45)(67)Cube1:(02)(13)(46)(57)Cube2:(04)(15)(26)(37),一般情况下，一个n()维超立方体共有n个互连函数(分别由n位地址中的每一位求反位值来确定)：,Cube0，Cube1，Cuben-1Cubei的功能是对入端结点编号二进制形式的第i位取反Cubei(Pn-1Pi+1PiPi-1P0)=Pn-1Pi+1PiPi-1P0，其中0in-1,网络直径：立方体网络直径为n立方体网络是一个可逆网络,连接规律：j号处理单元直接连接到j2i号处理单元PM2I函数定义：功能是对入端结点编号加或减2i，然后再作模N运算。PM2+i（j）=(j+2i)modNPM2-i（j）=(j-2i)modN其中j=0N-1，i=0n-1。PM2I函数共有n对成员，分别是PM20，PM21，PM2(n-1)。由于PM2(n-1)的函数值相等，所以只有2n-1个函数网络直径：,(2)PM2I网(移数网、单级加减2i网）,N=8时，有5个不同的互连函数,PM2+0：(01234567)PM2-0：(76543210)PM2+1：(0246)(1357)PM2-1：(6420)(7531)PM2+2：(04)(26)(15)(37),(3)均匀混洗交换网络,该网络由混洗函数(shuffle)与交换函数(exchange即Cube0)定义.混洗函数：将结点的二进制编号循环左移一位shuffle（Pn-1Pn-2P0）=Pn-2P0Pn-1,n=3的混洗网络拓扑形状如下图绿线所示，可以看出它不是一个连通图，所以还需要增加一个交换函数（图中红线所示），才能构成完整的单级混洗交换网络。,单级混洗交换网络的直径是2n-1。,3、多级互连网,定义：多级ICN使用多级开关，将多个单级网络串联，以实现任意两个处理单元之间的连接。将多级互连网络循环使用可实现复杂的互连。通常在N个结点的网络中，多级ICN由n级构成（n=log2N）。经典的多级互连网有多级立方体网、多级混洗交换网和多级PM2I网。,多级网络的三个参数：,(1)交换开关：二元交换开关的基本接通状态有“直连”、“交换”、“上播”和“下播”。,(2)拓扑结构(3)控制方式,(3)控制方式,各开关的控制信号可采用3种分配方式之一：级控方式、部分级控方式和单元控制方式。级控方式就是同一级（即同一列）开关共用一个控制信号，动作保持一致；部分级控方式在第i级设置i+1个独立的控制信号，每个信号管辖若干开关；单元控制方式为每个开关独自设置一个控制信号，各开关动作独立，性能比前两种方式都更灵活，结构也更复杂。,(1)多级立方体,它由n级构成，每一级包含N/2可控的二元交换开关采用二功能交换单元:直连和交换当第I级开关处理交换状态时，实现的是Cubei函数,多级立方体网络结构,多级立方体网络特点续：,采作三种不同的控制方式，可以构成三种不现的互连网络：级控制构成STARAN交换网络部分级控制构成STARAN移数网络单元控制构成间接立方体网络灵活性好,STARAN交换网络,级控制信号(二进制)：K2K1K0Ki=0表示第i级的开关为直连状态，Ki=1表示第i级的开关为交换状态,例：已知入端号和控制信号，求出端号若控制信号Ki=1，则入端号的第i位取反例：已知入端号和出端号，求控制信号控制信号=入端号和出端号异或,恒等,4组2元+2组4元,4组2元,(2)多级混洗交换网络,多级混洗交换网络又称为Omega网。多级混洗交换网络结构：它由n级构成，每一级包含一个全混拓扑线路和一列(N/2个)可控的二元交换开关四功能交换单元控制方式：单元控制,多级混洗交换网络结构,多级混洗交换网络的特点续：,在多级混洗交换网络中，单独一级混洗拓扑线路可完成一次数据混洗（shuffle），而单独一列二元交换开关在处于“交换”状态时可完成一次交换操作（Cube0）。如果各级二元交换开关都处于“直连”状态，N个结点的数据通过网络仅经过n次混洗操作，排列顺序最终恢复输入状态；如果各级二元交换开关都处于“交换”状态，则N个结点的数据在每次混洗之后紧接着一次交换（Cube0），也就是地址码的最低位取反，最后n位地址均被取反。程序员根据数据置换或复制的需要，可以灵活地设置各开关的状态。,多级混洗交换网络与多级立方体网络的关系,(3)多级PM2I,包含n级单元间连接，每一级前后两列的单元都按PM2I拓扑连接。第I级的每一个入端都连接到三个出端：j、(j+2i)modN、(j-2i)modN控制方式：部分级控制构成数据变换网络DM采用单元控制构成强化数据变换网络ADM,(4)全排列网络,非阻塞式网络：所有入端、出端的连接都不发生冲突的网络，又称为全排列网络N个结点的全部排列有N!种阻塞式网络(Blocking):在实现两对或多对入出端连接时，都因可能因争用数据传送路径而发生冲突的网络。立方体网络、PM2I、Omega网络都是阻塞式网络N个结点的多级阻塞式网络在一次传送这中能实现的排列有NN/2种,Benes网络：三维立方体多级网络和它的可逆网络构成的全排列网络,Benes网络：三维立方体多级网络和它的可逆网络构成的全排列网络,Benes网络：三维立方体多级网络和它的可逆网络构成的全排列网络,四、并行存储器的无冲突访问,阵列处理机中，存储器要采用多体并行，才能保证其频宽与多个处理单元速度匹配，还要保证实现无冲突访存操作(即要访问的数据不在同一体内)以数组为例：数组的访问模式：行、列、主对角线、次对角线、子方阵,1、一维数组,连续访问m=4个元素，无冲突按2i变址，冲突，存储器频宽降低一半为了避免冲突，M应取质数(只要变址跳距与m互质),2、二维数组,同时访问某一行、主对角线、次对角线上的所有元素时，无冲突同时访问某一列时，冲突，存储器频宽降低为1/4,错位存放,方案一中主对角线和次对角线并行访问冲突方案二中当访问模式为行、列、主对角线、次对角线、子方阵时均无冲突,(1)无冲突访问错位存放方案的一种实现,思想：数据交叉存储在m个存储体中，并且使存储体M大于每次要访问的全部向量元素N，且为质数。1表示同列相邻元素错开的距离2表示同行相邻元素错开的距离M确定：m=22p+1(p为正整数)实现无冲突访问的充分条件：1=2p,2=1对于一个n*n维的二维数组，元素Aab存放的地址：体号:j=(a1+b2+c)modm体内:i=a,(2)无冲突访问错位存放方案的第二种实现,有n个处理单元的并行处理机，为了能并行访问n个元素,存储体数m为大于n最小质数将多维数组行或列的顺序变换为一维数组，形成一个一维线性地址空间，地址用s表示。如果按行展开：S=元素的行号*行数+元