第6章阵列处理机.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第,6,章 阵列处理机,6.1,阵列处理机原理,6.2,阵列处理机的并行算法,6.3 SIMD,计算机的网络互连,6.4,并行存储器的无冲突访问,6.5,并行处理机举例,本章重点：,总的要求是理解阵列处理机的结构和工作原理。了解与流水处理机的差别。理解在阵列处理机解题时对并行算法及存储单元分配规则、互连网络等的特殊要求。熟练掌握基本的单级网络及其互连函数表示。理解循环互连网络的实现。熟练掌握多级网络、全排列网络的画法。理解解决并行存储器无冲突访问的办法。,互连函数和多级互连网络。,本章难点：,并行算法和多级互连网络。,6.1,阵列处理机原理,6.1.1,阵列处理机的基本构形,阵列处理机,(Array Processor),也称为并行处理机,(Parallel Processor),主要用于对大量向量、数组要求高速运算的场合。,阵列处理机是重复设置处理单元按一定方式连成阵列在单一控制部件控制下对各自分配的数据执行同一指令规定的操作，是操作级并行的,SIMD,的计算机。,由于存储器的组成方式不同，阵列处理机有两种不同的基本构形。,1,、分布式存储器的阵列处理机构形,各,处理单元有局部存储器,PEM(Processing,Element Memory),存放被分布的数据，只能被本处理单元直接访问。在控制部件,CU,上有一主存可传播给各个处理单元，运算中可通过互连网络,ICN,交换数据。,在执行主存中的用户程序时，所有指令都在控制部件中进行译码，把只适合串行处理的标量或控制类指令留给控制部件,CU,自己执行，而把适合于并行处理的向量类指令“播送”给各个,PE,，控制处于“活跃”的那些,PE,并行执行。下图是采用分布式存储器的阵列处理机构形。,PEM,0,ICN,互连网络,PE,0,CU,CUM,PEM,1,PE,1,PEM,N-1,PE,N-1,I/O,接口,SC,D,控制,数据总线,控制总线,控制,具有分布式存储器的阵列处理机构形,为了有效高速地处理向量数据，这种构形要求能把数据合理地预分配到各个处理单元的局部存储器中，使各处理单元,PE,i,主要用自己的局存,PEM,i,中的数据运算。,采用这种构形的阵列处理机是,SIMD,的主流。典型机器有,ILLIAC,、,MPP,、,DAP,、,CM-2,、,MP-1,、,DAP600,系列等。,2,、集中式共享存储器的阵列处理机构形,系统存储器由,K,个存储体集中组成，并经,ICN,为全部,N,个处理单元所共享。,为使各处理单元对长度为,N,的向量中各个元素都能同时并行处理，存储体体数,K,应等于或多于处理单元数,N,。,PE,0,ICN,互连网络,CU,PE,1,PE,N-1,I/O-CH,MM,0,MM,1,MM,k-1,SC,I/O,SM,具有集中式共享存储器的阵列处理机构形,各处理单元在访主存时，为避免发生分体冲突，也要求有合适的算法能将数据合理地分配到各个存储体中。,互连网络,ICN,是用于在处理单元与存储器分体之间进行转接构成数据通路，使各处理单元能高速灵活地动态与不同的存储体相连，使尽可能多的,PE,能无冲突地访问共享的主存模块。,集中式共享存储器的阵列处理机主要特点是将资源重复和时间重复结合起来开发并行性。,采用这种构形的典型机器有,BSP,。,6.1.2,阵列处理机的特点,1,、利用资源重复而不是时间重叠；利用并行性中的同,时性而不是并发性。,2,、,资源利用率不如流水线高，但提高速度的潜,力比流水线处理机大。,（阵列处理机主要是,靠增大处理单元数提高速度，向量流水处理,机主要靠缩短时钟周期提高速度）。,3,、,阵列处理机,使用简单规整的互连网络来确定处,理单元间的连接，因此，互连网络设计很重要。,4,、它是以某类算法为背景的专用计算机，基本上,是专用于向量处理的计算机,(,某类算法专用机,),，,故阵列处理机专用性强。,5,、,阵列机的研究必须与并行算法研究密切结合，以使它的求解算法适应性更强一些，应用面更广一些,(,与并行算法结合研究,),。,阵列处理机实质,上是由专门对付数组运算的处理单元阵列组成的,处理机,、专门从事处理单元阵列的控制及标量处理的,处理机,和专门从事系统输入输出及操作系统管理的,处理机,组成的一个异构型多处理机系统。,6.2,阵列处理机的并行算法,6.2.1 ILLIAC,的处理单元阵列结构,ILLIAC IV,处理阵列由,8,8,64,个,PU,组成。每个,PU,由处理部件,PE,和它的局部存储器,PEM,组成。,每一个,PU,i,只和它的上、下、左、右四个近邻直接连接。,PU,i+1,mod 64,、,PU,i-1,mod 64,、,PU,i+8,mod 64,、,PU,i-8,mod 64,上下方向上同一列的,PU,连成一个环，左右方向上构成一个闭合螺线。,采用闭合螺线最短距离不超过,7,步。而普通网格最短距离不超过,8,步。,这种阵列中，任意两个单元之间的最短距离不超过 步。,例如：,从,PU,0,到,PU,36,的距离：采用普通网格必须,8,步：,PU,0,PU,1,PU,2,PU,3,PU,4,PU,12,PU,20,PU,28,PU,36,或,PU,0,PU,8,PU,16,PU,24,PU,32,PU,33,PU,34,PU,35,PU,36,或,（等于,8,步的很多，大于,8,步的更多）,如果采用闭合螺旋线，只需要,7,步：,PU,0,PU,63,PU,62,PU,61,PU,60,PU,52,PU,44,PU,36,普通网格必须,8,步：,PU,0,PU,1,PU,2,PU,3,PU,4,PU,12,PU,20,PU,28,PU,36,或,PU,0,PU,8,PU,16,PU,24,PU,32,PU,33,PU,34,PU,35,PU,36,或,闭合螺旋线只要,7,步：,PU,0,PU,63,PU,62,PU,61,PU,60,PU,52,PU,44,PU,36,或,PU,0,PU,63,PU,55,PU,47,PU,39,PU,38,PU,37,PU,36,或,P,180,习题,6.1,解,如图：,与,PU0,相连的处理单元有：,PU1,、,PU12,、,PU15,、,PU4,与,PU1,、,PU12,、,PU15,、,PU4,相连的有,PU2,、,PU3,、,PU5,、,PU13,、,PU8,、,PU11,、,PU14,（删去一步单元）与,PU2,、,PU5,、,PU13,、,PU8,、,PU11,、,PU14,相连的有：,PU6,、,PU7,、,PU9,、,PU10,（删去一、二步单元）,PE0,经一步可将信息传送至,PU1,、,PU4,、,PU12,、,PU15,。,PE0,至少需经二步才能将信息传送至,PU2,、,PU3,、,PU5,、,PU8,、,PU11,、,PU13,、,PU14,。,PE0,至少需经三步步才能将信息传送至,PU6,、,PU7,、,PU9,、,PU10,。,6.2.2,阵列处理机的并行算法举例,1,、矩阵加,把,C=A+B,中的属于同一位置向量元素放在同一局部存储器中。,两个,8,8,的矩阵,A,、,B,相加，所得结果,C,也是,8,8,矩阵，矩阵相加的存储器分配如下图所示,(“,全并行”的工作特点，速度提高，但存储单元分配算法的设计比较麻烦,),。,C(0,1),B(0,1),A(0,1),C(7,7),B(7,7),A(7,7),C(0,0),B(0,0),A(0,0),PEM,0,PEM,63,PEM,1,矩阵相加的存储器分配举例,2,、矩阵乘,把,C=A*B,的各向量按列存放在一个局部存储器中。,设,A,、,B,和,C,为,3,个,8,8,的二维矩阵，给定,A,和,B,，计算,C=A*B,得,64,个分量可用公式：,其中,0 i 7,且,0 j 7,。,在,SISD,计算机上求解，用,FORTRAN,语言编写程序为：,DO 10 I=0,7,DO 10 J=0,7,C(I,J)=0,DO 10 K=0,7,10 C(I,J)=C(I,J)+A(I,K)*B(K,J),需经,I,、,J,、,K,三重循环完成。每重循环执行,8,次，共需,512,次相乘、加得时间，且每次还要包括执行循环控制判别等其它操作所需得时间。,如果在,SIMD,阵列机上运算，可用,8,个处理单元并行计算矩阵,C(I,J),得某一行或某一列，即将,J,循环或,I,循环转化成一维的向量处理，从而消去了一重循环。以消去,J,循环为例，可执行的,FORTRAN,语言编写的程序为：,DO 10 I=0,7,C(I,J)=0,DO 10 K=0,7,10 C(I,J)=C(I,J)+A(I,K)*B(K,J),让,J=07,各部分同时在,PE,0,PE,7,上运算，这样只需,K,、,J,二重循环，速度可提高至,8,倍，即只需,64,次乘、加的时间。,（,164,页图,6.5,）,每次控制部件执行的,PE,指令表面上是标量指令，实际上已等效于向量指令，是,8,个,PE,并行地执行同一条指令。每次播送时，利用阵列处理机的播送功能将处理单元,PE,K,中累加寄存器,RAG,K,的内容经控制部件,CU,播送到全部,8,个处理单元的,RGA,中去。,为了让各个处理单元,PE,i,尽可能只访问所带局部存储器,PEM,i,，以保证高速处理，就必须要求对矩阵,A,、,B,、,C,各分量在局部存储器中的分布采用,165,页如图,6.6,所示的方案。,3,、累加和,把向量存到所有处理单元的局部存储器中。,将,N,个数的顺序相加转为并行相加的问题。,取,N=8,，即有,8,个数,A(I),顺序累加，其中,0I7,。,在,SISD,计算机上可以写成,FORTRAN,程序：,C=0,DO 10 I=0,7,10 C=C+A(I),这是一个串行程序，需要,8,次加法时间。,在阵列处理机上用成对递归相加算法，只需,次加法时间即可。首先，原始数据,A(I),分别存放在,8,个,PEM,的 单元中，其中,0I7,，求累加和的步骤如下：,（,1,）置全部,PE,i,为活跃状态，,0I7,；,（,2,）全部,A(I),从,PEM,i,的 单元读到相应,PE,i,的累加寄存,器,RGA,i,中，,0I7,；,（,3,）令,K=0;,（,4,）将全部,PE,i,的,(,RGA,i,),转送到传送寄存器,RGR,i,0I7,；,（,5,）将全部,PE,i,的,(,RGR,i,),经过互连网络向右传送,2,K,步距,0I7,；,（,6,）令,j=2,K,-1;,（,7,）置,PE,0,PE,j,为不活跃状态；,（,8,）处于活跃状态的所有,PE,i,执行,(,RGA,i,),：,=,(,RGA,i,)+(,RGR,i,),ji7;,（,9,）,K:=K+1;,（,10,）如,K3,时称超立方体网络。,单级立方体网络的最大距离为,n,。,2.PM2I,单级网络,PM2I,单级网络是加减,2,i,单级网络的简称。能实现与,j,号处理单元直接相连的是号为,j2,i,的处理单元，即：,PM2,+i,(j)=j+2,i,mod N,PM2,-i,(j)=j-2,i,mod N,其中,0 i n-1,，,0 j N-1 n=log,2,N,N,是结点数。它共有,2n,个互连函数。,PM2I,网络的最大距离为,n/2,。,由于,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,+1,：（,0 2 4 6,）（,1 3 5 7,）,PM2,2,：（,0 4,）（,1 5,）（,2 6,）（,3 7,）,0,1,2,3,4,5,6,7,PM2,+0,PM2,+1,PM2,2,0,1,2,3,4,5,6,7,0,1,2,3,4,5,6,7,PM2I,互连网络的部分连接图,3.,混洗交换单级网络,混洗交换单级网络（,Shuffle-Exchange,）,包含两个互连函数，一个是全混（,PerfectShuffle,）,另一个是交换（,Exchange,）。,这种互连网络由全混洗和交换两种互连函数组成：,全混,Shuffle(P,n-1,P,n-2,.P,1,P,0,)=(P,n-2,.P,0,P,n-1,),式中，,n=log,2,N,。相当于将处理单元的进制地址位中的最左位移到最右位的循环移位。由于全混洗互连网络不能实现全,0,和全,1,单元与其他单元的连接，因此引入交换网络中的,Cube,0,函数，两函数复合后为：,ExchangeShuffle(P,n-1,P,n-2,.P,1,P,0,)=,(P,n-2,.P,0,P,n-1,),0,1,2,3,4,5,6,7,N=8,时全混交换互连网络连接图,在混洗交换网络中，最远的两个入、出端号是全“,0”,和全“,1”,，它们的连接需要,n,次交换和,n-1,次混洗，,所以最大距离为,2n-1,。,6.3.3,多级互连网络,将前面三种单级互连网络重复连接，就形成了最基本的多级互连网络。即多级立方体互连网络、多级混洗交换网络和多级,PM2I,网络。,决定多级互连网络的特性的主要因素有以下三个方面：,交换开关、拓扑结构和控制方式,。,交换开关是具有两个输入端和两个输出端的交换单元。,交换开关有直连、交换、上播、下播四种功能,；控制方式则有,级控制、单元控制、部分级控三种方式。,（,1,）,直连,i,入,连,i,出,，,j,入,连,j,出,；,（,2,）,交换,i,入,连,j,出,，,j,入,连,i,出,；,（,3,）,上播,i,入,连,i,出,和,j,出,，,j,入,悬空；,（,4,）,下播,j,入,连,i,出,和,j,出,，,i,入,悬空。,级控制,同一级的所有开关只用一个控制信号,控制，同时只能处于同一种状态；,单元控制,每一个开关都有自己独立的控制信,号控制，可各自处于不同的状态；,部分级控制,第,i,级的所有开关分别用,i+1,个信,号控制，,0 i n-1,，,n,为级数。,1.,多级立方体网络,通常是采用交换互连单级网络串接起来构成的。,采用三种不同的控制方式，可以构成三种不同的互连网络。,采用级控制可以构成,STARAN,交换网。采用部分级控制，可以构成,STARAN,移数网。采用单元控制可以构成间接二进制,n,方体网。,STARAN,多级互连网络就是,Cube,0,Cube,1,Cube,2,三种互连函数的三个单级立方体网串接起来的。在采用不同的级控制信号时，可以实现任一输入端到任一输出端的直接连接。,第,i,级（,0 i n-1,）交换单元处于交换状态时，实现的是互连函数，且都采用二功能交换单元。,A,B,C,D,E,F,G,H,I,J,K,L,0,1,2,3,4,5,6,7,0,1,2,3,4,5,6,7,k=0,k=1,k=2,N=8,多级立方体互连网络,开关组合控制：,级控制、部分级控制,-,STARAN,网络,(,交换、移数功能,),；,单元控制,-,间接二进制,n,方体网络,(,更复杂的功能,),。,（,1,）交换功能,开关组合控制方式：,级控制。,级,控制信号（,k,2,k,1,k,0,）,000,001,010,011,100,101,110,111,入 端,0,0,1,2,3,4,5,6,7,1,1,0,3,2,5,4,7,6,2,2,3,0,1,6,7,4,5,3,3,2,1,0,7,6,5,4,4,4,5,6,7,0,1,2,3,5,5,4,7,6,1,0,3,2,6,6,7,4,5,2,3,0,1,7,7,6,5,4,3,2,1,0,功,能,i,Cube,0,Cube,1,Cube,0,+,Cube,1,Cube,2,Cube,0,+,Cube,2,Cube,1,+,Cube,2,Cube,0,+,Cube,1,+,Cube,2,分组交换功能：,组间次序不变，组内元素镜像。,Cube,0,-,4,组,2,元交换；,Cube,1,-,2,组,4,元交换,+4,组,2,元交换；,Cube,2,-,1,组,8,元交换,+2,组,4,元交换。,（,2,）移位功能,开关组合控制方式：,部分级控制,(,第,i,级有,i+1,种控制信号,),2级,K,L,0,0,1,0,0,0,0,J,0,1,1,0,0,0,0,I,1,1,1,0,0,0,0,1级,F,H,0,1,0,0,1,0,0,E,G,1,1,0,1,1,0,0,0级,A,B,C,D,1,0,0,1,0,1,0,功 能,移,1,Mod 8,移,2,Mod 8,移,4,Mod 8,移,1,Mod 4,移,2,Mod 4,移,1,Mod 2,不,移,衡等,Mod,的作用：,不同,Mod,可用于不同的分组操作。,（,3,）应用,交换功能很适合于双向互连等要求的实现；,移数功能很适合于累加求和等要求的实现。,（,4,）带宽问题,STARAN,可同时多对结点连接，尚不能同时任意组合。,（,5,）例题,例,1,：,16,个,PE,采用,STARAN,网络互连时，实现相当于,4,组,4,元交换，然后,2,组,8,元交换，再,1,组,16,元交换功能。写出互连函数一般式、各级交换开关状态。,答：,因需实现交换功能，故选择,STARAN,的交换功能,(,级控制方式）。,4,组,4,元交换,Cube,0,+Cube,1,2,组,8,元交换,Cube,0,+Cube,1,+Cube,2,1,组,16,元交换,Cube,0,+Cube,1,+Cube,2,+Cube,3,相加,Cube,0,+Cube,1,+Cube,3,各级开关状态：,k,3,k,2,k,1,k,0,=(1011),互连函数：,f(b,3,b,2,b,1,b,0,)=(b,3,b,2,b,1,b,0,),例,2,：,编号,0F,的,PE,间，要实现下列通信配对：,(7,D),(6,C),(5,F),(4,E),(3,9),(2,8),(1,B),(0,A),。请画出互连网络结构图，写出控制方式及各开关状态。,答：,因需实现双向交换功能，选择,STARAN,网络的交换功能,(,级控制方式,),可满足要求。,网络拓扑结构：,因共有,16,个结点，编码需要,4,位，所以开关共,4,级。,0,级,开关,+,(1),，,f(b,3,b,2,b,1,b,0,)=b,3,b,2,b,0,b,1,1,级,-,开关,+,(2),，,f(b,3,b,2,b,0,b,1,)=b,3,b,1,b,0,b,2,2,级,-,开关,+,，,f(b,3,b,1,b,0,b,2,)=b,2,b,1,b,0,b,3,3,级,-,开关,+,逆,Shuffle,，,f(b,2,b,1,b,0,b,3,)=b,3,b,2,b,1,b,0,0,1,2,3,4,5,6,7,8,9,A,B,C,D,E,F,级,k0 k1 k2 k3,0,1,2,3,4,5,6,7,8,9,A,B,C,D,E,F,配对要求：,(7,D),(6,C),(5,F),(4,E),(3,9),(2,8),(1,B),(0,A),开关控制：,因,7,的结点与,7,的结点配对，故需,1,组,16,元交换,；,因,03,的结点与,8B,的结点配对,故需,2,组,8,元交换,；,因,01,的结点与,AB,的结点配对,故需,4,组,4,元交换,；,因,0,结点与,A,结点配对，故需,8,组,2,元交换,。,相加,Cube,1,+Cube,3,1,组,16,元交换,Cube,0,+Cube,1,+Cube,2,+Cube,3,2,组,8,元交换,Cube,0,+Cube,1,+Cube,2,4,组,4,元交换,Cube,0,+Cube,1,8,组,2,元交换,Cube,0,各级开关状态：,k,3,k,2,k,1,k,0,=(1010),2.,多级混洗交换网络,（,网络,即,Omega,网络,）,A,B,C,D,E,F,G,H,I,J,K,L,0,1,2,3,4,5,6,7,2,级,0,1,2,3,4,5,6,7,1,级,0,级,交换开关：,四功能；,拓扑结构：,多级,Shuffle,；,互连函数：,2,级,-f(b,2,b,1,b,0,)=b,1,b,0,b,2,1,级,-f(b,1,b,0,b,2,)=b,0,b,2,b,1,0,级,-f(b,0,b,2,b,1,)=b,2,b,1,b,0,开关组合控制：,级控制、开关二功能,-,STARAN,交换网络的逆网络；,部分级控制、开关二功能,STARAN,移数网络的逆网络；,单元控制、开关二、四功能,-,更强大的功能。,3.,多级,PM2I,网络,N=8,的多级,PM2I,网络的结构,如,174,页图,6.16,所示。它包含,n,级单元间连接，每一级都是把前后两列各,N=2,n,个单元按,PM2I,拓扑相互连接起来。从第,i,级（,0in-1,）来说，每一个单元,j,（,0iN-1,）都有,3,根连接线分别通往出单元,j,、,j+2,i,mod N,和,j-2,i,mod N,，在图中，它们分别用点线、实线和虚线表示。,采用单元控制增强对各级单元控制的灵活性，让每一单元都有自己独立的控制信号,H,、,D,、,U,（平控,H,、下控,D,、上控,U,）,。此种多级,PM2I,网络称为强化数据变换网络,AMD,（,Augmented Data Manipulator,），但是控制线多，成本较高。,ADM,的拓扑结构和控制方式使它可以完全模仿,omega,网络的四功能交换单元。利用数据变换网络可以实现各种灵活的移数、重复、间隔、展开等变换函数。,多级网络比较,灵活性,(,低高,),：,STARAN,、间接二进制,n,方体、,Omega(,),、,ADM(,混洗四功能,),成本,(,低高,),：,同上,用途：,STARAN,、,Omega PEM,间接二进制,n,方体,PEPE,功能：,只能实现同时,部分多对多,功能,。,4.,全排列网络,定义：,所有入端、出端的连接均不发生冲突的网络，又称非阻塞型网络，即：,N,入,N,出有,N,！种排列。,常规多级网络,(,如,STARAN,、,等,),属于阻塞型网络。,证明：,对,n=log2N,级网络，开关数,=N/2n,。,排列数,全排列网络实现：,思想：,N!,N,N/2,N,N/2,N,N,。,方法：,a.,原有多级网络通过锁存器运行两次即,可；,b.,两个,log2N,网络背靠背串联。,用多级网络也可以实现全排列网络。,将,log,2,N,级的,N,个入端和,N,个出端的互连网络和它的逆网络连在一起，省去中间完全重复的一级，就可以得到总级数为,2log,2,N-1,级的全排列网络。,175,页图,6.17,就是以三维立方体多级网络和它的逆网络连在一起，省去中间重复的一级后构成的全排列网络，称此网络为,Benes,网络,。,6.4,并行存储器的无冲突访问,在阵列处理机中，存储器频宽要与多个处理单元的速率匹配，如何保证在各种访问模式下，存储器都能实现无冲突访问？,为保证对存储器的并行无冲突访问，可采用的方法有，,数据交叉存储在,m,个存储体中，并且使存储体,M,大于每次要访问的全部向量元素,N,，且为质数。,将数组按行或列变换成一维数组，形成一个一维线性地址空间，地址用,a,表示，然后，将地址,a,所对应的元素存放在体号地址,j=a mod m,，体内地址,i=a/n,的单元中，就可以满足无冲突访问的要求。,无冲突访问技术,一、访问需求,并行存取向量中各分量信息；,对矩阵可按行、列、对角线等方法访问,(,步长不一致,),。,二、存在问题,存储器带宽限制,存储器带宽达不到向量带宽；,访存方式,(,步长,),不同，产生访存冲突。,三、解决方法,1,、采用多体交叉存储器,使存储体数超过,PE,数，保证,PE,所需要的带宽。,2,、对向量分组操作,解决,MEM,带宽小于向量长度问题，提高处理效率。,3,、选择适当的存储体数,m,使存储体数,mPE,数，达到无冲突访问,一维向量：,顺序存放，防止步长与,m,成比例；,m,取质数,(,与,PE,数互质,),，且与步长互质。,一维数组的并行递归算法,:,并行存储体数不能再取,2,的整数，而应该取成质数，当变址跳距与分体数互质时，就可以进行无冲突访问。,多维向量：,错位存放，满足行、列、对角线等访问要求；,对矩阵而言,(m,大于,PE,数时,)-,设,m=2,2P,+1,，,1=2,P,，同一列不同行错开距离,2=1,，同一行不同列错开距离,对,Aab,，,体号：,j=(a,1+b,2+C)mod m,体内序号：,i=a,a00 a01 a02 a03,a13 a10 a11 a12,a21 a22 a23 a20,a30 a31 a32 a33,体号,0 1 2 3 4,4,4,矩阵的错位存放,(m=5),当向量元素不固定，或非,nn,时,将多维变换成一维数组,S,，再对,S,进行处理。,对,S(a,),，体号：,j=a mod m,体内序号：,i=a/n,a00 a10 a20 a30 a01 a11,a31 a02 a12 a22 a32 a21,a23 a33 a04 a14 a03 a13,a24 a34,体号,0 1 2 3 4 5 6,45,二维数组的错位存放,(m=7,，,n=6),通过浪费少量存储带宽和空间来避免冲突。,浪费比例：,(m-n)/m,，,一般,n=m-1,。,常用方法：,存储体数为质数，将向量变换成一维数组,S,，,再对,S,进行处理。,6.5,并行处理机举例,6.5.1 MPP,位平面阵列处理机,MPP,位平面阵列处理机是美国,Goodyear,宇航公司专门设计用于遥感卫星图象处理的巨型并行处理机,1983,年在美国空军投入使用,.,它对,ILLIAC IV,阵列结构的重大改进就是采用位平面结构。每一个处理单元只包含一位的硬设备，内部的算术逻辑运算按位片串行进行。这既节省了设备，又使处理单元之间的信息通路宽度大大减小。与,64,位的,ILLIAC IV,阵列相比，硬件设备量可减少为原来的几十分之一，即用同样的硬件设备量至少可以扩大阵列规模几十倍，也利于采用,VLSI,工艺。,MPP,原理图,如,178,页图,6.23,所示：,1,、阵列部件,ARU(ARAY UNIT),由,16384=128*,128,个处理单元,PE,组成，每个,PE,附有,1024,个本地随机存储器。,2,、阵列物理规模为,128,行*,132,列，其中,4,列允许替换硬件出故障的列，使阵列规模仍保持,128*,128,，同时存储器有校错功能。,3,、字长可有,4,、,8,、,12,、,16,、,20,、,24,、,28,或,32,等多种，,基本时钟频率,10MHz,循环周期为,100ns,。,4,、在,MPP,阵列中，每一个,PE,只与其上、下、左、右,4,个邻近,PE,相连接，阵列四个边缘的连接可用程序设置，有,平面、水平圆柱、垂直圆柱、开螺线和闭螺线,5,种不同的阵列拓扑。,5,、阵列,ARU,的左、右两边各有一排,128,位的开关，各通过,128,根并行线与阵列相连。,6,、阵列控制部件执行,MPP,汇编语言，除了控制数据的输入输出通路外，还要执行存储在它的程序存储器中的应用程序，功能包括循环控制、子程序调用和标量运算等。,7,、,整个系统的控制任务是由程序及数据管理部件,PDMU,来承担的。,8,、,系统可有独立、联机和高速数据,3,种运行方式。,6.5.2 CM,连接机,20,世纪,80,年代末,90,年代初，,Thinking Machines,公司推出连接机,CM-2,，其后端处理阵列可含（,464,）,K,个,PE,，,采用位片结构。其中每个芯片是,4*4,个,PE,组成的网格，安置杂,12,维的超级立方体的顶角上，每个,PE,最多可自带,1Mb,存储器。所有数据处理器都受定序器控制，最大速度为,10GFLOPS,。,CM-2,已用于解决文档检索、医疗诊断、,VLSI,电路分析和布线、计算流体动力学等。,CM-5,是,CM-2,的高档机，其应用领域更宽，是实现,3T,性能目标的最新系统。它突破了,CM-2,和之前的系统所用的那种通用性有限的固定,SIMD,结构，改用把,SIMD,和,MIMD,优点相结合的更为通用的系统结构，采用同步,MIMD,并行计算结构。,CM-5,的组成,如,179,页图,6.24,所示：,1,、系统经数据网络、控制网络和诊断网络互连,3,个子系统。,2,、数据网络提供处理器结点间高速点点数据通信。,3,、控制网络提供广播、同步、扫描和系统系统管理功能。,4,、诊断网络对系统检测、诊断和故障隔离。,5,、,CM-5,的数据网络采用胖数型，,如,180,页图,6.25,所示是一种二叉胖树结构。控制网络是一棵完全二叉树，诊断网络也是一棵二叉树。,6,、处理结点子系统可带向量部件，执行由标量微处理机发出的向量指令。,20,世纪,90,年代初，,MasPar,计算机公司又推出了,MP-1,系统，它与,CM-2,结构很不相同，请大家参阅其它资料。,习题讲解：,P181,例,6.11,解,1,、,M,17,（大于,16,且为质数）,2,、,M,17,2,（,2,2,）,1,，所以,P,2,3,、,1,2,P,4,，,2,1,4,、体号地址：,J,（,4a+b+c)mod 17,5,、体内地址：,I=a,第,6,章 小结,1.,阵列处理机原理，要求达到识记层次。,1.1,阵列处理机的工作方式和两种基本结构形式。,1.2,与流水线对比，阵列处理机的主要特点。,2.,阵列处理机的并行算法，要求达到领会层次。,2.1 ILLIAC,的互连结构模式及最大传送步距。,2.2,在分布式存储器构形的阵列机上，并行算法对存,储器信息分布存放的特定要求。,2.3,并行算法要求处理单元之间的互连具有规律性，,有可能还需要有播送功能。,3.SIMD,计算机的互连网络，要求达到综合应用层次。,3.1,互连网络的设计目标。,3.2,互连函数的各种表示。,3.3,立方体、,PM21,、混洗交换三种单级网络的互连函数表示、,互连函数个数、最大距离。,3.4,循环互连网络和多级互连网络的思想，知道多级互连网络,的三个参量。,3.5,画,8,或,16,个端的多级立方体和多级混洗（,omega,）网络。,3.6,按算法要求，找出互连规律，选择适合于此算法的互连网,络及控制方式，画出网络拓扑图，确定开关状态。,3.7,立方体、,omega,、,PM21,网络都是阻塞式网络的含义，全排,列网络的含义及实现全排列网络的两种方式，这部分要求,达到领会层次。,4.,并行存储器的无冲突访问，要求达到简单应用层次。,4.1,实现一维数组步距为,2i,无冲突传送时，对存储器模,m,的要,求。,4.2,写出方阵和长方阵数组实现存储器无冲突访问时的存储体,数及数据元素在体中分布的规律。,作业,6.1,6.2,6.3,6.7,6.8,6.9,6.11,