Efficient Communication Algorithms in Hexagonal Mesh Interconnection Networks

TitleEfficient Communication Algorithms in Hexagonal Mesh Interconnection Networks
Publication TypeJournal Article
Year of Publication2012
AuthorsAlbader, B., B. Bose, and M. Flahive
JournalIEEE Transactions on Parallel and Distributed Systems
Pagination69 - 77
Date Published01/2012
Keywordsbroadcasting, communication algorithms, EJ networks, hexagonal mesh networks, interconnection networks, parallel processing

In this paper, we show that the hexagonal mesh networks developed in the early 1990s are a special case of the EJ networks that have been considered more recently. Using a node addressing scheme based on the EJ number system, we give a shortest path routing algorithm for hexagonal mesh networks. We also extend the known efficient one-to-all broadcasting algorithm on hexagonal mesh networks to algorithms for one-to-one personalized broadcasting, all-to-all broadcasting, and all-to-all personalized broadcasting algorithms. Their time complexity and optimality are analyzed.

Short TitleIEEE Trans. Parallel Distrib. Syst.