- 1 -
光超立方体的增强通信模式#
李显勇，杨小帆**
（重庆大学计算机学院，重庆 400044）
5 摘要：光网络具有良好的性能，有望取代电网络，实现并行处理。本文为理解光网络的通信
效率迈出了第一步。为了实现这一目标，引入了光网络的通信图。而且，为赋予了通信模式
的光网络定义了减小直径和增强连通度的概念。然后，确定了具有自然通信模式的光超立方
体的减小直径和增强连通度。结论表明，这一通信模式不仅显著地减少了传统电超立方体的
最大通信延迟，而且还极大地增强了它的容错能力。 10
关键词：光网络；增强通信模式；减小直径；增强连通度；超立方体
中图分类号：
An enhanced communication pattern for optical hypercubes
LI Xianyong, YANG Xiaofan 15
(College of Computer Science, Chongqing University, Chongqing 400044, )
Abstract: Due to prominent performance, optical networks are regarded as a promising alternative
to electrical networks for parallel processing. This paper aims to take the first step in
understanding the communication efficiency of optical networks. For that purpose, the notion of
communication graphs for optical networks is introduced. Furthermore, the reduced diameter and 20
enhanced connectivity of an optical network endowed with a communication pattern are defined.
Next, the reduced diameter and enhanced connectivity of an optical hypercube endowed with a
natural communication pattern are determined. The obtained results show that this communication
pattern not only reduces the maximum communication delay of the conventional electrical
hypercube significantly but improves its fault tolerance remarkably. 25
Key words: Optical network; enhanced communication pattern; reduced diameter; enhanced
connectivity; hypercube
0 引言
光网络具有许多迷人的性质，如极高的带宽、极低的能耗和延迟，因而，人们广泛认为30
它有希望替代电网络，实现并行处理[1,2]。由于在选定的发送器-接收器对之间可以充分利
用标准的光技术（如波分复用技术）建立专门的光路，那么在光连接的多计算机系统中，每
个处理器就能够同时发送多数据包给不同的处理器，极大地增强了网络的吞吐量；其中，芯
片上多处理器系统尤其如此，从而出现了芯片上光互连网络。这样，人们提出了各式各样的
光网络[3-13]。众所周知，超立方体具有良好的图理论性质和简单有效的路由策略，它时常35
被用作多计算机系统的互连网络[14-17]和光网络[5,8,9]。与电网络相比，光网络拥有更强的
通信能力，因而研究光网络的通信效率具有现实意义。然而，就我们所知，这方面的研究工
作几乎没有。
本文为理解光网络的通信效率迈出了第一步。为了获得光网络的通信模式，将引入通信
图概念。进而，在给定的通信模式下，将定义光网络的减小直径和增强连通度。在自然的通40
信模式（即 r -通信模式）下，确定光超立方体的减小直径和增强连通度。结果表明，光超
- 2 -
立方体这种增强通信模式不仅显著地降低了传统超立方体的最大通信延迟，而且极大地提高
了它的容错能力。
本文组织结构如下：第 1 节引入新的符号和术语；第 2 节明确给出并证明光超立方体的
结论；最后，在第 3 节中总结本文的主要工作，并介绍下一步将要进行的工作。 45
1 新的符号和术语
给定图G，设 ( )d G 表示它的直径， ( )G 表示它的连通度。基本的图理论术语和符号
见文献[18]。光互连网络可以抽象为图 ( , )G V E ，其中每个顶点代表它的处理器单元，处
理器的局部内存由光路由器连接。两个顶点之间有边相连接，当且仅当连接它们的光路由器
之间能够建立一条直接光路。在光互连网络中，一对不相邻的结点之间可以建立光路，该光50
路是通过适当地设置该光路上的光路由器的状态来实现的，这样就增强了光互连网络的通信
能力。
为了获得光网络的通信能力，下面我们引入通信模式的概念。
定义 光网络 ( , )G V E 的通信模式是所有结点对的集合，该结点对之间容许建立光路，
该通信模式记为C。对于通信模式C，光网络G的通信图定义为 ( , )CG V C 。 55
在设计光网络的并行算法时，由于波长资源有限，因此在所有结点对之间建立光路是不
可行的。但是，人们期望的仅仅是在相当靠近的结点对之间建立光路。
为了获得光网络的特征，下面再引入一个新的概念。
定义 光网络 ( , )G V E 的 r -通信模式是所有结点对的集合，该结点对之间的距离小于或
等于 r，该 r -通信模式记为 rC 。对于 r -通信模式 rC ，光网络G的 r -通信图定义为60
( , )r rG V C 。
网络的直径是结点对之间的最大通信延迟的一种度量。对于光网络，不相邻的结点对之
间建立光路有助于减小它的直径，下面引入减小直径的概念。
定义 在通信模式C下，光网络 ( , )G V E 的减小直径定义为 ( ) ( )C Cd G d G 。
定义 在 r -通信模式下，光网络 ( , )G V E 的 r -直径定义为 ( ) ( )rrd G d G 。 65
连通度是网络容错的一种度量，反应了在网络存在故障元件时正常运行的能力. 对于光
网络，不相邻的结点对之间建立光路，增强了网络的连通度，下面我们引入增强连通度的概
念。
定义 在通信模式C下，光网络 ( , )G V E 的增强连通度定义为 ( ) ( )C CG G 。
定义 在 r -通信模式下，光网络 ( , )G V E 的 r -连通度定义为 ( ) ( )rr G G 。 70
n -维超立方体，记为 nQ ，是一个具有 2
n 个顶点的图，其中顶点是用 n -长度的0-1字串
标记的，两结点间相邻当且仅当标号仅一位不相同。
定义 光n -维超立方体的 r -通信图，记为 rnQ ，可以如下递归地建立： 1
rQ 即是 1Q ；对于
2n ， rnQ 是由两个不交的 1
r
nQ 通过执行下面的操作：添加前缀0到一 1
r
nQ 中所有结点标号，
得到图 10
r
nQ ；添加前缀1到另一 1
r
nQ 中的所有结点标号，得到图 11
r
nQ ；并且在结点75
1 2 1 10 (0 )
r
n nu a a a V Q 和结点 1 2 1 11 (1 )
r
n nv b b b V Q 之间添加一条边，当且仅当
结点 1 2 1na a a 和结点 1 2 1nb b b 之间至多有 1r 位不同。边被称为立方体边或非立方体
- 3 -
中国科技论文在线
边依赖于 1 2 1na a a 和 1 2 1nb b b 是否一致。
2
2Q ，
2
3Q 和
2
4Q 如下图所示。
80
图1： 22Q ，
2
3Q 和
2
4Q ，其中虚边表示添加的边。
Figure 1： 22Q ,
2
3Q and
2
4Q , where the complementary edges are shown with dashed edges.
2 光 n -维超立方体的 r -直径和 r -连通度
本节将确定光超立方体的 r -直径和 r -连通度。
引理 rnQ 是
1 2
n n n
r
-正则的，具有 2n 个顶点。 85
定理 ( )r n
n
d Q
r
。
证明 对于 rnQ 中的两个标号仅仅 k位不同的结点来说，容易建立一个连接它们的
k
r
-长路。
因此，
1
( ) ( ) max .rr n n
k n
k n
d Q d Q
r r
另一方面，对于 rnQ 中的两个结点 0
nu 和 1nv 来说，每一个连接它们的路径长度都大于90
等于
n
r
，因而 ( ) ( )rr n n
n
d Q d Q
r
。因此，结论得证。■
引理 ( ) 2 1nn nQ 。
证明 ( ) ( ) ( ) 2 nn n n nQ Q K ■
引理 对于 r n ，
( )
1 2
r n
n n n
Q
r
。
证明 对n进行归纳。对于 3n ，断言显然成立。假设断言对于 3n k 成立。设 S是95
1
r
kG Q 的点子集，
1 1 1
| | 1
1 2
k k k
S
r
。因此，证明 \G S连通就足够
- 4 -
中国科技论文在线
了。为了简洁起见，记 0 0
r
kG Q ， 1 1
r
kG Q ， 0 0( )S S V G ， 1 1( )S S V G 。不失一
般性，假设 0 1| | | |S S 。因此，容易验证
0
1 1 1
1
1 2| |
| | .
1 22 2
k k k
k k krS
S
r
根据归纳假设， 0 0\G S 是连通的。考虑下面两种情况：
100
情况1
0
| | .
1 2 1
k k k
S
r
由于 1G 中的每一个顶点在 0G 中都有
1
1 2 1
k k k
r
个邻点，因而 1 1\G S 中的每一个顶点在 0 0\G S 中有一个邻点。
所以 \G S是连通的。
情况2
0
| | .
1 2 1
k k k
S
r
因此，
1 0| | | | | |
1 1 1
1
1 2 1 2 1
.
1 2
S S S
k k k k k k
r r
k k k
r
105
根据归纳假设， 1 1\G S 仍然是连通的。还需考虑下面两种子情况：
情况
1
.
2
k
r
因此，
0
1 1 1
0 1 1
| ( ) | 2
2
1 1 1
0 1
| | .
k
k k k
k
V G
k k k
r
S
所以 1 1\G S 与 0 0\G S 之间有边相连接，即 \G S是连通的。
情况
1
.
2
k
r
如果 1 1\G S 是空图，或者 1 1\G S 与 0 0\G S 之间有边相连接，则 \G S是110
连通的。因此，假设 1 1\G S 不是空图，且 1 1\G S 与 0 0\G S 之间没有边相连接。那么， 1 1\G S
中的每个顶点的标号与 0 0\G S 中的任何顶点标号至少有 r位不同，因而，
1 11 | ( ) \ | .
2 1 2
k k k
V G S
r r k
所以，
1
2
k
r
， 1| | 2 1
kS 。对于 1 1\G S 中的顶点u ，由于u 在 0 0\G S 中有
- 5 -
中国科技论文在线
1
0 1
2
k
k k
k
个邻点，因此，
115
0 1| | | | | |
1
1 1
21
1 2
2
,1
0 1
2
k
S S S
k
k k
k
k
k k
k
即
2 ,1
1 2
2
k
k
k k
k
这与事实
2 ,1
1 2 0 1
2
k
k
k k k k k
k
k
120
矛盾。
综合上面的讨论，断言对于 1n k 成立。根据归纳假设，可得断言对于所有 n都成
立。■
合并引理和，可得
定理 ( )
1 2
r n
n n n
Q
r
。 125
3 结论
为了理解光网络的增强通信效率，本章引入了通信图的概念。同时，定义了光网络的 r -
直径和 r -连通度。进而，确定了光超立方体的 r -直径和 r -连通度。结论表明，引入的这种
增强通信模式显著地减少了传统超立方体的最大通信延迟，极大地提高了它的容错能力。
沿着这个方向，大量的工作有待研究。首先，计算其它光网络的 r -直径和 r -连通度。130
其次，引入其它衡量光网络性能的标准。再次，设计和分析适合于芯片上多处理机的新颖的
光网络。最后，传统的并行算法，包括并行排序、并行矩阵乘法、并行离散傅里叶变换、线
性系统并行求解适用于光网络。
[参考文献] (References)
[1] Goodman J W, Leonberger F J, Kung S Y, Athale R A. Optical interconnections for VLSI systems [J]. 135
Proc. IEEE. 1984, 72(7): 850-866.
[2] Webb B, Louri A. A class of highly scalable optical crossbar connected interconnection networks (SOCNs) for
parallel computing [J]. IEEE Trans. Parallel Distrib. Syst. 2000, 11(5): 444-458.
[3] Al-Ayyoub A, Ould-Khaoua M, Day K. On the performance of parallel matrix factorisation on the
hypermesh [J]. J. Supercomput, 2001, 20(1): 37-53. 140
[4] Day K. Optical transpose k-ary n-cube networks [J]. J. Syst. Architect, 2004, 50(11): 697-705.
[5] Louri A, Furlonge S, Neocleous C. Experimental demonstration of the optical multi-mesh hypercube: scalable
- 6 -
中国科技论文在线
interconnection network for multiprocessors and multicomputers,[J]. Appl. Opt. 1996, 35(35): 6909-6919.
[6] Loucif S, Ould-Khaoua M, Al-Ayyoub A. Hypermeshes: Implementation and performance [J]. J. Syst.
Architect. 2002, 48(1-3): 37-47. 145
[7] Louri A, Furlonge S. Feasibility study of a scalable optical interconnection network for massively parallel
processing systems [J]. Appl. Opt. 1996, 35(8): 1296-1308.
[8] Louri A, Sung H. An optical multi-mesh hypercube: a scalable optical interconnection network for massively
parallel computing [J]. J. Lightwave Technol. 1994, 12(4): 704-716.
[9] Moraveji R, Sarbazi-Azad H, Nayebi A, Navi K. Modeling the effects of hot-spot traffic load on the 150
performance of wormhole-switched hypermeshes [J]. Comput. Electr. Eng. 2011, 37: 1-23.
[10] Louri A, Sung H. Scalable optical hypercube-based interconnection network for massively-parallel
Computing [J]. Appl. Opt. 1994, 33(32): 7588-7598.
[11] Ould-Khaoua M, Mackenzie L M. On the design of hypermesh interconnection networks for multicomputer
[J]. J. Syst. Architect. 2000, 46(9): 779-792. 155
[12] Rodríguez-Salazar F, Barker J R. Hamming hypermeshes: High performance interconnection networks for
pin-out limited systems [J]. Perform. Evaluation, 2006, 63(8): 759-775.
[13] Szymanski T. "Hypermeshes": optical interconnection networks for parallel computing [J]. J. Parall. Distrib.
Comput. 1995, 26(1): 1-23.
[14] Saad Y, Schultz M H. Topological properties of hypercubes [J]. IEEE Trans. Comput. 1988, 37(7): 867-872. 160
[15] Yang X, Evans D J, Megson G M, Lai H. On the maximal connected component of hypercube with faulty
vertices [J]. Int. J. Comput. Math. 2004, 81(5): 515-525.
[16] Yang X, Evans D J, Megson G M. On the maximal connected component of hypercube with faulty vertices (II)
[J]. Int. J. Comput. Math. 2004, 81(10): 1175-1185.
[17] West D B. Introduction to Graph Theory [M]. Prentice-Hall, Inc., 2001. 165
[18] Yang X, Evans D J, Megson G M. On the maximal connected component of hypercube with faulty
vertices (III) [J], Int. J. Comput. Math. 2006, 83(1): 27-37.
