Efficient Multicast Routing in Reconfigurable Networks-on-Chip
Subject Areas : electrical and computer engineeringF. Nasiri 1 , 2 * , Ahmad Khademzadeh 3
1 -
2 -
3 -
Keywords: Network on chip reconfigurable network multicast routing power consumption message latency,
Abstract :
Several routing algorithms have been presented for multicast and unicast traffic in MPSoCs. Multicast protocols in NoCs are used for clock synchronization, cache coherency in distributed shared memory on-chip multiprocessors, replication and barrier synchronization. Unicast routing algorithms are not useful for multicast. Indeed, when unicast routing algorithms are employed to realize multicast operation, high traffic, congestion and deadlock are imposed to the network. To prevent from these problems, Tree-based and path based techniques have been proposed for multicast in multicomputers (and recently NoCs). In this paper, we present a new multicast routing method to decrease power consumption and multicast message latency based on a reconfigurable NoC architecture. In this line, we benefit from simple switches in our reconfigurable architecture instead of routers; we then divide the network to smaller partitions to make better trees for conducting multicast packets. Our evaluation results reveal that, for both real and synthetic traffic loads, the proposed method outperforms the baseline tree-based routing method in a reconfigurable mesh, and reduces message latency by up to 51% and power consumption by up to 33%.
[1] W. J. Dally and B. Towles, "Route packets, not wires: on-chip interconnection networks," in Proc. Design Automation Conf,. DAC’01, pp. 684-689, Las Vegas, NV, USA, 22-22 Jun. 2001.
[2] W. O. Cesario, et al., "Multiprocessor SoC platforms: a component-based design approach," IEEE Design & Test of Computers, vol. 19, no.6, pp. 52-63, Nov.-Dec. 2002.
[3] L. Benini and G. De Micheli, "Networks on chips: a new SoC paradigm," Computer, vol. 35, no. 1, pp. 70-78, Jan. 2002. [4] N. E. Jerger, L. S. Peh, and M. H. Lipasti, "Virtual circuit tree multicasting: a case for onchip hardware multicast support," in Proc. of the Int. Conf. on Computer Architecture, pp. 229-240, Beijing, China, 21-25 Jun. 2008.
[5] P. McKinely, H. Xu, A. H. Esfahanian, and L. Ni, "Unicast-based multicast communication in wormhole-routed networks," IEEE Trans. of Parallel and Distributed Systems, vol. 5, no. 12, pp. 1252-1265, Dec. 1994.
[6] E. A. Carara and F. G. Moraes, "Deadlock-free multicast routing algorithm for wormhole-switched mesh networks-on-chip," in Proc. Computer Society Annual Symp. on the VLSI, ISVLSI’08, pp. 341-346, Montpellier, France, 7-9 Apr. 2008.
[7] X. Lin and L. M. Ni, "Multicast communication in multicomputer networks," IEEE Trans. on Parallel and Distributed Systems, vol. 4, no. 10, pp. 1105-1117, Oct. 1993.
[8] F. Nasiri, H. Sarbazi-Azad, and A. Khademzadeh, "Reconfigurable multicast routing for networks on chip," Microprocessors and Microsystems, vol. 42, pp. 180-189, May 2016.
[9] M. Modarressi, A. Tavakkol, and H. Sarbazi-Azad, "Application-aware topology reconfiguration for on-chip networks," IEEE Trans. on Very Large-Scale Integrated Circuits and Systems, vol. 19, no. 11, pp. 2010-2022, Nov. 2011.
[10] M. Modarressi and H. Sarbazi-Azad, "Reconfigurable cluster-based networks-on-chip for application-specific MPSoCs," in Proc. IEEE 23rd Int. Conf. on Application-Specific Systems, Architectures, and Pricessors, ASAP’12, pp. 153-156, Delft, Netherlands, 9-11 Jul. 2012.
[11] Y. Choi and T. M. Pinkston, "Evaluation of crossbar architectures for deadlock recovery routers," J. of Parallel and Distributed Computing, vol. 61, no. 1, pp. 49-78, Jan. 2001.
[12] R. V. Boppana, S. Chalasani, and C. S. Raghavendra, "Resource deadlock and performance of wormhole multicast routing algorithms," IEEE Trans. on Parallel and Distributed Systems, vol. 9, no. 6, pp. 535-549, Jun. 1998.
[13] M. Ebrahimi, M. Danestalab, P. Liljeberg, and H. Tenhunen, "HAMUM-a novel routing protocol for unicast and multicast traffic in MPSocs," in Proc. 18th Euro Micro Conf. on Parallel, Distributed and Network Based Processing, PDP’10, pp. 525-532, Pisa, Italy, 17-19 Feb. 2010.
[14] P. Bahrebar and D. Stroobandt, "Improving hamiltonian-based routing methods for on-chip networks: a turn model approach," in Proc. 14th Conf. on Design, Automation & Test in Europe, DATE’14, 4 pp., Dresden, Germany, 24-28 Mar. 2014.
[15] M. R. Arun, P. A. Jisha, and J. Jose, "A novel energy efficient multicasting approach for mesh NoCs," Procedia Computer Science, vol. 93, pp. 283-291, 2016.
[16] M. R. Arun and P. A. Jisha, "SMDP-single message duplicate in partition, a multicast routing method in mesh 2D NoC," in Proc. 3rd Int. Conf. on Innovations in Information Embedded and Communication Systems, pp. 676-680, 2016.
[17] Z. Wang, et al., "An adaptive partition-based multicast routing scheme for mesh-based networks-on-chip," Computers & Electrical Engineering, vol. 51, pp. 235-251, Apr. 2016.
[18] Xmulator NoC Simulator, Available: www.xmulator.org, Apr. 2012.
[19] W. Hu, Z. Lu, A. Jantsch, and H. Liu, "Power-efficient tree based multicast support for networks-on-chip," in Proc. 16th Asia and Pacific Design Automation Conf., ASP-DAC’11, pp. 363-368, Yokohama, Japan, 25-28 Jan. 2011.
[20] T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein, Introduction to Algorithms, MIT Press, 2001.
[21] C. J. Glass and L. M. Ni, "The turn model for adaptive routing," in Proc. Int. Conf. Computer Architecture, ISCA’92, pp. 278-287, Gold Coast, Australia, 19-21 May 1992.
[22] S. C. Woo, M. Ohara, E. Torrie, J. P. Singh, and A. Gupta, "The SPLASH-2 programs: characterization and methodological considerations," in Proc. Int. Conf. Computer Architecture, ISCA’95, vol. 23, pp. 24-36, S. Margherita Ligure, Italy, 22-24 Jun. 1995.
[23] A. Nayebi, S. Meraji, A. Shamaei, and H. Sarbazi-Azad, "XMulator: a listener-based integrated simulation platform for interconnection networks," in Proc. Int. Conf. on Modelling and Simulation, AMS’07, pp. 128-132, Phuket, Thailand, 27-30 Mar. 2007.
[24] W. Hang-Sheng, Z. Xinping, P. Li-Shiuan, and S. Malik, "Orion: a power-performance simulator for interconnection networks," in Proc. 35th Annual IEEE/ACM Int. Symp. on Microarchitecture, MICRO’02, pp. 294-305, Istanbul, Turkey, 18-22 Nov. 2002.
[25] H. Kahng, B. Li, L. Peh, and K. Samadi, "ORION 2.0: a fast and accurate NoC power and area model for early-stage design space exploration," in Proc. 9th Conf. on Design, Automation & Test in Europe, DATE’09, pp. 423-428, Nice, France, 20-24 Apr. 2009.