Authors

Amnah El-Obaid

Abstract

Broadcast is one of the most important approach in distributed memory parallel computers that is used to find a routing approach from one source to all nodes in the mesh. Broadcasting is a data communication task in which corresponds to one-to-all communication. Routing schema is the approach used to determine the road that is used to send a message from a source node to destination nodes. In this paper, we propose an efficient algorithm for broadcasting on an all-port wormhole-routed 3D mesh with arbitrary size. Wormhole routing is a fundamental routing mechanism in modern parallel computers which is characterized with low communication latency. We show how to apply this approach to 3-D meshes. In wormhole, routing large network packets are broken into small pieces called FLITs (flow control digits). The destination address is kept in the first flit which is called the header flit and sets up the routing behavior for all subsequent flits associated with the packet. In this paper, we introduce an efficient algorithm, X-Hamiltonian Surface Broadcast (X-HSB) which uses broadcast communication facility with deadlock-free wormhole routing in general three dimensional networks. In this paper, the behaviors of this algorithm are compared to the previous results using simulation; our paradigm reduces broadcast latency and is simpler. The results presented in this paper indicate the advantage of our proposed algorithm.

Citation

  • Journal: International Journal of Communications, Network and System Sciences
  • Year: 2016
  • Volume: 09
  • Issue: 06
  • Pages: 269–279
  • Publisher: Scientific Research Publishing, Inc.
  • DOI: 10.4236/ijcns.2016.96024

BibTeX

@article{El_Obaid_2016,
  title={{X-Hamiltonian Surface Broadcast Algorithm}},
  volume={09},
  ISSN={1913-3723},
  DOI={10.4236/ijcns.2016.96024},
  number={06},
  journal={International Journal of Communications, Network and System Sciences},
  publisher={Scientific Research Publishing, Inc.},
  author={El-Obaid, Amnah},
  year={2016},
  pages={269--279}
}

Download the bib file

References

  • Li, Y., Peng, S. & Chu, W. Hierarchical Dual-Net: A Flexible Interconnection Network and its Routing Algorithm. IJNC 2, 234–250 (2012) – 10.15803/ijnc.2.2_234
  • Li, Y., Peng, S. & Chu, W. Hierarchical Dual-Net: A Flexible Interconnection Network and its Routing Algorithm. IJNC 2, 234–250 (2012) – 10.15803/ijnc.2.2_234
  • Li, Y., Peng, S. & Chu, W. Hierarchical Dual-Net: A Flexible Interconnection Network and its Routing Algorithm. IJNC 2, 234–250 (2012) – 10.15803/ijnc.2.2_234
  • Foschia, R., Rauber, T. & Runger, G. Modeling the communication behavior of the Intel Paragon. Proceedings Fifth International Symposium on Modeling, Analysis, and Simulation of Computer and Telecommunication Systems 117–124 doi:10.1109/mascot.1997.567594 – 10.1109/mascot.1997.567594
  • Li, Y., Peng, S. & Chu, W. Hierarchical Dual-Net: A Flexible Interconnection Network and its Routing Algorithm. IJNC 2, 234–250 (2012) – 10.15803/ijnc.2.2_234
  • Athas, W. C. & Seitz, C. L. Multicomputers: message-passing concurrent computers. Computer 21, 9–24 (1988) – 10.1109/2.73
  • Li, Y., Peng, S. & Chu, W. Hierarchical Dual-Net: A Flexible Interconnection Network and its Routing Algorithm. IJNC 2, 234–250 (2012) – 10.15803/ijnc.2.2_234
  • Li, Y., Peng, S. & Chu, W. Hierarchical Dual-Net: A Flexible Interconnection Network and its Routing Algorithm. IJNC 2, 234–250 (2012) – 10.15803/ijnc.2.2_234
  • Dally, W. J. & Seitz, C. L. The torus routing chip. Distrib Comput 1, 187–196 (1986) – 10.1007/bf01660031
  • Li, Y., Peng, S. & Chu, W. Hierarchical Dual-Net: A Flexible Interconnection Network and its Routing Algorithm. IJNC 2, 234–250 (2012) – 10.15803/ijnc.2.2_234
  • Li, Y., Peng, S. & Chu, W. Hierarchical Dual-Net: A Flexible Interconnection Network and its Routing Algorithm. IJNC 2, 234–250 (2012) – 10.15803/ijnc.2.2_234
  • Samman, F., Hollstein, T. & Glesner, M. New Theory for Deadlock-Free Multicast Routing in Wormhole-Switched Virtual-Channelless Networks-on-Chip. IEEE Trans. Parallel Distrib. Syst. 22, 544–557 (2011) – 10.1109/tpds.2010.120
  • Li, Y., Peng, S. & Chu, W. Hierarchical Dual-Net: A Flexible Interconnection Network and its Routing Algorithm. IJNC 2, 234–250 (2012) – 10.15803/ijnc.2.2_234
  • Moharam, H., Abd El-Baky, M. A. & Nassar, S. M. M. YOMNA – An efficient deadlock-free multicast wormhole algorithm in 2-D mesh multicomputers. Journal of Systems Architecture 46, 1073–1091 (2000) – 10.1016/s1383-7621(00)00010-2
  • Wang, N.-C., Chu, C.-P. & Chen, T.-S. A dual-hamiltonian-path-based multicasting strategy for wormhole-routed star graph interconnection networks. Journal of Parallel and Distributed Computing 62, 1747–1762 (2002) – 10.1016/s0743-7315(02)00007-2
  • Xiaola Lin, McKinley, P. K. & Ni, L. M. Deadlock-free multicast wormhole routing in 2-D mesh multicomputers. IEEE Trans. Parallel Distrib. Syst. 5, 793–804 (1994) – 10.1109/71.298203
  • Fleury, E. & Fraigniaud, P. Strategies for Path-Based Multicasting in Wormhole-Routed Meshes. Journal of Parallel and Distributed Computing 53, 26–62 (1998) – 10.1006/jpdc.1998.1473
  • McKinley, P. K., Yih-jia Tsai & Robinson, D. F. Collective communication in wormhole-routed massively parallel computers. Computer 28, 39–50 (1995) – 10.1109/2.476198
  • Matam, R. & Tripathy, S. WRSR: wormhole-resistant secure routing for wireless mesh networks. J Wireless Com Network 2013, (2013) – 10.1186/1687-1499-2013-180
  • Karlsson, J., Dooley, L. & Pulkkis, G. Identifying Time Measurement Tampering in the Traversal Time and Hop Count Analysis (TTHCA) Wormhole Detection Algorithm. Sensors 13, 6651–6668 (2013) – 10.3390/s130506651
  • Kumar, D. R., Najjar, W. A. & Srimani, P. K. A new adaptive hardware tree-based multicast routing in k-ary n-cubes. IEEE Trans. Comput. 50, 647–659 (2001) – 10.1109/12.936232
  • Fan, J. Hamilton-connectivity and cycle-embedding of the Möbius cubes. Information Processing Letters 82, 113–117 (2002) – 10.1016/s0020-0190(01)00256-3
  • El-Obaid, A. Broadcast Wormhole-Routed 3-D Mesh Networks. IJCNC 7, 153–167 (2015) – 10.5121/ijcnc.2015.7411
  • Li, Y., Peng, S. & Chu, W. Hierarchical Dual-Net: A Flexible Interconnection Network and its Routing Algorithm. IJNC 2, 234–250 (2012) – 10.15803/ijnc.2.2_234
  • Li, Y., Peng, S. & Chu, W. Hierarchical Dual-Net: A Flexible Interconnection Network and its Routing Algorithm. IJNC 2, 234–250 (2012) – 10.15803/ijnc.2.2_234
  • Hamed, K. & A. El-Sayed, M. BTL - An Efficient Deadlock-Free Multicast Wormhole Algorithm to Optimize Traffic in 2D Torus Multicomputers. IJCA 111, 32–37 (2015) – 10.5120/19546-1415
  • Axelrod, T. S. Effects of synchronization barriers on multiprocessor performance. Parallel Computing 3, 129–140 (1986) – 10.1016/0167-8191(86)90030-x
  • Wang Hao & Wu Ling. Preconcerted wormhole routing algorithm for Mesh structure based on the network on chip. 2012 International Conference on Information Management, Innovation Management and Industrial Engineering 154–158 (2012) doi:10.1109/iciii.2012.6339801 – 10.1109/iciii.2012.6339801
  • Li, Y., Peng, S. & Chu, W. Hierarchical Dual-Net: A Flexible Interconnection Network and its Routing Algorithm. IJNC 2, 234–250 (2012) – 10.15803/ijnc.2.2_234
  • Moadeli, M. & Vanderbauwhede, W. A Communication Model of Broadcast in Wormhole-Routed Networks on-Chip. 2009 International Conference on Advanced Information Networking and Applications 315–322 (2009) doi:10.1109/aina.2009.126 – 10.1109/aina.2009.126
  • Seo, J. & Lee, H. Link-Disjoint Broadcasting Algorithm in Wormhole-Routed 3D Petersen-Torus Networks. International Journal of Distributed Sensor Networks 9, 501974 (2013) – 10.1155/2013/501974
  • Shen, Z. A generalized broadcasting schema for the mesh structures. Applied Mathematics and Computation 186, 1293–1310 (2007) – 10.1016/j.amc.2006.07.153
  • Seo, J. Three-dimensional Petersen-torus network: a fixed-degree network for massively parallel computers. J Supercomput 64, 987–1007 (2011) – 10.1007/s11227-011-0716-z
  • Li, Y., Peng, S. & Chu, W. Hierarchical Dual-Net: A Flexible Interconnection Network and its Routing Algorithm. IJNC 2, 234–250 (2012) – 10.15803/ijnc.2.2_234
  • Li, Y., Peng, S. & Chu, W. Hierarchical Dual-Net: A Flexible Interconnection Network and its Routing Algorithm. IJNC 2, 234–250 (2012) – 10.15803/ijnc.2.2_234
  • El-Obaid, A. Three-Dimension Hamiltonian Broadcast Wormhole-Routing. IJCNC 7, 31–46 (2015) – 10.5121/ijcnc.2015.7303
  • El-Obaid, A. & Zuo, W.-L. An Efficient Path-Based Multicast Algorithm for Minimum Communication Steps. Information Technology J. 7, 32–39 (2007) – 10.3923/itj.2008.32.39
  • Amnah, E.-O. & Zuo, W.-L. Hamiltonian Paths for Designing Deadlock-Free Multicasting Wormhole-Routing Algorithms in 3-D Meshes. J. of Applied Sciences 7, 3410–3419 (2007) – 10.3923/jas.2007.3410.3419
  • Li, Y., Peng, S. & Chu, W. Hierarchical Dual-Net: A Flexible Interconnection Network and its Routing Algorithm. IJNC 2, 234–250 (2012) – 10.15803/ijnc.2.2_234
  • Li, Y., Peng, S. & Chu, W. Hierarchical Dual-Net: A Flexible Interconnection Network and its Routing Algorithm. IJNC 2, 234–250 (2012) – 10.15803/ijnc.2.2_234