资源描述
单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第,6,章 阵列处理机,第,6,章 阵列处理机和相联处理机,6.1,阵列处理机的原理,6.2 SIMD,计算机的互连网络,6.3,并行存储器的无冲突访问,6.4,脉动阵列处理机,本章要点,阵列处理机的构型及特点,基本的单级互联网络结构图及互联函数,两功能交换开关及四功能交换开关,多级立方体网络拓扑结构图的画法,多级混洗交换网络拓扑结构图的画法,并行存储器的无冲突访问,1.,阵列处理机的构形,阵列机通常由一个控制部件,CU,、,N,个处理器单元,PE,、,M,个存储模块以及一个互连网络部件,(,IN,),组成。,根据存储器模块是以分布式方式存取还是集中方式存取,阵列机可分为两种基本结构:,分布式存储器的阵列机,和,共享存储器的阵列机。,6.1,阵列处理机的原理,6.1.1,阵列处理机的构形与特点,PEM0,PE0,PEM1,PE1,PEM,N-1,PE,N-1,IN,CU,CUM,I/O,接口,D,SC,分布存储器的阵列机结构,(,1,)分布式存储器的阵列机,各个处理单元设有,局部存,储,器,存放分布式数据,只能被本,处理单元直接访问。在控制部件,CU,内设有一个用来存放程序和,数据的主存,储,器,CUM,。各个,PE,同步执行来自,CU,的操作命令,,各处理单元通过,IN,来交换数据。,IN,PE0,PE1,PE,N-1,MM0,MM1,MM,K-1,CU,SC,I/O-CH,I/O,SM,具有共享存储器的阵列机结构,(,2,)集中式共享存储器的阵列机,每个,PE,没有局部存,储,器,,存储模块以集中形式为所有,PE,共,享。互连网,IN,受,CU,控制,用来构成,PE,和,MM,的数据交换通路,,具有双向性。,2,阵列机的特点,并行处理机有如下特点:,(,1,)利用,资源重复,(空间因素)而非时间重叠。,(,2,)利用,同时性,而非并发性。它的每个处理单元在同一时刻要,同等地担负起各种运算功能。,(,3,)提高运算速度主要是靠,增大处理单元个数,,比起向量流水,线处理机主要依靠缩短时钟周期来说,速度提高的潜力要大得多,(,4,)使用简单而又规整的,互连网络,来确定多个处理单元之间的,连接模式。,(,5,)并行处理机(阵列机)研究必须,与并行算法研究密切结合,,使之适应性更强,应用面更广。,6.1.2 ILLIAC-IV,处理单元阵列结构,处理单元阵列由,64,个,PU,i,构成,每个,PU,i,包括,(PE,i,、,PEM,i,和,MLU,),由,64,个结构完全相同的处理单元,PE,i,构成,每个处理单元,PE,i,字长,64,位,,PEM,i,为隶属于,PE,i,的局部存储器,全部,PE,i,由,CU,统一管理,,PE,i,都有一根方式位线,用来向,CU,传送每个,PE,i,的方,式寄存器,D,中的方式位,使,CU,能了解各,PE,i,的状态是否活动,作,为控制它们工作的依据。,阵列控制器,CU,相当一台小型控制计算机,对处理单元阵列实现控制,(,发控制信号,广播公共地址,(,广播公,共数据,),)对指令流进行译码控制,利用,CU,内部资源可以进行标,量操作,接受和处理各类中断,其他输入输出操作。,I/O,系统,由磁盘文件系统,DFS,,输入输出子系统和宿主计算机,S/C,构成,ILLIAC,的组成,PU16,PU0,PU8,PU7,PU55,PU63,PU0,PU1,PU7,PU8,PU9,PU15,PU56,PU57,PU63,PU0,PU1,PU7,PU56,PU57,PU58,ILLIAC-IV,的处理单元互连结构,特点,:,(1),闭合螺线阵列,(2),任意单元的最短距离不超过,7,步,将,PU63,传送到,PU10,,最快可经,PU63PU7PU8PU9PU10,。,(3),一般来讲:个处理单元组成的阵列中,任,意两个处理单元之间的最短距离不会超过 步,(,4,),处理单元为通常的累加型运算器,把累加寄存器,RGA,中的数据和存储器来的数据进行运算操作,数据传送寄存器,RGR,收发数据,实现数据在处理单元之间的传送。,一 矩阵加,矩阵加,(,配比加,),是最简单的情况。假定两个,8*8,的矩阵,A,、,B,相加,所得结果矩阵,C,也是一个,8*8,的矩阵。设,A,、,B,的分量元素分别存在,PEM,i,的,Z,Z+1,单元中,所得结果矩阵,C,各分量存在,PEM,i,的,Z+2,单元中,用下面三条指令可一次完成,(64,个处理单元并行,),LDA Z,;全部(,Z,)由,PEMi,送到,PE,的累加器,RGAi,ADRN Z+1,;全部(,Z+1,)与(,RGAi,)进行浮点加,结果,送,RGAi,STA Z+2,;全部(,RGAi,)由,PE,送到,PEMi,的(,Z+2,)单元,这里,0 i 63,6.1.3 ILLIAC,的并行算法举例,矩阵加存储器分举例,A(0,0),B(0,0),C(0,0),PEM,0,a,a+1,a+2,A(0,1),B(0,1),C(0,1),PEM,1,A(7,7),B(7,7),C(7,7),PEM,63,处理速度为顺序处理的,64,倍,二 矩阵乘,a0,0 a0,1 a0,7,a1,0 a1,1 a1,7,a7,0 a7,1 a7,7,b0,0 b0,1 b0,7,b1,0 b1,1 b1,7,b7,0 b7,1 b7,7,a0,0,b0,0+a0,1,b1,0+a0,7,b7,0 a0,0,b0,7+a0,1,b1,7+a0,7,b7,7,a1,0,b0,0+a1,1,b1,0+a1,7,b7,0 a1,0,b0,7+a1,1,b1,7+a1,7,b7,7,a7,0,b0,0+a7,1,b1,0+a7,7,b7,0 a7,0,b0,7+a7,1,b1,7+a7,7,b7,7,=,如果顺序执行,C=A,B,,那么,计算每个元素,c,ij,需要做,8,次乘法,,7,次加法,共需做,15,次乘,/,加运算。,在,ILLIAC IV,的处理机上,操作数,B,的,64,个元素存储在,64,个,PEM,中。当每次计算元素,c,ij,时,就把操作数,A,的,8,个元素,a,ik,(0=k=7),播送到相应的,8,个,PE,中,然后并行地,一次,完成,8,个中间积的运算。最后对,8,个中间积做,7,次加法,累加得到,c,ij,。,A(0,0),A(1,0),.,A(7,0),B(0,0),B(1,0),.,B(7,0),C(0,0),C(1,0),.,C(7,0),A(0,1),A(1,1),.,A(7,1),B(0,1),B(1,1),.,B(7,1),C(0,1),C(1,1),.,C(7,1),A(0,7),A(1,7),.,A(7,7),B(0,7),B(1,7),.,B(7,7),C(0,7),C(1,7),.,C(7,7),PE0,PEM2,PEM7,.,矩阵乘存储器分配举例 (设用八个处理单元即,PU,并行),.,八个局部存储器,PEM i,每个连续存放,A,B,和结果向量,C,的一列元素,三、,累加和,(成对递归),这是一个将,N,个数的顺序相加过程转变为并行相加过程的问题。,设,N,为,8,,即有,8,个数,A,(,I,)顺序累加,其中,0I 7,。,在,SISD,计算机上可写成下列程序:,C=0,DO 10 I=0,,,7,10 C=C+A,(,I,),用成对递归算法,只需,Log,2,8=3,在,SIMD,计算机上可写成下列程序,C=A,DO 10 K=0,Log,2,8-1,10 C=C+SHFTR(C,2*K),其中,SHFTR(C,2*K),是向量传送语句,C,向量各分量向右传送步距为,2,的,K,次幂,用成对递归算法求累加和的步骤:,1.,置全部,PE,i,为活跃状态,,0i 7,。,2.,全部,A,(,i,)从,PEM,i,的,a,单元读到相应,PE,i,的累加寄存器,RGA,i,中,,0i 7,;,3.,令,k=0,;,4.,将全部,PE,i,的(,RGA,i,)传送到寄存器,RGR,i,,,0i 7,;,5.,将全部,PE,i,的(,RGR,i,)经过互连网络向右传送,2,k,步距,,0i 7,;,6.,令,j=2,k,-1,;,7.,置,PE,0,至,PE,j,为不活跃状态;,8.,处于活跃状态的所有,PE,j,执行(,RGA,i,),:=(RGA,i,)+,(,RGR,i,),,ji 7,;,9.k:=k+1;,10.,如,k,3,则转回,4,否则往下继续执行,;,11.,置全部,PE,i,为活跃状态,,0i 7,存结果至,a+1,单元。,设原始数据,A,(,I,)分别存在,8,个,PEM,的某,a,单元中,设原始数据,A,(,I,)分别存在,PEM,的某个单元中,步距,1,步距,2,步距,4,K=0 K=1 K=2,PE,0,A0,A0,A0,A0,PE,1,A1,A0+A1,A0+A1,A0+A1,PE,2,A2 A1+A2,A0+A1+A2,A0+A1+A2,PE,3,A3 A2+A3,A0+A1+A2+A3,A0+A1+A2+A3,PE,4,A4 A3+A4 A1+A2+A3+A4 A0+A1+A2+A3+A4,PE,5,A5 A4+A5 A2+A3+A4+A5 A0+A1+A2+A3+A4+A5,PE,6,A6 A5+A6 A3+A4+A5+A6 A0+A1+A2+A3+A4+A5+A6,PE,7,A7 A6+A7 A4+A5+A6+A7 A0+A1+A2+A3+A4+A5+A6+A7,二、递归折叠求和,用递归折叠方法来求累加和过程如下图所示。,上述求累加和算法虽然使计算次数减少,但是速度的提高的倍,数只是,N/Log,2,N,,速度并没有提高多少。,PE,值 步,1,步,2,步,4,0 A0 A0+A1 A0+A1+A2+A3 A0+A1+A2+A3+,1 A1 A4+A5+A6+A7,2 A2 A2+A3,3 A3,4 A4 A4+A5 A4+A5+A6+A7,5 A5,6 A6 A6+A7,7 A7,8,个,PE,的递归折叠求和,长度为,N,的递归计算,时间正比于,Log,2,N,例:,A,和,B,都是元素为浮点表示的,64,64,的二维数组,一次浮点加法的计算过程由取数、求阶差、对阶、尾数加、规格化和存数共,6,个段组成。若每个段的执行时间均为,t,,,请分别求出在下列结构不同的处理机上完成,C=A+B,所需时间及相对于顺序处理的加速比。,(1),顺序处理方式的处理机,(2),具有浮点加法流水线的流水处理机,且浮点加法流水线分为,6,个段,各段执行时间均为,t,。,(3)8,8,的阵列处理机,且处理阵列上的每个处理器只能顺序处理浮点加运算。,(4)8,8,的阵列处理机,且处理阵列上的每个处理器均能流水处理浮点加运算。,(4)64,64,的阵列处理机。,a0,0 a0,1 a0,63,a1,0 a1,1 a1,63,a63,0 a63,1 a63,63,b0,0 b0,1 b0,63,b1,0 b1,1 b1,63,b63,0 b63,1 b63,63,+,a0,0+b0,0 a0,1+b0,1 a0,63+b0,63,a1,0+b1,0 a1,1+b1,1 a1,63+b1,63,a63,0+b63,0 a63,1+b63,1 a63,63+b63,63,=,解:,(1),顺序处理方式下,需要顺序执行的浮点加法次数为,64,64=,4096,,每次浮点加运算所需时间为,6,t,,则全部运算所需时间为:,T1=4096,6t=24576t,(2),需要流水执行的浮点加法次数为,64,64=,4096,,则一个,K=6,段浮点加法流水线处理全部运算所需时间为:,T2=(k+n-1),t=(6+,4096-1),t=4101t,加速比:,S2=T1/T2=5.9,(3),对于,8,8,的处理阵列,每个处理器需要处理,64,64,二维数组中的一个,8,8,子数组,因此,每个处理器需要执行的浮点加法次数为,8,8,。每次浮点加法运算需要时间,6,t,。每个处理器顺序执行,64,次浮点加法所需时间为,64,6t=384t,。,64,个处理器并行处理,同时完成各自的,64,次浮点加运算,所以,全部运算所需时间为:,T3=384,t,加速比:,S2=T1/T3=64,(4),对于,8,8,的处理阵列,每个处理器需要处理,64,64,二维数组中的一个,8,8,子数组,因此,每个处理器需要执行的浮点加法次数为,8,8,。,K=6,段的浮点加法流水线处理,64,次浮点加运算需要时间,(k+n-1),t=(6+6,4-1),t=67t,。,64,个处理器并行处理,同时完成各自的,64,次浮点加运算,所以,全部运算所需时间为:,T4=67,t,加速比:,S2=T1/T4=366.8,(5),对于,64,64,的处理阵列,每个处理器只需执行一次浮点加运算,所需时间为,6t,,所以,全部运算所需时间为:,T5=6,t,加速比:,S2=T1/T5=4096,6.2 SIMD,计算机的互连网络,6.2.1,互连网络的设计目标及互连函数,1.,互联网络的设计目标,a.,采取让相邻的处理单元之间只用有限的几种直连方式实现任何两个处理单元之间所需要的信息传送。,b.,设计目标:结构不要太复杂;灵活性高;信息交换所需传送步数尽可能少;能用规整单一的基本构件组合而成,模块性好;,2.,互连函数,互连网络的连接特征一般用一组,互连函数,表示。,互连函数:出端编码是入端编码的排列、组合、移位、取反等操作的结果。表示,所有入端,与出端的连接关系。,互连函数有,2,种表示方法:,(1),输入输出对应表示法,互连,0 1 N-1,函数,f,(0),f,(1),f,(N-1),(2),函数式表示法:,入端编码表示:,x=bn-1b0 n=log2N,出端编码表示:,f(x)=,基于,bn-1b0,的操作的结果。,自变量和函数可以用二进制表示,也可以用十进制等表示,输入,:0 1 2 3 4 5 6 7,输出,:1 0 3 2 5 4 7 6,6.2,.2,互联网络的应选择的几个问题,(,1,)操作方式:有同步、异步、同异组合三种;,(,2,)控制策略:集中和分布两种;,(,3,)交换方法:有线路交换、包交换及线路与包交换组合三种。,(,4,)网络拓扑:,互联网络入、出端可以实现连接的模式。,有静,态和动态两种;动态网络又有单级循环网络和多级互连网络两,类;,6.2.3,基本的单级互连网络,立方体、,PM2I,和混洗交换和蝶形单级网络。,三维立方体结构,处理单元,Z Y X,三位二进制码编号,每个处理单元只能直接连到其,二进制编号的某一位取反,的其,他,3,个处理单元上。,1.,立方体单级网络,(,交换互连网络,),互连函数:,Cube,0,(b2b1b0),=(b,2,b,1,b,0,),;,Cube,1,(b2b1b0),=(b,2,b,1,b,0,),Cube,2,(b2b1b0),=(b,2,b,1,b,0,),。,互连特性:,交换功能,-,互连函数可逆;,互连函数个数=,log,2,8=3,;,最大连接度,=log,2,8=3,;,结点最大间距,=log,2,8=3,。,互连函数:,Cube,i,函数表示相连的入端和出端的二进制编号只在,右起第,i,位,(,i,=0,1,2),上有差别,即仅在该位上的代码,“,0,”,、,“,1,”,互反,其余各位代码都相同。,立方体单级网络连接图,Cube,0,=(b,2,b,1,b,0,),(,0,,,1,)(,2,,,3,)(,4,,,5,)(,6,,,7,),Cube,1,=(b,2,b,1,b,0,),(,0,,,2,)(,1,,,3,)(,4,,,6,)(,5,,,7,),Cube,2,=(b,2,b,1,b,0,),(,0,,,4,)(,1,,,5,)(,2,,,6,)(,3,,,7,),其连接方式如下图中的,实线,所示。,100,110,注意:立方体坐标编号不能标错。,推广到,n,维的情形,,N,个节点的立方体单级网络共有,n,=log,2,N,种互连函数,即,式中,,0,i,n,-1,,,b,i,为入端号二进制码的第,i,位。当维数,n,3,时,称为超立方体,(Hyper Cube),网络。,它的,最大,距离为,n,,任意两个结点间有至少,n,条路径,容错性较强。,PM2I,单级网络是,“,加减,2,i,”,单级网络的简称。能实现与,j,号处理单元直接相连的是号为,j2,i,的处理单元,即,2.PM2I,单级网络,对于,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),式中,,0,j,N,-1,0,i,n,-1,n,=log,2,N,。因此,它共有,2,n,个互连函数。由于总存在,PM2,+(,n,-1),=PM2,-(,n,-1),,所以实际上,,PM2I,互连网络只有,2,n,-1,种不同的互连函数。,PM2I,互连网络的部分连接图,PM2I,单级网络的最大距离为,n,/2(,向上取整,),。以上面的三维,PM2I,互连网络的例子就可以看出,最多只要二次使用,即可实现任意一对入、出端号之间的连接。,应用:,几种,PM2I,变换的组合,可实现某结点到任意结点的连接,组合不同效率不同。,例:,闭合螺旋结构为,PM2I,0,(,横向,),及,PM2I,n/2,(,纵向,),互连函数。,3.,混洗交换,互连,网络,8,个处理单元的全混连接,这种互连网络由全混洗和交换两种互连函数组成:,全混,Shuffle(b,n-1,b,n-2.,b,1,b,0,)=(b,n-2.,b,1,b,0,b,n-1,),相当于将处理单元的二进制地址位中的,最左位移到最右位,的循环移位。下图示出了有,8,个,PE,的全混洗连接。,000,001,010,011,100,101,110,111,001,010,011,100,101,110,111,000,由于全混洗互连网络不能实现全,0,和全,1,单元与其他单元,的连接,因此引入交换网络中的,Cube0,交换互连函数,表达形,式如下:,Exchange(b,n-1,b,n-2,.b,1,b,0,)=b,n-1,b,n-2,.b,1,b,0,两函数复合后为:,ExchangeShuffle(b,n-1,b,n-2,.b,1,b,0,)=(b,n-2,.b,1,b,0,b,n-1,),下图示出了这种混洗交换互连网络的连接图。(实线表示交换,,虚线表示全混),N,=8,时全混交换互连网络连接图,在混洗交换网络中,最大距离为,2n-1,。最远的两个,PE,(全,0,和全,1,)连接需要,n,次交换和,n-1,次混洗。,4,、蝶式置换,-,编码最高位和最低位位交换位置,互连函数:,(b,n-1,b,n-2,b,1,b,0,)=(b,0,b,n-2,b,1,b,n-1,),;,000,001,010,011,100,101,110,111,N=8,蝶式,置换,000,001,010,011,100,101,110,111,N=8,(1),子,蝶式,置换,000,001,010,011,100,101,110,111,000,001,010,011,100,101,110,111,子蝶式置换:,(k),(b,n-1,b,k+1,b,k,b,k-1,b,0,)=(b,n-1,b,k+1,b,0,b,k-1,b,1,b,k,),(k),(,b,n-1,b,n-k,b,n-k-1,b,n-k-2,b,0,)=(,b,n-k-1,b,n-2,b,n-k,b,n-1,b,n-k-2,b,0,),5,、移数置换,-,编码值移位,互连函数:,(X)=(X+k)mod N,,,0kN-1,;,000,001,010,011,100,101,110,111,k=1,移数置换,000,001,010,011,100,101,110,111,000,001,010,011,100,101,110,111,k=2,移数置换,000,001,010,011,100,101,110,111,互连特性:,互连函数不可逆,(k=0,除外,),;,n,位编码有,2,n,个移数变换功能。,例,:编号为,0,、,1,、,15,的,16,个处理器用单级互连网络互连,,当互连函数分别为,:,(,1,),Cube,3,(,2,),PM2,+3,(,3,),PM2,+2,(,Cube,1,),(,4,),Shuffle(Cube,2,(PM2,-3,),时,第,13,号处理器各连至哪一,个处理器?,解,:编号为,0,、,1,、,.15,的,16,个处理器,所以可用,4,位二进制码,b,3,b,2,b,1,b,0,表示。第,13,号处理器的二进制编号为,1101,。所以,(,1,),Cube,3,(,1101,),=0101,,即连接到,5,号处理器上。,(,2,),PM2,+3,(,13+2,3,),mod 16=5,,即连接到,5,号处理器上。,(,3,),PM2,+2,(Cube,1,(1101)=3,,即连接到,3,号处理器上。,(,4,),Shuffle(Cube,2,(PM2,-3,(13)=Shuffle(Cube,2,(0101),=Shuffle,(,0001,),=0010,,即连接到,2,号处理器上。,6.2.4,基本的多级互连网络,交换开关,交换开关是组成互连网络的基本构件。通常,它是二功能,或四功能的。二功能是直连或交换。四功能就是在二功能基础,上在加上上播和下播,,,开关状态连接方式如下图所示;,决定多级互连网络的特性的主要因素有以下三个方面:,交,换开关、拓扑结构和控制方式,。,a.,直连,i,入,连,i,出,,,j,入,连,j,出,;,b.,交换,i,入,连,j,出,,,j,入,连,i,出,;,i,入,j,入,i,出,j,出,i,入,j,入,i,出,j,出,c.,上播,i,入,连,i,出,和,j,出,,,j,入,悬空;,d.,下播,j,入,连,i,出,和,j,出,,,i,入,悬空。,拓扑结构,是指各级之间出端和入端相互连接的模式。,可将单级互连网络的那些连接模式进行不同的组合,构成多,种不同的多级互连网络。,i,入,j,入,i,出,j,出,i,入,i,出,j,入,j,出,控制方式是对各个交换开关进行控制的方式,以多级立方体网络为例,它可以有,3,种:,(1),级控制,同一级的所有开关只用一个控制信号控制,同时只能处于同一种状态;,(2),单元控制,每一个开关都有自己独立的控制信号控制,可各自处于不同的状态;,(3),部分级控制,对不同的级采用不同数量的控制信号。第,i,级的所有开关分别用,i,+1,个信号控制,,0,i,n,-1,n,为级数。是前面两种方式的折衷。,控制方式,1.,多级立方体网络,(,STARAN,和间接二进制,n,方体网络,),以,8,个处理单元为例,其结构如下图所示。,共同特点,:第,i,级交换单元处于交换状态时,实现的是,Cube,i,互连函数,且都采用二功能交换单元。,区别:控制方式不同,,STARAN,网络采用级控制和部分级控制,间接二进制,n,方体网络采用单元控制。,常用的多级互连网络有:,多级立方体网络、多级混洗交换网络又称,omega,网络,和,多级,PM2I,网络,。,N,=8,多级立方体互连网络,Cube0,Cube1,Cube2,具有,N,个入端和,N,个出端的多级立方体网络拓扑结构图 的画法为:,先求出该多级立方体网络的级数,n,,每级画,N/2,个二功能,交换开关;级编号从输入到输出依次是:,0,1,i,n-1;,让所有,第,i,级各交换开关的两个出入端均按,Cubei,的关系配对编上号;,再将各级开关同一编号的端用线连上。,STARAN,网络用作交换网络时,采用级控制,实现的是交换,函数。所谓,交换,(Flip),函数,,是将一组元素首尾对称地进行,交换。如果一组元素包含有,2,s,个,则它是将所有第,k,个元素都,与第,(2,s,-(,k,+1),个元素相交换。如下表,1,列出级控信号采用各,种不同组合情况下,3,级交换网络所实现的入、出端的连接。,K0,控制,Cube0,K1,控制,Cube1,K2,控制,Cube2,K,i,=0,直连,K,i,=1,交换,表,1,三级,STAR,AN,交换网络实现的入出端连接及所执行的交换函数功能,(K,i,为第,I,级控制,信号,),(1),交换功能的控制与实现,开关组合控制方式:,级控制。,(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),网络功能的应用,交换功能很适合于双向互连,(,对称,),要求的实现;,移数功能很适合于累加求和等要求的实现。,例,1,:,阵列有,07,共,8,个处理单元,要求按(,0,,,5,)、(,1,,,4,)、(,2,,,7,)、(,3,,,6,)配对通信。,(1),写出实现此功能的互连函数一般式。,(,2,)画出用三级立方体网络实现互联函数的网络拓扑结构图,标出各级交换开关状态。,解:,f,(,b2b1b0,),=b2b1b0,交换,直连,交换,例,2,:,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,互连函数:,f(b,3,b,2,b,1,b,0,)=(b,3,b,2,b,1,b,0,),各级开关状态:,k,3,k,2,k,1,k,0,=(1011),由此得出第,0,、,1,、,3,级开关状态为交换,第,2,级为直连,交换,交换,交换,直连,级,k0 k1 k2 k3,0,1,2,3,4,5,6,7,8,9,A,B,C,D,E,F,0,1,2,3,4,5,6,7,8,9,A,B,C,D,E,F,共有,16,个结点,编码需要,4,位,开关共,4,级。,例,3,:,现有,16,个,PE(,编号,0F),与网络连接,程序在某个时刻需实现下列通信配对:,7D,、,6C,、,5F,、,4E,、,39,、,28,、,1B,、,0A,。请画出互连网络结构图,并写出控制方式及各开关状态。,答:,因需实现双向交换功能,选择,STARAN,网络的交换功能,(,级控制方式,),可满足要求。,网络拓扑结构:,共有,16,个结点,编码需要,4,位,开关共,4,级。,配对要求:,(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,结点配对,已经过,3,次镜像,需,8,组,2,元交换,。,各级开关状态:,k,3,k,2,k,1,k,0,=(1010),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,相加,Cube,1,+Cube,3,级,k0 k1 k2 k3,0,1,2,3,4,5,6,7,8,9,A,B,C,D,E,F,0,1,2,3,4,5,6,7,8,9,A,B,C,D,E,F,由此得出第,1,、,3,级开关状态为交换,第,0,、,2,级为直通,交换开关:,四功能;,拓扑结构:,多级,Shuffle,;,Omega,网络中各级编号的次序与多级立方体网络正好相反,,把,Omega,网络的入、出端对调,就等于多级立方体网络。,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,级,开关组合控制:,级控制、开关二功能,-,STARAN,交换网络的逆网络;,部分级控制、开关二功能,STARAN,移数网络的逆网络,;,单元控制、开关二、四功能,-,更强大的功能。,网络关系:按全混方法,Shuffle,(,p,n-1,p,n-2,p,0,),=p,n-2,p,0,p,n-1,则有:,入,0 0,出 入,41,出,1 2 53,2 4 65,3 6 77,混洗拓扑就是将编号为,0,,,1,.N-1,的入端分成前后个数相等的两半,前一半和后一半在连至输出时顺次一一相隔。各级画好后,再将连线沿途所经过的端号均标成同一端号即可。,例:画出,0,7,号共,8,个处理器的三级混洗交换网络,在该图,上标出实现将,6,号,处理器数据播送给,0,4,号,同时将,3,号,处理,器数据播送给,其余,3,个处理器,时的各有关交换开关的控制状态;,3.,多级,PM2I,网络(数据交换网络),N,=8,三级,PM2I,网络,2,j,j+2,i,mod N,j-2,i,mod N,结构:,n,级,每一级把前后各,N=2,n,个单元按,PM2I,拓扑互连接。,对第,i,级,每一个单元,j,(,0,j,N-1,)都有,3,根连线分别连到出端单元,j,、,j+2,i,mod N,和,j-2,i,mod N,,图中分别用不同的线段表示。,控制这三类连接线的信号分别为,平控,H,、上控,D,、下控,U,。若采用单元控制方式,每一级都有自己独立的控制信号,H,、,D,、,U,,称此,PM2I,网络为,强化数据交换网络(,ADM,),。,6.2.5,全排列网络,(1),多级网络比较,灵活性,(,低高,),:,STARAN,、间接二进制,n,方体、,Omega(),、,ADM(,混洗四功能,),成本,(,低高,),:,同上,用途:,STARAN,、,Omega PEPM,间接二进制,n,方体,PE-PE,功能:,同时,只能实现,部分互连函数,功能。,(2),全排列网络,定义:,所有入端、出端的连接均不发生冲突的网络,又称非阻塞型网络,即:,N,入,N,出,有,N,!种排列。,常规多级网络,(,如,STARAN,、,等,),属于阻塞型网络。,证明:,对,n=log,2,N,级网络,开关数,=N/2,n,。,排列数,回下页,DTR,MUX,循环,单级,/,多级网络,PE,0,来,去,PE,0,PE,N-1,来,去,PE,N-1,DTR,MUX,(3),全排列网络实现,方法:,a.,原有多级网络通过锁存器运行两次即可;,思想:,N!,N,N/2,N,N/2,N,N,。,b.,两个,log,2,N,网络背靠背串联。,Benes,网络,6.3,并行存储器无冲突访问,一、访问需求,并行存取向量中各分量信息;,对矩阵可按行、列、对角线等方法访问,(,步长不一致,),。,二、存在问题,存储器带宽限制,存储器带宽达不到向量带宽;,访存方式,(,步长,),不同,产生访存冲突。,三、解决方法,1,、采用多体交叉存储器,使存储体数超过,PE,数,保证,PE,所需要的带宽。,2,、对向量分组操作,解决,MEM,带宽小于向量长度问题,提高处理效率。,3,、选择适当的存储体数,m,使存储体数,mPE,数,达到无冲突访问,(,1,),一维向量:,顺序存放,防止步长与,m,成比例;,m,取质数,与步长互质。,一维数组的存贮,(,m,=4),假设,并行存贮器的分体数,m=4,,交叉存放一维向量,a0.,,如下左图所示。,a.,每次访问,m,个相连的元素,无冲突;,b.,若跳跃式访问,步距为,2,:,a0,a2,a4,a6,,有冲突;,步距为,4,:,a0,a4,a8,a12,,有冲突;,c.,把存贮器的体数取成一个质数,只要变址步距与,m,互质,存贮,器总能无冲突访问;(如下例所示,只要变址步长不是,5,的倍数就可以实现无冲突访问。),a,0,a,1,a,2,a,3,a,4,a,5,a,6,a,7,a,8,a,9,a,10,a,11,一维数组的存贮,(,m,=5),存贮器的体号,4,3,2,1,0,如果设,m,=,n,=4,一个,44,的二维数组直接按行存贮,方案如下图所示。虽然,同时访问某一行、主对角线或次对角线上的所有元素时,都可以做到无冲突地访问,但要同时访问某一列的各元素时,由于它们集中存放在同一存贮分体内,会产生访存冲突,所以每次只能顺序访问该列中其中的一个元素,致使实际频宽降低成,1/4,。,44,数组的直接按行存贮,(,m,=,n,=4),(,2,)多维向量,冲突,44,数组一种错位存放的方案,为了使行或列的各元素都能并行访问,若如下图所示的将,数据错位存放,但这样造成主对角线上各元素的并行访问冲突。,把存贮器的分体数,m,取成大于每次要访问的向量或数组的个数,n,,,且等于质数,同时在多维数组的行、列等方向上采取不同的错开,距离。,错位存放,满足行、列、对角线等访问要求;,对矩阵而言,(m,大于,PE,数时,)-,设,m=2,2P,+1,,,1,=2,P,,同一列不同行错开距离,2,=1,,同一行不同列错开距离,对,A,ab,,体号:,j=(a,1,+b,2,+C)mod m,体内序号:,i=a,C,为起始元素,A,00,所在体号地址,44,数组错位存放的例子,(,m,=5,n,=4,1,=2,2,=1),45,二维数组在并行存贮器中存放的例子,(,m,=7,n,=6),让地址,所对应的元素存放在体号地址,j=,mod m,,,体内地址为,i=,/n,的单元中,,就可实现无冲突访问。,当向量元素不固定,或非,n,n,时,-,将多维变换成一维数组,S,,再对,S,进行处理。,6.4,脉动阵列处理机和,6.5,相联处理机(自己看),本章小结,1,。阵列处理机的原理,(,1,)阵列机的分类及特点,(,2,),ILLIAC,的结构,2,。,SIMD,计算机的互连网络,(,1,)掌握各种互连函数,找出各处理单元的入出段连接。,(,2,)掌握多级网络拓扑结构图的画法,(,3,)根据要求标出各级开关的状态,3,。并行存贮器的无冲突访问,多维数组无冲突访问的条件以及各元素存放的具体位置。,
展开阅读全文