互连特性如图67所示,比如结点0可以与结点1,2,4,6,7直接 连接;而在图6.3所示的立方体互连中,每一个结点只能与相、的3个 结点连接 0 但是从图6.6中不难看出, PM2I1)=PM2I(m1因此 按照函数PM2I只能构成2n-1种 互连函数。网络的最大距离为 门/2 log2N/2,这 里表示向上取整。 4 图67PM2I互连特性
图6.7 PM2I互连特性 互连特性如图6.7所示，比如结点0可以与结点1，2，4，6，7直接 连接；而在图6.3所示的立方体互连中，每一个结点只能与相邻的3个 结点连接。 但是从图6.6中不难看出， PM2I+(n-1)=PM2I-(n-1)。因此， 按照函数PM2I只能构成2n-1种 互连函数。网络的最大距离为 n / 2 = log2N / 2 ，这 里 表示向上取整
5蝶形互连函数 000 000 蝶形互连函数实现输入端与 001 001 地址中最高位与最低位交换的输出 010 010 端连接 011 011 Butterfly(b,,b,.b,b) 100 100 bn2…bb 10l 101 按照蝶形互连函数的连接示意 110 110 如图6.8所示,犹如一只蝴蝶,中 l11 111 线对称,因此称为蝶形互连函数。 图6.8蝶形互连示意图 其中,№8
5.蝶形互连函数 蝶形互连函数实现输入端与 地址中最高位与最低位交换的输出 端连接： Butterfly(bn-1 bn-2…b1 b0 ) = b0 bn-2…b1 bn-1 按照蝶形互连函数的连接示意 如图6.8所示，犹如一只蝴蝶，中 线对称，因此称为蝶形互连函数。 其中，N=8。 图6.8 蝶形互连示意图
6混洗交换互连函数 混洗交换互连函数实际上是由全混洗互连函数与交换互连函数构 成的复合函数: Exchange[shuffle(bm,- 6n-26,bo) Exchange[b2…b,bbn=bn2… b,bob n-1 按照混洗交换互连函数的连接示意如图6.9所示,其中,№8。 2 3 4 6-7 图69混洗交换互连示意图 <
6.混洗交换互连函数 混洗交换互连函数实际上是由全混洗互连函数与交换互连函数构 成的复合函数： Exchange[shuffle(bn-1 bn-2…b1 b0 )] = Exchange[bn-2…b1 b0 bn-1 ]= bn-2…b1 b0 b̅n-1 按照混洗交换互连函数的连接示意如图6.9所示，其中，N=8。 图6.9 混洗交换互连示意图
【例6.2】设有128个处理器,其编号依次是0,1,2,.,127 当复合互连函数为 Shuffle( Exchange(PM2I2))时,第7号处 理器与哪一个处理器连接。 解:设待求处理器的序号为/,表示为P,则: P= Shuffle( Exchange (PM2I,(00000111)) Shuffle(Exchange(00000111-22))) Shuffle( Exchange (00000011)) Shuffle(00000011) = Shuffle(00000010)=00000100
【例6.2】设有128个处理器，其编号依次是0，1，2，…，127 ，当复合互连函数为 Shuffle(Exchange (PM2I-2 ))时，第7号处 理器与哪一个处理器连接。 解：设待求处理器的序号为i，表示为Pi，则： Pi = Shuffle(Exchange(PM2I-2 (00000111)) = Shuffle(Exchange(00000111-2 2))) = Shuffle(Exchange(00000011)) = Shuffle(00000011) = Shuffle(00000010)= 00000100
【例63】设有128个处理器,其编号依次是0,1,2,…,127, 当复合互连函数为Shue( Butterfly(PM2I+4)时,第27号处理器 与哪一个处理器连接。 解:设待求处理器的序号为i,表示为P,则 Pi= Shuffle Butterfly(PM2I+4(00011011)) Shuffle(Butterfly(00o11011+24)) Shuffle Butterfly(0o101011)) Shuffle(10101010)=01010101
【例6.3】设有128个处理器，其编号依次是0，1，2，…，127， 当复合互连函数为 Shuffle(Butterfly(PM2I+4))时，第27号处理器 与哪一个处理器连接。 解：设待求处理器的序号为i，表示为Pi，则： Pi = Shuffle(Butterfly(PM2I+4(00011011))) = Shuffle(Butterfly(00011011+24)) = Shuffle(Butterfly(00101011)) = Shuffle(10101010)= 01010101