文档下载 文档下载导航
设为首页 | 加入收藏
搜索 请输入内容:  
 导航当前位置: 文档下载 > 所有分类 > 关于超立方体与Mobius立方体的连接
侵权投诉

关于超立方体与Mobius立方体的连接

新型并行计算系统的研制依赖于对新型互连网络结构及其性质的研究.超立方体及其变型——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立方体的连接

第1页

你可能喜欢

热门文档

相关文档

站点地图 | 文档上传 | 侵权投诉 | 手机版
本站所有资源均来自互联网,本站只负责收集和整理,均不承担任何法律责任,如有侵权等其它行为请联系我们.
文档下载 Copyright 2013 doc.guandang.net All Rights Reserved.  -  email