第6章__阵列处理机

1、第第6 6章章 阵列处理机阵列处理机6.1 6.1 阵列处理机原理阵列处理机原理6.2 6.2 阵列处理机的并行算法阵列处理机的并行算法6.3 SIMD6.3 SIMD计算机的网络互连计算机的网络互连6.4 6.4 并行存储器的无冲突访问并行存储器的无冲突访问6.5 6.5 并行处理机举例并行处理机举例本章重点：本章重点： 总的要求是理解阵列处理机的结构和工作原总的要求是理解阵列处理机的结构和工作原理。了解与流水处理机的差别。理解在阵列处理。了解与流水处理机的差别。理解在阵列处理机解题时对并行算法及存储单元分配规则、理机解题时对并行算法及存储单元分配规则、互连网络等的特殊要求。熟练掌握基本的单

2、级互连网络等的特殊要求。熟练掌握基本的单级网络及其互连函数表示。理解循环互连网络的网络及其互连函数表示。理解循环互连网络的实现。熟练掌握多级网络、全排列网络的画法。实现。熟练掌握多级网络、全排列网络的画法。理解解决并行存储器无冲突访问的办法。理解解决并行存储器无冲突访问的办法。 互连函数和多级互连网络。互连函数和多级互连网络。本章难点：本章难点： 并行算法和多级互连网络。并行算法和多级互连网络。6.1 6.1 阵列处理机原理阵列处理机原理6.1.1 6.1.1 阵列处理机的基本构形阵列处理机的基本构形 阵列处理机阵列处理机(Array Processor),(Array Processor),

3、也称为并也称为并行处理机行处理机(Parallel Processor)(Parallel Processor)主要用于对大主要用于对大量向量、数组要求高速运算的场合。量向量、数组要求高速运算的场合。 阵列处理机是重复设置处理单元按一定方阵列处理机是重复设置处理单元按一定方式连成阵列在单一控制部件控制下对各自分配式连成阵列在单一控制部件控制下对各自分配的数据执行同一指令规定的操作，是操作级并的数据执行同一指令规定的操作，是操作级并行的行的SIMDSIMD的计算机。的计算机。 由于存储器的组成方式不同，阵列处理机由于存储器的组成方式不同，阵列处理机有两种不同的基本构形。有两种不同的基本构形。 1

4、 1、分布式存储器的阵列处理机构形、分布式存储器的阵列处理机构形 各各处理单元有局部存储器处理单元有局部存储器PEM(Processing PEM(Processing Element Memory)Element Memory)存放被分布的数据，只能被存放被分布的数据，只能被本处理单元直接访问。在控制部件本处理单元直接访问。在控制部件CUCU上有一上有一主存可传播给各个处理单元，运算中可通过主存可传播给各个处理单元，运算中可通过互连网络互连网络ICNICN交换数据。交换数据。 在执行主存中的用户程序时，所有指令都在执行主存中的用户程序时，所有指令都在控制部件中进行译码，把只适合串行处理在控制

5、部件中进行译码，把只适合串行处理的标量或控制类指令留给控制部件的标量或控制类指令留给控制部件CUCU自己执自己执行，而把适合于并行处理的向量类指令行，而把适合于并行处理的向量类指令“播播送送”给各个给各个PEPE，控制处于，控制处于“活跃活跃”的那些的那些PEPE并行执行。下图是采用分布式存储器的阵列并行执行。下图是采用分布式存储器的阵列处理机构形。处理机构形。PEM0ICN互连网络互连网络PE0CUCUMPEM1PE1PEMN-1PEN-1I/O接口接口SCD控制控制数据总线数据总线控制总线控制总线控制控制具有分布式存储器的阵列处理机构形具有分布式存储器的阵列处理机构形 为了有效高速地处理向

6、量数据，这种构形要为了有效高速地处理向量数据，这种构形要求能把数据合理地预分配到各个处理单元的局求能把数据合理地预分配到各个处理单元的局部存储器中，使各处理单元部存储器中，使各处理单元PEPEi i主要用自己的局主要用自己的局存存PEMPEMi i中的数据运算。中的数据运算。 采用这种构形的阵列处理机是采用这种构形的阵列处理机是SIMDSIMD的主流。的主流。典型机器有典型机器有ILLIAC ILLIAC 、MPPMPP、 DAPDAP、CM-2CM-2、MP-1MP-1、DAP600DAP600系列等。系列等。 2 2、集中式共享存储器的阵列处理机构形、集中式共享存储器的阵列处理机构形 系统

7、存储器由系统存储器由K K个存储体集中组成，并经个存储体集中组成，并经ICNICN为全部为全部N N个处理单元所共享。个处理单元所共享。 为使各处理单元对长度为为使各处理单元对长度为N N的向量中各个元的向量中各个元素都能同时并行处理，存储体体数素都能同时并行处理，存储体体数K K应等于或多应等于或多于处理单元数于处理单元数N N。PEPE0 0ICNICN互连网络互连网络CUCUPEPE1 1PEPEN-1N-1I/O-CHI/O-CHMMMM0 0MMMM1 1MMMMk-1k-1 SC SC I/O I/OSMSM具有集中式共享存储器的阵列处理机构形具有集中式共享存储器的阵列处理机构形

8、各处理单元在访主存时，为避免发生分体冲各处理单元在访主存时，为避免发生分体冲突，也要求有合适的算法能将数据合理地分配到突，也要求有合适的算法能将数据合理地分配到各个存储体中。各个存储体中。 互连网络互连网络ICNICN是用于在处理单元与存储器分是用于在处理单元与存储器分体之间进行转接构成数据通路，使各处理单元能体之间进行转接构成数据通路，使各处理单元能高速灵活地动态与不同的存储体相连，使尽可能高速灵活地动态与不同的存储体相连，使尽可能多的多的PEPE能无冲突地访问共享的主存模块。能无冲突地访问共享的主存模块。 集中式共享存储器的阵列处理机主要特点是集中式共享存储器的阵列处理机主要特点是将资源重

9、复和时间重复结合起来开发并行性。将资源重复和时间重复结合起来开发并行性。 采用这种构形的典型机器有采用这种构形的典型机器有BSPBSP。6.1.2 6.1.2 阵列处理机的特点阵列处理机的特点1 1、利用资源重复而不是时间重叠；利用并行性中的同、利用资源重复而不是时间重叠；利用并行性中的同 时性而不是并发性。时性而不是并发性。2 2、资源利用率不如流水线高，但提高速度的潜资源利用率不如流水线高，但提高速度的潜 力比流水线处理机大。力比流水线处理机大。（阵列处理机主要是（阵列处理机主要是 靠增大处理单元数提高速度，向量流水处理靠增大处理单元数提高速度，向量流水处理 机主要靠缩短时钟周期提高速度）

10、。机主要靠缩短时钟周期提高速度）。 3 3、阵列处理机阵列处理机使用简单规整的互连网络来确定处使用简单规整的互连网络来确定处 理单元间的连接，因此，互连网络设计很重要。理单元间的连接，因此，互连网络设计很重要。4 4、它是以某类算法为背景的专用计算机，基本上、它是以某类算法为背景的专用计算机，基本上 是专用于向量处理的计算机是专用于向量处理的计算机( (某类算法专用机某类算法专用机) )， 故阵列处理机专用性强。故阵列处理机专用性强。5 5、阵列机的研究必须与并行算法研究密切结阵列机的研究必须与并行算法研究密切结合，以使它的求解算法适应性更强一些，应合，以使它的求解算法适应性更强一些，应用面更

11、广一些用面更广一些( (与并行算法结合研究与并行算法结合研究) )。 阵列处理机实质阵列处理机实质上是由专门对付数上是由专门对付数组运算的处理单元阵列组成的组运算的处理单元阵列组成的处理机处理机、专门从事处理单元阵列的控制及标量处专门从事处理单元阵列的控制及标量处理的理的处理机处理机和专门从事系统输入输出及和专门从事系统输入输出及操作系统管理的操作系统管理的处理机处理机组成的一个异构组成的一个异构型多处理机系统。型多处理机系统。6.2 6.2 阵列处理机的并行算法阵列处理机的并行算法6.2.1 ILLIAC 6.2.1 ILLIAC 的处理单元阵列结构的处理单元阵列结构 ILLIAC IVIL

12、LIAC IV处理阵列由处理阵列由8 8 8 86464个个PUPU组成。组成。每个每个PUPU由处理部件由处理部件PEPE和它的局部存储器和它的局部存储器PEMPEM组组成。成。 每一个每一个PUPUi i只和它的上、下、左、右四个只和它的上、下、左、右四个近邻直接连接。近邻直接连接。PUPUi+1i+1 mod 64 mod 64、PUPUi-1i-1 mod 64 mod 64、PUPUi+8i+8 mod 64 mod 64、PUPUi-8i-8 mod 64 mod 64 上下方向上同一列的上下方向上同一列的PUPU连成一个环，左右连成一个环，左右方向上构成一个闭合螺线。方向上构成一

13、个闭合螺线。 PU56 PU57 PU63 PU63 2 3 4 5 6 PU8 PU8 10 11 12 13 14 PU16 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 PU55 58 59 60 61 62 PU0 PU0 PU1 PU7PU0PU1PU8PU9PU56PU57PU7PU15PU63 采用闭合螺线最短距离不超过采用闭合螺线最短距离不超过7 7步。而普通网步。而普通网格最短距离不超

14、过格最短距离不超过8 8步。步。这种阵列中，任意两这种阵列中，任意两个单元之间的最短距离不超过个单元之间的最短距离不超过 步。步。 例如：例如：从从PUPU0 0到到PUPU3636的距离：采用普通网格必须的距离：采用普通网格必须8 8步：步：PUPU0 0 PUPU1 1 PU PU2 2 PU PU3 3 PU PU4 4 PU PU1212 PU PU2020 PU PU2828 PU PU3636或或 PUPU0 0 PU PU8 8 PU PU1616 PU PU2424 PU PU3232 PUPU3333 PU PU3434 PU PU3535 PU PU3636或或 （等于（等

15、于8 8步的很多，大于步的很多，大于8 8步的更多）步的更多）如果采用闭合螺旋线，只需要如果采用闭合螺旋线，只需要7 7步：步：PUPU0 0 PU PU63 63 PU PU62 62 PU PU61 61 PU PU60 60 PU PU52 52 PU PU44 44 PU PU36361 1N N 普通网格必须普通网格必须8 8步：步：PUPU0 0 PU PU1 1 PU PU2 2 PU PU3 3 PU PU4 4 PU PU12 12 PUPU20 20 PU PU28 28 PU PU3636或或 PUPU0 0 PU PU8 8 PU PU16 16 PU PU24 24

16、PU PU32 32 PU PU33 33 PU PU34 34 PU PU35 35 PU PU3636或或 闭合螺旋线只要闭合螺旋线只要7 7步：步：PUPU0 0 PU PU63 63 PU PU62 62 PU PU61 61 PU PU60 60 PU PU52 52 PU PU44 44 PU PU3636或或 PUPU0 0 PU PU63 63 PU PU55 55 PU PU47 47 PU PU39 39 PU PU38 38 PU PU37 37 PU PU3636或或 P P180180习题习题6.16.1 解解 如图：如图： 与与PU0PU0相连的处理单元有：相连的处

17、理单元有：PU1PU1、PU12PU12、PU15PU15、PU4PU4 与与PU1PU1、PU12PU12、PU15PU15、PU4PU4相连的有相连的有PU2PU2、PU3PU3、PU5PU5、PU13PU13、PU8PU8、PU11PU11、PU14PU14（删去一步单元）（删去一步单元）与与PU2PU2、PU5PU5、PU13PU13、PU8PU8、PU11PU11、PU14PU14相连的有：相连的有：PU6PU6、PU7PU7、PU9PU9、PU10PU10（删去一、二步单元）（删去一、二步单元） PE0PE0经一步可将信息传送至经一步可将信息传送至PU1PU1、PU4PU4、PU1

18、2PU12、PU15PU15。 PE0PE0至少需经二步才能将信息传送至至少需经二步才能将信息传送至PU2PU2、PU3PU3、PU5PU5、PU8PU8、PU11PU11、PU13PU13、PU14PU14。 PE0PE0至少需经三步步才能将信息传送至至少需经三步步才能将信息传送至PU6PU6、PU7PU7、PU9PU9、PU10PU10。 6.2.2 6.2.2 阵列处理机的并行算法举例阵列处理机的并行算法举例1 1、矩阵加、矩阵加 把把C=A+BC=A+B中的属于同一位置向量元素放在同一局部中的属于同一位置向量元素放在同一局部存储器中。存储器中。两个两个8 8 8 8的矩阵的矩阵A A、

19、B B相加，所得结果相加，所得结果C C也也是是8 8 8 8矩阵，矩阵相加的存储器分配如下图所示矩阵，矩阵相加的存储器分配如下图所示(“(“全并行全并行”的工作特点，速度提高，但存储单元分配的工作特点，速度提高，但存储单元分配算法的设计比较麻烦算法的设计比较麻烦) )。 C(0,1)C(0,1)B(0,1)B(0,1)A(0,1)A(0,1)C(7,7)C(7,7)B(7,7)B(7,7)A(7,7)A(7,7)C(0,0)C(0,0)B(0,0)B(0,0)A(0,0)A(0,0) 1 1 2 2 PEMPEM0 0PEMPEM6363PEMPEM1 1矩阵相加的存储器分配举例矩阵相加的存

20、储器分配举例2 2、矩阵乘、矩阵乘 把把C=AC=A* *B B的各向量按列存放在一个局部存储器中。的各向量按列存放在一个局部存储器中。 设设A A、B B和和C C为为3 3个个8 8 8 8的二维矩阵，给定的二维矩阵，给定A A和和B B，计，计算算C=AC=A* *B B得得6464个分量可用公式：个分量可用公式： 其中其中0 i 70 i 7且且 0 j 70 j 7。 在在SISDSISD计算机上求解，用计算机上求解，用FORTRANFORTRAN语言编写程序为：语言编写程序为： DO 10 I=0,7DO 10 I=0,7 DO 10 J=0,7 DO 10 J=0,7 C(I,J

21、)=0 C(I,J)=0 DO 10 K=0,7 DO 10 K=0,7 10 C(I,J)=C(I,J)+A(I,K) 10 C(I,J)=C(I,J)+A(I,K)* *B(K,J)B(K,J) k kj j7 71 1k ki ik ki ij jb ba aC C 需经需经I I、J J、K K三重循环完成。每重循环执行三重循环完成。每重循环执行8 8次，共需次，共需512512次相乘、加得时间，且每次还要包次相乘、加得时间，且每次还要包括执行循环控制判别等其它操作所需得时间。括执行循环控制判别等其它操作所需得时间。 如果在如果在SIMDSIMD阵列机上运算，可用阵列机上运算，可用8

22、8个处理单个处理单元并行计算矩阵元并行计算矩阵C(I,J)C(I,J)得某一行或某一列，即将得某一行或某一列，即将J J循环或循环或I I循环转化成一维的向量处理，从而消去循环转化成一维的向量处理，从而消去了一重循环。以消去了一重循环。以消去J J循环为例，可执行的循环为例，可执行的 FORTRANFORTRAN语言编写的程序为：语言编写的程序为： DO 10 I=0,7DO 10 I=0,7 C(I,J)=0 C(I,J)=0 DO 10 K=0,7 DO 10 K=0,7 10 C(I,J)=C(I,J)+A(I,K) 10 C(I,J)=C(I,J)+A(I,K)* *B(K,J)B(K

23、,J) 让让J=07J=07各部分同时在各部分同时在PEPE0 0PEPE7 7上运算，这上运算，这样只需样只需K K、J J二重循环，速度可提高至二重循环，速度可提高至8 8倍，即倍，即只需只需6464次乘、加的时间。次乘、加的时间。（164164页图页图6.56.5） 每次控制部件执行的每次控制部件执行的PEPE指令表面上是标量指令表面上是标量指令，实际上已等效于向量指令，是指令，实际上已等效于向量指令，是8 8个个PEPE并并行地执行同一条指令。每次播送时，利用阵列行地执行同一条指令。每次播送时，利用阵列处理机的播送功能将处理单元处理机的播送功能将处理单元PEPEK K中累加寄存中累加寄

24、存器器RAGRAGK K的内容经控制部件的内容经控制部件CUCU播送到全部播送到全部8 8个处个处理单元的理单元的RGARGA中去。中去。 为了让各个处理单元为了让各个处理单元PEPEi i尽可能只访问所带尽可能只访问所带局部存储器局部存储器PEMPEMi i，以保证高速处理，就必须要，以保证高速处理，就必须要求对矩阵求对矩阵A A、B B、C C各分量在局部存储器中的分各分量在局部存储器中的分布采用布采用165165页如图页如图6.66.6所示的方案。所示的方案。3 3、累加和、累加和 把向量存到所有处理单元的局部存储器中。把向量存到所有处理单元的局部存储器中。 将将N N个数的顺序相加转为

25、并行相加的问题。个数的顺序相加转为并行相加的问题。 取取N=8N=8，即有，即有8 8个数个数A(I)A(I)顺序累加，其中顺序累加，其中 0I70I7。 在在SISDSISD计算机上可以写成计算机上可以写成FORTRANFORTRAN程序：程序： C=0C=0 DO 10 I=0,7 DO 10 I=0,7 10 C=C+A(I) 10 C=C+A(I) 这是一个串行程序，需要这是一个串行程序，需要8 8次加法时间。次加法时间。 在阵列处理机上用成对递归相加算法，只需在阵列处理机上用成对递归相加算法，只需 次加法时间即可。首先，原始数据次加法时间即可。首先，原始数据A(I)A(I)分别存放在

26、分别存放在8 8个个PEMPEM的的 单元中，其中单元中，其中0I70I7，求累加和的步骤如下：，求累加和的步骤如下：（1 1）置全部）置全部PEPEi i为活跃状态，为活跃状态， 0I70I7；（2 2）全部）全部 A(I)A(I)从从PEMPEMi i的的 单元读到相应单元读到相应PEPEi i的累加寄存的累加寄存 器器RGARGAi i中，中， 0I70I7；（3 3）令）令K=0;K=0;（4 4）将全部）将全部PEPEi i的的(RGA(RGAi i) )转送到传送寄存器转送到传送寄存器RGRRGRi i, , 0I7 0I7；（5 5）将全部）将全部PEPEi i的的(RGR(RG

27、Ri i) )经过互连网络向右传送经过互连网络向右传送2 2K K步距步距, , 0I7 0I7；（6 6）令）令j=2j=2K K-1;-1;（7 7）置）置PEPE0 0PEPEj j为不活跃状态；为不活跃状态；3 38 8l lo og g2 2 （8 8）处于活跃状态的所有）处于活跃状态的所有PEPEi i执行执行(RGA(RGAi i) )：= = (RGA (RGAi i)+ (RGR)+ (RGRi i), ji7;), ji7;（9 9） K:=K+1;K:=K+1;（1010）如）如K3,K3n3时称超立方体网络。时称超立方体网络。 单级立方体网络的最大距离为单级立方体网络的

28、最大距离为n n。 2.PM2I2.PM2I单级网络单级网络 PM2IPM2I单级网络是加减单级网络是加减2 2i i单级网络的简称。单级网络的简称。能实现与能实现与j j号处理单元直接相连的是号为号处理单元直接相连的是号为j j2 2i i的的处理单元，即：处理单元，即： PM2PM2+i+i(j)=j+2(j)=j+2i i mod N mod NPM2PM2-i-i(j)=j-2(j)=j-2i i mod N mod N其中其中0 i n-10 i n-1， 0 j N-1 0 j N-1 n=logn=log2 2N ,NN ,N是结点数。它共有是结点数。它共有2n2n个互连函数。个

29、互连函数。PM2IPM2I网络的最大距离为网络的最大距离为 n/2 n/2 。由于由于PM2PM2+(n-1)+(n-1)= = PM2 PM2-(n-1),-(n-1),所以所以PM2IPM2I互连网络有互连网络有2n-12n-1种互连函数种互连函数是不同的。对于是不同的。对于N=8N=8的三维的三维PM2IPM2I互连网络的互连互连网络的互连函数，有函数，有PM2PM2+0+0、PM2PM2-0-0、PM2PM2+1+1、PM2PM2-1-1、PM2PM22 2等等5 5个不同的互连函数。部分互连函数分别为：个不同的互连函数。部分互连函数分别为： PM2PM2+0+0：(0 1 2 3 4

30、 5 6 7)(0 1 2 3 4 5 6 7) PM2 PM2+1+1：（：（0 2 4 60 2 4 6） （1 3 5 71 3 5 7） PM2PM22 2 ：（：（0 40 4）（）（1 51 5）（）（2 62 6）（）（3 73 7）0 01 12 23 34 45 56 67 7PM2PM2+0+0 PM2PM2+1+1 PM2PM22 20 01 12 23 34 45 56 67 70 01 12 23 34 45 56 67 7PM2IPM2I互连网络的部分连接图互连网络的部分连接图3.3.混洗交换单级网络混洗交换单级网络 混洗交换单级网络（混洗交换单级网络（Shuffl

31、e-ExchangeShuffle-Exchange） 包含两个互连函数，一个是全混（包含两个互连函数，一个是全混（PerfectShufflePerfectShuffle）, ,另一个是交换（另一个是交换（ExchangeExchange）。）。 这种互连网络由全混洗和交换两种互连函数组成：这种互连网络由全混洗和交换两种互连函数组成： 全混全混Shuffle(PShuffle(Pn-1n-1P Pn-2n-2.P.P1 1P P0 0)=(P)=(Pn-2n-2.P.P0 0P Pn-1n-1) ) 式中，式中， n=logn=log2 2N N。相当于将处理单元的进制地址。相当于将处理单元

32、的进制地址位中的最左位移到最右位的循环移位。由于全混洗互位中的最左位移到最右位的循环移位。由于全混洗互连网络不能实现全连网络不能实现全0 0和全和全1 1单元与其他单元的连接，因单元与其他单元的连接，因此引入交换网络中的此引入交换网络中的CubeCube0 0函数，两函数复合后为：函数，两函数复合后为： ExchangeShuffle(PExchangeShuffle(Pn-1n-1P Pn-2n-2.P.P1 1P P0 0)=)= (P (Pn-2n-2.P.P0 0PPn-1n-1) )01234567N=8N=8时全混交换互连网络连接图时全混交换互连网络连接图 在混洗交换网络中，最远的

33、两个在混洗交换网络中，最远的两个入、出端号是全入、出端号是全“0”0”和全和全“1”1”，它，它们的连接需要们的连接需要n n次交换和次交换和n-1n-1次混洗，次混洗，所以最大距离为所以最大距离为2n-12n-1。6.3.3 6.3.3 多级互连网络多级互连网络 将前面三种单级互连网络重复连接，就形成将前面三种单级互连网络重复连接，就形成了最基本的多级互连网络。即多级立方体互连网了最基本的多级互连网络。即多级立方体互连网络、多级混洗交换网络和多级络、多级混洗交换网络和多级PM2IPM2I网络。网络。 决定多级互连网络的特性的主要因素有以下决定多级互连网络的特性的主要因素有以下三个方面：三个方

34、面：交换开关、拓扑结构和控制方式交换开关、拓扑结构和控制方式。 交换开关是具有两个输入端和两个输出端的交换开关是具有两个输入端和两个输出端的交换单元。交换单元。交换开关有直连、交换、上播、下播交换开关有直连、交换、上播、下播四种功能四种功能；控制方式则有；控制方式则有级控制、单元控制、部级控制、单元控制、部分级控三种方式。分级控三种方式。（1 1）直连直连ii入入连连i i出出，j j入入连连j j出出；（2 2）交换交换ii入入连连j j出出，j j入入连连i i出出；（3 3）上播上播ii入入连连i i出出和和j j出出，j j入入悬空；悬空；（4 4）下播下播jj入入连连i i出出和和j

35、 j出出，i i入入悬空。悬空。级控制级控制同一级的所有开关只用一个控制信号同一级的所有开关只用一个控制信号 控制，同时只能处于同一种状态；控制，同时只能处于同一种状态；单元控制单元控制每一个开关都有自己独立的控制信每一个开关都有自己独立的控制信 号控制，可各自处于不同的状态；号控制，可各自处于不同的状态；部分级控制部分级控制第第i i级的所有开关分别用级的所有开关分别用i+1i+1个信个信 号控制，号控制，0 i n-10 i n-1，n n为级数。为级数。1.1.多级立方体网络多级立方体网络 通常是采用交换互连单级网络串接起来构成通常是采用交换互连单级网络串接起来构成的。的。采用三种不同的

36、控制方式，可以构成三种不采用三种不同的控制方式，可以构成三种不同的互连网络。同的互连网络。采用级控制可以构成采用级控制可以构成STARANSTARAN交换网。交换网。采用部分级控制，可以构成采用部分级控制，可以构成STARANSTARAN移数网。移数网。采用单元控制可以构成间接二进制采用单元控制可以构成间接二进制n n方体网。方体网。 STARANSTARAN多级互连网络就是多级互连网络就是CubeCube0 0,Cube,Cube1 1,Cube,Cube2 2三种互连函数的三个单级立方体网串接起来的。三种互连函数的三个单级立方体网串接起来的。在采用不同的级控制信号时，可以实现任一输入在采用

37、不同的级控制信号时，可以实现任一输入端到任一输出端的直接连接。端到任一输出端的直接连接。第第i i级（级（0 i 0 i n-1n-1）交换单元处于交换状态时，实现的是互）交换单元处于交换状态时，实现的是互连函数，且都采用二功能交换单元。连函数，且都采用二功能交换单元。 A AB BC CD DE EF FG GH HI IJ JK KL L0 01 12 23 34 45 56 67 70 01 12 23 34 45 56 67 7k = 0k = 0k = 1k = 1k = 2k = 2N=8N=8多级立方体互连网络多级立方体互连网络开关组合控制：开关组合控制： 级控制、部分级控制级控

38、制、部分级控制-STARANSTARAN网络网络( (交换、交换、移数功能移数功能) )； 单元控制单元控制-间接二进制间接二进制n n方体网络方体网络( (更复杂更复杂的功能的功能) )。（1 1）交换功能）交换功能 开关组合控制方式：开关组合控制方式：级控制。级控制。级控制信号（级控制信号（k k2 2k k1 1k k0 0）000000001001010010011011100100101101110110111111入入 端端0 00 01 12 23 34 45 56 67 71 11 10 03 32 25 54 47 76 62 22 23 30 01 16 67 74 45

39、53 33 32 21 10 07 76 65 54 44 44 45 56 67 70 01 12 23 35 55 54 47 76 61 10 03 32 26 66 67 74 45 52 23 30 01 17 77 76 65 54 43 32 21 10 0功功能能i iCubeCube0 0CubeCube1 1CubeCube0 0+ +CubeCube1 1CubeCube2 2CubeCube0 0+ +CubeCube2 2CubeCube1 1+ +CubeCube2 2CubeCube0 0+ +CubeCube1 1+ +CubeCube2 2分组交换功能：分组交

40、换功能：组间次序不变，组内元素镜像。组间次序不变，组内元素镜像。 CubeCube0 0-4 4组组2 2元交换；元交换；CubeCube1 1-2 2组组4 4元交换元交换+4+4组组2 2元交换；元交换； CubeCube2 2-1 1组组8 8元交换元交换+2+2组组4 4元交换。元交换。（2 2）移位功能）移位功能 开关组合控制方式：开关组合控制方式：部分级控制部分级控制( (第第i i级有级有i+1i+1种控种控制信号制信号) )2 2级级K,LK,L0 00 01 10 00 00 00 0J J0 01 11 10 00 00 00 0I I1 11 11 10 00 00 00

41、 01 1级级F,HF,H0 01 10 00 01 10 00 0E,GE,G1 11 10 01 11 10 00 00 0级级A,B,C,DA,B,C,D1 10 00 01 10 01 10 0功功 能能移移1 1Mod 8Mod 8移移2 2Mod 8Mod 8移移4 4Mod 8Mod 8移移1 1Mod 4Mod 4移移2 2Mod 4Mod 4移移1 1Mod 2Mod 2不移不移衡等衡等 ModMod的作用：的作用：不同不同ModMod可用于不同的分组操作。可用于不同的分组操作。（3 3）应用）应用 交换功能很适合于双向互连等要求的实现；交换功能很适合于双向互连等要求的实现；

42、 移数功能很适合于累加求和等要求的实现。移数功能很适合于累加求和等要求的实现。（4 4）带宽问题）带宽问题 STARANSTARAN可同时多对结点连接，尚不能同时可同时多对结点连接，尚不能同时任意组合。任意组合。（5 5）例题）例题 例例1 1：1616个个PEPE采用采用STARANSTARAN网络互连时，实现相网络互连时，实现相当于当于4 4组组4 4元交换，然后元交换，然后2 2组组8 8元交换，再元交换，再1 1组组1616元元交换功能。写出互连函数一般式、各级交换开关交换功能。写出互连函数一般式、各级交换开关状态。状态。答：答：因需实现交换功能，故选择因需实现交换功能，故选择STAR

43、ANSTARAN的交换功的交换功能能( (级控制方式）。级控制方式）。 4 4组组4 4元交换元交换 CubeCube0 0+Cube+Cube1 1 2 2组组8 8元交换元交换 CubeCube0 0+Cube+Cube1 1+Cube+Cube2 2 1 1组组1616元交换元交换 CubeCube0 0+Cube+Cube1 1+Cube+Cube2 2+Cube+Cube3 3 相加相加 CubeCube0 0+Cube+Cube1 1 +Cube+Cube3 3 各级开关状态：各级开关状态：k k3 3k k2 2k k1 1k k0 0=(1011)=(1011) 互连函数：互连

44、函数：f(bf(b3 3b b2 2b b1 1b b0 0)=(b)=(b3 3b b2 2b b1 1b b0 0) )例例2 2：编号编号0F0F的的PEPE间，要实现下列通信配对：间，要实现下列通信配对：(7,D),(6,C),(5,F),(4,E),(3,9),(2,8),(1,(7,D),(6,C),(5,F),(4,E),(3,9),(2,8),(1,B),(0,A)B),(0,A)。请画出互连网络结构图，写出控制。请画出互连网络结构图，写出控制方式及各开关状态。方式及各开关状态。答：答：因需实现双向交换功能，选择因需实现双向交换功能，选择STARANSTARAN网络网络的交换功

45、能的交换功能( (级控制方式级控制方式) )可满足要求。可满足要求。 网络拓扑结构：网络拓扑结构： 因共有因共有1616个结点，编码需要个结点，编码需要4 4位，所以开关共位，所以开关共4 4级。级。 0 0级级开关开关+(1)(1)，f(bf(b3 3b b2 2b b1 1b b0 0)=b)=b3 3b b2 2b b0 0b b1 1 1 1级级-开关开关+(2)(2)，f(bf(b3 3b b2 2b b0 0b b1 1)=b)=b3 3b b1 1b b0 0b b2 2 2 2级级-开关开关+， f(bf(b3 3b b1 1b b0 0b b2 2)=b)=b2 2b b1

46、1b b0 0b b3 3 3 3级级-开关开关+ +逆逆ShuffleShuffle，f(bf(b2 2b b1 1b b0 0b b3 3)=b)=b3 3b b2 2b b1 1b b0 00123456789ABCDEF级 k0 k1 k2 k30123456789ABCDEF配对要求：配对要求：(7,D),(6,C),(5,F),(4,E),(3,9),(2,8),(1,B),(7,D),(6,C),(5,F),(4,E),(3,9),(2,8),(1,B),(0,A)(0,A) 开关控制：开关控制：因因77的结点与的结点与7 7的结点配对，故的结点配对，故需需1 1组组1616元交

47、换元交换；因因0303的结点与的结点与8B8B的结点配对的结点配对, ,故需故需2 2组组8 8元交换元交换；因因0101的结点与的结点与ABAB的结点配对的结点配对, ,故需故需4 4组组4 4元交换元交换；因因0 0结点与结点与A A结点配对，故需结点配对，故需8 8组组2 2元交换元交换。 相加相加 CubeCube1 1+ Cube+ Cube3 3 1 1组组1616元交换元交换 CubeCube0 0+Cube+Cube1 1+Cube+Cube2 2+Cube+Cube3 3 2 2组组8 8元交换元交换 CubeCube0 0+Cube+Cube1 1+Cube+Cube2 2

48、 4 4组组4 4元交换元交换 CubeCube0 0+Cube+Cube1 1 8 8组组2 2元交换元交换 CubeCube0 0 各级开关状态：各级开关状态：k k3 3k k2 2k k1 1k k0 0=(1010)=(1010)2.2.多级混洗交换网络多级混洗交换网络（网络网络,即即OmegaOmega网络网络）ABCDEFGHIJKL012345672级级012345671级级0级级交换开关：交换开关：四功能；四功能；拓扑结构：拓扑结构：多级多级ShuffleShuffle；互连函数：互连函数：2 2级级-f(b-f(b2 2b b1 1b b0 0)=b)=b1 1b b0 0

49、b b2 2 1 1级级-f(b-f(b1 1b b0 0b b2 2)=b)=b0 0b b2 2b b1 1 0 0级级-f(b-f(b0 0b b2 2b b1 1)=b)=b2 2b b1 1b b0 0 开关组合控制：开关组合控制： 级控制、开关二功能级控制、开关二功能-STARANSTARAN交换网络的逆网络；交换网络的逆网络； 部分级控制、开关二功能部分级控制、开关二功能STARANSTARAN移数网络的逆网络；移数网络的逆网络； 单元控制、开关二、四功能单元控制、开关二、四功能-更强大的功能。更强大的功能。3.3.多级多级PM2IPM2I网络网络 N=8N=8的多级的多级PM2

50、IPM2I网络的结构网络的结构如如174174页图页图6.166.16所示。它包含所示。它包含n n级单元间连接，每一级都是把前级单元间连接，每一级都是把前后两列各后两列各N=2N=2n n个单元按个单元按PM2IPM2I拓扑相互连接起来。拓扑相互连接起来。从第从第i i级（级（0in-10in-1）来说，每一个单元）来说，每一个单元j j （0iN-10iN-1）都有）都有3 3根连接线分别通往出单元根连接线分别通往出单元j j、j+2j+2i i mod Nmod N和和j-2j-2i i mod Nmod N，在图中，它们分别用，在图中，它们分别用点线、实线和虚线表示。点线、实线和虚线表

51、示。 采用单元控制增强对各级单元控制的灵活采用单元控制增强对各级单元控制的灵活性，让每一单元都有自己独立的控制信号性，让每一单元都有自己独立的控制信号H H、D D、U U（平控（平控H H、下控、下控D D、上控、上控U U）。此种多级。此种多级PM2IPM2I网络网络称为强化数据变换网络称为强化数据变换网络AMDAMD（Augmented Data Augmented Data ManipulatorManipulator），但是控制线多，成本较高。），但是控制线多，成本较高。 ADM ADM的拓扑结构和控制方式使它可以完全模的拓扑结构和控制方式使它可以完全模仿仿omegaomega网络的

52、四功能交换单元。利用数据变换网络的四功能交换单元。利用数据变换网络可以实现各种灵活的移数、重复、间隔、展网络可以实现各种灵活的移数、重复、间隔、展开等变换函数。开等变换函数。 多级网络比较多级网络比较灵活性灵活性( (低低高高) )：STARANSTARAN、间接二进制、间接二进制n n方体、方体、 Omega()Omega()、ADM(ADM(混洗四功能混洗四功能) )成本成本( (低低高高) )：同上同上用途：用途： STARANSTARAN、Omega PEMOmega PEM 间接二进制间接二进制n n方体方体 PEPEPEPE功能：功能：只能实现同时只能实现同时部分多对多部分多对多功

53、能功能。4.4.全排列网络全排列网络定义：定义：所有入端、出端的连接均不发生冲突的所有入端、出端的连接均不发生冲突的网络，又称非阻塞型网络，即：网络，又称非阻塞型网络，即：N N入入NN出有出有N N！种排列。种排列。常规多级网络常规多级网络( (如如STARANSTARAN、等等) )属于阻塞型网属于阻塞型网络。络。证明：证明：对对n=log2Nn=log2N级网络，开关数级网络，开关数=N/2=N/2n n。排列数排列数N NN NN N/ /2 2N Nl lo og gN N) )l lo og g( (N N/ /2 2N NN N! !N NN N2 22 2N N/ /2 22

54、22 2全排列网络实现：全排列网络实现：思想：思想：N!N!N NN/2N/2N NN/2N/2N NN N。方法：方法：a.a.原有多级网络通过锁存器运行两次即原有多级网络通过锁存器运行两次即 可；可； b.b.两个两个log2Nlog2N网络背靠背串联。网络背靠背串联。 用多级网络也可以实现全排列网络。用多级网络也可以实现全排列网络。将将loglog2 2N N级的级的N N个入端和个入端和N N个出端的互连网络和它的个出端的互连网络和它的逆网络连在一起，省去中间完全重复的一级，就逆网络连在一起，省去中间完全重复的一级，就可以得到总级数为可以得到总级数为2log2log2 2N-1N-1级

55、的全排列网络。级的全排列网络。175175页图页图6.176.17就是以三维立方体多级网络和它的就是以三维立方体多级网络和它的逆网络连在一起，省去中间重复的一级后构成的逆网络连在一起，省去中间重复的一级后构成的全排列网络，称此网络为全排列网络，称此网络为BenesBenes网络网络。6.4 6.4 并行存储器的无冲突访问并行存储器的无冲突访问 在阵列处理机中，存储器频宽要与多个处理单元在阵列处理机中，存储器频宽要与多个处理单元的速率匹配，如何保证在各种访问模式下，存储器都的速率匹配，如何保证在各种访问模式下，存储器都能实现无冲突访问？能实现无冲突访问？ 为保证对存储器的并行无冲突访问，可采用的

56、方为保证对存储器的并行无冲突访问，可采用的方法有，法有，数据交叉存储在数据交叉存储在m m个存储体中，并且使存储体个存储体中，并且使存储体M M大于每次要访问的全部向量元素大于每次要访问的全部向量元素N N，且为质数。，且为质数。将数将数组按行或列变换成一维数组，形成一个一维线性地址组按行或列变换成一维数组，形成一个一维线性地址空间，地址用空间，地址用a a表示，然后，将地址表示，然后，将地址a a所对应的元素存所对应的元素存放在体号地址放在体号地址j=a mod mj=a mod m，体内地址，体内地址i= a/n i= a/n 的单元中，的单元中，就可以满足无冲突访问的要求。就可以满足无冲

57、突访问的要求。 无冲突访问技术无冲突访问技术 a30 a20 a10 a00 a31 a21 a11 a01 a32 a22 a12 a02 a33 a23 a13 a03 3 2 1 0 体体 3 体体 6 体体 5 体体 4 体体 3 体体 3 体体 2 体体 2 体体 2 体体 0 体体 0 体体 0 体体 1 体体 1 体体内内地地址址 体体内内地地址址 体体内内地地址址 (b) 错位存储错位存储 访存冲突及其避免方法访存冲突及其避免方法 (c) 44 二维数组在二维数组在 7 体交叉存储器中的存放体交叉存储器中的存放 (a) 直接按行存储直接按行存储 体体 0 2 1 0 3 2 1

58、 0 a31 a22 a13 a00 a32 a23 a10 a01 a33 a20 a11 a02 a30 a21 a12 a03 a32 a13 a00 a22 a03 a21 a02 a33 a20 a01 - a23 a10 a30 - a11 a31 a12 - 一、访问需求一、访问需求并行存取向量中各分量信息；并行存取向量中各分量信息；对矩阵可按行、列、对角线等方法访问对矩阵可按行、列、对角线等方法访问( (步长不一致步长不一致) )。二、存在问题二、存在问题存储器带宽限制存储器带宽限制存储器带宽达不到向量带宽；存储器带宽达不到向量带宽；访存方式访存方式( (步长步长) )不同，产

59、生访存冲突。不同，产生访存冲突。三、解决方法三、解决方法1 1、采用多体交叉存储器、采用多体交叉存储器 使存储体数超过使存储体数超过PEPE数，保证数，保证PEPE所需要的带宽。所需要的带宽。2 2、对向量分组操作、对向量分组操作 解决解决MEMMEM带宽小于向量长度问题，提高处理效率。带宽小于向量长度问题，提高处理效率。3 3、选择适当的存储体数、选择适当的存储体数m m 使存储体数使存储体数mPEmPE数，达到无冲突访问数，达到无冲突访问一维向量：一维向量： 顺序存放，防止步长与顺序存放，防止步长与m m成比例；成比例； m m取质数取质数( (与与PEPE数互质数互质) )，且与步长互质

60、。，且与步长互质。一维数组的并行递归算法一维数组的并行递归算法: :并行存储体数不能再取并行存储体数不能再取2 2的整数，而应该取成质数，当的整数，而应该取成质数，当变址跳距与分体数互质时，就可以进行无冲突访问。变址跳距与分体数互质时，就可以进行无冲突访问。多维向量：多维向量： 错位存放，满足行、列、对角线等访问要求；错位存放，满足行、列、对角线等访问要求；对矩阵而言对矩阵而言(m(m大于大于PEPE数时数时)-)-设设m=2m=22P2P+1+1，1=21=2P P，同一列不同行错开距离，同一列不同行错开距离 2=12=1， 同一行不同列错开距离同一行不同列错开距离对对AabAab，体号：体