本知识点对三种基本的单级互连网络：立方体、PM2I、混洗交换。
一、立方体单级网络
1、结构
三维立方体单级网络（cube）结构如下图所示：
图6-7
其中：
（1）立方体的每一个顶点（网络的节点）代表一个处理单元，共有8个处理单元，用zyx三位二进制码编号；
（2）每个处理单元只能直接连到其二进制编号的某一位取反的其他3个处理单元上；
（3）最大距离为n，任意两个节点之间至少有n条不同的路径，容错性强；
（4）n>3为超立方体（Hyper-Cube）。
2、互连函数
N个节点的立方体单级网络共有
种互连函数，三维的立方体（8个节点）单级网络有3种互连函数：Cube0、Cube1和Cube2。
不同的立方体单级互连函数可统一表示为Cubei，第i位互为反码：
0≤i≤n-1，Pi为入端号二进制码的第i位。
三种互连函数中定点连接关系为：
图6-8
cube0中，只有顶点的二进制编码的最后一位不同的顶点之间可直接相连，如001与000，100与101，111与110相连。任意两个节点之间最大距离为3，如000与111之间可通过000→001→011→111可达，其距离为3。同时，任意两个节点之间有3条路径，如000与111之间可通过000→001→011→111，000→100→101→111，000→010→110→111可达。
Cube1中，只有顶点的二进制编码的最右边第二位不同的顶点之间可直接相连，如001与011，100与110，111与101相连。任意两个节点之间最大距离为3，如000与111之间可通过000→001→011→111可达，其距离为3。同时，任意两个节点之间有3条路径，如000与111之间可通过000→001→011→111，000→100→101→111，000→010→110→111可达。
Cube2中，只有顶点的二进制编码的最左边一位不同的顶点之间可直接相连，如001与101，100与000，111与011相连。任意两个节点之间最大距离为3，如000与111之间可通过000→001→011→111可达，其距离为3。同时，任意两个节点之间有3条路径，如000与111之间可通过000→001→011→111，000→100→101→111，000→010→110→111可达。
二、PM2I单级网络
PM2I单级网络是“加减2i”（Plus-Minus 2i）单级网络的简称。P和M分别表示加和减，2I表示2i。能实现与j号处理单元直接相连的是号为j±2i的处理单元。
其互连函数表示为：
0≤j≤N-1，0≤i≤n-1，n=log2N。因此，它共有2n个互连函数。
【例1】N=8的三维PM2I互连网络的互连函数有6个不同的互连函数，分别为：
PM2+0：（0 1 2 3 4 5 6 7）
PM2-0：（7 6 5 4 3 2 1 0）
PM2+1：（0 2 4 6）（1 3 5 7）
PM2-1：（6 4 2 0）（7 5 3 1（
PM2+2：（0 4）（1 5）（2 6）（3 7）
PM2-2：（4 0）（5 1）（6 2）（7 3）
根据互连函数的定义，其中的PM2+0、PM2+1和PM2±2连接图为：
图6-9
某些阵列处理机采用单向环网或双向环网实现处理器的互连，可以看成是PM2I网络的特例，它仅使用了其中的PM2+0、PM2-0、PM2+2或PM2-2互连函数。
PM2I单级网络的最大距离为［n/2］。三维PM2I互连网络中，最多只要二次使用，即可实现任意一对入、出端号之间的连接。
三、混洗交换单级网络
包含两个函数：全混与交换。
1、全混
全混函数为：
n=log2N，Pn-1Pn-2…P1P0为入端编号的二进制码。
全混下的不同混洗连接图为：
图6-10
从上图可得全混函数的特点为：
（1）不可逆；
（2）每全混一次，新的最高位就被移至最低位；
（3）n次全混后，全部N个处理单元便又恢复到最初的排列次序；
（4）除了编号为全“0”和全“1”的处理单元外，各个处理单元都遇到了与其他多个处理单元连接的机会。
2、交换
全混不能实现全“0”和全“1”的结点与其它结点之间的增加交换函数cube0，得到全混交换单级网络。与立方体连接存在对应关系，可构成多级连接。最远的入、出端号为全0与全1，需经过n次交换和n-1次混洗，最大距离为2n-1。
【例2】下图为n=8时全混交换互连网络连接图：
图6-11
其中实线为交换，虚线为全混。
上图中，0结点到7结点之间距离最远，其距离为5（n=3），可通过0→1→2→3→6→7可达。其中，0→1、2→3、6→7为交换，共3次。1→2、3→6为混洗，共2次。
