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

The decycling problem in hierarchical cubic networks

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

Abstract

Hierarchical cubic networks (HCN) have been introduced as interconnection networks for massively parallel systems. This topology is based on hypercubes, and thus benefits from their desirable properties such as a small diameter. However, an HCN supersedes a hypercube in many ways: for instance, the number of links per node in an HCN is significantly lower than that of a hypercube of the same size, while their diameters remain similar. In this paper we address the decycling problem in an HCN. It consists in finding a node set of minimum size such that excluding these nodes from the network ensures an acyclic (cycle-free) network. This is a critical problem with many applications, and notably in parallel computing as it allows for the prevention of resource allocation issues such as deadlocks, livelocks and starvations. We propose an efficient algorithm generating in an \(n\)-dimensional HCN a decycling set of at most \(2^{2n-1} - (2^{2n-2}/n + \lfloor 2^{n-1}/n\rfloor )\) nodes.

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

Similar content being viewed by others

References

  1. Bau S, Beineke LW (2002) The decycling number of graphs. Aust J Comb 25:285–298

    MATH  MathSciNet  Google Scholar 

  2. Bau S, Beineke LW, Liu Z, Du G, Vandell RC (2001) Decycling cubes and grids. Utilitas Mathe 59:129–137

    MATH  MathSciNet  Google Scholar 

  3. Beineke LW, Vandell RC (1997) Decycling graphs. J Graph Theory 25(1):59–77

    Article  MATH  MathSciNet  Google Scholar 

  4. Bossard A, Kaneko K (2012) Node-to-set disjoint-path routing in hierarchical cubic networks. Comput J 55(12):1440–1446

    Article  Google Scholar 

  5. Festa P, Pardalos PM, Resende MGC (1999) Feedback set problems. Handbook of Combinatorial, Optimization A, pp 209–258

  6. Fu JS, Chen GH, Duh DR (2002) Node-disjoint paths and related problems on hierarchical cubic networks. Networks 40(3):142–154

    Article  MATH  MathSciNet  Google Scholar 

  7. Gargano L, Vaccaro U, Vozella A (1993) Fault-tolerant routing in the star and pancake interconnection networks. Inf Process Lett 45(6):315–320

    Article  MATH  MathSciNet  Google Scholar 

  8. Ghose K, Desai KR (1995) Hierarchical cubic network. IEEE Trans Parallel Distrib Syst 6(4):427–435

    Article  Google Scholar 

  9. Karp R (1972) Reducibility among combinatorial problems. In: Thatcher J (ed) Miller R. Plenum Press, Complexity of computer computations, pp 85–103

  10. Li DM, Liu YP (1999) A polynomial algorithm for finding the minimum feedback vertex set of a 3-regular simple graph. Acta Mathe Scientia (English Ed) 19(4):375–381

    MATH  Google Scholar 

  11. Li Y, Peng S, Chu W (2004) Efficient collective communications in dual-cube. J Supercomput 28(1):71–90

    Article  MATH  Google Scholar 

  12. Li Y, Peng S, Chu W (2010) Metacube—a versatile family of interconnection networks for extremely large-scale supercomputers. J Supercomput 53(2):329–351

    Article  Google Scholar 

  13. Liang YD (1994) On the feedback vertex set problem in permutation graphs. Inf Process Lett 52(3):123–129

    Article  MATH  Google Scholar 

  14. Liang YD, Chang MS (1997) Minimum feedback vertex sets in cocomparability graphs and convex bipartite graphs. Acta Inform 34(5):337–346

    Article  MathSciNet  Google Scholar 

  15. Pike DA (2003) Decycling hypercubes. Graphs Combin 19(4):547–550

    Article  MATH  MathSciNet  Google Scholar 

  16. TOP500 (2011) Japan’s K computer tops 10 petaflop/s to stay atop TOP500 list. http://top500.org/lists/2011/11/. Last Accessed June 2013

  17. Vardy A (1997) Algorithmic complexity in coding theory and the minimum distance problem. In: Proceedings of the symposium on the theory of computing, pp 92–109

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

    Article  Google Scholar 

Download references

Acknowledgments

The author sincerely thanks the reviewers, and especially Reviewers 1, 4 and 5 for their comments and suggestions which significantly improved the quality of this paper.

Author information

Authors and Affiliations

  1. Advanced Institute of Industrial Technology, Tokyo Metropolitan University, Shinagawa-ku Higashiooi 1-10-40, Tokyo , 140-0011, Japan

    Antoine Bossard

Authors
  1. Antoine Bossard
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Antoine Bossard.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Bossard, A. The decycling problem in hierarchical cubic networks. J Supercomput 69, 293–305 (2014). https://doi.org/10.1007/s11227-014-1152-7

Download citation

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s11227-014-1152-7

Keywords

Search

Navigation