Computer Science ›› 2017, Vol. 44 ›› Issue (Z11): 308-311.doi: 10.11896/j.issn.1002-137X.2017.11A.065

Previous Articles     Next Articles

M-layers Binary Graph Model for Interconnection Networks

SHI Hai-zhong and SHI Yue   

  • Online:2018-12-01 Published:2018-12-01

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

[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.

No related articles found!
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!