article

An efficient algorithm for embedding exchanged hypercubes into grids

Authors:

Cheng-Kuan Lin,

Ruchuan WangAuthors Info & Claims

The Journal of Supercomputing, Volume 75, Issue 2

Pages 783 - 807

https://doi.org/10.1007/s11227-018-2612-2

Published: 01 February 2019 Publication History

Abstract

Graph embedding is an important technology in simulating parallel structures and designing VLSI layout. Hypercube is one of the most significant interconnection networks in parallel computing systems. The exchanged hypercube is an important variant of the hypercube, which is obtained by systematically deleting edges from a hypercube. It not only retains several valuable and desirable properties of the hypercube, but also has lower hardware cost. In this paper, we first give an exact formula of minimum wirelength of exchanged hypercube layout into a grid. Furthermore, we propose an O(N) algorithm for embedding exchanged hypercube into a gird with load 1, expansion 1 and minimum wirelength and derive a linear layout of exchanged hypercube with minimum number of tracks and efficient layout areas. Finally, we present simulation experiments of our embedding algorithm on network overhead and total wirelength, which conduce to estimate the total wirelength and chip area.

References

[1]

Arabnia HR, Oliver MA (1986) Fast operations on raster images with SIMD machine architectures. Int J Eurographics Assoc (Comput Graph Forum) 5(3):179---189

Digital Library

[2]

Valafar H, Arabnia HR, Williams G (2004) Distributed global optimization and its development on the multiring network. Int J Neural Parallel Sci Comput (Dynamic Publishers) 12(4):465---490

[3]

Hamid R, Arabnia A (1990) Parallel algorithm for the arbitrary rotation of digitized images using process-and-data-decomposition approach. J Parallel Distrib Comput 10(2):188---193

Digital Library

[4]

Hamid R Arabnia (1995) A distributed stereocorrelation algorithm. In: Proceedings of Fourth International Conference on IEEE Computer Communications and Networks, INSPEC Accession Number 5557991, pp 479---482

Digital Library

[5]

Arabnia Hamid R, Bhandarkar SM (1996) Parallel stereocorrelation on a reconfigurable multi-ring network. J Supercomput 10(3):243---270 (Special Issue on Parallel and Distributed Processing)

Digital Library

[6]

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

Digital Library

[7]

Bhandarkar SM (1997) Parallel computer vision on a reconfigurable multiprocessor network. IEEE Trans Parallel Distrib Syst 8(3):292---310

Digital Library

[8]

Manuel P, Rajasingh I, Rajan B (2009) Exact wirelength of hypercubes on a grid. Discrete Appl Math 157(7):1486---1495

Digital Library

[9]

Yeh C-H, Varvarigos EA, Parhami B (2000) Multilayer VLSI layout for interconnection networks. In: Proceedings of the International Conference on Parallel Processing, pp 33---40

Digital Library

[10]

Singh SP, Sharma RRK (2006) A review of different approaches to the facility layout problems. Int J Adv Manuf Technol 30(5---6):425---433

[11]

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

Digital Library

[12]

Nakano K (2003) Linear layout of generalized hypercubes. Int J Found Comput Sci 14(01):137---156

[13]

Arockiaraj M, Abraham J, Quadras J (2017) Linear layout of locally twisted cubes. Int J Comput Math 94(1):56---65

Digital Library

[14]

Liu YL (2015) Routing and wavelength assignment for exchanged hypercubes in linear array optical networks. Inf Process Lett 115(2):203---208

Digital Library

[15]

Yu C, Yang X (2012) Routing and wavelength assignment for 3-ary $$n$$n-cube in array-based optical network. Inf Process Lett 112(6):252---256

Digital Library

[16]

Bezrukov SL, Chavez JD, Harper LH, Röttger M, Schroeder UP (1998) Embedding of hypercubes into grids. In: Brim L, Gruska J, Zlatuška J (eds) International Symposium on Mathematical Foundations of Computer Science, vol 1450. Springer, Berlin, Heidelberg, pp 693---701

Digital Library

[17]

Bezrukov SL, Chavez JD, Harper LH (2000) The congestion of $$n$$n-cube layout on a rectangular grid. Discrete Math 213(1---3):13---19

Digital Library

[18]

Abraham J, Arockiaraj M (2017) Optimal embedding of locally twisted cubes into grids. In: Proceedings of International Conference on Springer Algorithms and Discrete Applied Mathematics, pp 1---11

[19]

Han Z, Li Y, Li J (2018) A novel routing algorithm for IoT cloud based on hash offset tree. Future Gener Comput Syst 86:456---463

Digital Library

[20]

Xiang D, Chakrabarty K, Fujiwara H (2016) Multicast-based testing and thermal-aware test scheduling for 3D ICs with a stacked network-on-chip. IEEE Trans Comput 65(9):2767---2779

Digital Library

[21]

Wang X, Fan J, Jia X (2011) Embedding meshes into twisted-cubes. Inf Sci 181(14):3085---3099

Digital Library

[22]

Han Y, Fan J, Zhang S, Yang J, Qian P (2010) Embedding meshes into locally twisted cubes. Inf Sci 180(19):3794---3805

Digital Library

[23]

Lv YL, Lin C-K, Fan JX (2017) Hamiltonian cycle and path embeddings in $$k$$k-ary $$n$$n-cubes based on structure faults. Comput J 60(2):159---179

[24]

Wang X, Fan J, Jia X, Zhang S, Yu J (2011) Embedding meshes into twisted-cubes. Inf Sci 181(14):3085---3099

Digital Library

[25]

Zhou DF, Fan JX, Lin C-K, Cheng BL, Zhou JY, Liu Z (2017) Optimal path embedding in the exchanged crossed cube. J Comput Sci Technol 32(3):618---629

[26]

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

Digital Library

[27]

Fan J, Jia X, Lin X (2008) Embedding of cycles in twisted cubes with edge-pancyclic. Algorithmica 51(3):264---282

[28]

Fan J, Jia X, Lin X (2006) Complete path embeddings in crossed cubes. Inf Sci 176(22):3332---3346

Digital Library

[29]

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

Digital Library

[30]

Ma M, Liu B (2009) Cycles embedding in exchanged hypercubes. Inf Process Lett 110(2):71---76

Digital Library

[31]

Ma M, Zhu L (2011) The super connectivity of exchanged hypercubes. Inf Process Lett 111(8):360---364

Digital Library

[32]

Zhang Z, Deng Y, Min G, Xie J, Huang S (2017) ExCCC-DCN: a highly scalable, cost-effective and energy-efficient data center structure. IEEE Trans Parallel Distrib Syst 28(4):1046---1060

Digital Library

[33]

Thompson CD (1980 Aug) A complexity theory for VLSI. Ph.D. thesis, Carnegie-Mellon University

Digital Library

[34]

Bezrukov SL, Das SK, Elsasser R (2000) An edge-isoperimetric problem for powers of the Petersen graph. Ann Comb 4(2):153---169

[35]

Tsai T-H, Chen Y-C, Tan JJM (2016) Optimal edge congestion of exchanged hypercubes. IEEE Trans Parallel Distrib Syst 27(1):250---262

Digital Library

[36]

Katseff H (1988) Incomplete hypercubes. IEEE Trans Comput 37:604---608

Digital Library

[37]

Harper LH (2004) Global methods for combinatorial isoperimetric problems. Cambridge University Press, Cambridge

[38]

Boals AJ, Gupta AK, Sherwani NA (1994) Incomplete hypercubes: algorithms and embeddings. J Supercomput 8(3):263---294

Digital Library

[39]

Yang X, David JE, Graham M (2005) Maximum induced subgraph of a recursive circulant. Inf Process Lett 95(1):293---298

[40]

Aroca JA, Anta AF (2014) Bisection (band) width of product networks with application to data centers. IEEE Trans Parallel Distrib Syst 25(3):570---580

Digital Library

[41]

Massie ML, Chun BN, Culler DE (2004) The ganglia distributed monitoring system: design, implementation, and experience. Parallel Comput 30(7):817---840

[42]

Zhang J, Yang X, Yu C, Li H, Yang L (2013) Implementing duplex crossed cube communication patterns on optical linear arrays. Optik Int J Light Electron Opt 124(24):6496---6500

[43]

Glantz R, Meyerhenke H (2015) Algorithms for mapping parallel processes onto grid and torus architectures. In: proceedings of International Conference on IEEE 23rd Euromicro Parallel, Distributed and Network-Based Processing (PDP), pp 236---243

Digital Library

Cited By

Afiya SRajesh M(2023)MinLA of and its optimal layout into certain treesThe Journal of Supercomputing10.1007/s11227-023-05140-379:11(12000-12012)Online publication date: 6-Mar-2023
https://dl.acm.org/doi/10.1007/s11227-023-05140-3
Guo RWang YFan JFan W(2023)Embedding hierarchical folded cubes into linear arrays and complete binary trees with minimum wirelengthThe Journal of Supercomputing10.1007/s11227-023-05095-579:10(11300-11327)Online publication date: 24-Feb-2023
https://dl.acm.org/doi/10.1007/s11227-023-05095-5
Jha P(2022)Vertex transitivity, distance metric, and hierarchical structure of the dual-cubeThe Journal of Supercomputing10.1007/s11227-022-04557-678:16(17758-17775)Online publication date: 1-Nov-2022
https://dl.acm.org/doi/10.1007/s11227-022-04557-6
Show More Cited By

An efficient algorithm for embedding exchanged hypercubes into grids
1. Mathematics of computing
  1. Discrete mathematics
    1. Graph theory

Recommendations

Exact wirelength of hypercubes on a grid

Grid embeddings are used not only to study the simulation capabilities of a parallel architecture but also to design its VLSI layout. In addition to dilation and congestion, wirelength is an important measure of an embedding. There are very few papers ...
Cycles embedding in exchanged hypercubes

The exchanged hypercube EH(s,t), proposed by Loh et al., is obtained by systematically removing links from a binary hypercube. This paper investigates important properties related to embedding cycles into the exchanged hypercube EH(s,t). The authors ...
Mesh-Connected Trees: A Bridge Between Grids and Meshes of Trees

The grid and the mesh of trees (or MOT) are among the best-known parallel architectures in the literature. Both of them enjoy efficient VLSI layouts, simplicity of topology, and a large number of parallel algorithms that can efficiently execute on them. ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image The Journal of Supercomputing

The Journal of Supercomputing Volume 75, Issue 2

February 2019

509 pages

ISSN:0920-8542

Issue’s Table of Contents

Copyright © Copyright © 2019 Springer Science+Business Media, LLC, part of Springer Nature.

Publisher

Kluwer Academic Publishers

United States

Publication History

Published: 01 February 2019

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

11
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 07 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Afiya SRajesh M(2023)MinLA of and its optimal layout into certain treesThe Journal of Supercomputing10.1007/s11227-023-05140-379:11(12000-12012)Online publication date: 6-Mar-2023
https://dl.acm.org/doi/10.1007/s11227-023-05140-3
Guo RWang YFan JFan W(2023)Embedding hierarchical folded cubes into linear arrays and complete binary trees with minimum wirelengthThe Journal of Supercomputing10.1007/s11227-023-05095-579:10(11300-11327)Online publication date: 24-Feb-2023
https://dl.acm.org/doi/10.1007/s11227-023-05095-5
Jha P(2022)Vertex transitivity, distance metric, and hierarchical structure of the dual-cubeThe Journal of Supercomputing10.1007/s11227-022-04557-678:16(17758-17775)Online publication date: 1-Nov-2022
https://dl.acm.org/doi/10.1007/s11227-022-04557-6
Xie YLiang JYin WLi C(2022)The properties and t/s-diagnosability of k-ary n-cube networksThe Journal of Supercomputing10.1007/s11227-021-04155-y78:5(7038-7057)Online publication date: 1-Apr-2022
https://dl.acm.org/doi/10.1007/s11227-021-04155-y
Han ZFu YDu X(2021)Embedding Cube-Connected Cycles into Grid Network for Minimum WirelengthIEEE/WIC/ACM International Conference on Web Intelligence and Intelligent Agent Technology10.1145/3498851.3498998(461-465)Online publication date: 14-Dec-2021
https://dl.acm.org/doi/10.1145/3498851.3498998
Fan WFan JHan ZLi PZhang YWang R(2021)Fault-tolerant hamiltonian cycles and paths embedding into locally exchanged twisted cubesFrontiers of Computer Science: Selected Publications from Chinese Universities10.1007/s11704-020-9387-315:3Online publication date: 1-Jun-2021
https://dl.acm.org/doi/10.1007/s11704-020-9387-3
Zhang YFan WHan ZSong YWang R(2021)Fault-tolerant routing algorithm based on disjoint paths in 3-ary n-cube networks with structure faultsThe Journal of Supercomputing10.1007/s11227-021-03799-077:11(13090-13114)Online publication date: 1-Nov-2021
https://dl.acm.org/doi/10.1007/s11227-021-03799-0
Sundara Rajan RKalinowski TKlavžar SMokhtar HRajalaxmi T(2021)Lower bounds for dilation, wirelength, and edge congestion of embedding graphs into hypercubesThe Journal of Supercomputing10.1007/s11227-020-03420-w77:4(4135-4150)Online publication date: 1-Apr-2021
https://dl.acm.org/doi/10.1007/s11227-020-03420-w
Wang YZhou SYu Z(2021)Reliability Evaluation of Subsystem Based on Exchanged HypercubeComputing and Combinatorics10.1007/978-3-030-89543-3_23(271-282)Online publication date: 24-Oct-2021
https://dl.acm.org/doi/10.1007/978-3-030-89543-3_23
Liu NZhang YFan W(2020)Construction of Completely Independent Spanning Tree Based on Vertex DegreeParallel and Distributed Computing, Applications and Technologies10.1007/978-3-030-69244-5_8(94-103)Online publication date: 28-Dec-2020
https://dl.acm.org/doi/10.1007/978-3-030-69244-5_8
Show More Cited By

View Options

View options

Figures

Tables

Media

View Issue’s Table of Contents