http://iet.metastore.ingenta.com
1887

Embedding torus in hexagonal honeycomb torus

Embedding torus in hexagonal honeycomb torus

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

Buy article PDF
$19.95
(plus tax if applicable)
Buy Knowledge Pack
10 articles for $120.00
(plus taxes if applicable)

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

You must fill out fields marked with: *

Librarian details
Name:*
Email:*
Your details
Name:*
Email:*
Department:*
Why are you recommending this title?
Select reason:
 
 
 
 
 
IET Computers & Digital Techniques — Recommend this title to your library

Thank you

Your recommendation has been sent to your librarian.

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)
      • A. Grama , A. Gupta , G. Karypis , V. Kumar . (2003) Introduction to parallel computing.
    2. 2)
    3. 3)
    4. 4)
      • B. Hendrickson , D. Womble . The torus-wrap mapping for dense matrix calculations on massively parallel computers. SIAM J. Sci. Stat. Comput. , 5 , 1201 - 1226
    5. 5)
    6. 6)
      • B. Parhami . (1999) An introduction to parallel processing: algorithms and architectures.
    7. 7)
      • Andreae, T., Nö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.
    8. 8)
    9. 9)
    10. 10)
      • I. Stojmenovic . Honeycomb networks: topological properties and communication algorithms. IEEE Trans. Parallel Distrib. Syst. , 10 , 650 - 663
    11. 11)
    12. 12)
      • X. Yang , G.M. Megson , S. Zhang . A solution to the three disjoint path problem on honeycomb meshes. Parallel Process. Lett. , 399 - 410
    13. 13)
      • X. Yang , G.M. Megson , S. Zhang . A solution to the three disjoint path problem on honeycomb tori. Parallel Process. Lett. , 411 - 422
    14. 14)
    15. 15)
    16. 16)
      • X. Yang . The diameter of honeycomb rhombic tori. Appl. Math. Lett. , 2 , 167 - 172
    17. 17)
    18. 18)
    19. 19)
      • H. Cho , L. Hsu . Generalized honeycomb torus. Inf. Process. Lett. , 5 , 185 - 190
    20. 20)
      • H. Cho , L. Hsu . Ring embedding in faulty honeycomb rectangular torus. Inf. Process. Lett. , 5 , 277 - 284
    21. 21)
    22. 22)
    23. 23)
    24. 24)
      • D. Bein , W.W. Bein , N. Brajkovska . Optimal embedding of honeycomb networks into hypercubes. Parallel Process. Lett. , 367 - 375
    25. 25)
      • X. Yang , Y.Y. Tang , J. Cao . Embedding even-length cycles in a hexagonal honeycomb mesh. Int. J. Comput. Math.
    26. 26)
      • F. Harary . (1969) Graph theory.
http://iet.metastore.ingenta.com/content/journals/10.1049/iet-cdt_20050219
Loading

Related content

content/journals/10.1049/iet-cdt_20050219
pub_keyword,iet_inspecKeyword,pub_concept
6
6
Loading
This is a required field
Please enter a valid email address