互连网络-单极网络

列：分别实现16个处理单元互连的立方体单级网络、PM2I单级网络、混洗交换单级网络、蝶形单级互连网络。

1）写出所有各种互连函数的一般式。

2）3号处理单元可将数据直接传送到哪些处理单元上？

相关函数：

1. 立方体单级网络

定义：扩大到n维时，N个结点的立方体单级网络共有$n=log_2N$中互连函数，n>3时，称之为超立方体网络

互连函数表示为（第i位互换）：$Cube_i(b_{n-1}...b_i...b_1b_0)=b_{n-1}...\overline{b_i}...b_1b_0$

2. PM2I($Plus-minus2^i$)单级网络

定义：能实现与j号处理单元直接相连的号为$j\pm2^i$的处理单元

与单级互连函数相比，成对出现，即每个相连($log_2{N}$)单元都有两个互连函数,一加一减,一般格式如下（能与j号单元互连的是$j\pm2^i$单元，N为总共有多少处理单元，mod取余））：

互连函数表示为(加和减2的i次方)： $ \begin{cases} PM2_{+i}(j)=j+2^i\mod N \ PM2_{-i}(j)=j-2^i\mod N \end{cases}$

3. 混洗交换单级网络（Shuffle-Exchange）

定义：每次整体左移一位，二进制最高位补充到最低位位置

互连函数表示为：$shuffle(b_{n-1}b_{n-2}...b_1b_0)=b_{n-2}...b_1b_0b_{n-1}$ 混洗交换多级网络：又称omega网络

4. 蝶形单级网络（Butterfly）

定义：最高位和最低位交换，像蝴蝶的翅膀

互连函数表示为：$Butterfly(b_{n-1}b_{n-2}..b_1b_0)=b_0b_{n-2}...b_1b_{n-1}$

概念：

立方体单级网络

1. 无论有多少个处理单元的单极网络；都可以用公式$log_2N$求出有几个顶点相连；N为处理单元数；

2. 16个单元,$log_2{16}=4$,即有4个顶点互连；即互连函数的表达式也有4个：

   示列：

解1：

因为有$log_2{16}=4$个处理单元相连；所以互连函数一般式为（标横杠为表示交换(即0为1，1为0)）：

$Cube_0(b_3b_2b_1b_0)=b_3b_2b_1\overline{b_0}$

$Cube_1(b_3b_2b_1b_0)=b_3b_2\overline{b_1}b_0$

$Cube_2(b_3b_2b_1b_0)=b_3\overline{b_2}b_1b_0$

$Cube_3(b_3b_2b_1b_0)=\overline{b_3}b_2b_1b_0$

解2：

由题1知，有四个单元相连；所以:3=0011(二进制)

根据互连函数一般式知：

3(0011)号单元经互连函数之后$Cube_0$=0010=2,第0位交换

3(0011)号单元经互连函数之后$Cube_1$=0001=1,第1位交换

3(0011)号单元经互连函数之后$Cube_2$=0111=7,第2位交换

3(0011)号单元经互连函数之后$Cube_3$=1011=11,第3位交换

所以3号单元与：1，2，7，11号单元互连

PM2I($Plus-mins2^i$)单级网络(加和减2的i次方)

解1：

已知题有16个处理单元，4个互连顶点，即PM2I有8个互连函数，函数一般式为（：

$PM2+0(j)=j+2^0 \pmod{16}$

$PM2-0(j)=j-2^0 \pmod{16}$

$PM2-1(j)=j-2^1 \pmod{16}$

$PM2-1(j)=j-2^1 \pmod{16}$

$PM2-2(j)=j-2^2 \pmod{16}$

$PM2-2(j)=j-2^2 \pmod{16}$

$PM2-3(j)=j-2^3 \pmod{16}$

$PM2-3(j)=j-2^3 \pmod{16}$

解2： 根据一般式得（这里省掉mod是应为，算出来的结果不影响）： $PM2+0(j)=j+2^0 \pmod{16}$=$3+2^0$=4

$PM2-0(j)=j-2^0 \pmod{16}$=$3-2^0$=2

$PM2+1(j)=j+2^1 \pmod{16}$=$3+2^1$=5

$PM2-1(j)=j-2^1 \pmod{16}$=$3-2^1$=1

$PM2+2(j)=j+2^2 \pmod{16}$=$3+2^2$=7

$PM2-2(j)=j-2^2 \pmod{16}$=$3-2^2$=-1(15)

$PM2+3(j)=j+2^3 \pmod{16}$=$3+2^3$=11

$PM2-3(j)=j-2^3 \pmod{16}$=$3-2^3$=-5(11)

所以在PM2I单级网络楼下，3号单元与4,2,5,1,7,15,11号单元相连

负号结果，即从0-15(题目总共是16单元)后往前数的单元

混洗交换单级网络（Shuffle-Exchange）

解1： 已上题为列，一般式为：

$shuffle(b_2b_1b_0b_3)$=$b_2b_1b_0b_3$ 解2： 所以在混洗交换单级网络下，3号单元与6号单元相连

蝶形单级网络（Butterfly）

解1：已上题为列，一般式为：

$shuffle(b_0b_2b_1b_3)$=$b_0b_2b_1b_3$

解2：

所以在蝶形单级网络下，3号单元与10号单元相连

延伸阅读