互连网络的m层二进制图模型

doi:10.11896/j.issn.1002-137X.2017.11A.065

摘要/Abstract

摘要： 超立方体、交叉立方体、Mbius立方体以及折叠立方体等都是著名的互连网络。它们有一个共同的弱点:其结点度随着网络规模(结点数)的增大而增大。这意味着依此互连网络设计出的超级计算机的扩展性很差。能否构建出既能保持它们已有特性又能使结点度固定的互连网络呢？现提出互连网络的m层二进制图模型,并依此模型设计了分别由超立方体、交叉立方体、Mbius立方体以及折叠立方体等生成的m层超立方体、m层交叉立方体、m层Mbius立方体以及m层折叠立方体。特别地,m层超立方体有一个特点:结点度可以不随网络规模的增大而增大,而且具有超立方体的特性。另外,还提出了由已知图生成m层图的概念。

关键词: m层超立方体,m层交叉立方体,m层Mbius立方体,m层折叠立方体,m层二进制图

Abstract: All of the hypercube,crossed cube,Mbius cube and Folded cube are famous interconnection networks.They have a common weak:its degree of node in Hypercube (crossed cube,Mbius cube or folded cube) increases with the increase of network scale (number of nodes).It means that the scalability of the super computer whose interconnection nework is Hypercube is weak.Can we design the interconnection network that has features of Hypercube and fixed degree of nodes?In this paper,we proposed m-layers binary graph model for interconnection networks.From the model,we designed new interconnection networks-m-layers hypercube,m-layers crossed cube,m-layers mbius cube and m-layers folded cube.Especially,m-layers hypercube have a feature:the degree of node in m-layers hypercube can not increase with the increase of newtork scale and it almost has all features of hypercube.In addition,we proposed the concept of m-layers graph generated by given graph.

Key words: M-layers hypercube,M-layers crossed cube,M-layers Mbius cube,M-layers folded cube,M-layers binary graph

师海忠,师越. 互连网络的m层二进制图模型[J]. 计算机科学, 2017, 44(Z11): 308-311. https://doi.org/10.11896/j.issn.1002-137X.2017.11A.065

SHI Hai-zhong and SHI Yue. M-layers Binary Graph Model for Interconnection Networks[J]. Computer Science, 2017, 44(Z11): 308-311. https://doi.org/10.11896/j.issn.1002-137X.2017.11A.065

参考文献

[1] 王鼎兴,陈国良.互连网络结构分析[M].北京:科学出版社,1990.
[2] BERMOND J C,PEYRAT C.De Brujin and Kautz networks:A competitor for the hypercube? [M]∥ Andre F,Verjus J P,eds.Hypercube and Distributed Computer.North-Holland:Elservier Science Publishers,1984:300-343.
[3] 徐俊明.组合网络理论[M].北京:科学出版社,2007.
[4] XU J M.Combinatorial Theory in Networks[M].Science Press,Beijing,2013.
[5] ANDRE F,VERJUS J P.Hypercubes and Distributed Compu-ters[M].Amsterdam,New York,Oxford:North-Halland,1989.
[6] LEIGHTON F T.Introduction to Parallel Algorithms and Ar-chitectures[M]∥Introduction to Parallel Algorithms and Architectures:Rings,Trees,Hypercubes.San Mateo,California:Morgan Kaufman Publishers,1992.
[7] EFE K.A Variation on the hypercube with lower diameter[J].IEEE Transactions on Computers,1991,40(11):1312-1316.
[8] EFE K.The crossed cube architecture for parallel computing[J].IEEE Transactions on Parallel and Distributed Systems,1992,3(5):31-42.
[9] CULL P,LARSON S M.The Mbius cubes[J].IEEETransations on Computers,1995,44(5):647-659.
[10] EL-AMAWY A,LATIFI S.Properties and performance of folded hypercubes[J].IEEE Transactions on Parallel and Distributed Systems,1991,2(3):31-42.
[11] KULASINGHE P,BETTAYEB S.Embedding binary tree into crossed cubes[J].IEEE Transactions on Computers,1995,44(7):923-929.
[12] 马美杰,徐俊明.Edeg-pancyclicity of crossed cubes[J].中国科学技术大学学报,2005,35(3):329-333.
[13] FAN J X,LIN X L,JIA X H.Node-pancyclicity and edge-pancyclicity of crossed cubes[J].Information Processing Letters,2005,93(3):133-138.
[14] XU M,XU J M.Edge-pancyclicity of Mbius cubes[J].Information Processing Letters,2005,9(4):136-140.
[15] HUANG W T,CHEN W K,CHEN C H.Pancyclicity of Mbius cubes[C]∥Proceedings of the Ninth International Conference on Parallel and Distributed Systems(ICPADS’02).2002:591-596.
[16] FAN J X.Hamilton-connectivity and cycle-embedding of Mbius cubes [J].Information Processing Letters,2005,93(3):133-138.
[17] SIM E,YEBRA J L A.The vulnerability of diameter of folded cubes[J].Discrete Mathematics,1997,174(3):317-302.
[18] XU J M,L M.On restricted edge-connectivity of regular di-graphs[J].Taiwan Journal of Mathematics,2005,9(4):661-670.
[19] 师海忠.互连网络的新模型:多部群论模型[J].计算机科学,2013,40(9):21-24.
[20] 师海忠.正则图连通圈:多种互连网络的统一模型[C]∥中国运筹学会第十届学术交流会论文集.2010:202-208.
[21] 张欣,师海忠.交叉立方体连通圈网络的Hamilton 分解[J].软件,2015,36(8):92-98.
[22] 王海锋,师海忠.Mbius 超立方体网络的Hamilton 分解[J].软件,2015,36(10):85-89.

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed