阵列处理机幻灯片.ppt

阵列处理机第1页，共68页，编辑于2022年，星期三本章重点：本章重点：总的要求是理解阵列处理机的结构和工作原总的要求是理解阵列处理机的结构和工作原理。了解与流水处理机的差别。理解在阵列处理理。了解与流水处理机的差别。理解在阵列处理机解题时对并行算法及存储单元分配规则、互连机解题时对并行算法及存储单元分配规则、互连网络等的特殊要求。熟练掌握基本的单级网络及网络等的特殊要求。熟练掌握基本的单级网络及其互连函数表示。理解循环互连网络的实现。熟其互连函数表示。理解循环互连网络的实现。熟练掌握多级网络、全排列网络的画法。理解解决练掌握多级网络、全排列网络的画法。理解解决并行存储器无冲突访问的办法。并行存储器无冲突访问的办法。互连函数和多级互连网络。互连函数和多级互连网络。本章难点：本章难点：并行算法和多级互连网络。并行算法和多级互连网络。第2页，共68页，编辑于2022年，星期三6.1 6.1 阵列处理机原理阵列处理机原理6.1.1 6.1.1 阵列处理机的基本构形阵列处理机的基本构形 阵列处理机阵列处理机(Array Processor),(Array Processor),也称为并行也称为并行处理机处理机(Parallel Processor)(Parallel Processor)主要用于对大量主要用于对大量向量、数组要求高速运算的场合。向量、数组要求高速运算的场合。阵列处理机是重复设置处理单元按一定方阵列处理机是重复设置处理单元按一定方式连成阵列在单一控制部件控制下对各自分配式连成阵列在单一控制部件控制下对各自分配的数据执行同一指令规定的操作，是操作级并的数据执行同一指令规定的操作，是操作级并行的行的SIMDSIMD的计算机。的计算机。由于存储器的组成方式不同，阵列处理机由于存储器的组成方式不同，阵列处理机有两种不同的基本构形。有两种不同的基本构形。第3页，共68页，编辑于2022年，星期三 1 1、分布式存储器的阵列处理机构形、分布式存储器的阵列处理机构形各各处理单元有局部存储器处理单元有局部存储器PEM(Processing PEM(Processing Element Memory)Element Memory)存放被分布的数据，只能被存放被分布的数据，只能被本处理单元直接访问。在控制部件本处理单元直接访问。在控制部件CUCU上有一主上有一主存可传播给各个处理单元，运算中可通过互连存可传播给各个处理单元，运算中可通过互连网络网络ICNICN交换数据。交换数据。在执行主存中的用户程序时，所有指令都在执行主存中的用户程序时，所有指令都在控制部件中进行译码，把只适合串行处理的在控制部件中进行译码，把只适合串行处理的标量或控制类指令留给控制部件标量或控制类指令留给控制部件CUCU自己执行，自己执行，而把适合于并行处理的向量类指令而把适合于并行处理的向量类指令“播送播送”给给各个各个PEPE，控制处于，控制处于“活跃活跃”的那些的那些PEPE并行执行。并行执行。下图是采用分布式存储器的阵列处理机构形。下图是采用分布式存储器的阵列处理机构形。第4页，共68页，编辑于2022年，星期三PEM0ICN互连网络互连网络PE0CUCUMPEM1PE1PEMN-1PEN-1I/O接口接口SCD控制控制数据总线数据总线控制总线控制总线控控制制具有分布式存储器的阵列处理机构形具有分布式存储器的阵列处理机构形 第5页，共68页，编辑于2022年，星期三 为了有效高速地处理向量数据，这种构形要为了有效高速地处理向量数据，这种构形要求能把数据合理地预分配到各个处理单元的局求能把数据合理地预分配到各个处理单元的局部存储器中，使各处理单元部存储器中，使各处理单元PEPEi i主要用自己的局主要用自己的局存存PEMPEMi i中的数据运算。中的数据运算。采用这种构形的阵列处理机是采用这种构形的阵列处理机是SIMDSIMD的主流。的主流。典型机器有典型机器有ILLIAC ILLIAC 、MPPMPP、DAPDAP、CM-2CM-2、MP-1MP-1、DAP600DAP600系列等。系列等。2 2、集中式共享存储器的阵列处理机构形、集中式共享存储器的阵列处理机构形 系统存储器由系统存储器由K K个存储体集中组成，并经个存储体集中组成，并经ICNICN为全部为全部N N个处理单元所共享。个处理单元所共享。为使各处理单元对长度为为使各处理单元对长度为N N的向量中各个元的向量中各个元素都能同时并行处理，存储体体数素都能同时并行处理，存储体体数K K应等于或多应等于或多于处理单元数于处理单元数N N。第6页，共68页，编辑于2022年，星期三PEPE0 0ICNICN互连网络互连网络CUCUPEPE1 1PEPEN-1N-1I/O-CHI/O-CHMMMM0 0MMMM1 1MMMMk-1k-1 SC SC I/O I/OSMSM具有集中式共享存储器的阵列处理机构形具有集中式共享存储器的阵列处理机构形 第7页，共68页，编辑于2022年，星期三 各处理单元在访主存时，为避免发生分体冲突，各处理单元在访主存时，为避免发生分体冲突，也要求有合适的算法能将数据合理地分配到各个也要求有合适的算法能将数据合理地分配到各个存储体中。存储体中。互连网络互连网络ICNICN是用于在处理单元与存储器分体是用于在处理单元与存储器分体之间进行转接构成数据通路，使各处理单元能高之间进行转接构成数据通路，使各处理单元能高速灵活地动态与不同的存储体相连，使尽可能多速灵活地动态与不同的存储体相连，使尽可能多的的PEPE能无冲突地访问共享的主存模块。能无冲突地访问共享的主存模块。集中式共享存储器的阵列处理机主要特点是集中式共享存储器的阵列处理机主要特点是将资源重复和时间重复结合起来开发并行性。将资源重复和时间重复结合起来开发并行性。采用这种构形的典型机器有采用这种构形的典型机器有BSPBSP。第8页，共68页，编辑于2022年，星期三6.1.2 6.1.2 阵列处理机的特点阵列处理机的特点1 1、利用资源重复而不是时间重叠；利用并行性中的同、利用资源重复而不是时间重叠；利用并行性中的同 时性而不是并发性。时性而不是并发性。2 2、资源利用率不如流水线高，但提高速度的潜资源利用率不如流水线高，但提高速度的潜力比流水线处理机大。力比流水线处理机大。（阵列处理机主要是（阵列处理机主要是靠增大处理单元数提高速度，向量流水处理靠增大处理单元数提高速度，向量流水处理机主要靠缩短时钟周期提高速度）。机主要靠缩短时钟周期提高速度）。3 3、阵列处理机阵列处理机使用简单规整的互连网络来确定处使用简单规整的互连网络来确定处 理单元间的连接，因此，互连网络设计很重要。理单元间的连接，因此，互连网络设计很重要。4 4、它是以某类算法为背景的专用计算机，基本上、它是以某类算法为背景的专用计算机，基本上 是专用于向量处理的计算机是专用于向量处理的计算机(某类算法专用机某类算法专用机)，故阵列处理机专用性强。故阵列处理机专用性强。第9页，共68页，编辑于2022年，星期三5 5、阵列机的研究必须与并行算法研究密切结合，阵列机的研究必须与并行算法研究密切结合，以使它的求解算法适应性更强一些，应用面以使它的求解算法适应性更强一些，应用面更广一些更广一些(与并行算法结合研究与并行算法结合研究)。阵列处理机实质阵列处理机实质上是由专门对付数组上是由专门对付数组运算的处理单元阵列组成的运算的处理单元阵列组成的处理机处理机、专门从、专门从事处理单元阵列的控制及标量处理的事处理单元阵列的控制及标量处理的处理机处理机和专门从事系统输入输出及操作系统管理和专门从事系统输入输出及操作系统管理的的处理机处理机组成的一个异构型多处理机系统。组成的一个异构型多处理机系统。第10页，共68页，编辑于2022年，星期三6.2 6.2 阵列处理机的并行算法阵列处理机的并行算法6.2.1 ILLIAC 6.2.1 ILLIAC 的处理单元阵列结构的处理单元阵列结构 ILLIAC IVILLIAC 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连成一个环，左右连成一个环，左右方向上构成一个闭合螺线。方向上构成一个闭合螺线。第11页，共68页，编辑于2022年，星期三第12页，共68页，编辑于2022年，星期三采用闭合螺线最短距离不超过采用闭合螺线最短距离不超过7 7步。而普通网格步。而普通网格最短距离不超过最短距离不超过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或或 （等于（等于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 PU3636第13页，共68页，编辑于2022年，星期三普通网格必须普通网格必须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 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或或 第14页，共68页，编辑于2022年，星期三P P180180习题习题6.16.1 解解 如图：如图：第15页，共68页，编辑于2022年，星期三 与与PU0PU0相连的处理单元有：相连的处理单元有：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、PU12PU12、PU15PU15。PE0PE0至少需经二步才能将信息传送至至少需经二步才能将信息传送至PU2PU2、PU3PU3、PU5PU5、PU8PU8、PU11PU11、PU13PU13、PU14PU14。PE0PE0至少需经三步步才能将信息传送至至少需经三步步才能将信息传送至PU6PU6、PU7PU7、PU9PU9、PU10PU10。第16页，共68页，编辑于2022年，星期三6.2.2 6.2.2 阵列处理机的并行算法举例阵列处理机的并行算法举例1 1、矩阵加、矩阵加 把把C=A+BC=A+B中的属于同一位置向量元素放在同一局部中的属于同一位置向量元素放在同一局部存储器中。存储器中。两个两个8 8 8 8的矩阵的矩阵A A、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,0C(0,0)B(0,0B(0,0)A(0,0A(0,0)PEMPEM0 0PEMPEM6363PEMPEM1 1矩阵相加的存储器分配举例矩阵相加的存储器分配举例第17页，共68页，编辑于2022年，星期三2 2、矩阵乘、矩阵乘 把把C=A*BC=A*B的各向量按列存放在一个局部存储器中。的各向量按列存放在一个局部存储器中。设设A A、B B和和C C为为3 3个个8 8 88的二维矩阵，给定的二维矩阵，给定A A和和B B，计算，计算C=A*BC=A*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)=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)*B(K,J)10 C(I,J)=C(I,J)+A(I,K)*B(K,J)第18页，共68页，编辑于2022年，星期三 需经需经I I、J J、K K三重循环完成。每重循环执行三重循环完成。每重循环执行8 8次，共需次，共需512512次相乘、加得时间，且每次还要包次相乘、加得时间，且每次还要包括执行循环控制判别等其它操作所需得时间。括执行循环控制判别等其它操作所需得时间。如果在如果在SIMDSIMD阵列机上运算，可用阵列机上运算，可用8 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)*B(K,J)10 C(I,J)=C(I,J)+A(I,K)*B(K,J)第19页，共68页，编辑于2022年，星期三 让让J=07J=07各部分同时在各部分同时在PEPE0 0PEPE7 7上运算，这上运算，这样只需样只需K K、J J二重循环，速度可提高至二重循环，速度可提高至8 8倍，即倍，即只需只需6464次乘、加的时间。次乘、加的时间。（164164页图页图6.56.5）每次控制部件执行的每次控制部件执行的PEPE指令表面上是标量指令表面上是标量指令，实际上已等效于向量指令，是指令，实际上已等效于向量指令，是8 8个个PEPE并并行地执行同一条指令。每次播送时，利用阵列行地执行同一条指令。每次播送时，利用阵列处理机的播送功能将处理单元处理机的播送功能将处理单元PEPEK K中累加寄存器中累加寄存器RAGRAGK K的内容经控制部件的内容经控制部件CUCU播送到全部播送到全部8 8个处理单个处理单元的元的RGARGA中去。中去。为了让各个处理单元为了让各个处理单元PEPEi i尽可能只访问所带尽可能只访问所带局部存储器局部存储器PEMPEMi i，以保证高速处理，就必须要，以保证高速处理，就必须要求对矩阵求对矩阵A A、B B、C C各分量在局部存储器中的分各分量在局部存储器中的分布采用布采用165165页如图页如图6.66.6所示的方案。所示的方案。第20页，共68页，编辑于2022年，星期三3 3、累加和、累加和 把向量存到所有处理单元的局部存储器中。把向量存到所有处理单元的局部存储器中。将将N N个数的顺序相加转为并行相加的问题。个数的顺序相加转为并行相加的问题。取取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次加法时间。次加法时间。第21页，共68页，编辑于2022年，星期三在阵列处理机上用成对递归相加算法，只需在阵列处理机上用成对递归相加算法，只需 次加法时间即可。首先，原始数据次加法时间即可。首先，原始数据A(I)A(I)分别存放在分别存放在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(RGRi i)经过互连网络向右传送经过互连网络向右传送2 2K K步距步距,0I7 0I7；（6 6）令）令j=2j=2K K-1;-1;（7 7）置）置PEPE0 0PEPEj j为不活跃状态；为不活跃状态；第22页，共68页，编辑于2022年，星期三（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时称超立方体网络。时称超立方体网络。单级立方体网络的最大距离为单级立方体网络的最大距离为n n。2.PM2I2.PM2I单级网络单级网络 PM2IPM2I单级网络是加减单级网络是加减2 2i i单级网络的简称。单级网络的简称。能实现与能实现与j j号处理单元直接相连的是号为号处理单元直接相连的是号为j2j2i i的的处理单元，即：处理单元，即：第32页，共68页，编辑于2022年，星期三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 n=log0 j N-1 n=log2 2N N,N,N是结点数。它共有是结点数。它共有2n2n个互连函数。个互连函数。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、PM2PM222等等5 5个不同的互连函数。部分互连函数分别为：个不同的互连函数。部分互连函数分别为：PM2PM2+0+0：(0 1 2 3 4 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）第33页，共68页，编辑于2022年，星期三0 01 12 23 34 45 56 67 7PM2PM2+0+0 PM2PM2+1+1 PM2PM2220 01 12 23 34 45 56 67 70 01 12 23 34 45 56 67 7PM2IPM2I互连网络的部分连接图互连网络的部分连接图第34页，共68页，编辑于2022年，星期三3.3.混洗交换单级网络混洗交换单级网络 混洗交换单级网络（混洗交换单级网络（Shuffle-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。相当于将处理单元的进制地址位中的最。相当于将处理单元的进制地址位中的最左位移到最右位的循环移位。由于全混洗互连网络不能实现全左位移到最右位的循环移位。由于全混洗互连网络不能实现全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)第35页，共68页，编辑于2022年，星期三01234567N=8N=8时全混交换互连网络连接图时全混交换互连网络连接图 在混洗交换网络中，最远的两个入、在混洗交换网络中，最远的两个入、出端号是全出端号是全“0”0”和全和全“1”1”，它们的连接，它们的连接需要需要n n次交换和次交换和n-1n-1次混洗，次混洗，所以最大距离所以最大距离为为2n-12n-1。第36页，共68页，编辑于2022年，星期三6.3.3 6.3.3 多级互连网络多级互连网络将前面三种单级互连网络重复连接，就形成将前面三种单级互连网络重复连接，就形成了最基本的多级互连网络。即多级立方体互连网了最基本的多级互连网络。即多级立方体互连网络、多级混洗交换网络和多级络、多级混洗交换网络和多级PM2IPM2I网络。网络。决定多级互连网络的特性的主要因素有以下决定多级互连网络的特性的主要因素有以下三个方面：三个方面：交换开关、拓扑结构和控制方式交换开关、拓扑结构和控制方式。交换开关是具有两个输入端和两个输出端的交换开关是具有两个输入端和两个输出端的交换单元。交换单元。交换开关有直连、交换、上播、下播交换开关有直连、交换、上播、下播四种功能四种功能；控制方式则有；控制方式则有级控制、单元控制、部级控制、单元控制、部分级控三种方式。分级控三种方式。第37页，共68页，编辑于2022年，星期三（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 j出出，i i入入悬空。悬空。级控制级控制同一级的所有开关只用一个控制信号同一级的所有开关只用一个控制信号 控制，同时只能处于同一种状态；控制，同时只能处于同一种状态；单元控制单元控制每一个开关都有自己独立的控制信每一个开关都有自己独立的控制信 号控制，可各自处于不同的状态；号控制，可各自处于不同的状态；部分级控制部分级控制第第i i级的所有开关分别用级的所有开关分别用i+1i+1个信个信 号控制，号控制，0 i n-10 i n-1，n n为级数。为级数。第38页，共68页，编辑于2022年，星期三1.1.多级立方体网络多级立方体网络 通常是采用交换互连单级网络串接起来构成通常是采用交换互连单级网络串接起来构成的。的。采用三种不同的控制方式，可以构成三种不采用三种不同的控制方式，可以构成三种不同的互连网络。同的互连网络。采用级控制可以构成采用级控制可以构成STARANSTARAN交换网。交换网。采用部分级控制，可以构成采用部分级控制，可以构成STARANSTARAN移数网。移数网。采用单元控制可以构成间接二进制采用单元控制可以构成间接二进制n n方体网。方体网。STARANSTARAN多级互连网络就是多级互连网络就是CubeCube0 0,Cube,Cube1 1,Cube,Cube2 2三种互连函数的三个单级立方体网串接起来的。三种互连函数的三个单级立方体网串接起来的。在采用不同的级控制信号时，可以实现任一输入在采用不同的级控制信号时，可以实现任一输入端到任一输出端的直接连接。端到任一输出端的直接连接。第第i i级（级（0 i 0 i n-1n-1）交换单元处于交换状态时，实现的是互）交换单元处于交换状态时，实现的是互连函数，且都采用二功能交换单元。连函数，且都采用二功能交换单元。第39页，共68页，编辑于2022年，星期三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多级立方体互连网络多级立方体互连网络第40页，共68页，编辑于2022年，星期三开关组合控制：开关组合控制：级控制、部分级控制级控制、部分级控制-STARANSTARAN网络网络(交换、交换、移数功能移数功能)；单元控制单元控制-间接二进制间接二进制n n方体网络方体网络(更复杂更复杂的功能的功能)。（1 1）交换功能）交换功能 开关组合控制方式：开关组合控制方式：级控制。级控制。第41页，共68页，编辑于2022年，星期三级控制信号（级控制信号（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 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分组交换功能：分组交换功能：组间次序不变，组内元素镜像。组间次序不变，组内元素镜像。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元交换。元交换。第42页，共68页，编辑于2022年，星期三（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 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可用于不同的分组操作。可用于不同的分组操作。第43页，共68页，编辑于2022年，星期三（3 3）应用）应用 交换功能很适合于双向互连等要求的实现；交换功能很适合于双向互连等要求的实现；移数功能很适合于累加求和等要求的实现。移数功能很适合于累加求和等要求的实现。（4 4）带宽问题）带宽问题 STARANSTARAN可同时多对结点连接，尚不能同时任可同时多对结点连接，尚不能同时任意组合。意组合。（5 5）例题）例题 例例1 1：1616个个PEPE采用采用STARANSTARAN网络互连时，实现相网络互连时，实现相当于当于4 4组组4 4元交换，然后元交换，然后2 2组组8 8元交换，再元交换，再1 1组组1616元元交换功能。写出互连函数一般式、各级交换开关交换功能。写出互连函数一般式、各级交换开关状态。状态。第44页，共68页，编辑于2022年，星期三答：答：因需实现交换功能，故选择因需实现交换功能，故选择STARANSTARAN的交换功的交换功能能(级控制方式）。级控制方式）。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)互连函数：互连函数：f(bf(b3 3b b2 2b b1 1b b0 0)=(b)=(b3 3b b2 2b b1 1b b0 0)第45页，共68页，编辑于2022年，星期三例例2 2：编号编号0F0F的的PEPE间，要实现下列通信配对：间，要实现下列通信配对：(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)。请画出互连网络结构图，写出控制。请画出互连网络结构图，写出控制方式及各开关状态。方式及各开关状态。答：答：因需实现双向交换功能，选择因需实现双向交换功能，选择STARANSTARAN网络的交网络的交换功能换功能(级控制方式级控制方式)可满足要求。可满足要求。网络拓扑结构：网络拓扑结构：因共有因共有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 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 0第46页，共68页，编辑于2022年，星期三0123456789ABCDEF级 k0 k1 k2 k30123456789ABCDEF配对要求：配对要求：(7,D),(6,C),(5,F),(4,E),(3,9),(2,8),(1,B),(0,A)(7,D),(6,C),(5,F),(4,E),(3,9),(2,8),(1,B),(0,A)开关控制：开关控制：因因7 7的结点与的结点与7 7的结点配对，故需的结点配对，故需1 1组组1616元交换元交换；第47页，共68页，编辑于2022年，星期三因因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 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)第48页，共68页，编辑于2022年，星期三2.2.多级混洗交换网络多级混洗交换网络（网络网络,即即OmegaOmega网络网络）ABCDEFGHIJKL012345672级级012345671级级0级级交换开关：交换开关：四功能；四功能；拓扑结构：拓扑结构：多级多级ShuffleShuffle；互连函数：互连函数：2 2级级-f(b-f(b2 2b b1 1b b0 0)=b)=b1 1b b0 0b 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移数网络的逆网络；移数网络的逆网络；单元控制、开关二、四功能单元控制、开关二、四功能-更强大的功能。更强大的功能。第49页，共68页，编辑于2022年，星期三3.3.多级多级PM2IPM2I网络网络 N=8N=8的多级的多级PM2IPM2I网络的结构网络的结构如如174174页图页图6.166.16所示。它包含所示。它包含n n级单元间连接，每一级都是把前级单元间连接，每一级都是把前后