南大自考流程详解

自考-计算机应用专业

  进行系统结构学习的过程中，多级立方体网络这部分，真的是难以理解。我觉得吧，这本书编的也太垃圾了，一点也不通俗易懂。

  进行了各种资料搜索后，也没有找到详尽的解释。

下面这部分直接抄的百度百科，划重点，要有开关元件控制。简单来说，就是为了处理机和功能部件可以互相连接。

由开关元件按一定拓扑结构和控制方式构成的网络以实现计算机系统内部多个处理机或多个功能部件间的相互连接。 在并行处理计算机系统、分布计算机系统和计算机网等由多个处理机或多个功能部件组成的各种系统中，都会遇到机间互连问题。互连必须遵循一定的拓扑结构，通过开关元件来完成，以一定的控制方式实现机间通信。因此，互连网络是这些系统的重要组成部分，它对系统的性能指标有决定性的影响。

  比如我们有16个处理单元。你就这么想吧，把一个处理单元当做是一个房子。现在16座房子，这些房子里住了小红0，小明1，小黑15等等小朋友。现在呢，每座房子都是独立的，没有路径可达，所以要修路。最简单的方法是什么，每两座房子之前就修一条路直达。开心不，贼爽。小红0想去小黑15家，直接抵达，想去小明1家也直接抵达。如下图所示。但这样问题就出来了，除了小黑，小明，还有小2，小3，小n呢，如果两两间都修路的话，代价也太大了。光为了方便小红一人，就要修15条路。那小明肯定也想方便，也要直达小黑等朋友的家，也要修路。何等卧槽，这路也修太多了吧。 于是呢，就出现了网络互连的设计这个概念。

既然两两相连的话，过于复杂，会增加成本，那我们就不两两相连。如果我们顺序连接，0-1-2-3-。。。-15-0，如此这般，行程一个回路，卧槽，两两之间皆可达，这才用了15根线啊亲，省材省料。但是吧，这样子成本降了，性能也不行了，距离远的岂不是步数贼多。

于是呢，接着提出了设计互连网络的主要目标： 翻译成人能听懂的话就是,平衡成本和性能： （1）两两相连的话，过于复杂，会增加成本，所以别这么干老兄； （2）这个路也能走，那个 路也能走； （3）减少通讯延迟，提高并行处理的效率； （4）64处理单元的非常复杂，可以用4个16的来组合； 又想巧又想好，想要小羊跑得快，还要小羊少吃草(≧▽≦)

比如看下图，就是16个处理单元的线路图。每个处理单元只有四根线与其他单元直连，比如0和1、4，12，15相连，但是通过迂回的方式，任意两个之间都可达了，而且可以有好几种路径过去，提高了灵活性。

定义：互连函数表示互连网络的出端号和入端号的一一对应关系。所有入端和出端f(x)都用二进制编码,从两者的二进制编码上找出其函数规律。 翻译成人话就是：找出到底要在哪两座房子房子之间修路的规律呗。

立方体、PM21、混洗交换、蝶形单级网络

下图首行就是立方体互连函数的表达式，翻译一下就是，Cube的下标i（下标从0开始）所对应的进制位取非。 以001这个二进制举例： Cube0的情况下，下标为0取非：001——》000 Cube1的情况下，下标为1取非：001——》011 Cube2的情况下，下标为2取非：001——》101

下图首行就是PM21函数的表达式，N代表几个元素，j代表当前值，mod是取余符号。翻译一下就是，PM 2+i=的下标i（下标从0开始）所对应的进制位取非。 example： N=8,i=0时，PM 2+0=j+2^0 mod 8: 当前值为j=1,所要连接的下个数值为，1+2^0 mod 8=2 mod 8=2（2取余8还是2） 当前值为j=7,所要连接的下个数值为，7+2^0 mod 8=8 mod 8=0（8取余8是0） N=8,i=1时，PM 2+1=j+2^1 mod 8: 当前值为j=1,所要连接的下个数值为，1+2^1 mod 8=3 mod 8=3 当前值为j=7,所要连接的下个数值为，7+2^1 mod 8=9 mod 8=1

下图首行就是混洗交换函数的表达式，这个很简单，就是把最前面一位移动到最后面。 example:001——》010——》100——》001

多级立方体网络、多级混洗交换网络、多级PM21网络、基准网络、多级交叉开关网络

多级互连网络采用多个相同的或不同的单级互连网络直接连接起来，实现任意节点间的直接互连。

交换开关是具有两个入端和两个出端的交换单元,用作各种多级互连网络的基本构件。无论入端或出端,如果令居于上方的都用i表示,居于下方的都用j表示，则可以定义下列4种开关状态或连接方式： 1)直连，即i入连i出,j入连j出； 2)交换，即i入连j出,j入连i出； 3)上播，即i入连i出和j出,j入悬空； 4)下播，即j入连i出和j出,i入悬空。 仅具有直连和交换两种功能的是二功能交换单元，需1位控制信号；具有全部4种功能的是四功能开关，需4位控制信号。

前一级交换开关的输出端和后一级交换开关的输入端的连接模式。

注意：接下来的案例都以8个处理单元为例 多级立方体网络，以八个处理单元为例，其普遍结构如下图所示。 特点是:第i级交换单元处于交换状态时,实现的是Cubei互连函数,且都采用二功能交换单元。 翻译一下： 1、首先什么叫做二功能交换单元？ 我们需要复习一下1.1交换开关的概念，交换开关是具有两个入端和两个出端的交换单元。而二功能交换单元仅具有直连和交换两种功能。无论入端或出端,如果令居于上方的都用i表示,居于下方的都用j表示，则2功能交换单元的连接方式可表示为2种： 1)直连，即i入连i出,j入连j出； 2)交换，即i入连j出,j入连i出； 联系到这里，以上图单元A举例，它有入端（0，1）和出端（0，1） ，那么它的连接方式可为： 1)直连，即0入连0出，1入连1出； 2)交换，即0入连1出，1入连0出； 2、第i级交换单元处于交换状态时,实现的是Cubei互连函数，是什么意思呢？ 继续以单元A为例，已知入端号“0”，当处于交换状态时，单元A位于第0级，即它的出端号应实现Cube0互连函数。000，Cube的下标0位所对应的进制位取非=001，即出端号为"1"。 继续看第1级的单元E,已知入端号“0”，当处于交换状态时，单元E位于第1级，即它的出端号应实现Cube1互连函数。000，Cube的下标1位所对应的进制位取非=010，即出端号为"2"。 依次类推。害，原来这个图是这么画的。

0 000 1 001 2 010 3 011 4 100 5 101 6 110 7 111 (1)写出实现此功能的互连函数的一般式； (2)画出用三级立方体网络实现互连函数的互连网络拓扑图，并标出各控制开关的状态。 我们要知道一个重点，0，1,2这三级，都是由交换开关控制的，一般呢，只用到两种功能的开关状态，也就是直连和交换。下图我画的辅助线，0入5出，就是设置了三级的开关状态为0,2交换，1直连。

如果是（0,7）（1,6）（2，5）(3,4)呢？ 三位进制位全取非，开关都是交换

比起多级立方体网络，混洗就简单多了

参考链接：https://wenku.baidu.com/view/8406426f58fafab069dc021c.html