Regional Power-Aware Routing for Partially-Connected 3D Network-on-Chip
Subject Areas : electrical and computer engineeringMitra Moalemnia 1 , HadiShahriar Shahhoseini 2
1 - Student
2 - Iran University of Science and Technology
Keywords: Network-on-chip, routing algorithm, energy management, performance evaluation,
Abstract :
Network-on-chip provides an efficient communication platform for Systems-on-chip. The static power consumption is an important issue in these networks. Switching the power supply on virtual channels during idle time is a common method for reducing the network power consumption. The traffic load at the network level and non-continuous idle period of virtual channel have caused the sources to be switched on and off continuously, which leads to increase in power consumption and other overheads. This will be more important, in partially connected 3D chip networks in which a limited number of vertical connections has been used. In this paper, a routing algorithm is proposed who employs an appropriate policy for packet distribution, and reduces the load distribution in the network and creates a continuous idle time for the resources, result in suitable power management in the network. In this routing scheme the network is divided to north and south region and some restriction applied in usage of elevators in each region and try to increase the utilization of the used resources as well as the ideal time of low traffic paths. The simulation results, derived by BookSim, show the proposed method improve the network power consumption by 18% to 30% comparing previous algorithms, and the network delay has been reduced by 32%.
[1] W. J. Dally and B. P. Towles, Principles and Practices of Interconnection Networks, Morgan Kaufmann San Fr., p. 588, Mar. 2004.
[2] J. Henkel, W. Wolf, and S. Chakradhar, "On-chip networks: a scalable, communication-centric embedded system design paradigm," in Proc. IEEE Int. Conf. VLSI Des., pp. 845-851, Mumbai, India, 9-9 Jan. 2004.
[3] V. F. Pavlidis and E. G. Friedman, "3-D topologies for networks-on-chip," IEEE Trans. on Very Large Scale Integration (VLSI) Systems, vol. 15, no. 10, pp. 1081-1090, Sep. 2006.
[4] K. Manna, S. Chattopadhyay, and I. Sengupta, "Through silicon via placement and mapping strategy for 3D mesh based network-on-chip," in Proc. IEEE/IFIP Int. Conf. VLSI Syst. VLSI-SoC, 6 pp., Playa del Carmen, Mexico, 6-8 Oct. 2014.
[5] A. I. Arka, S. Gopal, J. R. Doppa, D. Heo, and P. P. Pande, "Making a case for partially connected 3D NoC: NFIC versus TSV," ACM J. Emerg. Technol. Comput. Syst., vol. 16, no. 4, pp. 1-17, Aug. 2020.
[6] M. Bahmani, A. Sheibanyrad, F. Pétrot, F. Dubois, and P. Durante, "A 3D-NoC router implementation exploiting vertically-partially-connected topologies," in Proc. IEEE Comput. Soc. Annu. Symp. VLSI, ISVLSI, pp. 9-14, Amherst, MA, USA, 19-21 Aug. 2012.
[7] A. Coelho, A. Charif, N. E. Zergainoh, and R. Velazco, "A runtime fault-tolerant routing scheme for partially connected 3D networks-on-chip," in Proc. IEEE Int. Symp. Defect Fault Toler. VLSI Nanotechnol. Syst. DFT, 6 pp., Chicago, IL, USA, 8-10 Oct. 2018.
[8] E. Ofori-Attah, W. Bhebhe, and M. O. Agyeman, "Architectural techniques for improving the power consumption of NoC-based CMPS: a case study of cache and network layer," J. Low Power Electron. Appl., vol. 7, no. 2, pp. 1-24, May 2017.
[9] H. Zheng and A. Louri, "EZ-Pass: an energy & performance-efficient power-gating router architecture for scalable NoCs," IEEE Comput. Archit. Lett., vol. 17, no. 1, pp. 88-91, Jan./Jun. 2018.
[10] H. Matsutani, M. Koibuchi, H. Amano, and D. Wang, "Run-time power gating of on-chip routers using look-ahead routing," in Proc. Asia South Pacific Des. Autom. Conf. ASP-DAC, pp. 55-60, Seoul, South Korea, 21-24 Mar. 2008.
[11] N. Nasirian, R. Soosahabi, and M. A. Bayoumi, "Probabilistic analysis of power-gating in network-on-chip routers," IEEE Trans. Circuits Syst. II Express Briefs, vol. 66, no. 2, pp. 242-246, Feb. 2019.
[12] L. Chen, D. Zhu, M. Pedram, and T. M. Pinkston, "Power punch: towards non-blocking power-gating of NoC routers," in Proc. IEEE 21st Int. Symp. High Perform. Comput. Archit. HPCA'15, pp. 378-389, Burlingame, CA, USA, 7-11 Feb. 2015.
[13] P. Wang, S. Niknam, Z. Wang, and T. Stefanov, "A novel approach to reduce packet latency increase caused by power gating in network-on-chip," in Proc. 11th IEEE/ACM Int. Symp. Networks-on-Chip, NOCS'17, 8 pp., Seoul, South Korea, 19-20 Oct. 2017.
[14] H. Farrokhbakht, M. Taram, B. Khaleghi, and S. Hessabi, "TooT: an efficient and scalable power-gating method for NoC routers," in Proc. 10th IEEE/ACM Int. Symp. Networks-on-Chip, NOCS'16, 8 pp., Nara, Japan 31 Aug.-2 Sept. 2016.
[15] H. Farrokhbakht, H. M. Kamali, N. E. Jerger, and S. Hessabi, "SPONGE: a scalable pivot-based on/off gating engine for reducing static power in NoC routers," in Proc. Int. Symp. Low Power Electron. Des., 6 pp., Seattle, WA, USA ,23-25 Jul. 2018.
[16] H. Farrokhbakht, H. Kao, and N. E. Jerger, " UBERNoC: unified buffer power-efficient router for network-on-chip," in Proc. 13th IEEE ACM Int. Symp. Networks-on-Chip, NOCS'19, 8 pp., New York, NY, USA, 17-18 Oct. 2019.
[17] D. Zoni, et al., "BlackOut: enabling fine-grained power gating of buffers in network-on-chip routers," J. Parallel Distrib. Comput., vol. 104, pp. 130-145, Jun. 2017.
[18] F. Wang, X. Tang, Q. Wang, Z. Xing, and H. Liu, "Flexible virtual channel power-gating for high-throughput and low-power network-on-chip," in Proc. 17th Euromicro Conf. Digit. Syst. Des. DSD'14, pp. 504-511, Verona, Italy, 27-29 Aug. 2014.
[19] A. Mirhosseini, M. Sadrosadati, A. Fakhrzadehgan, M. Modarressi, and H. Sarbazi-Azad, "An energy-efficient virtual channel power-gating mechanism for on-chip networks," in Proc. Design, Autom. Test Eur. DATE, pp. 1527-1532, Grenoble, France, 9-13 Mar. 2015.
[20] P. Wang, On the Power Efficiency, Low Latency, and Quality of Service in Network-on-Chip Peng Wang, PhD Diss., Leiden Universiteit, Jun. 2020.
[21] Y. Wu, et al., "Aggressive fine-grained power gating of NoC buffers," IEEE Trans. Comput. Des. Integr. Circuits Syst., vol. 39, no. 11, pp. 3177-3189, Nov. 2020.
[22] H. Farrokhbakht, H. M. Kamali, and S. Hessabi, "SMART: a scalable mapping and routing technique for power-gating in NoC routers," in Proc. of the 11th IEEE/ACM International Symposium on Networks-on-Chip, 8 pp., Seoul, South Korea, 19-20 Oct. 2017.
[23] M. Safari, Z. Shirmohammadi, N. Rohbani, and H. Farbeh, "LETHOR: a thermal-aware proactive routing algorithm for 3D NoCs with less entrance to hot regions," The J. of Supercomputing, vol. 78, no. 6, pp. 1-25, Apr. 2022.
[24] F. Dubois, A. Sheibanyrad, F. Ptrot, and M. Bahmani, "Elevator-first: a deadlock-free distributed routing algorithm for vertically partially connected 3D-NoCs," IEEE Trans. Comput., vol. 62, no. 3, pp. 609-615, Mar. 2013.
[25] A. Coelho, A. Charif, N. E. Zergainoh, and R. Velazco, "FL-RuNS: a high-performance and runtime reconfigurable fault-tolerant routing scheme for partially connected three-dimensional networks on chip," IEEE Trans. Nanotechnol., vol. 18, pp. 806-818, 2019.
[26] R. Salamat, M. Khayambashi, M. Ebrahimi, and N. Bagherzadeh, "LEAD: an adaptive 3D-NoC routing algorithm with queuing-theory based analytical verification," IEEE Trans. Comput., vol. 67, no. 8, pp. 1153-1166, Feb. 2018.
[27] A. Charif, N. E. Zergainoh, A. Coelho, and M. Nicolaidis, "Rout3D: a lightweight adaptive routing algorithm for tolerating faulty vertical links in 3D-NoCs," in Proc. Eur. Test Work., 6 pp., Limassol, Cyprus, 22-26 May 2017.
[28] A. A. Da Silva, L. M. E. Silva Junior, A. Coelho, J. Silveira, and C. Marcon, "Reflect3d: an adaptive and fault-tolerant routing algorithm for vertically-partially-connected 3D-NoC," in Proc. 34th SBC SBMicro IEEE ACM Symp. on Integrated Circuits and Systems Design, SBCCI'21, 6 pp., Campinas, Brazil, 23-27 Aug. 2021.
[29] M. Nezarat, H. S. Shahhoseini, and M. Momeni, "Thermal-aware routing algorithm in partially connected 3D NoC with dynamic availability for elevators," J. of Ambient Intelligence and Humanized Computing, pp. 1-14, Aug. 2022.
[30] A. Charif, A. Coelho, M. Ebrahimi, N. Bagherzadeh, and N. E. Zergainoh, "First-last: a cost-effective adaptive routing solution for TSV-based three-dimensional networks-on-chip," IEEE Trans. Comput., vol. 67, no. 10, pp. 1430-1444, Apr. 2018.
[31] M. Ebrahimi, et al., "DyXYZ: fully adaptive routing algorithm for 3D NoCs," in Proc. 21st Euromicro Int. Conf. Parallel, Distrib. Network-Based Process., PDP'18, pp. 499-503, Belfast, UK, 27 Feb.-1 Mar. 2013.
[32] E. Taheri, R. G. Kim, and M. Nikdast, "AdEle: an adaptive congestion-and-energy-aware elevator selection for partially connected 3D NoCs," in Proc. 58th ACM/IEEE Design Automation Conf., DAC'21, pp. 67-72, San Francisco, CA, USA, 5-9 Dec. 2021.
[33] Y. Fu, et al., "Congestion-aware dynamic elevator assignment for partially connected 3D-NoCs," in Proc. IEEE Int. Symp. Circuits Syst., 5 pp., Sapporo, Japan, 26-29 May 2019.
[34] M. Ebrahimi and M. Daneshtalab, "EbDa: a new theory on design and verification of deadlock-free interconnection networks," in Proc. Int. Symp. Comput. Archit., pp. 703-715, Toronto, Canada, 24-28 Jun. 2017.
[35] N. Jiang, G. Michelogiannakis, D. Becker, B. Towles, and W. J. Dally, Booksim 2.0 User's Guide, Standford Univ., pp. 1-10, Mar. 2010.
[36] H. S. Wang, X. Zhu, L. S. Peh, and S. Malik, "Orion: a power-performance simulator for interconnection networks," in Proc. Annu. Int. Symp. Microarchitecture, MICRO'02, pp. 294-305, Istanbul, Turkey 18-22 Nov. 2002.