互联网结构.docVIP

7.3.1 几种单级互联网7.3.2 基本的循环互联网和多级互联网7.3.3 互联网络的设计特性7.3.4 网络拓扑结构7.3.5 互联网其他分类 7.3 互联网结构 　　利用上述的基本互联函数，可以构成单级互联网、多级互联网和计算机系统互联网。 　　7.3.1 几种单级互联网 　　在计算机中，单级互联网不论哪一种，都可以表示为一个普通模型。图7.3.1为单级互联网的一个普遍模型。 图中IS代表输入端选择器，OS代表输出端选择器，二者配合能实现N个入端和N个出端之间的各种连接。 　　由于SIMD互联网往往是用一些基本的单级互联网经过多次通过或多级连接而成。 因此下面以N=8为例介绍常用的三个单级互联网，即立方体网，PM2I和混洗交换单级网。 　　1.立方体单级网 　 　立方体单级网各结点间互联关系实现的是立方置换。其结构为一个立方体，立方体的每个顶点表示一个结点，共有8个结点，用ZYX三位二进制代码予以标号， 它所能实现的入、出端连接如同立方体各顶点间能实现的互联一样，即每个结点只能直接连到其二进制标号的某一位取反的其他3个结点上。 如010只能连到011，000，110上，分别对应010节点的右起第0位，第1位，第2位变反。但不能直接连到对角线上的001，100，101， 111上， 所以，三维的立方体单级网络有3种互联函数：Cube0，Cube1和Cube2，这里Cubei函数下标数宁0（1或2）表示右起第0位，（第1位或第2位）变反， 它们分别对应节点坐标在X，Y，2轴上的连接，其连接方式如图7.3.2来表示，单级立方体网的最大距离为3，若反复使用应用该立方体单级网，最多3次可实现任意一对结点连接。 　　立方体单级网循环表示为：　　Cube0：(0 1) (2 3) (4 5) (6 7)　　Cube1：(0 2) (1 3) (4 6) (5 7)　　Cube2：(0 4) (1 5) (2 6) (3 7)　　推广到n维的情形。立方体网共有n=Log2N种互联函数，即为：　　其中Xk为输入端标号的第k位二进制代号，且0≤k≤n-1　　显然，这里单级立方体网的最大距离为n， 若反复使用单级立方体网，最多n次可实现任意一对结点连接。 　　2.PM2I单级互联网 　　PM2I单级网结点间的互联函数关系为加减2i置换，对于N=8 PM2I单级网共有2×3=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) 　　比较而言， 立方体单级网络中的一个入端只有3个出端可与之直接相连， 如0可直接连到1，2或4，而PM2I中0却可以直接连到1，2，4，6，7上（实现加减2i置换）， 比立方体网更灵活，就更一般的普遍情况来说，PM2I网络总存在有PM2+(n-1)=PM2-(n-1)， 所以实际PM2I 互联网络只有2n-1种不同的互联函数。 图7.3.3为三维的PM2I网的互联网连接图，对于其余PM2I， 0≤i≤n-2等互联函数，连接的箭头相反。PM2I单级网络的最大距离为[n/2]，从上面N=8的三维PM2I互联网络的例子就可以看出，最多只要二 次使用，即可实现任意一对入、出端号之间的连接。 　　3.混洗交换单级互联网络 　 　混洗交换单级互联网络，它包含了两个互联函数，一个是全混洗(Perfect shuffle)，另一个是交换(Exchange)。 当各站点间按均匀洗牌置换的互联函数关系相连，每混洗一次，其二进制编码循环左移一位，当全混洗总次数为n时，全部N个处理器便又恢复到最初的排列次序， 由此可以发现， 在多次全混的过程中，除了编号为全“0”和全“1”的处理器外， 各个处理器都遇到了与其他多个处理器连接的机会。　　单纯的全混互联网络增加交换互联函数（它就是Cube0）， 便可实现二进制编号为全“0”和全“1”的处理器与其他处理器的任何连接，即全混交换单级网络如图7.3.4所示。 其中实线表示交换，虚线表示全混。从图中也可以看到，全混3次以后， 入端标号恰好回到了原来的位置。在混洗交换网络中， 最远的两个入、出端号是全“0”和全“1”，它们的连接， 需要n次交换和n-1次混洗，所以其最大距离为2n-1。 　　7.3.2 基本的循环互联网和多级互联网 　 　单级互联网络只能实现有限几种基本连接，并不能实现任意处理器之间的互联，为实现任意处理器之间的互联，可以对单级互联网采取下面两种基本方法实现。一 种是将同一套单级互联网循环使用，组成循