新型并行计算系统的研制依赖于对新型互连网络结构及其性质的研究.超立方体及其变型——Mobius立方体两者都具有优点,也具有缺点.本文给出了在超立方体与Mobius立方体的顶点之间的一种连接,从而得到一种称为HMm-立方体的新型网络,证明了HMn-立方体不仅保持了超立方体和Mobius立方体的低顶点度数和高连通度以及其直径至多比Mobius立方体大2的性质,而且它克服了超立方体对圈模拟能力
维普资讯 doc.guandang.net
20 0 7年 9月 第 3卷第 5期 1
安徽大学学报 (自然科学版 ) J u n l fAn u n v ri tr lS in eEdt n o r a h iU ie s y Nau a ce c i o o t i
S ptmbe 00 e e r2 7 Vo . . 131 No 5
关于超立方体与 M iu立方体的连接 tis b 张修梅 (海杉达学院计算机学院,上上海 2 10 ) 0 29
摘
要:新型并行计算系统的研制依赖于对新型互连网络结构及其性质的研究 .超立方体及其变
型—— M u立方体两者都具有优点,曲is也具有缺点.本文给出了在超立方体与 M ̄is b立方体的顶点之 u间的一种连接,从而得到一种称为 H M一立方体的新型网络,明了 H证 M一立方体不仅保持了超立方体和 M b s 6 i立方体的低顶点度数和高连通度以及其直径至多比 M ̄is u i u立方体大 2的性质, b而且它克服了超立方体对圈模拟能力的不足. 关键词:超立方体; bu立方体; a io连通 M ̄is H mln t 中图分类号: 17 0 5文献标识码: A文章编号:0 0— 12 2 0 )5— 0 2 3 10 2 6 (0 7 0 0 1—0
互连网络的性质是决定整个并行计算系统性能优劣的重要因素,因此,对互连网络结构及其性质的研究是并行计算系统研究的一个重要课题 .今为止,迄文献中已经提出了很多种互连网络,中超立方其 体以其低直径、高连通度、对称性等许多良好的性质已被用作多种并行机中处理器连接的结构 .然而,超立方体并非各种性质都最优的互连网络,改变超立方体的某些连接而得到一个具有最高连通度和更小直径的互连网络是可能的. tis方体¨由超立方体获得的变型,具有与超立方体相同的连通 Miu立 b 它
度,而它的直径都大约是超立方体的一半,这表明,某些 SM I D算法如矩阵乘法、排序等所花费的通讯时问步大约是超立方体的一半 .实上,立方体的变型 Miis事超 Su立方体已经引起了国际上许多研究者的 b 研究兴趣,已被证明 Ha l n性质和圈等方面的性能都比超立方体强 .它 mio t当然, ̄is方体也有 Mt u立 b 一
些比超立方体差的性质, Mtis如 i
u立方体不像超立方体那样是边对称的.文将给出在超立方体与 b本
Mt is方体的顶点之问的一种连接, iu立 b因此得到一种称为 H M一方体的新型网络 .立
1定义与引理 设 G是一个图, ( ) E G, G,( ), G V G, ( ) D( ) 6 G, ( )和 A G分别表示 G的顶点集、集、 ( ()边直径、最小顶
点度数、顶点连通度和边连通度 .于对
VG, ( ) G—V表示图 G中由顶点子集 V G)一V导出的子图. (
设“∈ V G) G中“与之间的距离 ds G,,)定义为 G中顶点“与问最短路径的长度., (, i(“ G的直径定义为 D( )=ma ( i(,,)l,∈V G) . G中的任意两个不同顶点问存在一条 Ha l n, G x ds G““ ( )若 mio路 t则称 G是 H mio a l n连通的.斗 P(, t, H )表示 H与之间的一条 Ha l n路 . G与 G是两个图, G} j mio t设 若
与 G同构, G兰 G. 记,同构的图可以认为是相同的图.维 Mt is n i u立方体 MQ都是具有 2个顶点的n一 b 正则图,它们的每个顶点都标有一个长度为 n的二进制串(为该顶点的地址 )本文将用顶点的地址表称, 示相应的顶点.面给出 Q一和 MQ之间的一种连接以及由该连接所得到的图(为 H立方体 )下 称 M .
定义对于 1≤ n≤ 3 n维 H, M一立方体为 n维 Mtis方体 MQ .于 n≥4, H ̄u立 b对 n维 M一立方体由一个 ( n一1维超立方体 Q和一个 ( ) n一1 )维 Mt is方体 Q一按下述方式相互连接而成: i u立 b
在 Q的每个顶点的最低位左边添加一个 0 并将 Q记为Q在MQ的每个顶点的最低位左边添 :, 加个 1将该 Q记为 Q并, 若再在一的每个顶点的最低位左边添加一个 0或 1,记为 ( )则 0 或 1一Q一)显然有 0一Q ( 1一Q一 Q若再在Q一的每个顶点的最低位左边添加一 Q一( o,, o或, ): 一
个 0或 1, ( )则记为 0一 I ( 1一Q一)显然有 0一Q一或 1。 Q对于=0。 ∈ Q,或一 , , (一Q一) x… 收稿日期:0
7— 3—2 20 0 5
基金项目:海高校选拔培养优秀青年教师科研专项基金资助项目.上
作者简介:张修梅 (9 8一)女, 17,安徽天长人,二』海杉达学院讲师,硕士

关于超立方体与Mobius立方体的连接_IT/计算机_专业资料。第 八届中国 青年运筹信息管 理学者大 会论文集桂林 ,20 8月1-2日,第2227页06年826-6 关于超立方体...
关于超立方体与Mobius立方... 6页 5财富值 超立方体 10页 1财富值 超... 关于超立方体与交叉立方体的交叉连接 樊建席刘昕王庆红 青岛大学信息工程学院 ...
已经被用作多种并行机中处理器连接的拓扑结构并引起了...
关于超立方体与交叉立方体的交叉连接樊建席 刘听 王庆 红 青岛 信息工 大学 程学院 青岛267601Ea: de. .unmijfudclx@g 摘要 新型并行计算系统的研制依赖于对...
基于超立方体与交叉立方体的交叉连接的HC-立方体网络_专业资料。给出了在超立方体与交叉立方体的顶点之间的一种连接——交叉连接,从而得到一种称为HC-立方体的新型...
基于超立方体的双Petersen图连接的互联网络研究_专业资料。基于Petersen图的短直径与超立方体节点的高可连接性,提出了一种新型的互连网络拓扑结构———基于超立方体的...
关于超立方体与交叉立方体... 5页 5财富值 关于超立方体与Mobius立方... 6...维坐标按立方体的定义取值并在所得数组进行按立方 体定 义的方式连边 , 显然...
基于交叉立方体环连接的Petersen图互联网络研究_专业资料。交叉立方体是近年来提出... 基于超立方体的双Peters... 7人阅读 6页 2.00 基于k-Petersen图的超...
它的顶点是以 0 或 1 为坐标的 n 重有序数组,两个顶点为一条边连接,当... 关于超立方体与Mobius立... 6页 2下载券 交叉超立方体的转发指数 41页 7...
k-元n-立方体的路和圈_数学_自然科学_专业资料。...立方体网络的连接方 式 .对于互连网络来说 ,有一类...自从那以后,关于超立方体上经过指定边的哈密顿路和圈...
热门文档