vchap6阵列处理机.ppt

* 第六章 阵列处理机 (并行处理机) 互连网络要求： 1、熟练掌握立方体、PN2I、混洗交换三种基本的单级网络的互连函数表示、掌握立方体、Omega多级互连网络的交换单元功能，拓扑结构、及所用的开关控制方式 2 、 熟练掌握8或16个入端和出端的多级立方体多级混洗交换网络的画法 1、 SIMD系统的互连网络的设计目标（P234） 2、互连网络的组成 3、互连函数的定义（P235） 4、单级立方体、 PN2I 、Omega多级互连网络及其函数表达式（P235-236） 互连网络 是将集中式系统或分布式系统中的结点连接起来所构成的网络。 在拓扑上，互连网络为输入和输出两组结点之间提供一组互连或映象。 互连网络的一般模型是有N个输入端和N个输出端的封闭装置，通过其内部在入端、出端之间构造的多条路径实现数据按某种算法的传播。入端和出端所连可以是N个处理单元或其它并行处理设备，统称为“结点”。 　互连网络与处理单元的连接模型如下图所示。 互连函数 如果把互连网络的N个入端和N个出端各自用整 数0，1，…，N-1代表，则互连函数表示互连的出 端号和入端号的一一对应关系。 ? 在互连函数中，记:我们总是记N──结点数，n=log2N ── 维数，j= Xn-1…X0──结点编号的二进制形式，位数为n。 ?? 由于这些开关的触点是可动的，所以一个互连网络的输入/输出对应关系有多种，也就是有多个互连函数，我们把它们合称为“互连函数族”。一般而言，互连函数的复合连接作用必须使网络中所有结点互相可达，即构成一个连通图。 6.2.1 互连网络的性能参数 1. 互连网络的拓扑结构 (1) 静态网络 由点和点直接相连而成，这种连接方式在 程序执行过程中不会改变。 (2) 动态网络 用开关通道实现，可动态地改变结构， 使其与用户程序中通信要求匹配。 2. 性能参数 (1) 网络规模：结点数 (2) 结点度：与结点相连接的边的数目。 入度：进入结点的通道数 出度：从结点出来的通道数 (3) 网络直径 网络中任意两个结点间最短路径长度的最大值。 (4) 路由 在网络通信中对路径的选择与指定。 6. 2. 2 三种基本的单级网络 立方体 PM2I 混洗交换 ? 立方体函数定义：Cubei的功能是对入端结点编号二进制形式的第i位取反，即 ??? Cubei(Xn-1…Xi+1XiXi-1…X0)=Xn-1…Xi+1XiXi-1…X0， ?????? 其中0≤i≤n-1。 ??? 例如：Cube0(0)=1，Cube3(7)=15。 1. 单级立方体 三维二进制立方体网络 ????? n=3的混洗函数开关状态如下图所示，其连接规律是把全部入端结点按编号从当中分成数目相等的前后两半，前一半与后一半在连到出端结点时正好一一隔开，就像人们在洗扑克牌时，把整副牌分成两半后相互对插一样。“混洗”（shuffle）这个名词由此而来。 2. 单级混洗—交换网络 　 该网络由混洗函数（shuffle）与交换函数（exchange即Cube0）定义， ?? 混洗函数性质1：当把结点编号写成二进制形式时，混洗函数满足 ????????????? shuffle(bn-1bn-2……b0) = bn-2……b0bn-1 对n=2k个对象均匀混洗，可用k位二进制数 x=(xk-1,…,x1,x0) 表示定义域中的每个对象 均匀混洗将x映射到f(x)，得到：f(x)=( xk-2,…,x1,x0,xk-1) 也就是说每混洗运算一次，结点编号的二进制形式就循环左移一位。 均匀混洗 n=8（对象个数）的均匀混洗所对应的映射与其逆过程 3 .单级PM2I网络（又称加减2i网络） 　 该网络由PM2I函数定义，PM2I函数共有n对成员，分别是PM2 ±0，PM2 ±1，……，PM2 ±(n-1)。 ??? ? PM2I函数定义：PM2±i的功能是对入端结点编号加或减2i，然后再作模N运算 ?????? PM2+i（j）=j+2i?mod N ??? ?? ?PM2-i（j）=j-2i?mod N ??? 其中j = 0 ～ N - 1，i = 0 ～ n - 1。 ??? 例如：当N=8时，PM2+0（0）=0+20=1，PM2+0（1)=1+20=2