哈尔滨工业大学计算机科学与技术学院
并行处理与体系结构
哈尔滨工业大学计算机科学与技术学院
第 6章 系统的互联和千兆位网络
??1 系统互连基础
??2 静态连接网络
??3 动态连接网络
??4 消息传递机制
??5 千兆位网络技术
??6 ATM交换器和网络
哈尔滨工业大学计算机科学与技术学院
?1 系统互连基础
?一, 网络的分类方式
?静态网络
?动态网络
哈尔滨工业大学计算机科学与技术学院
?二, 网络特性和寻径功能
?1.结点度
?包括出度和入度
?2.网络直径
?3.等分宽度
?当某一网络被切成相等的两半时，
沿切口的最小边数 (通道 )
哈尔滨工业大学计算机科学与技术学院
?4.数据寻径功能
? 数据寻径网络用来进行 PE间数据
交换。
?通常见到的 PE之间的数据寻径功
能有移数 (shifting)、循环
(rotation)、置换 (一对一 )、广
播 (一对全体 )、选播 (多对多 )、
个人通信 (一对多 )、洗牌、交换
等。
哈尔滨工业大学计算机科学与技术学院
?5.置换
?对 n个对象来说，有 n！种置换，
n个对象可照此重新排序。整个
置换集合形成一个与复合运算
有关的置换群。
?可以用轮换方法来描述置换功
能。
哈尔滨工业大学计算机科学与技术学院
?例如，置换 ?＝ (a,b,c)(d，
e)即是以轮换形式表示的置换
映射。
?(d,e)循环周期为 2。
哈尔滨工业大学计算机科学与技术学院
?三,互连函数
（一）基本概念
?除了上述的置换表示，还有函数
表示。
?1.互连函数：表示相互连接的输
出端号和输入端号之间的一一对
应关系。
哈尔滨工业大学计算机科学与技术学院
?互连函数有时可表示成为置换函
数或排列函数。
?函数表示法用 x表示输入端变量，
用 f(x)表示互连函数。
?x还常用 n位二进制形式来表示,
?写成 xn-1,xn-2… x1x0。
?互连函数则对应地表示为,
f(xn-1,xn-2… x1x0)。
哈尔滨工业大学计算机科学与技术学院
?2.输入输出对应表示法
? 优点,
?更直观
哈尔滨工业大学计算机科学与技术学院
（二）常用的基本互连函数和特征
?1．恒等置换
? 相同编号的输入端与
输出端一一对应互连
所实现的置换。
f(xn-1,xn-2… x1x0)
= xn-1xn-2… x1x0
哈尔滨工业大学计算机科学与技术学院
?2.交换置换
哈尔滨工业大学计算机科学与技术学院
?3．方体置换
? 是实现二进制地址编号中第 k位位值不
同的输入端和输出端之间的连接。其
表达式为,
哈尔滨工业大学计算机科学与技术学院
? 如以 N=8为例。
哈尔滨工业大学计算机科学与技术学院
哈尔滨工业大学计算机科学与技术学院
哈尔滨工业大学计算机科学与技术学院
哈尔滨工业大学计算机科学与技术学院
?4．均匀洗牌置换
? 均匀洗牌置换
? 将输入端分成数目相等的两半，前一
半和后一半按序一个隔一个地从头至
尾依次与输出端相连。
? 这好比洗扑克牌时，将整副牌分成相
等的两叠来洗，以达到理想的一张隔
一张的均匀情况，故称为均匀洗牌置
换，或简称为洗牌置换。
哈尔滨工业大学计算机科学与技术学院
? 其函数关系可表示为,
? 由此表达式可见，洗牌变换是将输
入端二进制地址循环左移一位即得
到对应的输出端二进制地址。
哈尔滨工业大学计算机科学与技术学院
哈尔滨工业大学计算机科学与技术学院
? 还可以定义,
? 子洗牌
?超洗牌,
哈尔滨工业大学计算机科学与技术学院
? 逆均匀洗牌
? 是均匀洗牌的逆函数，其函数表达式
为,
哈尔滨工业大学计算机科学与技术学院
哈尔滨工业大学计算机科学与技术学院
?5.蝶式置换
? 蝶式置换的名称源于 FFT变换的实现
时其图形的形状如蝴蝶式样。
哈尔滨工业大学计算机科学与技术学院
? 可定义子蝶式,
? 超蝶式
哈尔滨工业大学计算机科学与技术学院
哈尔滨工业大学计算机科学与技术学院
?6,位序颠倒置换
?位序颠倒置换是将输入端二进制
地址的位序颠倒过来求得相应输
出的地址。其表达,
??(k)(xn-1xn-2… x1x0)
=x0x1… xn-1
哈尔滨工业大学计算机科学与技术学院
?7．移数置换
? 移数置换是将输入端数组循环移动一
定的位置向输出端传输。其函数表示
式无需用二进制编号来写，可表达如
下,
?d(X)＝ (X+k) mod N,0≤X≤N
?k为常数，指移过的位置值，也可以
将整个输入数组分成若干个子数组。
哈尔滨工业大学计算机科学与技术学院
? 三,网络性能
(1)功能特性 —— 这指的是网络如何支
持数据寻径、中断处理、同步、请求
／消息组合和一致性。
(2)网络时延 —— 这是指单位消息通过
网络传送时，最坏情况下的时间延迟。
(3)带宽 —— 这是指通过网络的最大数
据传输率，用 M字节／秒表示。
哈尔滨工业大学计算机科学与技术学院
(4)硬件复杂性 —— 这是指诸如导
线、开关、连接器、仲裁和接口
逻辑等的造价。
(5)可扩展性 —— 这是指在增加机
器资源使性能可扩展的情况下，
网络具备模块化可扩展的能力。
哈尔滨工业大学计算机科学与技术学院
?2 静态连接网络
?静态网络的基本概念
1.线性阵列
?内部结点度
?直径,N-1
?等分宽度 b＝ 1。
哈尔滨工业大学计算机科学与技术学院
?2,环和带弦环
?结点度是常数 2
?直径
?双向环,N/2
?单向环
:N
哈尔滨工业大学计算机科学与技术学院
? 带弦环
? 可以提高结点度
? 减小直径,5,3
哈尔滨工业大学计算机科学与技术学院
哈尔滨工业大学计算机科学与技术学院
?3.循环移数网络
?一个循环移数网络，其结点数
N＝ 16，它是将环上每个结点到与
其距离为 2整数幂的结点之间增加
一条附加链而构成的 ;
?结点度 d=2n-1;直径 D=n/2;N=2n
哈尔滨工业大学计算机科学与技术学院
?结点度,
?网络直径,
哈尔滨工业大学计算机科学与技术学院
?4.树形和星形
? （ 1）树形,
? 结点数
? 一棵 k层完全平衡的二叉树应有 N＝ 2k-1
个结点
? 最大结点度 3
? 直径,2(k-1)
? 二叉树是一种可扩展的系统结构
? 由于结点度是常数，但其直径相当长
哈尔滨工业大学计算机科学与技术学院
哈尔滨工业大学计算机科学与技术学院
?（ 2）星形
?如上图所示
?直径,2
?结点数,N-1
哈尔滨工业大学计算机科学与技术学院
?5,胖树形
?1985年 Leiserson提出将计算机科学
中所用的一般树结构修改为胖树形
(fat tree)。
? 二叉胖树结构的通道宽度从叶结点往
根结点上行方向逐渐增宽，它更象真
实的树，其向树根方向的枝叉变得愈
来愈粗。
哈尔滨工业大学计算机科学与技术学院
哈尔滨工业大学计算机科学与技术学院
? 解决了使用传统二叉树的主要问题；
?CM— 5已采用胖树结构；
? 胖树体系结构在 Connection Machine的 CM-
5系统中实现
?CM5采用 4叉胖树来构造数据网络，允许每
个结点有 4个子结点和 2个或 4个父结点。
? 还可将二叉胖树的思想推广到多路胖
树
哈尔滨工业大学计算机科学与技术学院
哈尔滨工业大学计算机科学与技术学院
?6.网格形和环网形
?(1)3X3网格如下图所示,
?这是一种比较流行的结构，它已以
各种变体形式在 ILLiac 4,MPP,
DAP,CM-2和 Intel Paragon中得到
了实现
?N＝ nk结点的 k维网格的内部结点度为
2k；可知边界点度和角结点度
? 网格直径为 k(n-1)
哈尔滨工业大学计算机科学与技术学院
哈尔滨工业大学计算机科学与技术学院
?(2) Illiac 4网格
? 是一种可回绕连接的网格图，如上图所
示。假定 Illiac 4系统采用 8X8的这种
Illiac网格，则其结点度为常数 4，直径
为 7。
? N＝ 16＝ 4X4构型的 Illiac网格与图所示
的结点度为 4的带弦环在拓扑上是等效的。
? 一般说来，一个 nXn的 Illiac网格的直径
应为 d＝ n-1，它仅为纯网格直径的一半
哈尔滨工业大学计算机科学与技术学院
?(3) 环网形
? 上图所示,可看做是另一种直径更短的网
格。这种拓扑结构将环形和网格组合在
一起，并能向高维扩展。
? 环网形沿阵列每行每列都有环形连接。
一个 n× n二元环网的结点度为 4,
? 直径为 2[n／ 2]。
? 环网是一种对称的拓扑结构，所有附加
的回绕连接可使其直径较之网格结构减
少 1/2。
哈尔滨工业大学计算机科学与技术学院
?7.搏动式阵列
? 这是一类为实现确定算法而设计的多维流
水线阵列结构。下图所示就是为完成矩阵
--矩阵相乘而专门设计的搏动式阵列。此
例的内部结点度为 6。
? 静态搏动式阵列可在多个方向上使数据流
变成以流水线方式工作。商用 Intel Warp
系统 (Anaratone等,1986)就是用搏动式
结构设计而成的。自从 1978年 Kung和
Leiserson提出搏动式阵列后，它已成为
广泛研究的领域。
哈尔滨工业大学计算机科学与技术学院
哈尔滨工业大学计算机科学与技术学院
? 通过确定的互连和同步操作，搏动式
阵列可与算法的通信结构相匹配。针
对信号 /图象处理等特殊应用，可提
供更好的性能／价格比。
? 缺点：其结构的实用性有限，而且编
程难。
? 有兴趣的读者可参考 S,Y,Kung
(1988)关于用搏动式和波前沿结构实
现 VLSI阵列处理机的专著。
哈尔滨工业大学计算机科学与技术学院
?8.超立方体
?这是一种二元 n-立方体结构，它已
在 iPSC,nCUBE和 CM-2系统中得到
实现
?一个 n-立方体由 N＝ 2n个结点组成，
它们分布在 n维上，每维有两个结
点。 8个结点的 3-立方体如下图所
示
哈尔滨工业大学计算机科学与技术学院
哈尔滨工业大学计算机科学与技术学院
?9.带环立方体
?这种结构是从超立方体改进而来
的。如下图所示，一个 3-立方体
可改成带环 3-立方体 (CCC)。 构
成的办法是将 3-立方体的角结点
(顶角 )用一个结点环来代替。
哈尔滨工业大学计算机科学与技术学院
? 可以从一个 k-立方体构成一个有 n＝
2k个结点环的带环 k— 立方体；
? 如下图所示，所用的办法是用 k个结
点的环取代 k维超立方体的每个顶角。
? 一个 k— 立方体可变为 kX2k个结点的
k-CCC。
哈尔滨工业大学计算机科学与技术学院
? 如图所示 3-CCC的直径为 6，比原来 3-
立方体的直径大一倍。一般说来,k-
CCC的网络直径 2k,CCC的主要改进之
处即在其结点度为常数 3，与超立方
体的维数无关。
? 假设一超立方体有 N=2n结点。一个有
同样 N结点数的 CCC一定是由低维 k—
立方体组成，即 2n＝ k·2k，其中 k<n。
哈尔滨工业大学计算机科学与技术学院
? 例题,
? 对应于 n=6和 k=4的情况；
? 一个 64结点的 CCC可用 4结点的环取代
4— 立方体的角结点组成。
?CCC的直径为 2k＝ 8；
? 比 6-立方体的 6要长些。 CCC的结点度为 3，
比 6-立方体的结点度 6要小。
? 如果容许一定的时延，则 CCC是一种
构造可扩展系统的较好的结构。
哈尔滨工业大学计算机科学与技术学院
哈尔滨工业大学计算机科学与技术学院
?10.k元 n-立方体网络
?环形、网格形、环网形、二元
n-立方体 (超立方体 )和 ?网络都
是 k元 n-立方体网络系列的拓扑
同构体。
?下图所示是一种 4元 3-立方体网
络。
哈尔滨工业大学计算机科学与技术学院
哈尔滨工业大学计算机科学与技术学院
? 参数 n是立方体的维数,k是基数或者
说是沿每个方向的结点数 (多重性 )。
? 这两个数与网络中结点数 N的关系为,
N＝ kn,(k=N1/n,n＝ logkN)
哈尔滨工业大学计算机科学与技术学院
?k元 n-立方体的结点可用基数为 k的 n
位地址；
?A＝ a0a1a2… an来表示，其中 ai代表第
i维结点的位置。为简单起见，所有
链路都认为是双向的。
? 各结点之间的连线都是双向链路。
哈尔滨工业大学计算机科学与技术学院
?低维 k元 n-立方体称为环网；
?而高维二元 n-立方体则称为超立
方体。
哈尔滨工业大学计算机科学与技术学院
哈尔滨工业大学计算机科学与技术学院
? 总结,
? 大多数网络的结点度都小于 4，比较理想的
? 网络直径的变化范围很大，直径已不是一个严
重问题
? 链路数会影响网络价格，等分宽度将影响网络
的带宽
? 对称性会影响可扩展性和寻径效率，客观地说，
网络的总价格随节点度和链路度增大而上升。
直径小仍然是一种优点
? 结点间的平均距离可能是一种更好的量度指标
哈尔滨工业大学计算机科学与技术学院
并行处理与体系结构
哈尔滨工业大学计算机科学与技术学院
第 6章 系统的互联和千兆位网络
??1 系统互连基础
??2 静态连接网络
??3 动态连接网络
??4 消息传递机制
??5 千兆位网络技术
??6 ATM交换器和网络
哈尔滨工业大学计算机科学与技术学院
?1 系统互连基础
?一, 网络的分类方式
?静态网络
?动态网络
哈尔滨工业大学计算机科学与技术学院
?二, 网络特性和寻径功能
?1.结点度
?包括出度和入度
?2.网络直径
?3.等分宽度
?当某一网络被切成相等的两半时，
沿切口的最小边数 (通道 )
哈尔滨工业大学计算机科学与技术学院
?4.数据寻径功能
? 数据寻径网络用来进行 PE间数据
交换。
?通常见到的 PE之间的数据寻径功
能有移数 (shifting)、循环
(rotation)、置换 (一对一 )、广
播 (一对全体 )、选播 (多对多 )、
个人通信 (一对多 )、洗牌、交换
等。
哈尔滨工业大学计算机科学与技术学院
?5.置换
?对 n个对象来说，有 n！种置换，
n个对象可照此重新排序。整个
置换集合形成一个与复合运算
有关的置换群。
?可以用轮换方法来描述置换功
能。
哈尔滨工业大学计算机科学与技术学院
?例如，置换 ?＝ (a,b,c)(d，
e)即是以轮换形式表示的置换
映射。
?(d,e)循环周期为 2。
哈尔滨工业大学计算机科学与技术学院
?三,互连函数
（一）基本概念
?除了上述的置换表示，还有函数
表示。
?1.互连函数：表示相互连接的输
出端号和输入端号之间的一一对
应关系。
哈尔滨工业大学计算机科学与技术学院
?互连函数有时可表示成为置换函
数或排列函数。
?函数表示法用 x表示输入端变量，
用 f(x)表示互连函数。
?x还常用 n位二进制形式来表示,
?写成 xn-1,xn-2… x1x0。
?互连函数则对应地表示为,
f(xn-1,xn-2… x1x0)。
哈尔滨工业大学计算机科学与技术学院
?2.输入输出对应表示法
? 优点,
?更直观
哈尔滨工业大学计算机科学与技术学院
（二）常用的基本互连函数和特征
?1．恒等置换
? 相同编号的输入端与
输出端一一对应互连
所实现的置换。
f(xn-1,xn-2… x1x0)
= xn-1xn-2… x1x0
哈尔滨工业大学计算机科学与技术学院
?2.交换置换
哈尔滨工业大学计算机科学与技术学院
?3．方体置换
? 是实现二进制地址编号中第 k位位值不
同的输入端和输出端之间的连接。其
表达式为,
哈尔滨工业大学计算机科学与技术学院
? 如以 N=8为例。
哈尔滨工业大学计算机科学与技术学院
哈尔滨工业大学计算机科学与技术学院
哈尔滨工业大学计算机科学与技术学院
哈尔滨工业大学计算机科学与技术学院
?4．均匀洗牌置换
? 均匀洗牌置换
? 将输入端分成数目相等的两半，前一
半和后一半按序一个隔一个地从头至
尾依次与输出端相连。
? 这好比洗扑克牌时，将整副牌分成相
等的两叠来洗，以达到理想的一张隔
一张的均匀情况，故称为均匀洗牌置
换，或简称为洗牌置换。
哈尔滨工业大学计算机科学与技术学院
? 其函数关系可表示为,
? 由此表达式可见，洗牌变换是将输
入端二进制地址循环左移一位即得
到对应的输出端二进制地址。
哈尔滨工业大学计算机科学与技术学院
哈尔滨工业大学计算机科学与技术学院
? 还可以定义,
? 子洗牌
?超洗牌,
哈尔滨工业大学计算机科学与技术学院
? 逆均匀洗牌
? 是均匀洗牌的逆函数，其函数表达式
为,
哈尔滨工业大学计算机科学与技术学院
哈尔滨工业大学计算机科学与技术学院
?5.蝶式置换
? 蝶式置换的名称源于 FFT变换的实现
时其图形的形状如蝴蝶式样。
哈尔滨工业大学计算机科学与技术学院
? 可定义子蝶式,
? 超蝶式
哈尔滨工业大学计算机科学与技术学院
哈尔滨工业大学计算机科学与技术学院
?6,位序颠倒置换
?位序颠倒置换是将输入端二进制
地址的位序颠倒过来求得相应输
出的地址。其表达,
??(k)(xn-1xn-2… x1x0)
=x0x1… xn-1
哈尔滨工业大学计算机科学与技术学院
?7．移数置换
? 移数置换是将输入端数组循环移动一
定的位置向输出端传输。其函数表示
式无需用二进制编号来写，可表达如
下,
?d(X)＝ (X+k) mod N,0≤X≤N
?k为常数，指移过的位置值，也可以
将整个输入数组分成若干个子数组。
哈尔滨工业大学计算机科学与技术学院
? 三,网络性能
(1)功能特性 —— 这指的是网络如何支
持数据寻径、中断处理、同步、请求
／消息组合和一致性。
(2)网络时延 —— 这是指单位消息通过
网络传送时，最坏情况下的时间延迟。
(3)带宽 —— 这是指通过网络的最大数
据传输率，用 M字节／秒表示。
哈尔滨工业大学计算机科学与技术学院
(4)硬件复杂性 —— 这是指诸如导
线、开关、连接器、仲裁和接口
逻辑等的造价。
(5)可扩展性 —— 这是指在增加机
器资源使性能可扩展的情况下，
网络具备模块化可扩展的能力。
哈尔滨工业大学计算机科学与技术学院
?2 静态连接网络
?静态网络的基本概念
1.线性阵列
?内部结点度
?直径,N-1
?等分宽度 b＝ 1。
哈尔滨工业大学计算机科学与技术学院
?2,环和带弦环
?结点度是常数 2
?直径
?双向环,N/2
?单向环
:N
哈尔滨工业大学计算机科学与技术学院
? 带弦环
? 可以提高结点度
? 减小直径,5,3
哈尔滨工业大学计算机科学与技术学院
哈尔滨工业大学计算机科学与技术学院
?3.循环移数网络
?一个循环移数网络，其结点数
N＝ 16，它是将环上每个结点到与
其距离为 2整数幂的结点之间增加
一条附加链而构成的 ;
?结点度 d=2n-1;直径 D=n/2;N=2n
哈尔滨工业大学计算机科学与技术学院
?结点度,
?网络直径,
哈尔滨工业大学计算机科学与技术学院
?4.树形和星形
? （ 1）树形,
? 结点数
? 一棵 k层完全平衡的二叉树应有 N＝ 2k-1
个结点
? 最大结点度 3
? 直径,2(k-1)
? 二叉树是一种可扩展的系统结构
? 由于结点度是常数，但其直径相当长
哈尔滨工业大学计算机科学与技术学院
哈尔滨工业大学计算机科学与技术学院
?（ 2）星形
?如上图所示
?直径,2
?结点数,N-1
哈尔滨工业大学计算机科学与技术学院
?5,胖树形
?1985年 Leiserson提出将计算机科学
中所用的一般树结构修改为胖树形
(fat tree)。
? 二叉胖树结构的通道宽度从叶结点往
根结点上行方向逐渐增宽，它更象真
实的树，其向树根方向的枝叉变得愈
来愈粗。
哈尔滨工业大学计算机科学与技术学院
哈尔滨工业大学计算机科学与技术学院
? 解决了使用传统二叉树的主要问题；
?CM— 5已采用胖树结构；
? 胖树体系结构在 Connection Machine的 CM-
5系统中实现
?CM5采用 4叉胖树来构造数据网络，允许每
个结点有 4个子结点和 2个或 4个父结点。
? 还可将二叉胖树的思想推广到多路胖
树
哈尔滨工业大学计算机科学与技术学院
哈尔滨工业大学计算机科学与技术学院
?6.网格形和环网形
?(1)3X3网格如下图所示,
?这是一种比较流行的结构，它已以
各种变体形式在 ILLiac 4,MPP,
DAP,CM-2和 Intel Paragon中得到
了实现
?N＝ nk结点的 k维网格的内部结点度为
2k；可知边界点度和角结点度
? 网格直径为 k(n-1)
哈尔滨工业大学计算机科学与技术学院
哈尔滨工业大学计算机科学与技术学院
?(2) Illiac 4网格
? 是一种可回绕连接的网格图，如上图所
示。假定 Illiac 4系统采用 8X8的这种
Illiac网格，则其结点度为常数 4，直径
为 7。
? N＝ 16＝ 4X4构型的 Illiac网格与图所示
的结点度为 4的带弦环在拓扑上是等效的。
? 一般说来，一个 nXn的 Illiac网格的直径
应为 d＝ n-1，它仅为纯网格直径的一半
哈尔滨工业大学计算机科学与技术学院
?(3) 环网形
? 上图所示,可看做是另一种直径更短的网
格。这种拓扑结构将环形和网格组合在
一起，并能向高维扩展。
? 环网形沿阵列每行每列都有环形连接。
一个 n× n二元环网的结点度为 4,
? 直径为 2[n／ 2]。
? 环网是一种对称的拓扑结构，所有附加
的回绕连接可使其直径较之网格结构减
少 1/2。
哈尔滨工业大学计算机科学与技术学院
?7.搏动式阵列
? 这是一类为实现确定算法而设计的多维流
水线阵列结构。下图所示就是为完成矩阵
--矩阵相乘而专门设计的搏动式阵列。此
例的内部结点度为 6。
? 静态搏动式阵列可在多个方向上使数据流
变成以流水线方式工作。商用 Intel Warp
系统 (Anaratone等,1986)就是用搏动式
结构设计而成的。自从 1978年 Kung和
Leiserson提出搏动式阵列后，它已成为
广泛研究的领域。
哈尔滨工业大学计算机科学与技术学院
哈尔滨工业大学计算机科学与技术学院
? 通过确定的互连和同步操作，搏动式
阵列可与算法的通信结构相匹配。针
对信号 /图象处理等特殊应用，可提
供更好的性能／价格比。
? 缺点：其结构的实用性有限，而且编
程难。
? 有兴趣的读者可参考 S,Y,Kung
(1988)关于用搏动式和波前沿结构实
现 VLSI阵列处理机的专著。
哈尔滨工业大学计算机科学与技术学院
?8.超立方体
?这是一种二元 n-立方体结构，它已
在 iPSC,nCUBE和 CM-2系统中得到
实现
?一个 n-立方体由 N＝ 2n个结点组成，
它们分布在 n维上，每维有两个结
点。 8个结点的 3-立方体如下图所
示
哈尔滨工业大学计算机科学与技术学院
哈尔滨工业大学计算机科学与技术学院
?9.带环立方体
?这种结构是从超立方体改进而来
的。如下图所示，一个 3-立方体
可改成带环 3-立方体 (CCC)。 构
成的办法是将 3-立方体的角结点
(顶角 )用一个结点环来代替。
哈尔滨工业大学计算机科学与技术学院
? 可以从一个 k-立方体构成一个有 n＝
2k个结点环的带环 k— 立方体；
? 如下图所示，所用的办法是用 k个结
点的环取代 k维超立方体的每个顶角。
? 一个 k— 立方体可变为 kX2k个结点的
k-CCC。
哈尔滨工业大学计算机科学与技术学院
? 如图所示 3-CCC的直径为 6，比原来 3-
立方体的直径大一倍。一般说来,k-
CCC的网络直径 2k,CCC的主要改进之
处即在其结点度为常数 3，与超立方
体的维数无关。
? 假设一超立方体有 N=2n结点。一个有
同样 N结点数的 CCC一定是由低维 k—
立方体组成，即 2n＝ k·2k，其中 k<n。
哈尔滨工业大学计算机科学与技术学院
? 例题,
? 对应于 n=6和 k=4的情况；
? 一个 64结点的 CCC可用 4结点的环取代
4— 立方体的角结点组成。
?CCC的直径为 2k＝ 8；
? 比 6-立方体的 6要长些。 CCC的结点度为 3，
比 6-立方体的结点度 6要小。
? 如果容许一定的时延，则 CCC是一种
构造可扩展系统的较好的结构。
哈尔滨工业大学计算机科学与技术学院
哈尔滨工业大学计算机科学与技术学院
?10.k元 n-立方体网络
?环形、网格形、环网形、二元
n-立方体 (超立方体 )和 ?网络都
是 k元 n-立方体网络系列的拓扑
同构体。
?下图所示是一种 4元 3-立方体网
络。
哈尔滨工业大学计算机科学与技术学院
哈尔滨工业大学计算机科学与技术学院
? 参数 n是立方体的维数,k是基数或者
说是沿每个方向的结点数 (多重性 )。
? 这两个数与网络中结点数 N的关系为,
N＝ kn,(k=N1/n,n＝ logkN)
哈尔滨工业大学计算机科学与技术学院
?k元 n-立方体的结点可用基数为 k的 n
位地址；
?A＝ a0a1a2… an来表示，其中 ai代表第
i维结点的位置。为简单起见，所有
链路都认为是双向的。
? 各结点之间的连线都是双向链路。
哈尔滨工业大学计算机科学与技术学院
?低维 k元 n-立方体称为环网；
?而高维二元 n-立方体则称为超立
方体。
哈尔滨工业大学计算机科学与技术学院
哈尔滨工业大学计算机科学与技术学院
? 总结,
? 大多数网络的结点度都小于 4，比较理想的
? 网络直径的变化范围很大，直径已不是一个严
重问题
? 链路数会影响网络价格，等分宽度将影响网络
的带宽
? 对称性会影响可扩展性和寻径效率，客观地说，
网络的总价格随节点度和链路度增大而上升。
直径小仍然是一种优点
? 结点间的平均距离可能是一种更好的量度指标
哈尔滨工业大学计算机科学与技术学院
