مسیریابی منطقهای توانآگاه برای شبکههایروی تراشه سهبعدی نیمهمتصل
محورهای موضوعی : مهندسی برق و کامپیوترمیترا معلم نیا 1 , هادی شهریار شاه حسینی 2 *
1 - دانشگاه علم و صنعت ايران
2 - دانشگاه علم و صنعت ایران
کلید واژه: شبکه روی تراشه, مسیریابی در شبکه, مدیریت انرژی, ارزیابی کارایی,
چکیده مقاله :
شبکههای روی تراشه،یک بستر ارتباطی کارآمد را برای برقراری ارتباط بین تعداد بالای هسته پردازشی در تراشههای مدرن امروز فراهم میکنند. با این حال کاهش ابعاد ترانزیستورها سبب شده تا مصرف توان ایستا به یکی از مسائل مهم در این شبکهها تبدیلگردد. معمولاً از روش قطع تغذیه سیستم بر روی کانالهای مجازی در زمان بیکاریشان برای کاهش توان مصرفی شبکه استفاده میشود؛ اما پراکندگی بار در سطح شبکه و عدم پیوستگی دوره بیکاری در کانالهای مجازی باعث روشن و خاموششدن متوالی این منابع میشود که سربار تأخیر و توان مصرفی را به دنبال دارد. این مسئله در شبکههای روی تراشه سهبعدی نیمهمتصل که تعداد اتصالات عمودیشان محدود میباشد از اهمیت بیشتری برخوردار است. در این مقاله،یک الگوریتم مسیریابی برای شبکههای سهبعدی نیمهمتصل ارائه میشود که با توزیع مناسب بستهها، پراکندگی بار را در شبکه کاهش میدهد تا یک دوره بیکاری پیوسته در کانالهای مجازی ایجاد کند. به این ترتیب میتوان با بیشتر خاموش نگه داشتن آنها بهترین تأثیر را از روش قطع تغذیه سیستم در مدیریت توان مصرفی گرفت. این مسیریابی با تقسیمبندی شبکه به دو منطقه شمالی و جنوبی و ایجاد محدودیت در استفاده از آسانسورهای هر منطقه، سعی دارد که بستهها را از مسیرهایی عبور دهد که اخیراً بیشتر استفاده شدهاند تا دوره بیکاری را در منابع پرمصرف موجود در مسیرهای کمتردد افزایش دهد. نتایج شبیهسازی تحت شبیهسازBooksim نشان میدهند که مسیریابی پیشنهادی در مقایسه با مسیریابیهای دیگر، توانسته 18% تا 30% بهبود در توان مصرفی شبکه ایجاد کند و عملکرد شبکه را نیز از نظر تأخیر تا 32% بهبود بخشد.
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.