Shortest path routing algorithm for hierarchical interconnection network-on-chip

Article English OPEN
Inam, Omair ; Al Khanjari, Sharifa ; Vanderbauwhede, Wim (2015)

Interconnection networks play a significant role in efficient on-chip communication for multicore systems. This paper introduces a new interconnection topology called the Hierarchical Cross Connected Recursive network (HCCR) and a shortest path routing algorithm for the HCCR. Proposed topology offers a high degree of regularity, scalability, and symmetry with a reduced number of links and node degree. A unique address encoding scheme is proposed for hierarchical graphical representation of HCCR networks, and based on this scheme a shortest path routing algorithm is devised. The algorithm requires 5(k-1) time where k=logn4-2 and k>0, in worst case to determine the next node along the shortest path.
  • References (12)
    12 references, page 1 of 2

    1. Bononi, L., & Concer, N. (2006, March). Simulation and analysis of network on chip architectures: ring, spidergon and 2D mesh. In Proceedings of the conference on Design, automation and test in Europe: Designers' forum (pp. 154-159). European Design and Automation Association.

    2. Singh, H., Lee, M. H., Lu, G., Kurdahi, F. J., Bagherzadeh, N., & Chaves Filho, E. M. (2000). MorphoSys: an integrated reconfigurable system for data-parallel and computation-intensive applications. Computers, IEEE Transactions on,49(5), 465-481.

    3. Duh, D. R., & Chen, G. H. (1994). Topological properties of WK-recursive networks. Journal of Parallel and Distributed Computing, 23(3), 468-474.

    4. Mirza-Aghatabar, M., Koohi, S., Hessabi, S., & Pedram, M. (2007, August). An empirical investigation of mesh and torus NoC topologies under different routing algorithms and traffic models. In Digital System Design Architectures, Methods and Tools, 2007. DSD 2007. 10th Euromicro Conference on (pp. 19-26). IEEE.

    5. Karim, F., Nguyen, A., Dey, S., & Rao, R. (2001, June). On-chip communication architecture for OC-768 network processors. In Proceedings of the 38th annual Design Automation Conference (pp. 678-683). ACM.

    6. Bononi, L., & Concer, N. (2006, March). Simulation and analysis of network on chip architectures: ring, spidergon and 2D mesh. In Proceedings of the conference on Design, automation and test in Europe: Designers' forum (pp. 154-159). European Design and Automation Association.

    7. Xue, L., Shi, F., & Ji, W. (2011). 3D floorplanning of low-power and area-efficient Network-on-Chip architecture. Microprocessors and Microsystems,35(5), 484-495.

    8. Yu, X., & Li, T. S. (2009, October). On shortest path routing algorithm in crossed cube-connected ring networks. In Cyber-Enabled Distributed Computing and Knowledge Discovery, 2009. CyberC'09. International Conference on (pp. 348-354). IEEE.

    9. Dobravec, T., Žerovnik, J., & Robič, B. (2006). An optimal message routing algorithm for circulant networks. Journal of Systems Architecture, 52(5), 298-306.

    10. Su, M. Y., Chen, G. H., & Duh, D. R. (1997). A shortest path routing algorithm for incomplete WK-recursive networks. Parallel and Distributed Systems, IEEE Transactions on, 8(4), 367-379.

  • Metrics
    No metrics available
Share - Bookmark