More Web Proxy on the site http://driver.im/

research-article

3D Hexagonal Network: Modeling, Topological Properties, Addressing Scheme, and Optimal Routing Algorithm

Authors:

Catherine Decayeux,

David SemeAuthors Info & Claims

IEEE Transactions on Parallel and Distributed Systems, Volume 16, Issue 9

Pages 875 - 884

https://doi.org/10.1109/TPDS.2005.100

Published: 01 September 2005 Publication History

Abstract

The 2D hexagonal mesh, based on triangle plane tessellation, is considered as a multiprocessor interconnection network. The 3D hexagonal mesh is presented as a natural extension of the hexagonal mesh. Although the topological properties of the 2D hexagonal mesh are well known, existing addressing schemes are not suitable to be extended to 3D hexagonal mesh. Then, we present, in this paper, a new addressing scheme and an optimal routing algorithm for 2D hexagonal network based on the distance formula and using shortest paths. We propose also a 3D hexagonal network that can be built with 2D hexagonal meshes as a natural generalization. We also present some topological properties, an efficient addressing scheme, and an optimal routing algorithm based on our 2D routing algorithm.

References

[1]

S.G. Akl, Parallel Computation: Models and Methods. Prentice Hall, 1997.

Digital Library

[2]

H. Aykanat and T. Ozguner, “A Fault Tolerant Hexagonal Systolic Array,” Information Processing Letters, vol. 42, pp. 187-196, 1992.

Digital Library

[3]

U. Black, Mobile and Wireless Networks. Upper Saddle River, N.J.: Prentice-Hall PTR, 1996.

Digital Library

[4]

J. Carle, “Etude des propriétés des réseaux d'interconnexion de type nids d'abeilles,” PhD thesis, Université de Picardie Jules Verne, Faculté de Mathématiques et d'Informatique, Amiens, France, 2000.

[5]

J. Carle and J.F. Myoupo, “Topological Properties and Optimal Routing Algorithms for Three Dimensional Hexagonal Networks,” Proc. Int'l Conf. High-Performance Computing in the Asia-Pacific Region (HPC-Asia 2000), pp. 116-121, 2000.

[6]

J. Carle J.F. Myoupo and D. Semé, “All-to-All Broadcasting Algorithms on Honeycomb Networks and Applications,” Parallel Processing Letters, vol. 9, no. 4, pp. 539-550, 1999.

[7]

M.S. Chen K.G. Shin and D.D. Kandlur, “Addressing, Routing and Broadcasting in Hexagonal Mesh Multiprocessors,” IEEE Trans. Computers, vol. 39, no. 1, pp. 10-18, Jan. 1990.

Digital Library

[8]

J.W. Dolter P. Ramanathan and K.G. Shin, “Performance Analysis of Virtual Cut-through Switching in HARTS: A Hexagonal Mesh Multicomputer,” IEEE Trans. Computers, vol. 40,no. 6, pp. 669-680, June 1991.

Digital Library

[9]

F. Garcia I. Stojmenovic and J. Zhang, “Addressing and Routing in Hexagonal Networks with Applications for Location Update and Connection Rerouting in Cellular Networks,” technical report, manuscript, 2000.

[10]

V.K. Garg and J.E. Wilkes, Wireless and Personal Communication Systems. Upper Saddle River, N.J.: Prentice-Hall PTR, 1996.

Digital Library

[11]

D. Gordon I. Koren and G.M. Silberman, “Embedding Tree Structures in VLSI Hexagonal Arrays,” IEEE Trans. Computers, vol. 33, pp. 104-107, 1984.

[12]

D. Milutinovic V. Milutinovic and B. Soucek, “The Honeycomb Architecture,” Computer, vol. 20, no. 4, pp. 81-83, Apr. 1987.

Digital Library

[13]

V. Milutinovic, “Mapping of Neural Network on the Honeycomb Architecture,” Proc. IEEE, vol. 77, no. 12, pp. 1875-1878, 1989.

[14]

J.-F. Myoupo H. NDamas and D. Semé, “Hexagonal Mesh: A New Addressing Scheme and an Optimal Routing Algorithm,” Proc. Int'l Symp. Parallel and Distributed Computing and Networks, PDCN '02, 2002.

[15]

F. Garcia Nocetti J. Solano González I. Stojmenovic and M. Stojmenovic, “Addressing and Routing in Higher Dimensional Hexagonal Networks,” Proc. Int'l Conf. Parallel and Distributed Processing Techniques and Applications, PDPTA-01, pp. 1726-1732, 2001.

[16]

F. Garcia Nocetti J. Solano González I. Stojmenovic and M. Stojmenovic, “Higher Dimensional Hexagonal Networks,” J. Parallel Distributed Computing, vol. 63, pp. 1164-1172, 2003.

Digital Library

[17]

B. Parhami, Introduction to Parallel Processing: Algorithms and Architectures. Plenium, 1998.

Digital Library

[18]

Y.R. Potlapalli, “Trend in Interconnection Network Topologies: Hierarchical Networks,” Proc. Int'l Conf. Parallel Processing Workshop, 1995.

[19]

M.J. Quinn, Parallel Computing, Theory and Practice. McGraw-Hill, 1994.

Digital Library

[20]

B. Robic and J. Silc, “High-Performance Computing on a Honeycomb Architecture,” Proc. Second Int'l ACPC, Parallel Computation Conf., 1993.

Digital Library

[21]

K.G. Shin, “HARTS: A Distributed Real-Time Architecture,” Computer, vol. 24, no. 5, pp. 25-35, May 1991.

Digital Library

[22]

I. Stojmenovic, Parallel and Distributed Computing Handbook, chapter direct interconnection networks, pp. 537-567, A.Y. Zomaya, ed., 1996.

[23]

I. Stojmenovic, “Honeycomb Networks: Topological Properties and Communication Algorithms,” IEEE Trans. Parallel and Distributed Systems, vol. 8, no. 10, pp. 1036-1042, Oct. 1997.

Digital Library

[24]

H.Y. Youn and J.Y. Lee, “An Efficient Dictionary Machine Using Hexagonal Processor Array,” IEEE Trans. Parallel and Distributed Systems, vol. 7, no. 3, pp. 266-273, Mar. 1996.

Digital Library

Cited By

Seo JLee H(2020)Design and analysis of the rotational binary graph as an alternative to hypercube and TorusThe Journal of Supercomputing10.1007/s11227-019-03115-x76:9(7161-7176)Online publication date: 15-Jan-2020
https://dl.acm.org/doi/10.1007/s11227-019-03115-x
Seo JKim JChang HLee H(2018)The hierarchical Petersen networkThe Journal of Supercomputing10.1007/s11227-017-2186-474:4(1636-1654)Online publication date: 1-Apr-2018
https://dl.acm.org/doi/10.1007/s11227-017-2186-4
Hussain ZShamaei A(2017)Higher dimensional EisensteinJacobi networksJournal of Parallel and Distributed Computing10.1016/j.jpdc.2016.11.006102:C(91-102)Online publication date: 1-Apr-2017
https://dl.acm.org/doi/10.1016/j.jpdc.2016.11.006
Show More Cited By

Index Terms

3D Hexagonal Network: Modeling, Topological Properties, Addressing Scheme, and Optimal Routing Algorithm

Recommendations

Higher dimensional hexagonal networks

We define the higher dimensional hexagonal graphs as the generalization of a triangular plane tessellation, and consider it as a multiprocessor interconnection network. Nodes in a k-dimensional (k-D) hexagonal network are placed at the vertices of a k-D ...
Efficient Communication Algorithms in Hexagonal Mesh Interconnection Networks

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 ...
Fault-Tolerant Routing in Mesh Architectures

It is important for a distributed computing system to be able to route messages aroundwhatever faulty links or nodes may be present. We present a fault-tolerant routingalgorithm that assures the delivery of every message as long as there is a path ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image IEEE Transactions on Parallel and Distributed Systems

IEEE Transactions on Parallel and Distributed Systems Volume 16, Issue 9

September 2005

128 pages

ISSN:1045-9219

Issue’s Table of Contents

Copyright © 2005.

Publisher

IEEE Press

Publication History

Published: 01 September 2005

Author Tags

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

7
Total Citations
View Citations
0
Total Downloads

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

Reflects downloads up to 06 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Seo JLee H(2020)Design and analysis of the rotational binary graph as an alternative to hypercube and TorusThe Journal of Supercomputing10.1007/s11227-019-03115-x76:9(7161-7176)Online publication date: 15-Jan-2020
https://dl.acm.org/doi/10.1007/s11227-019-03115-x
Seo JKim JChang HLee H(2018)The hierarchical Petersen networkThe Journal of Supercomputing10.1007/s11227-017-2186-474:4(1636-1654)Online publication date: 1-Apr-2018
https://dl.acm.org/doi/10.1007/s11227-017-2186-4
Hussain ZShamaei A(2017)Higher dimensional EisensteinJacobi networksJournal of Parallel and Distributed Computing10.1016/j.jpdc.2016.11.006102:C(91-102)Online publication date: 1-Apr-2017
https://dl.acm.org/doi/10.1016/j.jpdc.2016.11.006
Seo J(2013)Three-dimensional Petersen-torus networkThe Journal of Supercomputing10.1007/s11227-011-0716-z64:3(987-1007)Online publication date: 1-Jun-2013
https://dl.acm.org/doi/10.1007/s11227-011-0716-z
Ki WLee HOh J(2009)The new torus network design based On 3-dimensional hypercubeProceedings of the 11th international conference on Advanced Communication Technology - Volume 110.5555/1701955.1702076(615-620)Online publication date: 15-Feb-2009
https://dl.acm.org/doi/10.5555/1701955.1702076
Zhang ZXiao WHe M(2007)Optimal routing algorithm and diameter in hexagonal torus networksProceedings of the 7th international conference on Advanced parallel processing technologies10.5555/1785246.1785277(241-250)Online publication date: 22-Nov-2007
https://dl.acm.org/doi/10.5555/1785246.1785277
Zhang ZXiao WHe M(2007)Optimal Routing Algorithm and Diameter in Hexagonal Torus NetworksAdvanced Parallel Processing Technologies10.1007/978-3-540-76837-1_28(241-250)Online publication date: 22-Nov-2007
https://dl.acm.org/doi/10.1007/978-3-540-76837-1_28

View Options

View options

Media

Figures

Other

Tables

View Issue’s Table of Contents