Embedding torus in hexagonal honeycomb torus

Author(s): X. Yang ; Y.Y. Tang ; J. Cao
DOI: 10.1049/iet-cdt:20050219

For access to this article, please select a purchase option:

Buy article PDF

Buy Knowledge Pack

IET members benefit from discounts to all IET publications and free access to E&T Magazine. If you are an IET member, log in to your account and the discounts will automatically be applied.

Learn more about IET membership

Recommend Title Publication to library

IET Computers & Digital Techniques — Recommend this title to your library

Thank you

Your recommendation has been sent to your librarian.

Author(s): X. Yang ^{1, 2} ; Y.Y. Tang ¹ ; J. Cao ²
- Affiliations: 1: College of Computer Science, Chongqing University, Chongqing, People's Republic of China
  2: School of Computer and Information, Chongqing Jiaotong University, Chongqing, People's Republic of China
Source: Volume 2, Issue 2, March 2008, p. 86 – 93
DOI: 10.1049/iet-cdt:20050219 , Print ISSN 1751-8601, Online ISSN 1751-861X

A number of parallel algorithms admit a static torus-structured task graph. Hexagonal honeycomb torus (HHT) networks are regarded as promising candidates for interconnection networks. In order to efficiently execute a torus-structured parallel algorithm on an HHT, it is essential to map the tasks to processors so that the communication overhead is minimised. The study proves that a (3n, 2n) torus can be embedded into an nth-order HHT with dilation 3, congestion 4, expansion 1 and load factor 1. Consequently, a parallel algorithm with a (3n, 2n) torus task graph can be executed on an nth-order HHT efficiently.

References

1. 1)
  - B. Hendrickson , D. Womble . The torus-wrap mapping for dense matrix calculations on massively parallel computers. SIAM J. Sci. Stat. Comput. , 5 , 1201 - 1226
2. 2)
  - H. Cho , L. Hsu . Generalized honeycomb torus. Inf. Process. Lett. , 5 , 185 - 190
3. 3)
  - X. Yang , G.M. Megson , S. Zhang . A solution to the three disjoint path problem on honeycomb meshes. Parallel Process. Lett. , 399 - 410
4. 4)
  - B. Parhami , D. Kwai . A unified formulation of honeycomb and diamond networks. IEEE Trans. Parallel Distrib. Syst. , 1 , 74 - 80
5. 5)
  - D. Bein , W.W. Bein , N. Brajkovska . Optimal embedding of honeycomb networks into hypercubes. Parallel Process. Lett. , 367 - 375
6. 6)
  - H. Cho , L. Hsu . Ring embedding in faulty honeycomb rectangular torus. Inf. Process. Lett. , 5 , 277 - 284
7. 7)
  - F. Harary . (1969) Graph theory.
8. 8)
  - J. Carle , J.F. Myoupo , I. Stojmenovic . Higher dimensional honeycomb networks. J. Interconnect. Netw. , 4 , 391 - 420
9. 9)
  - X. Yang , D.J. Evans , H. Lai . Generalized honeycomb torus is Hamiltonian. Inf. Process. Lett. , 1 , 31 - 37
10. 10)
  - B. Parhami . (1999) An introduction to parallel processing: algorithms and architectures.
11. 11)
  - A. Grama , A. Gupta , G. Karypis , V. Kumar . (2003) Introduction to parallel computing.
12. 12)
  - I. Stojmenovic . Honeycomb networks: topological properties and communication algorithms. IEEE Trans. Parallel Distrib. Syst. , 10 , 650 - 663
13. 13)
  - B. Hendrickson . Parallel QR factorization using the torus-wrap mapping. Parallel Comput. , 11 , 1259 - 1271
14. 14)
  - G.M. Megson , X. Liu , X. Yang . Fault-tolerant ring embedding in a honeycomb torus with node failures. Parallel Process. Lett. , 4 , 551 - 561
15. 15)
  - X. Yang , G.M. Megson , Y.Y. Tang . Diameter of parallelogramic honeycomb torus. Comput. Math. Appl. , 1477 - 1486
16. 16)
  - R.A. Ayoubi , M.A. Bayoumi . Efficient mapping algorithm of multilayer neural network on torus architecture. IEEE Trans. Parallel Distrib. Syst. , 9 , 932 - 943
17. 17)
  - C.C. Lam , C.-H. Huang , P. Sadayappan . Optimal algorithms for all-to-all personalized communication on rings and two dimensional tori. J. Parallel Distrib. Comput. , 1 , 3 - 13
18. 18)
  - Andreae, T., Nölle, M., Rempel, C.: `On embedding 2-dimensional toroidal grids into de Brujin graphs with clocked congestion one', Proc. 4th Franco-Japanese and 8th Franco-Chinese Conf. Combinatorics and Computer Science, 1995, Brest, France, p. 316–327.
19. 19)
  - J. Fang , J. Hsiao , C. Tang . Embedding meshes and TORUS networks onto degree-four chordal rings. IEE Proc., Comput. Digit. Tech. , 2 , 73 - 80
20. 20)
  - J. Carle , J.F. Myoupo , D. Seme . All-to-all broadcasting algorithms on honeycomb networks and applications. Parallel Process. Lett. , 539 - 550
21. 21)
  - D.K. Saikia , R. Badrinath , R.K. Sen . Embedding torus on the star graph. IEEE Trans. Parallel Distrib. Syst. , 7 , 650 - 663
22. 22)
  - G.M. Megson , X. Yang , X. Liu . Honeycomb tori are Hamiltonian. Inf. Process. Lett. , 99 - 103
23. 23)
  - X. Yang . The diameter of honeycomb rhombic tori. Appl. Math. Lett. , 2 , 167 - 172
24. 24)
  - X. Yang , G.M. Megson , S. Zhang . A solution to the three disjoint path problem on honeycomb tori. Parallel Process. Lett. , 411 - 422
25. 25)
  - X. Yang , Y.Y. Tang , Q. Lu . Optimal doublecast path in hexagonal honeycomb mesh. Appl. Math. Comput. , 1267 - 1279
26. 26)
  - X. Yang , Y.Y. Tang , J. Cao . Embedding even-length cycles in a hexagonal honeycomb mesh. Int. J. Comput. Math.

Embedding torus in hexagonal honeycomb torus

Embedding torus in hexagonal honeycomb torus

Buy article PDF

Buy Knowledge Pack

Thank you

References

Related content