Authors

Paul Immanuel, A. Berin Greeni

Abstract

Embedding a graph into another graph can be utilized for structural simulation, processor allocation, and algorithm porting in the field of parallel architecture. This has the potential to enhance the physical layout of network‐on‐chip (NoC) devices as well as to investigate their virtualization possibilities. Layout is one of the many indicators of graph embedding. An optimal layout in NoC design can result in a decreased wiring area and cost, as well as the reduction in communication delay between parallel processing components. In this work, the guest graph is the half hypercube, which possess efficient routing, fault tolerance, and Hamiltonian features. The edge isoperimetric problems is solved for the half hypercube using a novel technique called the isochronal ordering. The host graphs considered in our work are complete binary trees, ‐rooted complete binary trees, and other few predominantly investigated tree based architectures.

Citation

  • Journal: Concurrency and Computation: Practice and Experience
  • Year: 2024
  • Volume: 36
  • Issue: 12
  • Pages:
  • Publisher: Wiley
  • DOI: 10.1002/cpe.8058

BibTeX

@article{Immanuel_2024,
  title={{Optimization of layout for embedding half hypercube into conventional tree architectures}},
  volume={36},
  ISSN={1532-0634},
  DOI={10.1002/cpe.8058},
  number={12},
  journal={Concurrency and Computation: Practice and Experience},
  publisher={Wiley},
  author={Immanuel, Paul and Greeni, A. Berin},
  year={2024}
}

Download the bib file

References

  • Guo, R., Wang, Y., Fan, J. & Fan, W. Embedding hierarchical folded cubes into linear arrays and complete binary trees with minimum wirelength. J Supercomput 79, 11300–11327 (2023) – 10.1007/s11227-023-05095-5
  • Bezrukov, S., Monien, B., Unger, W. & Wechsung, G. Embedding ladders and caterpillars into the hypercube. Discrete Applied Mathematics 83, 21–29 (1998) – 10.1016/s0166-218x(97)00101-7
  • Cai, H., Zheng, V. W. & Chang, K. C.-C. A Comprehensive Survey of Graph Embedding: Problems, Techniques, and Applications. IEEE Trans. Knowl. Data Eng. 30, 1616–1637 (2018) – 10.1109/tkde.2018.2807452
  • Fan, W., He, J., Han, Z., Li, P. & Wang, R. Reconfigurable Fault‐tolerance mapping of ternary N‐cubes onto chips. Concurrency and Computation 32, (2020) – 10.1002/cpe.5659
  • Guo R, Embedding hierarchical cubic networks into k‐rooted complete binary trees for minimum wirelength. Int J Found Comput Sci (2023)
  • Rajasingh, I., Manuel, P., Rajan, B. & Arockiaraj, M. Wirelength of hypercubes into certain trees. Discrete Applied Mathematics 160, 2778–2786 (2012) – 10.1016/j.dam.2011.12.007
  • Sundara Rajan, R., Kalinowski, T., Klavžar, S., Mokhtar, H. & Rajalaxmi, T. M. Lower bounds for dilation, wirelength, and edge congestion of embedding graphs into hypercubes. J Supercomput 77, 4135–4150 (2020) – 10.1007/s11227-020-03420-w
  • Arockiaraj, M., Abraham, J. & Shalini, A. J. Node set optimization problem for complete Josephus cubes. J Comb Optim 38, 1180–1195 (2019) – 10.1007/s10878-019-00443-9
  • Berin Greeni, A., Sundara Rajan, R. & Immanuel, P. Embedding Augmented Cube into Certain Trees and Windmill Graphs. Int. J. Found. Comput. Sci. 35, 409–434 (2023) – 10.1142/s0129054123500090
  • Bezrukov, S. L. Embedding complete trees into the hypercube. Discrete Applied Mathematics 110, 101–119 (2001) – 10.1016/s0166-218x(00)00256-0
  • Jha, P. K. Optimal embeddings of the exchanged hypercube and the dual-cube as vertex-induced subgraphs of the hypercube. Discrete Applied Mathematics 337, 218–231 (2023) – 10.1016/j.dam.2023.04.025
  • Liu, Q. & Tang, Z. A Rigorous Proof on Circular Wirelength for Hypercubes. Acta Math Sci 43, 919–941 (2023) – 10.1007/s10473-023-0223-3
  • Shalini, A. J., Abraham, J. & Arockiaraj, M. A linear time algorithm for embedding locally twisted cube into grid network to optimize the layout. Discrete Applied Mathematics 286, 10–18 (2020) – 10.1016/j.dam.2018.06.039
  • Tang, Z. Optimal embedding of hypercube into cylinder. Theoretical Computer Science 923, 327–336 (2022) – 10.1016/j.tcs.2022.05.020
  • Bezrukov, S. L., Chavez, J. D., Harper, L. H., Röttger, M. & Schroeder, U.-P. The congestion of n-cube layout on a rectangular grid. Discrete Mathematics 213, 13–19 (2000) – 10.1016/s0012-365x(99)00162-4
  • Manuel, P., Rajasingh, I., Rajan, B. & Mercy, H. Exact wirelength of hypercubes on a grid. Discrete Applied Mathematics 157, 1486–1495 (2009) – 10.1016/j.dam.2008.09.013
  • Bezrukov, S. L., Chavez, J. D., Harper, L. H., Röttger, M. & Schroeder, U.-P. Embedding of hypercubes into grids. Lecture Notes in Computer Science 693–701 (1998) doi:10.1007/bfb0055820 – 10.1007/bfb0055820
  • Arockiaraj, M., Delaila, J. N. & Abraham, J. Optimal Wirelength of Balanced Complete Multipartite Graphs onto Cartesian Product of {Path, Cycle} and Trees. Fundamenta Informaticae 178, 187–202 (2021) – 10.3233/fi-2021-2003
  • Arockiaraj, M., Liu, J.-B., Delaila, J. N. & Shalini, A. J. On the optimal layout of balanced complete multipartite graphs into grids and tree related structures. Discrete Applied Mathematics 288, 50–65 (2021) – 10.1016/j.dam.2020.08.022
  • Arockiaraj, M., Shalini, A. J. & Nancy Delaila, J. Embedding algorithm of spined cube into grid structure and its wirelength computation. Theoretical Computer Science 905, 69–86 (2022) – 10.1016/j.tcs.2021.12.016
  • Berin Greeni A, Embedding complete bipartite graph into sibling trees with optimum wirelength. J Comb Math Comb Comput (2020)
  • Fan, W.-B. et al. Optimally Embedding 3-Ary n-Cubes into Grids. J. Comput. Sci. Technol. 34, 372–387 (2019) – 10.1007/s11390-019-1893-0
  • Bezrukov SL, Graph Theory and Combinatorial Biology (1999)
  • Garey M, Computers and Intractability ‐ A Guide to the Theory of NP‐Completeness (1979)
  • Abdel-Ghaffar, K. A. S. Maximum number of edges joining vertices on a cube. Information Processing Letters 87, 95–99 (2003) – 10.1016/s0020-0190(03)00257-6
  • Bezrukov, S. L. An Edge-Isoperimetric Problem for Powers of the Petersen Graph. Annals of Combinatorics 4, 153–169 (2000) – 10.1007/s000260050003
  • Manuel, P. Minimum average congestion of enhanced and augmented hypercubes into complete binary trees. Discrete Applied Mathematics 159, 360–366 (2011) – 10.1016/j.dam.2010.12.001
  • Tan, X., Yu, S.-Z. & Park, J. H. A note about some properties of BC graphs. Information Processing Letters 108, 398–401 (2008) – 10.1016/j.ipl.2008.07.014
  • Yang, X., Evans, D. J. & Megson, G. M. Maximum induced subgraph of a recursive circulant. Information Processing Letters 95, 293–298 (2005) – 10.1016/j.ipl.2005.03.004
  • Kim, M.-H., Kim, J.-S. & Lee, H.-O. Broadcasting and Embedding Algorithms for a Half Hypercube Interconnection Network. Lecture Notes in Electrical Engineering 553–559 (2013) doi:10.1007/978-94-007-6738-6_67 – 10.1007/978-94-007-6738-6_67
  • Liu, J., Zhou, S., Wang, D. & Zhang, H. Component diagnosability in terms of component connectivity of hypercube-based compound networks. Journal of Parallel and Distributed Computing 162, 17–26 (2022) – 10.1016/j.jpdc.2021.12.004
  • Lv, M., Zhou, S., Sun, X., Lian, G. & Chen, G. The g-good-neighbour conditional diagnosability of multiprocessor system based on half hypercube. International Journal of Computer Mathematics: Computer Systems Theory 3, 160–176 (2018) – 10.1080/23799927.2018.1517131
  • Glantz, R., Meyerhenke, H. & Noe, A. Algorithms for Mapping Parallel Processes onto Grid and Torus Architectures. 2015 23rd Euromicro International Conference on Parallel, Distributed, and Network-Based Processing 236–243 (2015) doi:10.1109/pdp.2015.21 – 10.1109/pdp.2015.21
  • Harper, L. H. Global Methods for Combinatorial Isoperimetric Problems. (2004) doi:10.1017/cbo9780511616679 – 10.1017/cbo9780511616679
  • Kim, J.-S., Kim, M.-H. & Lee, H.-O. Analysis and Design of a Half Hypercube Interconnection Network. Lecture Notes in Electrical Engineering 537–543 (2013) doi:10.1007/978-94-007-6738-6_65 – 10.1007/978-94-007-6738-6_65
  • Dong, H., Lv, M., Fan, W. & Wang, G. Reliability evaluation of half hypercube networks. Theoretical Computer Science 975, 114142 (2023) – 10.1016/j.tcs.2023.114142
  • Boals, A. J., Gupta, A. K. & Sherwani, N. A. Incomplete hypercubes: Algorithms and embeddings. J Supercomput 8, 263–294 (1994) – 10.1007/bf01204731
  • Katseff, H. P. Incomplete hypercubes. IEEE Trans. Comput. 37, 604–608 (1988) – 10.1109/12.4611
  • Rajasingh, I. & Arockiaraj, M. Linear Wirelength of Folded Hypercubes. Math.Comput.Sci. 5, 101–111 (2011) – 10.1007/s11786-011-0085-2