vchap6阵列处理机(2)(1).ppt

《vchap6阵列处理机(2)(1).ppt》由会员分享，可在线阅读，更多相关《vchap6阵列处理机(2)(1).ppt（24页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第六章第六章 阵列处理机阵列处理机(并行处理机并行处理机)互连网络互连网络要求：要求：1、熟练掌握立方体、熟练掌握立方体、PN2I、混洗交换三种基混洗交换三种基本的单级网络的互连函数表示、掌握立方体、本的单级网络的互连函数表示、掌握立方体、Omega多级互连网络的交换单元功能，拓扑结多级互连网络的交换单元功能，拓扑结构、及所用的开关控制方式构、及所用的开关控制方式2、熟练掌握熟练掌握8或或16个入端和出端的多级立方体个入端和出端的多级立方体多级混洗交换网络的画法多级混洗交换网络的画法1、SIMD系统的互连网络的设计目标系统的互连网络的设计目标（P234）2、互连网络的组成互连网络的组成3、互连

2、函数的定义（、互连函数的定义（P235）4、单级单级立方体、立方体、PN2I、Omega多级互多级互连网络及其函数表达式连网络及其函数表达式（P235-236）互连网络互连网络是将集中式系统或分布式系统中的结点连是将集中式系统或分布式系统中的结点连接起来所构成的网络。接起来所构成的网络。在拓扑上，互连网络为输入和输出两组在拓扑上，互连网络为输入和输出两组结点之间提供一组互连或映象。结点之间提供一组互连或映象。互连网络互连网络的一般模型是有的一般模型是有N个输入端个输入端和和N个输出端个输出端的封的封闭装置，通过其内部在入端、出端之间构造的多条路径闭装置，通过其内部在入端、出端之间构造的多条路径

3、实现数据按某种算法的传播。入端和出端所连可以是实现数据按某种算法的传播。入端和出端所连可以是N个处理单元或其它并行处理设备，统称为个处理单元或其它并行处理设备，统称为“结点结点”。互连网络与处理单元的连接模型如下图所示。互连网络与处理单元的连接模型如下图所示。互连函数互连函数 如果把互连网络的N个入端和N个出端各自用整数0，1，N-1代表，则互连函数表示互连的出端号和入端号的一一对应关系。在互连函数中，在互连函数中，记记:我们总是记我们总是记NN结点数，结点数，n=logn=log2 2N N 维数，维数，j=Xj=Xn-1n-1XX0 0结点编号的二进制形式，位数为结点编号的二进制形式，位数

4、为n n。由于这些开关的触点是可动的，所以由于这些开关的触点是可动的，所以一个互连网络的一个互连网络的输入输入/输出对应关系有多种，也就是有多个互连函数，我们输出对应关系有多种，也就是有多个互连函数，我们把它们合称为把它们合称为“互连函数族互连函数族”。一般而言，互连函数的复合一般而言，互连函数的复合连接作用必须使网络中所有结点互相可达，即构成一个连通连接作用必须使网络中所有结点互相可达，即构成一个连通图。图。6.2.1 互连网络的性能参数1.互连网络的拓扑结构 (1)静态网络 由点和点直接相连而成，这种连接方式在由点和点直接相连而成，这种连接方式在 程序执行过程中不会改变。程序执行过程中不会

5、改变。(2)动态网络 用开关通道实现，可动态地改变结构，用开关通道实现，可动态地改变结构，使其与用户程序中通信要求匹配。使其与用户程序中通信要求匹配。2.性能参数 (1)网络规模：结点数结点数 (2)结点度：与结点相连接的边的数目与结点相连接的边的数目。入度：入度：进入结点的通道数进入结点的通道数 出度：出度：从结点出来的通道数从结点出来的通道数 (3)网络直径 网络中任意两个结点间最短路径长度的最大值网络中任意两个结点间最短路径长度的最大值。(4)路由 在网络通信中对路径的选择与指定。在网络通信中对路径的选择与指定。6.2.2 三种基本的单级网络三种基本的单级网络立方体立方体PM2I混洗交换

6、混洗交换 立方体函数定义：立方体函数定义：CubeCubei i的功能的功能是对入端结点编号二是对入端结点编号二进制形式的第进制形式的第i i位取反位取反，即，即 CubeCubei i(X(Xn-1n-1X Xi+1i+1X Xi iX Xi-1i-1X X0 0)=X)=Xn-1n-1X Xi+1i+1X Xi iX Xi-1i-1X X0 0，其中其中0in-1in-1。例如：例如：CubeCube0 0(0)=1(0)=1，CubeCube3 3(7)=15(7)=15。1.单级单级立方体立方体三维二进制立方体网络 n=3n=3的混洗函数开关状态如下图所示，其连接规的混洗函数开关状态如

7、下图所示，其连接规律是把全部入端结点按编号从当中分成数目相等的前后两半，律是把全部入端结点按编号从当中分成数目相等的前后两半，前一半与后一半在连到出端结点时正好一一隔开，就像人们前一半与后一半在连到出端结点时正好一一隔开，就像人们在洗扑克牌时，把整副牌分成两半后相互对插一样。在洗扑克牌时，把整副牌分成两半后相互对插一样。“混洗混洗”（shuffle）这个名词由此而来。这个名词由此而来。2.2.单级混洗单级混洗交换网络交换网络该网络由混洗函数（该网络由混洗函数（shuffle）与交换函数（与交换函数（exchange即即CubeCube0 0）定义，定义，混洗函数性质混洗函数性质1：当把结点编号

8、写成二进制形式时，：当把结点编号写成二进制形式时，混洗函数满足混洗函数满足 shuffle(b(bn-1n-1b bn-2n-2b b0 0)=b=bn-2n-2b b0 0b bn-1n-1 对对n=2n=2k k个对象均匀混洗，可用个对象均匀混洗，可用k k位二进制数位二进制数 x=(xx=(xk-1k-1,x,x1 1,x,x0 0)表示定义域中的每个对象表示定义域中的每个对象均匀混洗将均匀混洗将x x映射到映射到f(x)f(x)，得到：得到：f(x)=(xf(x)=(xk-2k-2,x,x1 1,x,x0,0,x xk-1k-1)也就是说每混洗运算一次，结点编号的二进制形式也就是说每混

9、洗运算一次，结点编号的二进制形式就循环左移一位。就循环左移一位。均匀混洗 n=8（对象个数）的均匀混洗所对应的映射与其逆过程 3.3.单级单级PM2IPM2I网络（又称加减网络（又称加减2 2i i网络）网络）该网络由该网络由PM2IPM2I函数定义，函数定义，PM2IPM2I函数共有函数共有n n对成员，分别是对成员，分别是PM2PM2 0 0，PM2PM2 1 1，PM2PM2(n-1)(n-1)。PM2IPM2I函数定义：函数定义：PM2PM2ii的功能是对入端结点编号加的功能是对入端结点编号加或减或减2 2i i，然后再作模然后再作模N N运算运算 PM2PM2+i+i（j j）=j+

10、2=j+2i imod Nmod N PM2 PM2-i-i（j j）=j-2=j-2i imod Nmod N 其中其中j=0 j=0 N-1N-1，i=0 i=0 n-1n-1。例如：当例如：当N=8N=8时，时，PM2PM2+0+0（0 0）=0+2=0+20 0=1=1，PM2PM2+0+0（1)=1+21)=1+20 0=2=2，PM2PM2+0+0（7 7）=7+2=7+20 0=0=0，PM2PM2+1+1（0)=0+20)=0+21 1=2=2。多级网络 多级网络可用于构造大型多处理机系统。通用多级网络通用多级网络 各种多级网络的区别就在于所用开关模各种多级网络的区别就在于所用

11、开关模 块和级间连接模式的不同。块和级间连接模式的不同。多级互连网络多级互连网络定义：多级定义：多级ICN使用多级开关，使得数据在使用多级开关，使得数据在一次通过网络的过程中可以实现的置换种类更多。一次通过网络的过程中可以实现的置换种类更多。通常在通常在N N个结点的网络中，多级个结点的网络中，多级ICN由由n级构成级构成（n=logn=log2 2N N）。经典的多级互连网有多级立方体网、多级混洗经典的多级互连网有多级立方体网、多级混洗交换网和交换网和多级多级PM2IPM2I网。网。多级立方体网和多级混洗多级立方体网和多级混洗交换网不使用单级互交换网不使用单级互连网中的那种多路选择开关，而是

12、用一种连网中的那种多路选择开关，而是用一种2 2输入输入/2/2输出的二输出的二元交换开关，以减少开关总数。二元交换开关的基本接通元交换开关，以减少开关总数。二元交换开关的基本接通状态有状态有“直连直连”、“交换交换”、“上播上播”和和“下播下播”，在进，在进行数据置换时只能使用前行数据置换时只能使用前2种。种。多级互连网络（多级互连网络（P238）（1）交换开关：二功能交换单元和四功能交换单元。交换开关：二功能交换单元和四功能交换单元。（2）多级立方体网络（）多级立方体网络（P239）它们的共同特点：第它们的共同特点：第i级交换单元处于交换状态时，实级交换单元处于交换状态时，实现的是现的是C

13、ubei互连函数，且都是采用二功能交换单元。互连函数，且都是采用二功能交换单元。画法：先由画法：先由n=log2N,求得该多级网络的级数求得该多级网络的级数n;每级画上每级画上N/2个两功能交换开关，级编号从输入到输出依次定为个两功能交换开关，级编号从输入到输出依次定为0，1，,I,n-1;让所有第让所有第I级各交换开关的两个入级各交换开关的两个入/出端均按出端均按cubei的关系配对编上号；再将各级开关同一编号的端用线的关系配对编上号；再将各级开关同一编号的端用线连上。按此方法，三级立方体网络的画法如下：连上。按此方法，三级立方体网络的画法如下：8个处理单元的多级立方体网络结构见个处理单元的

14、多级立方体网络结构见P239图图6。14 由由abab开关模块和级间构成的通用多级互连网络结构开关模块和级间构成的通用多级互连网络结构(3)多级混洗交换网络（多级混洗交换网络（Omega网络）（网络）（P241）特点：交换开关：四功能交换单元，拓扑结构为混洗，特点：交换开关：四功能交换单元，拓扑结构为混洗，控制方式为单元控制。控制方式为单元控制。具有具有N个入端和个入端和N个出端的个出端的Omega网络的画法是：用网络的画法是：用n个个（n=log2N)相同的单级网络串联组成：每一级都是相同的单级网络串联组成：每一级都是N个端个端的混洗拓扑之后再加一级四功能交换开关；每一级用的混洗拓扑之后再加

15、一级四功能交换开关；每一级用N/2个交换单元。级编号从输入到输出依次为个交换单元。级编号从输入到输出依次为n-1,n-2,i,1,0。混洗拓扑就是将编号为混洗拓扑就是将编号为0，1，。，。，N-1的入的入端分成前后相等的两半，前一半和后一半在连至输出时顺端分成前后相等的两半，前一半和后一半在连至输出时顺次一一相隔。等各级全部画好后，再将连线沿途所经过的次一一相隔。等各级全部画好后，再将连线沿途所经过的端子均标成同一端号即可。端子均标成同一端号即可。按此思路，八个端子的三级混洗交换网络可以见下图按此思路，八个端子的三级混洗交换网络可以见下图 多级混洗多级混洗交换网络结构交换网络结构(又称为又称为OmegaOmega网网)：它由它由n级构成，每一级包含一个无条件混洗拓扑线路和一列级构成，每一级包含一个无条件混洗拓扑线路和一列可控的二元交换开关，前后重复，便于制造。如下图中实可控的二元交换开关，前后重复，便于制造。如下图中实线所示。线所示。一个1616 Omega网络