[go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

The divide-and-swap cube: a new hypercube variant with small network cost

  • Published:
The Journal of Supercomputing Aims and scope Submit manuscript

Abstract

The hypercube is one of the most popular interconnection networks. Its network cost is \(O(n^2)\). In this paper, we propose a new hypercube variant, the divide-and-swap cube \(\textit{DSC}(n)\,(n=2^d,\,d\ge 1)\), which reduces the network cost to \(O(n \log n)\) while maintaining the same number of nodes and the same asymptotic performances for fundamental algorithms such as the broadcasting. The new network has nice hierarchical properties. We first show that the diameter of \(\textit{DSC}(n)\) is lower than or equal to \(\frac{5n}{4}-1\). However, unlike the hypercube of dimension n whose degree is n, the node degree of the network is \(\log n + 1\), resulting in a network cost of \(O(n \log n)\). We then examine the one-to-all and all-to-all broadcasting times of \(\textit{DSC}(n)\), based on the single-link-available and multiple-link-available models. We also present an upper bound on the bisection width of the \(\textit{DSC}(n)\) and show that \(\textit{DSC}(n)\) is Hamiltonian. Finally, we introduce the folded divide-and-swap cube, \(\textit{FDSC}(n)\), a variant of the \(\textit{DSC}(n)\) and study its many properties including its hierarchical structure, routing algorithm, broadcasting algorithms, bisection width, and its Hamiltonicity. All the broadcasting algorithms presented in this paper are asymptotically optimal.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6

Similar content being viewed by others

References

  1. Abraham S, Padmanabhan K (1991) The twisted cube topology for multiprocessors: a study in network asymmetry. J Parallel Distrib Comput 13(1):104–110

    Article  Google Scholar 

  2. Akers SB, Harel D, Krishnamurthy B (1989) A group-theoretic model for symmetric interconnection network. IEEE Trans Comput 38(4):555–565

    Article  MathSciNet  MATH  Google Scholar 

  3. Arabnia HR, Oliver MA (1987) A transputer network for the arbitrary rotation of digitised images. Comput J 30(5):425–433

    Article  Google Scholar 

  4. Arabnia HR, Smith JW (1993) A reconfigurable interconnection network for imaging operations and its implementation using a multi-stage switching box. In: Proceedings of the 7th Annual International High Performance Computing Conference. The 1993 High Performance Computing: New Horizons Supercomputing Symposium, Calgary, Alberta, Canada, pp 349–357

  5. Arabnia HR, Taha TR (1998) A parallel numerical algorithm on a reconfigurable multi-ring network. J Telecommun Syst 10:185–203

    Article  Google Scholar 

  6. Bornstein CF, Litman A, Maggs BM, Sitaraman RK, Yatzkar T (2001) On the bisection width and expansion of butterfly networks. Theory Comput Syst 34:491–518

    Article  MathSciNet  MATH  Google Scholar 

  7. Chang CP, Wang JN, Hsu LH (1999) Topological properties of twisted cube. Inf Sci 113(1–2):147–167

    Article  MathSciNet  MATH  Google Scholar 

  8. Choudum SA, Sunitha V (2002) Augmented cubes. Networks 40(2):71–84

    Article  MathSciNet  MATH  Google Scholar 

  9. Cull P, Larson SM (1995) The Möbius cubes. IEEE Trans Comput 44(5):647–659

    Article  MathSciNet  MATH  Google Scholar 

  10. De Azevedo MM, Bagherzadeh N (1995) Broadcasting algorithms for the star-connected cycles interconnection network. J Parallel Distrib Comput 25:209–222

    Article  Google Scholar 

  11. Díaz J, Serna MJ, Wormald MC (2007) Bounds on the bisection width for random \(d\)-regular graphs. Theo Comput Sci 382:120–130

    Article  MathSciNet  MATH  Google Scholar 

  12. Duh DR, Chen GH, Fang JF (1995) Algorithms and properties of a new two-level network with folded hypercubes as basic modules. IEEE Trans Parallel Distrib Syst 6(7):714–723

    Article  Google Scholar 

  13. Efe K (1991) A variation on the hypercube with lower diameter. IEEE Trans Comput 40(11):1312–1316

    Article  Google Scholar 

  14. Efe K (1992) The crossed cube architecture for parallel computing. IEEE Trans Parallel Distrib Syst 3(5):513–524

    Article  Google Scholar 

  15. El-Amawy A, Latifi S (1991) Properties and performance of folded hypercubes. IEEE Trans Parallel Distrib Syst 2(1):31–42

    Article  Google Scholar 

  16. Fan J, Jia X (2007) Embedding meshes into crossed cubes. Inf Sci 177(15):3151–3160

    Article  MATH  Google Scholar 

  17. Garey MR, Johnson DS (1979) Computers and intractability: a guide to the theory of NP-completeness. Freeman, San Francisco

    MATH  Google Scholar 

  18. Ghose K, Desai KR (1995) Hierarchical cubic networks. IEEE Trans Parallel Distrib Syst 6(4):427–436

    Article  Google Scholar 

  19. Harary F, Hayes JP, Wu HJ (1988) A survey of the theory of hypercube graphs. Comput Math Appl 15(4):277–289

    Article  MathSciNet  MATH  Google Scholar 

  20. Hsu LH, Lin CK (2008) Graph theory and interconnection networks. CRC Press, Boca Raton

    Book  MATH  Google Scholar 

  21. Johnson SL, Ho CT (1989) Optimal broadcasting and personalized communication in hypercubes. IEEE Trans Comput 38(9):1249–1268

    Article  MathSciNet  MATH  Google Scholar 

  22. Kim JS, Kim SW, Qiu K, Lee HO (2014) Some properties and algorithms for the hyper-torus network. J Supercomput 69(1):121–138

    Article  Google Scholar 

  23. Li TK, Tan JJM, Hsu LH, Sung TY (2001) The shuffle-cubes and their generalization. Inf Process Lett 77(1):35–41

    Article  MathSciNet  MATH  Google Scholar 

  24. Li K, Mu Y, Li K, Min G (2013) Exchanged crossed cube: a novel interconnection network for parallel computation. IEEE Trans Parallel Distrib Syst 24(11):2211–2219

    Article  Google Scholar 

  25. Loh PKK, Hsu WJ, Pan Y (2005) The exchanged hypercube. IEEE Trans Parallel Distrib Syst 16(9):866–874

    Article  Google Scholar 

  26. Mendia VE, Sarkar D (1992) Optimal broadcasting on the star graph. IEEE Trans Parallel Distrib Syst 3(4):389–396

    Article  MathSciNet  Google Scholar 

  27. Mkwawa IM, Kouvatsos DD (2003) An optimal neighborhood broadcasting scheme for star interconnection networks. J Interconnect Netw 4(1):103–111

    Article  Google Scholar 

  28. Monien B, Preis R (2006) Upper bounds on the bisection width of 3- and 4-regular graphs. J Discrete Algorithms 4(3):475–498

    Article  MathSciNet  MATH  Google Scholar 

  29. Parhami B, Kwai DM (2001) A unified formulation of honeycomb and diamond networks. IEEE Trans Parallel Distrib Syst 12(1):74–80

    Article  Google Scholar 

  30. Rahman MS, Kaykobad M (2005) On Hamiltonian cycles and Hamiltonian paths. Inf Process Lett 94(1):37–41

    Article  MathSciNet  MATH  Google Scholar 

  31. Tang KW, Kamoua R (2007) An upper bound for the bisection width of a diagonal mesh. IEEE Trans Comput 56(3):429–431

    Article  MathSciNet  MATH  Google Scholar 

  32. Wang D (2001) Embedding Hamiltonian cycles into folded hypercubes with faulty links. J Parallel Distrib Comput 61(4):545–564

    Article  MATH  Google Scholar 

  33. Yang XF, Evans DJ, Megson GM (2005) The locally twisted cubes. Int J Comput Math 82(4):401–413

    Article  MathSciNet  MATH  Google Scholar 

  34. Yun SK, Park KH (1998) Comments on “hierarchical cubic networks”. IEEE Trans Parallel Distrib Syst 9(4):410–414

    Article  Google Scholar 

  35. Zhou W, Fan J, Jia X, Zhang S (2012) The spined cube: a new hypercube variant with smaller diameter. Inf Process Lett 111(12):561–567

    Article  MathSciNet  MATH  Google Scholar 

  36. Zhu Q, Liu SY, Xu M (2008) On conditional diagnosability of the folded hypercubes. Inf Sci 178(4):1069–1077

    Article  MathSciNet  MATH  Google Scholar 

Download references

Acknowledgements

This research was supported by Basic Science Research Program through the National Research Foundation of Korea(NRF) funded by the Ministry of Education (2017R1D1A3B03032173). We are grateful to the anonymous referees for their helpful comments and suggestions.

Author information

Authors and Affiliations

  1. Department of Mathematics and Physics, North Carolina Central University, Durham, NC, 27707, USA

    Jong-Seok Kim

  2. Department of Computer Science, Kennesaw State University, Marietta, GA, 30060, USA

    Donghyun Kim

  3. Department of Computer Science, Brock University, St. Catharines, ON, Canada

    Ke Qiu

  4. Department of Computer Education, Sunchon National University, Sunchon, Jeonnam, 57922, South Korea

    Hyeong-Ok Lee

Authors
  1. Jong-Seok Kim
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Donghyun Kim
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Ke Qiu
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Hyeong-Ok Lee
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Hyeong-Ok Lee.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Kim, JS., Kim, D., Qiu, K. et al. The divide-and-swap cube: a new hypercube variant with small network cost. J Supercomput 75, 3621–3639 (2019). https://doi.org/10.1007/s11227-018-2712-z

Download citation

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s11227-018-2712-z

Keywords

Search

Navigation