کد مقاله : 1400092032611 بازدید : 4247 صفحه: 13 - 23

نوع مقاله: پژوهشی

مسیریابی منطقه‌ای توان‌آگاه برای شبکه‌هایروی تراشه سه‌بعدی نیمه‌متصل

محورهای موضوعی : مهندسی برق و کامپیوتر

میترا معلم نیا ¹ , هادی شهریار شاه حسینی ²

1 - دانشگاه علم و صنعت ايران
2 - دانشگاه علم و صنعت ایران

تاریخ دریافت : 1400/09/20 تاریخ پذیرش : 1401/08/23 تاریخ انتشار : 1402/02/13

کلید واژه: شبکه روی تراشه, مسیریابی در شبکه, مدیریت انرژی, ارزیابی کارایی,

چکیده مقاله :

شبکه‌های روی تراشه،یک بستر ارتباطی کارآمد را برای برقراری ارتباط بین تعداد بالای هسته پردازشی در تراشه‌های مدرن امروز فراهم می‌کنند. با این‌ حال کاهش ابعاد ترانزیستورها سبب شده تا مصرف توان ایستا به یکی از مسائل مهم در این شبکه‌ها تبدیلگردد. معمولاً از روش قطع تغذیه سیستم بر روی کانال‌های مجازی در زمان بیکاری‌شان برای کاهش توان مصرفی شبکه استفاده می‌شود؛ اما پراکندگی بار در سطح شبکه و عدم پیوستگی دوره بیکاری در کانال‌های مجازی باعث روشن و خاموش‌شدن متوالی این منابع می‌شود که سربار تأخیر و توان مصرفی را به دنبال دارد. این مسئله در شبکه‌های روی تراشه سه‌بعدی نیمه‌متصل که تعداد اتصالات عمودی‌شان محدود می‌باشد از اهمیت بیشتری برخوردار است. در این مقاله،یک الگوریتم مسیریابی برای شبکه‌های سه‌بعدی نیمه‌متصل ارائه می‌شود که با توزیع مناسب بسته‌ها، پراکندگی بار را در شبکه کاهش می‌دهد تا یک دوره بیکاری پیوسته در کانال‌های مجازی ایجاد ‌کند. به این ترتیب می‌توان با بیشتر خاموش نگه داشتن آنها بهترین تأثیر را از روش قطع تغذیه سیستم در مدیریت توان مصرفی گرفت. این مسیریابی با تقسیم‌بندی شبکه به دو منطقه شمالی و جنوبی و ایجاد محدودیت در استفاده از آسانسورهای هر منطقه، سعی دارد که بسته‌ها را از مسیرهایی عبور ‌دهد که اخیراً بیشتر استفاده شده‌اند تا دوره بیکاری را در منابع پرمصرف موجود در مسیرهای کم‌تردد افزایش ‌دهد. نتایج شبیه‌سازی تحت شبیه‌ساز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.

متن کامل:

معرفي يک روش جديد خوشه‌يابي خودکار

مقاله پژوهشی

مسیریابی منطقه‌ای توان‌آگاه برای شبکه‌های
روی تراشه سه‌بعدی نیمه‌متصل

میترا معلم‌نیا و هادی‌شهریار شاه‌حسینی

چكیده: شبکه‌های روی تراشه، یک بستر ارتباطی کارآمد را برای برقراری ارتباط بین تعداد بالای هسته پردازشی در تراشه‌های مدرن امروز فراهم می‌کنند. با این‌ حال کاهش ابعاد ترانزیستورها سبب شده تا مصرف توان ایستا به یکی از مسائل مهم در این شبکه‌ها تبدیل گردد. معمولاً از روش قطع تغذیه سیستم بر روی کانال‌های مجازی در زمان بیکاری‌شان برای کاهش توان مصرفی شبکه استفاده می‌شود؛ اما پراکندگی بار در سطح شبکه و عدم پیوستگی دوره بیکاری در کانال‌های مجازی باعث روشن و خاموش‌شدن متوالی این منابع می‌شود که سربار تأخیر و توان مصرفی را به دنبال دارد. این مسئله در شبکه‌های روی تراشه سه‌بعدی نیمه‌متصل که تعداد اتصالات عمودی‌شان محدود می‌باشد از اهمیت بیشتری برخوردار است. در این مقاله، یک الگوریتم مسیریابی برای شبکه‌های سه‌بعدی نیمه‌متصل ارائه می‌شود که با توزیع مناسب بسته‌ها، پراکندگی بار را در شبکه کاهش می‌دهد تا یک دوره بیکاری پیوسته در کانال‌های مجازی ایجاد ‌کند. به این ترتیب می‌توان با بیشتر خاموش نگه داشتن آنها بهترین تأثیر را از روش قطع تغذیه سیستم در مدیریت توان مصرفی گرفت. این مسیریابی با تقسیم‌بندی شبکه به دو منطقه شمالی و جنوبی و ایجاد محدودیت در استفاده از آسانسورهای هر منطقه، سعی دارد که بسته‌ها را از مسیرهایی عبور ‌دهد که اخیراً بیشتر استفاده شده‌اند تا دوره بیکاری را در منابع پرمصرف موجود در مسیرهای کم‌تردد افزایش ‌دهد. نتایج شبیه‌سازی تحت شبیه‌ساز Booksim نشان می‌دهند که مسیریابی پیشنهادی در مقایسه با مسیریابی‌های دیگر، توانسته 18% تا 30% بهبود در توان مصرفی شبکه ایجاد کند و عملکرد شبکه را نیز از نظر تأخیر تا 32% بهبود بخشد.

کلیدواژه: شبکه روی تراشه، مسیریابی در شبکه، مدیریت انرژی، ارزیابی کارایی.

1- مقدمه

به دنبال کاهش ابعاد ترانزیسورها، به تدریج تعداد هسته‌های پردازشی روی تراشه افزایش یافت و سبب شد تا ساختارهای ارتباطی قدیمی روی تراشه مانند گذرگاه² و اتصالات نقطه‌به‌نقطه³ که از مقیاس‌پذیری کمی برخوردار بودند، کارایی خود را از دست بدهند. به این ترتیب شبکه روی

(الف) (ب)

شکل 1: ساختمان یک شبکه سه‌بعدی، (الف) تمام‌متصل و (ب) نیمه‌متصل.

تراشه⁴ به‌عنوان یک ساختار ارتباطی مقیاس‌پذیر طراحی شد تا نیازهای ارتباطی تراشه‌های مدرن امروز با تعداد زیاد هسته ‌پردازشی را پوشش دهد [1] و [2]. اما طولانی‌شدن سیم‌ها در پی بزرگ‌ترشدن ابعاد تراشه، تأخیر در ارسال بسته‌ها و افت عملکرد شبکه را به همراه داشت.

به‌عنوان یک راه‌حل برای این مشکل، شبکه‌های روی تراشه سه‌بعدی⁵ معرفی شدند. در این شبکه‌ها لایه‌های سیلیکونی تراشه روی یکدیگر پشته شده‌اند و با استفاده از کانال‌های عمودی به یکدیگر متصل می‌شوند. به ‌این ‌ترتیب مساحت تراشه کاهش پیدا کرده و همین طور ارتباطات کوتاه‌تر و سریع‌تری برای شبکه فراهم آمده است [3]. رایج‌ترین فناوری برای ساخت کانال‌های عمودی ⁶TSV است و به همین دلیل به این کانال‌ها TSV نیز گفته می‌شود [4] و [5]. اما اتصالات عمودی مبتنی بر TSV، علی‌رغم مسیرهای کوتاه و سریعی که برای شبکه فراهم می‌کنند، فضای زیادی اشغال می‌کنند، هزینه ساخت بالایی نیز دارند و همین طور قابلیت اطمینان شبکه را با چالش روبه‌رو می‌کنند. این مسائل، ساخت یک تراشه سه‌بعدی تمام‌متصل را که در آن همه گره‌ها دارای TSV باشند با مشکل روبه‌رو می‌سازد. بنابراین در طراحی‌های جدید، تعداد TSVها در شبکه کاهش داده شد و شبکه‌های سه‌بعدی نیمه‌متصل را پدید آورد [6]. در شکل 1- الف و 1- ب، نمونه‌ای از یک شبکه سه‌بعدی تمام‌متصل و نیمه‌متصل به ترتیب آورده شده و همان طور که دیده می‌شود، در شکل 1- الف تمامی گره‌ها دارای کانال عمودی هستند. این در حالی است که در شکل 1- ب تنها سه گره دارای کانال عمودی می‌باشند که این سه کانال‌ به‌ صورت اشتراکی توسط همه گره‌های موجود در لایه استفاده می‌شوند. شبکه‌های نیمه‌متصل را می‌توان به یک ساختمان چندطبقه تشبیه کرد که دارای تعداد محدودی آسانسور است؛ به همین دلیل به کانال‌های عمودی، اصطلاحاً آسانسور نیز گفته می‌شود.

شکل 2: نمونه‌ای از یک مسیریاب سه‌بعدی.

مسیریابی⁷ از اصلی‌ترین پارامترهای شبکه روی تراشه است که وظیفه توزیع بسته‌ها را در شبکه بر عهده دارد. مسیریاب‌ها می‌توانند دوبعدی یا سه‌بعدی باشند و شکل 2 نمونه‌ای از یک مسیریاب سه‌بعدی را نشان می‌دهد. مسیریاب‌های دوبعدی دارای چهار درگاه ورودی/ خروجی برای ارتباط‌گرفتن با گره‌های موجود در همسایگی شمال، جنوب، غرب و شرق خود هستند. در حالی که مسیریاب‌های سه‌بعدی مطابق با شکل 2 علاوه بر این چهار درگاه، دارای دو درگاه بالا و پایین نیز می‌باشند تا با گره‌های موجود در همسایگی خود در لایه‌های بالایی و پایینی ارتباط برقرار کنند (در هر مسیریاب علاوه بر درگاه‌های ذکرشده، یک درگاه محلی نیز برای ارتباط با پردازنده محلی خود گره وجود دارد). در شبکه‌های نیمه‌متصل، تنها گره‌های دارای آسانسور، مسیریاب سه‌بعدی دارند و مسیریاب موجود در باقی گره‌ها دوبعدی است. مسیریابی از بخش‌های بسیار پراهمیت در شبکه‌های سه‌بعدی نیمه‌متصل است؛ زیرا که در این شبکه‌ها به دلیل محدودیت در تعداد آسانسورها، همه گره‌های موجود در یک لایه به ‌صورت اشتراکی از آنها استفاده می‌کنند [7]. این استفاده اشتراکی امکان ایجاد بن‌بست⁸ و یا از بین رفتن بسته‌ها بر اثر درگیری بر سر منابع مشترک را بالا می‌برد. بنابراین الگوریتم‌های مسیریابی معمولاً برای اجتناب از این مسائل از تعداد زیادی کانال مجازی⁹ اضافه در ورودی مسیریاب‌ها استفاده می‌کنند تا در هنگام اشغال‌بودن مسیرها بتوان بسته‌ها را برای مدتی ذخیره کرد. کانال‌های مجازی در واقع صف‌هایی مجزا از بافرها هستند که مطابق با شکل 2 در هر درگاه ورودی مسیریاب قرار دارند و برای انتقال داده‌ها کانال فیزیکی را به اشتراک می‌گذارند. به ‌این‌ ترتیب چندین بسته می‌توانند به‌ نوبت وارد یک درگاه ورودی مسیریاب شوند و در کانال‌های مجازی مجزا از هم قرار بگیرند؛ اما هر بار فقط به یکی اجازه داده می‌شود تا از گذرگاه عبور کرده و از کانال فیزیکی خروجی استفاده کند. بدیهی است که هرچه تعداد کانال‌های مجازی بیشتر باشد احتمال بن‌بست یا از بین رفتن بسته‌ها به دلیل اشغال‌بودن کانال فیزیکی کمتر است. اما همان قدر که مسیریابی در شبکه‌های سه‌بعدی نیمه‌متصل پراهمیت است، مصرف توان ایستا نیز از مسائل مهم در این شبکه‌ها به شمار می‌رود؛ چرا که از تعداد زیادی کانال مجازی در این شبکه‌ها استفاده می‌شود [8].

بافرهای کانال مجازی از منابع پرمصرف توان ایستا در شبکه‌های روی تراشه هستند. معمولاً از روش‌های کاهش توان مصرفی از جمله روش قطع تغذیه سیستم¹⁰ بر روی بافرها به ‌صورت گسترده در شبکه‌های روی تراشه استفاده می‌شود تا بتوان با حذف توان مصرفی این منابع در زمان بیکاری‌شان به کاهش توان مصرفی شبکه کمک کرد [9] و [10].

قطع تغذیه سیستم، زمانی می‌تواند بیشترین تأثیر را در کاهش توان مصرفی شبکه بگذارد که منابع برای مدت زمان بیشتری بیکار باشند. اما پراکندگی بار در سطح شبکه، روبه‌رویی بسته‌ها را با منابع خاموش بیشتر کرده که سبب روشن و خاموش‌شدن متوالی کانال‌های مجازی و افت بیشتری در عملکرد شبکه می‌شود. بنابراین اعمال این روش در کنار یک مسیریابی مناسب برای توزیع بسته‌ها با هدف افزایش دوره بیکاری در منابع، می‌تواند بهترین تأثیر را بر کاهش مصرف توان شبکه بگذارد.

از آنجا که مسیریابی از بخش‌های مهم در شبکه روی تراشه است که توزیع بسته‌ها در شبکه را بر عهده دارد، به‌کارگیری یک سیاست مناسب برای آن با هدف متمرکزکردن بار در برخی قسمت‌های شبکه می‌تواند این پراکندگی را تا جای ممکن کاهش دهد و از روشن‌شدن متوالی بافرهای بیکار تا جای ممکن جلوگیری کند. به این ‌ترتیب می‌توان بیشترین تأثیر را از روش قطع تغذیه سیستم در ذخیره توان مصرفی گرفت و همچنین با کاهش تأخیر روشن‌شدن منابع، عملکرد شبکه را بهبود بخشید. با این حال الگوریتم‌های مسیریابی سنتی در شبکه‌های سه‌بعدی نیمه‌متصل، علی‌رغم استفاده زیاد از کانال‌های مجازی، قادر به مدیریت توان یا فراهم‌کردن شرایط برای به‌کارگیری روش‌های کاهش توان مصرفی در شبکه نیستند. این الگوریتم‌ها از تعداد قابل ‌توجهی کانال مجازی استفاده می‌نمایند و بار را به ‌صورت پراکنده در شبکه پخش می‌کنند که سبب روبه‌رویی متوالی بسته‌ها با منابع کم‌کار می‌شود.

به این منظور یک مسیریابی نیمه‌وفق‌پذیر و بدون بن‌بست در این مقاله پیشنهاد می‌شود که هدف آن کاهش پراکندگی بار و افزایش دوره بیکاری در بافرها برای ذخیره بیشتر توان مصرفی در شبکه است. همین طور با کاهش تعداد دفعات روشن و خاموش‌شدن این منابع، در کاهش تأخیر و بهبود عملکرد شبکه تأثیر بسزایی می‌گذارد. مسیریابی پیشنهادی از تعداد کمی کانال مجازی استفاده می‌کند و با تقسیم شبکه به دو منطقه شمالی و جنوبی و ایجاد محدودیت در استفاده از آسانسورها، بار را در برخی مسیرهای شبکه متمرکز می‌کند. به این ترتیب می‌توان منابع بیکار و پرمصرف موجود در سایر مسیرهای شبکه را برای مدت زمان بیشتری خاموش نگه داشت و بهترین تأثیر را از روش قطع تغذیه سیستم در کاهش توان مصرفی شبکه گرفت. به این ترتیب مسیریابی پپیشنهادی نسبت به روش‌های دیگر 18% تا 30% بهبود در ذخیره توان مصرفی به وجود آورده و تأخیر ارسال بسته‌ها را نیز تا 32% بهبود می‌بخشد.

2- پیشینه و کارهای مرتبط

کاهش اندازه ترانزیستورها به مقیاس نانومتر سبب گردیده تا در فناوری‌های امروز، تعداد بیشتری از آنها روی سطح تراشه قرار بگیرد. هرچه اندازه ترانزیستورها کوچک‌تر شود، توان نشتی آنها بیشتر می‌شود و با افزایش تعداد آنها در مساحت ثابت تراشه، توان نشتی تراشه به ‌طور قابل‌ ملاحظه‌ای افزایش پیدا می‌کند. این مسئله باعث شده که مصرف توان ایستا به یکی از ملاحظات مهم در طراحی تراشه‌های مدرن امروز تبدیل شود. مطابق با تحقیقات انجام‌شده، حدود 35% از کل توان مصرفی یک تراشه متعلق به شبکه ارتباطی آن است که در فناوری‌های امروز بخش قابل‌ توجهی از آن مربوط به توان ایستای شبکه می‌باشد. کانال‌های مجازی از بزرگ‌ترین مصرف‌کنندگان توان ایستا در شبکه هستند که در عین حال خیلی وقت‌ها بیکارند. این کانال‌ها برای بار کاری زیاد تعبیه می‌شوند و در خیلی از مواقع به خصوص در بارهای کاری کم و متوسط شبکه بیکار هستند؛ یعنی همواره توان زیادی در شبکه صرف منابع پرمصرف و بیکار می‌شود.

قطع تغذیه سیستم، یکی از روش‌های رایج در کاهش توان نشتی است که امروزه به ‌صورت گسترده در مطالعات مختلف برای کاهش توان نشتی شبکه‌های روی تراشه به کار گرفته می‌شود [11] تا [15]. این روش که در سطح مدار است، منابع بیکار را با قطع تغذیه برق از آنها خاموش می‌کند و هنگام مراجعه بسته‌ها دوباره آنها را روشن می‌کند و با این کار مقدار زیادی توان ذخیره می‌کند. قطع تغذیه سیستم عمدتاً بر روی منابع پرمصرف تراشه از جمله مسیریاب‌ها و کانال‌های مجازی درون آنها اعمال می‌شود. بر این اساس مطالعات زیادی به کاهش توان مصرفی بافرها در شبکه‌های روی تراشه پرداخته‌اند [16] تا [21]. در قطع تغذیه سیستم، روشن‌کردن منابع خاموش، هر بار تأخیری به شبکه اعمال می‌کند که به آن تأخیر بیدارسازی می‌گویند. هنگامی که بسته‌ها به یک بافر خاموش می‌رسند به اندازه تأخیر بیدارسازی باید منتظر بمانند تا بافر مورد نظر روشن و آماده دریافت بسته‌ها شود. حال اگر بسته‌ها به ‌طور مرتب با منابع خاموش مواجه شوند، مجموع تأخیرهای بیدارسازی منابع در نهایت شبکه را با افت زیادی در عملکرد و مصرف توان روبه‌رو می‌سازد.

SMART [22] با استفاده از یک روش مسیریابی و نگاشت از روبه‌روشدن بسته‌ها با مسیریاب‌های خاموش جلوگیری می‌کند. به این صورت که با در نظر گرفتن یک مسیریابی رفت و برگشتی ، به بسته‌ها فقط اجازه عبور در یک جهت بین هر جفت مبدأ و مقصد را می‌دهد. سپس با اعمال قطع تغذیه سیستم بر روی مسیریاب‌های بیکار موجود در مسیرهای دیگر، آنها را خاموش می‌کند و به این ترتیب، الگوریتمی برای کاهش توان مصرفی شبکه روی تراشه در سطح دو بعد ارائه می‌دهد؛ اما تا کنون به این مسئله در الگوریتم‌های مسیریابی شبکه‌های سه‌بعدی نیمه‌متصل توجه زیادی نشده است. با توجه به این که طراحی‌های امروز عمدتاً به سمت مجتمع‌سازی سه‌بعدی پیش می‌روند،
به کارگیری تدبیری برای کاهش میزان این مصرف توان در این شبکه‌ها امری ضروری است.

LETHOR [23] بر کنترل دمای شبکه‌های سه‌بعدی تمرکز دارد و با شناسایی نقاط داغ شبکه، تلاش می‌کند تا بسته‌ها را از مسیری عبور دهد که از این نقاط عبور نکنند و یا کمترین تعداد گام را در این مناطق داشته ‌باشند. با این که یکی از اهداف اصلی مدیریت توان مصرفی، کنترل دمای شبکه است و LETHOR به خوبی توانسته این مسئله را در شبکه‌های سه‌بعدی حل کند، اما مسیریابی پیشنهادی در این مرجع برای شبکه‌های تمام‌متصل مناسب است و قابل اعمال برای شبکه‌های نیمه‌متصل با تعداد محدود آسانسور نمی‌باشد.

اول- آسانسور [24] یک مسیریابی قطعی و از اولین الگوریتم‌های مسیریابی ارائه‌شده برای شبکه‌های سه‌بعدی نیمه‌متصل است که برای
از بین بردن بن‌بست از چهار کانال مجازی اضافه در هر مسیریاب استفاده می‌کند تا مسیر بسته‌های بالارونده (به سمت لایه‌های بالایی) را از
مسیر بسته‌های پایین‌رونده (به سمت لایه‌های پایینی) جدا کند. در این مسیریابی، بسته‌ها با استفاده از الگوریتم مسیریابی هدایت می‌شوند؛ یعنی ابتدا در جهت و سپس در جهت حرکت می‌کنند. اگر مقصد در لایه‌ای متفاوت با لایه مبدأ باشد، مسیریابی دوبخشی است. در گام اول، بسته‌ها از گره مبدأ به‌سوی یک آسانسور هدایت می‌شوند و در گام دوم، پس از عبور از آسانسور انتخاب‌شده و رسیدن به لایه مقصد، به‌سوی گره مقصد حرکت می‌کنند. در این مسیریابی قطعی، به دلیل عدم آزادی در انتخاب مسیر، جایگزینی برای انتخاب مسیرهای کم‌تردد وجود ندارد و مراجعه گاه ‌و ‌بیگاه بسته‌ها به این منابع امکان پیوستگی بیکاری را از بین می‌برد.

FL-RuNs [25] یک مسیریابی وفق‌پذیر با شش کانال مجازی برای جلوگیری از بن‌بست و نیز تحمل‌پذیری خطا در شبکه ارائه می‌دهد. وجود شش کانال مجازی اضافه در هر مسیریاب، توان مصرفی زیادی به دنبال دارد و همچنین در مسیریابی تماماً وفقی به دلیل انتخاب‌های زیاد برای مسیر، پراکندگی بسته‌ها در شبکه زیاد است که یک بیکاری ناپیوسته در منابع کم‌کار به وجود می‌آورد.

LEAD [26] نیز یک مسیریابی وفق‌پذیر برای کاهش تأخیر و افزایش عملکرد شبکه ارائه می‌دهد که مشابه اول- آسانسور در هر مسیریاب از 4 کانال مجازی اضافه استفاده می‌کند که تعداد زیادی است. این کانال‌ها در ورودی‌های شمال، جنوب، شرق و غرب هر مسیریاب قرار گرفته‌اند.

D3Rout [27] نیز یک الگوریتم‌ مسیریابی تحمل‌پذیر خطا برای شبکه‌های سه‌بعدی نیمه‌متصل است که بدون بن‌بست و وفق‌پذیر بوده و از کانال‌های مجازی اضافه استفاده می‌کند. در این مسیریابی، اولویت انتخاب با مسیرهای خلوت‌تر می‌باشد که از پیوستگی بیکاری در منابع پرمصرف جلوگیری می‌کند.

از دیگر الگوریتم‌های مسیریابی برای شبکه‌های نیمه‌متصل می‌توان به d3Reflect [28] اشاره کرد که از 4 کانال مجازی اضافه استفاده می‌کند تا با تقسیم آنها به 4 زیرشبکه مجزا، احتمال وقوع بن‌بست را از بین ببرد. استفاده از کانال‌های مجازی زیاد در این مسیریابی سبب بالارفتن توان مصرفی ایستا می‌شود. از طرفی در این مسیریابی تحمل‌پذیر خطا، ‌پیداکردن آسانسور سالم، شبکه را با تأخیر زیاد روبه‌رو می‌کند. همین طور انتخاب کاملاً وفق‌پذیر برای مسیر بار را به‌ صورت پراکنده در شبکه پخش می‌کند.

در [29] یک مسیریابی دومرحله‌ای برای مدیریت دما در شبکه‌های سه‌بعدی نیمه‌متصل ارائه گردیده که هر گره با داشتن آدرس مقصد و اطلاعات دمایی چهار گره همسایه، آسانسوری را که در مسیر خنک‌تر است، انتخاب می‌کند و در مرحله دوم به‌سوی مقصد، مسیردهی می‌شود. با این که دما و توان مصرفی شبکه با یکدیگر مستقیماً در ارتباط هستند اما استفاده بیش از حد از مسیرهای خنک‌تر، پراکندگی بار را در شبکه بیشتر می‌کند.

مسیریابی‌های دیگری نیز با رویکردهای مختلف برای شبکه‌های نیمه‌متصل ارائه شده که سعی در بهبود عملکرد شبکه دارند. اما سیاست اتخاذشده در هیچ ‌کدام از آنها تدبیری برای مدیریت توان مصرفی در نظر ندارد. در این الگوریتم‌ها به دلیل محدودیت در تعداد آسانسورها معمولاً از کانال‌های مجازی زیادی استفاده می‌شود تا مسیریابی دچار بن‌بست و یا تأخیر زیاد در ارسال بسته‌ها نشود [30] و [31]. هرچه تعداد کانال‌های مجازی بیشتر باشد توان مصرفی در شبکه بالاتر می‌رود؛ اما این کانال‌ها برای بار کاری زیاد طراحی شده‌اند و خیلی وقت‌ها به‌ ویژه در بارهای کاری کم و متوسط شبکه بیکار هستند. مطابق با مشاهدات انجام‌شده در این تحقیق، میزان بیکاری در بافرها در شبکه به طور متوسط 82/73% است. از طرفی در شبکه‌های سه‌بعدی نیمه‌متصل به دلیل محدودیت در

شکل 3: میزان بیکاری بافرها در گره‌های لایه اول یک شبکه مش سه‌بعدی نیمه‌متصل .

تعداد اتصالات عمودی و استفاده اشتراکی از آنها، مسیریابی مبتنی بر پیداکردن بهترین آسانسور مستلزم روشن‌بودن تمامی مسیریاب‌ها است؛ یعنی در این شبکه‌ها همواره توان مصرفی زیادی صرف منابع روشن و بیکار کانال مجازی می‌شود. بنابراین اعمال قطع تغذیه سیستم بر روی کانال‌های مجازی می‌تواند تأثیر خوبی بر روی کاهش توان این شبکه‌ها بگذارد؛ اما تا زمانی که پراکندگی بار در شبکه زیاد است، بسته‌ها مرتب با منابع کم‌کار روبه‌رو می‌شوند که سبب روشن و خاموش‌شدن متوالی این منابع و سربار تأخیر و توان مصرفی می‌شود. بنابراین به‌کارگیری روش قطع تغذیه سیستم، نیازمند الگوریتم مسیریابی مناسبی است تا با کاهش پراکندگی بار در سطح شبکه، دوره بیکاری را در منابع کم‌کار، بیشتر و به این ترتیب شرایط را برای خاموش‌کردن این منابع فراهم کند.

3- روش پیشنهادی

همان طور که پیش‌تر اشاره شد، مسیریابی‌های موجود از کانال‌های مجازی زیادی استفاده می‌کنند که خیلی وقت‌ها بیکارند و توان مصرفی شبکه را بالا می‌برند. همچنین این مسیریابی‌ها بار را به ‌صورت پراکنده در شبکه پخش می‌کنند که پیوستگی بیکاری را در منابع پرمصرف از بین می‌برد و این سبب می‌شود اعمال قطع تغذیه سیستم بر روی این منابع، سربار تأخیر و توان مصرفی به بار بیاورد. در این قسمت ابتدا در بخش مقدمه به بررسی میزان بیکاری در کانال‌های مجازی و علت انتخاب روش پیشنهادی پرداخته می‌شود و سپس در بخش دوم، شرح مسیریابی پیشنهادی آمده است.

3-1 مقدمه

کانال‌های مجازی، جزء جدانشدنی از شبکه‌های روی تراشه سه‌بعدی نیمه‌متصل هستند که از منابع پرمصرف توان ایستا در شبکه به شمار می‌روند؛ اما در عین حال خیلی وقت‌ها بیکار هستند. برای مشاهده نرخ بیکاری بافرها و نیز میزان مراجعه بسته‌ها به هر گره، آزمایشی در این تحقیق انجام شده که نتایج آن به ترتیب مطابق با شکل 3 و 4 است. این آزمایش بر روی یک شبکه مش با چهار آسانسور در هر لایه، تحت ترافیک یکنواخت و نرخ‌های مختلف تزریق انجام شده است. آسانسورها در گره‌های 1، 7، 8 و 14 لایه اول و گره‌های متناظر با آنها در لایه‌های دیگر قرار دارند. با توجه به شکل 3 میزان بیکاری بافرها به‌ طور متوسط حدود 9/73% است که مقدار قابل ‌توجهی است. این مقدار برای لایه‌های دوم، سوم و چهارم نیز به ترتیب 36/73%، 45/73% و 57/74% است. اگرچه مدت زمان بیکاری قابل ‌توجه است اما به دلیل پراکندگی بار در شبکه، این بیکاری پیوسته نیست و این سبب می‌شود اعمال قطع تغذیه سیستم بر روی بافرها به دلیل خاموش و روشن‌شدن‌های متوالی کلیدهای تغذیه، سربار تأخیر و توان مصرفی به دنبال داشته باشد. از طرفی با توجه به شکل 4، مراجعه به گره‌های دارای آسانسور به ‌وضوح بیشتر از سایر گره‌ها است؛ چرا که نقطه اتصال با لایه‌های دیگر شبکه

شکل 4: نرمال‌شده میزان مراجعه بسته‌ها به گره‌ها در لایه اول یک شبکه مش سه‌بعدی نیمه‌متصل .

هستند. مراجعه بسته‌ها به سایر گره‌ها کمتر است و می‌توان آنها را خاموش کرد. از این دو شکل می‌توان نتیجه گرفت که اگرچه مراجعه به گره‌های دارای آسانسور و گره‌های اطراف آنها بیشتر است، اما باز هم نرخ بیکاری در بافرهای آنها بالاست. پس اگر بتوان مسیریابی بسته‌ها را به ‌گونه‌ای انجام داد که تا جای ممکن از مسیرهای دارای آسانسور گذر کنند، از پراکندگی آنها در شبکه و مراجعه نامنظم به گره‌های موجود در مسیرهای کم‌تردد که دارای بافرهای بیکار هستند، اجتناب می‌شود و این سبب کاهش تعداد دفعات روشن و خاموش‌شدن بافرها می‌گردد. ممکن است به نظر برسد که هدایت بسته‌ها به مسیرهای پرتردد، سبب افزایش تأخیر یا شلوغی در شبکه شود اما این‌گونه نیست؛ زیرا با توجه به شکل 3 نرخ بیکاری در بافرها هنوز هم زیاد است و با این کار تنها از ظرفیت مجاز آنها استفاده می‌شود تا جایی که سبب تأخیر نشود. با این حال برای اطمینان از این موضوع، محدودیتی برای استفاده از مسیرهای پرتردد تعیین گردیده که در ادامه به آن پرداخته خواهد شد.

3-2 الگوریتم مسیریابی پیشنهادی

مسیریابی پیشنهادی با دورکردن بسته‌ها از مسیرهای کم‌تردد و کاهش پراکندگی بار در سطح شبکه هدف در افزایش دوره بیکاری در بافرهای کم‌کار دارد تا بتوان مدت زمان بیشتری آنها را خاموش نگه داشت و در تأخیر و توان مصرفی شبکه صرفه‌جویی کرد. بر این اساس، سیاست مسیریابی، بسته به این که مبدأ و مقصد در یک لایه باشند و یا در دو لایه مختلف، متفاوت و به‌ صورت زیر است:

الف) مبدأ و مقصد در یک لایه باشند: در این حالت از بین مسیرهای کمینه (کوتاه‌ترین مسیرها) بین مبدأ و مقصد، اولویت با مسیر دارای آسانسور است؛ چرا که منابع موجود در این مسیرها همیشه روشن هستند. بنابراین احتمال روشن‌کردن منابع خاموش در سایر مسیرها کمتر می‌شود و دوره بیکاری در بافرهای آنها افزایش می‌یابد. البته باید در نظر داشت که تردد بیش از حد ظرفیت در این مسیرها ممکن است منجر به ایجاد ترافیک و تأخیر در رسیدن بسته‌ها و یا از بین رفتن آنها شود. نتایج حاصل از آزمایش انجام‌شده در این تحقیق نشان می‌دهد که اگر از بیش از 50% ظرفیت بافرهای موجود در مسیریاب استفاده شود، بسته از بین می‌رود یا دچار بن‌بست می‌شود. میزان این شلوغی در این آزمایش از اندازه‌گیری نسبت تعداد بافرهای اشغال‌شده به ظرفیت کل بافرهای ورودی موجود در هر مسیریاب به ازای هر سیکل به‌ دست ‌آمده است. بنابراین برای جلوگیری از بن‌بست و از بین رفتن بسته‌ها، شرطی برای ظرفیت بافرها در مسیرهای شلوغ تعیین شده که مطابق با آن، بسته فقط مجاز به استفاده از مسیرهایی است که ظرفیت پر بافرهای کانال مجازی در هر مسیریاب از 50 درصد کل ظرفیت بافرهای ورودی مسیریاب تجاوز نکرده باشد؛ در غیر این صورت بسته باید مسیر دیگری را برگزیند. این شرط، شرط- ازدحام نامیده می‌شود.

شکل 5: محدودیت استفاده از آسانسور در مسیریابی پیشنهادی.

ب) مبدأ و مقصد در دو لایه مختلف باشند: در هر لایه همواره تعداد زیادی از بسته‌ها به سمت آسانسورها می‌روند. با محدودکردن این بسته‌ها به استفاده از برخی آسانسورها می‌توان مسیر گذر آنها را از برخی کانال‌ها کم یا حتی حذف کرد؛ در نتیجه، کانال‌های مجازی موجود در این مسیرها را می‌توان برای مدت زمان بیشتری خاموش نگه داشت. بنابراین در مسیریابی پیشنهادی برای بسته‌هایی که قصد جابه‌جایی بین طبقات را دارند، با تقسیم شبکه به دو منطقه شمالی و جنوبی و ایجاد محدودیت در استفاده از آسانسورهای هر منطقه، این شرایط فراهم می‌شود. به این صورت که گره‌های موجود در منطقه شمالی شبکه تنها مجاز به استفاده از آسانسورهای هم‌ردیف یا شمالی‌تر از خود هستند. از طرفی گره‌های موجود در منطقه جنوبی شبکه نیز تنها می‌توانند از آسانسورهای هم‌ردیف و یا جنوبی‌تر از خود استفاده کنند.

برای توصیف بهتر این مسیریابی با توجه به شکل 5 که در آن شبکه به دو منطقه شمالی و جنوبی تقسیم شده است، گره واقع در منطقه شمالی شبکه می‌تواند از تمامی آسانسورهای منطقه خود استفاده کند، چرا که همگی هم‌راستا یا شمالی‌تر از آن هستند. اما گره تنها مجاز به استفاده از دو آسانسور می‌باشد یعنی آسانسور شماره 1 و 2. گره نیز که در منطقه جنوبی شبکه قرار دارد، تنها می‌تواند از آسانسورهای شماره 7 و 8 استفاده کند. استفاده از این روش دو مزیت دارد:

• اول این که با این کار، استفاده از برخی کانال‌ها کمتر شده و در نتیجه، نرخ بیکاری در کانال‌های مجازی آنها بیشتر می‌شود و می‌توان آنها را برای مدت زمان بیشتری خاموش نگه داشت. مثلاً در منطقه شمالی شبکه، بسته‌ها به سمت آسانسورهای جنوبی خود نمی‌روند و این یعنی بافرهای شمالی در این گره‌ها اکثر مواقع بیکار هستند. برای مثال شکل 6- الف را در نظر بگیرید که نشان‌دهنده منطقه شمالی یک شبکه است. مبدأ در منطقه شمالی شبکه و مقصد در لایه دیگر است. بسته مجاز به استفاده از آسانسور شماره 2 نیست؛ پس بافرهای شمالی گره جنوبی این گره استفاده نمی‌شوند. از آنجا که هیچ‌ کدام از گره‌ها به آسانسورهای جنوبی‌تر خود بسته نمی‌فرستند، بنابراین این اتفاق برای تمامی گره‌های منطقه شمالی رخ می‌دهد و از بافرهای شمالی آنها هنگام استفاده از آسانسور، استفاده نمی‌شود. از طرفی دیگر، از برخی بافرهای غربی نیز کمتر استفاده می‌شود که در شکل 6- ب قابل مشاهده است. بسته مجاز به استفاده از آسانسور شماره 2 نیست، پس از خروجی شرق خود برای استفاده از آسانسور استفاده نمی‌کند و بنابراین بافر ورودی غرب گره همسایه در این موقعیت بی‌استفاده می‌ماند. به این ترتیب محدودکردن بسته‌ها به استفاده از آسانسورهای شمالی یا هم‌راستا، سبب بیکاری در بافرهای شمالی و کم‌کاری در برخی بافرهای

(الف) (ب)

شکل 6: کانال‌های کم‌استفاده در منطقه شمالی شبکه، (الف) بافرهای شمالی و (ب) بافرهای غربی.

(الف) (ب)

شکل 7: کانال‌های کم‌استفاده در منطقه جنوبی شبکه، (الف) بافرهای جنوبی و (ب) بافرهای شرقی.

غربی شده که دوره بیکاری را در آنها افزایش می‌دهد. در منطقه جنوبی شبکه نیز اتفاقی مشابه رخ می‌دهد که سبب بیکاری در بافرهای جنوبی و کم‌کاری در برخی بافرهای شرقی می‌شود که در شکل 7- الف و 7- ب، به ترتیب هر دوی این حالات به تصویر کشیده شده است.

• مزیت دیگر این روش دورشدن بار از مرکز شبکه و انتقال به حاشیه‌ها می‌باشد که انتظار می‌رود سبب کاهش ازدحام و تعادل بار در شبکه شود.

اگرچه ممکن است که با ایجاد محدودیت در انتخاب آسانسور برای بسته‌هایی که مبدأ و مقصد آنها در دو منطقه متفاوت است تأخیر ایجاد شود، اما در عوض از تأخیر بیداری بافرها اجتناب و در واقع این تأخیر جبران می‌شود. روندنمای مسیریابی پیشنهادی در شکل 8 آمده است.

3-2-1 پیاده‌سازی

برای پیاده‌سازی این الگوریتم مسیریابی مطابق شکل 9 با تقسیم‌بندی کانال‌های مجازی، شبکه به 3 زیرشبکه تقسیم شده و تنها از 3 کانال مجازی اضافه استفاده می‌گردد. همان طور که دیده می‌شود در هر جهت ، و تنها از یک کانال مجازی اضافه استفاده شده است. استفاده از زیرشبکه‌ها به این صورت است:

• اگر مبدأ و مقصد در دو لایه مختلف باشند و بسته در منطقه شمالی شبکه قرار داشته باشد، ابتدا در زیرشبکه اول به سمت آسانسور مورد نظر حرکت می‌کند. سپس به زیرشبکه دوم رفته و با استفاده از کانال‌های یا با توجه به موقعیت مقصد به طبقه بالا یا پایین منتقل می‌شود. در آنجا اگر مقصد در جنوب موقعیت فعلی قرار داشته باشد، حرکت خود را در بعد در زیرشبکه دوم تکمیل می‌کند و سپس در صورت لزوم به زیرشبکه سوم می‌رود. برای بسته‌هایی که در منطقه جنوبی شبکه قرار دارند، بسته ابتدا حرکت خود را در جهت یا در زیرشبکه اول تکمیل می‌کند، سپس به زیرشبکه دوم رفته و به لایه مورد نظر منتقل می‌شود. مشابه حالت قبل اگر در لایه مقصد، گره مقصد در جنوب آسانسور

شکل 8: الگوریتم مسیریابی پیشنهادی.

قرار داشت، بسته باید ابتدا حرکت خود در بعد را تکمیل کند و سپس به زیرشبکه سوم برود.

• در صورتی که مبدأ و مقصد در یک لایه باشند، دو حالت ممکن است: اول این که مقصد در شمال غرب یا شمال شرق مبدأ باشد که در این صورت در زیرشبکه اول حرکت کرده و به مقصد می‌رسد. در حالت دوم، مقصد در جنوب غرب یا جنوب شرق مبدأ است که بسته ابتدا در زیرشبکه اول در جهت حرکت می‌کند و سپس برای تکمیل حرکت خود در جهت جنوب به زیرشبکه دوم می‌رود.

3-2-2 وفق‌پذیری

مسیریابی پیشنهادی، الگوریتم مسیریابی نیمه‌وفق‌پذیری است که در آن، بسته در زیرشبکه‌های اول و سوم می‌تواند به ‌صورت وفقی حرکت کند. به این صورت که مطابق با شکل 10 برای حرکت به سمت شمال غرب می‌تواند اول به شمال و سپس به غرب حرکت کند یا برعکس. همین طور برای حرکت به سمت شمال شرق مجاز است که اول به شمال و سپس به شرق حرکت کند و یا برعکس، اول به شرق و سپس به شمال برود. یعنی حرکت بسته به سمت شمال غرب یا شمال شرق به ‌صورت وفقی است و بسته مجاز است به فرم یا حرکت کند. اولویت انتخاب جهت یا همان طور که قبلاً ذکر شد، با مسیری می‌باشد که اخیراً بیشتر مورد استفاده قرار گرفته است؛ به ‌گونه‌ای که ازدحام مسیر بیش از 50% ظرفیت بافرهای موجود در مسیریاب‌ها نباشد. اما حرکت به سمت جنوب قطعی است؛ یعنی بسته برای حرکت به سمت جنوب شرق یا جنوب غرب، اگر در زیرشبکه دوم قرار داشت ابتدا باید حرکت خود را در بعد به سمت جنوب در زیرشبکه دوم تکمیل کند و سپس در صورت نیاز به زیرشبکه سوم برود تا در بعد حرکت کند؛ زیرا حرکت از زیرشبکه فعلی به زیرشبکه قبلی غیر مجاز است. اگر در زیرشبکه اول بود نیز می‌تواند حرکت خود در بعد را تکمیل کند و سپس به زیرشبکه دوم برود و در جهت جنوب حرکت کند.

شکل 9: زیرشبکه‌های موجود در مسیریابی پیشنهادی.

شکل 10: وفق‌پذیری در مسیریابی پیشنهادی.

(الف) (ب)

شکل 11: اجتناب از بن‌بست در مسیریابی پیشنهادی؛ خطوط مشکی نشان‌دهنده چرخش‌های مجاز و خطوط قرمز نشان‌دهنده چرخش‌های حذف‌شده هستند. (الف) عدم وجود حلقه در زیرشبکه اول و سوم و (ب) عدم وجود حلقه در زیرشبکه دوم.

3-2-3 انتخاب آسانسور

انتخاب کانال عمودی یا آسانسور، بخشی مهم از هر الگوریتم مسیریابی نیمه‌متصل است که باید سیاست درستی برای آن در نظر گرفته شود [32] و [33]. در هر شبکه سه‌بعدی نیمه‌متصل ممکن است چندین آسانسور واجد شرایط برای انتخاب موجود باشد. در این شرایط، اولویت با آسانسوری است که مسیر آن اخیراً بیشتر مورد استفاده قرار گرفته تا از روشن‌کردن کانال‌های خاموش احتمالی در مسیرهای خلوت (یعنی مسیرهایی که در سیکل‌های اخیر کمتر استفاده شده‌اند) جلوگیری به عمل آید. مسیریابی پیشنهادی این کار را با مقایسه ظرفیت بافرها در مسیرهای مورد نظر انجام می‌دهد. بافرهای کانال مجازی مسیریاب‌ها در مسیرهای پرتردد، ظرفیت خالی کمتری نسبت به مسیرهای خلوت دارند. همان طور که پیش‌تر ذکر شد برای جلوگیری از بن‌بست یا از بین رفتن بسته‌ها، ظرفیت اشغال‌شده در بافرهای ورودی هر مسیریاب موجود در مسیر نباید از 50% کل ظرفیت موجود تجاوز کند (شرط ازدحام).

3-2-4 اجتناب از بن‌بست

در این قسمت به بررسی و اثبات بدون بن‌بست‌بودن الگوریتم مسیریابی پیشنهادی پرداخته شده است. این الگوریتم مسیریابی با رعایت شرایط ذکرشده برای طراحی مسیریابی بدون بن‌بست که در [34] برای شبکه‌های سه‌بعدی نیمه‌متصل ارائه گردیده، طراحی شده است. شرط اول، عدم وجود دو بعد کامل در یک زیرشبکه است؛ زیرا وجود چهار جهت از دو بعد کامل، چهار چرخش 90 درجه ایجاد می‌کند و تشکیل حلقه می‌دهد. الگوریتم مسیریابی پیشنهادی دارای سه زیرشبکه است که در هیچ‌ کدام دو بعد کامل وجود ندارد. مثلاً در زیرشبکه اول و سوم، بعد کامل است؛ چرا که هر دو جهت مثبت و منفی آن در زیرشبکه وجود دارد. اما از بعد تنها جهت مثبت آن موجود است و از آنجا که برای تشکیل حلقه، چهار چرخش 90 درجه لازم است، بنابراین این دو زیرشبکه بدون بن‌بست هستند. چرخش‌های مجاز در این دو زیرشبکه در شکل 11- الف با رنگ

جدول 1: مشخصه‌های شبیه‌سازی.

همبندی شبکه روی تراشه	مش سه‌بعدی نیمه‌متصل
ابعاد شبکه
تعداد آسانسورها	4
تعداد کانال‌های مجازی اضافه	3
عمق بافر	8
طول بسته	8 فلیت
ورودی شبکه	ترافیک یکنواخت و ترانهاده

مشکی نشان داده شده و رنگ قرمز نیز نشان‌دهنده چرخش‌های حذف‌شده است. به دلیل عدم وجود جهت چهارم یعنی در زیرشبکه اول و سوم، در هر حلقه ساعت‌گرد و پادساعت‌گرد، دو چرخش 90 درجه حذف شده و حلقه تشکیل نمی‌شود. به همین ترتیب در زیرشبکه دوم نیز مطابق با شکل 11- ب بعد کامل است اما از بعد تنها جهت منفی آن وجود دارد و بنابراین حلقه تشکیل نمی‌شود. مطابق با قانون دوم، حرکت بسته‌ها فقط از زیرشبکه با شماره کوچک‌تر به بزرگ‌تر مجاز است و برعکس این حالت، مجاز نیست. به این معنی که از زیرشبکه اول می‌توان به زیرشبکه دوم و سوم گذر کرد و از زیرشبکه دوم نیز فقط به زیرشبکه سوم امکان گذر هست؛ اما حرکت از زیرشبکه دوم و سوم به زیرشبکه‌های قبلی امکان‌پذیر نیست. پس امکان تشکیل حلقه با بازگشت به زیرشبکه‌های قبلی وجود ندارد.

4- نتایج شبیه‌سازی

در این قسمت به شبیه‌سازی الگوریتم مسیریابی پیشنهادی و بررسی نتایج حاصل از آن در مقایسه با کارهای موجود پرداخته می‌شود. برای این کار از شبیه‌ساز Booksin [35] استفاده شده که یک شبیه‌ساز انعطاف‌پذیر تحت زبان C++ برای شبکه روی تراشه می‌باشد و برای به دست آوردن نتایج دقیق‌تری از توان مصرفی با کتابخانه توان مصرفی Orion-II [36] ادغام گردیده است. الگوریتم مسیریابی پیشنهادی از نظر تأخیر و توان مصرفی با الگوریتم شناخته‌شده اول- آسانسور و همچنین دو مسیریابی d3Reflect [28] و مسیریابی پیشنهادی در [29] مقایسه می‌شود.

برای بررسی عملکرد الگوریتم مسیریابی پیشنهادی، ابتدا این مسیریابی در شبکه‌ای با مشخصات ذکرشده در جدول 1 پیاده‌سازی گردیده و نتایج حاصل از توان مصرفی با نتایج توان مصرفی حاصل از روش‌های دیگر مقایسه شده است. سپس یک فن کاهش توان مطابق با کارهای گذشته [20] در شرایط یکسان بر روی هر 4 الگوریتم مسیریابی اعمال می‌شود تا با مقایسه نتایج تأخیر و توان مصرفی، میزان تأثیر الگوریتم پیشنهادی بر عملکرد شبکه به دست آید. نتایج حاصل از شبیه‌سازی تحت ترافیک مصنوعی یکنواخت و ترانهاده به‌ دست ‌آمده است. در ترافیک یکنواخت، هر مسیریاب با یک احتمال برابر به دیگر گره‌ها بسته می‌فرستد اما در ترافیک ترانهاده، این احتمال برای همه گره‌ها برابر نیست و هر گره با وزن

(1)

به تولید ترافیک می‌پردازد که در آنها به امین بیت از گره مبدأ (مقصد) اشاره دارد، طول آدرس است که برابر با می‌باشد و نیز تعداد گره‌های موجود در شبکه است. این سبب می‌شود که شبکه در برخی نواحی، ازدحام بیشتری داشته و در برخی نواحی خلوت‌تر باشد. در این تحقیق برای ارزیابی عملکرد روش پیشنهادی در شرایط مختلف، شبیه‌سازی تحت هر دو ترافیک صورت می‌پذیرد.

جدول 2: توان مصرفی ایستا پیش از قطع تغذیه سیستم.

الگوریتم مسیریابی	کل توان ایستا (mw)	توان ایستا در بافرها (mw)
Proposed method	16/1	388/0
ELF	267/1	445/0
d3Reflect	395/1	49/0
TS	32/1	466/0

لازم به ذکر است که در ادامه به مسیریابی اول- آسانسور و مسیریابی ارائه‌شده در [29] به ترتیب با ELF و TS اشاره می‌شود. همین طور در نمودارها منظور از PG، روش قطع تغذیه سیستم می‌باشد.

4-1 توان مصرفی

نتایج توان مصرفی ایستا در حالت عادی شبکه یعنی پیش از اعمال قطع تغذیه سیستم برای هر چهار روش در جدول 2 آمده است. همان طور که دیده می‌شود، توان مصرفی در مسیریابی پیشنهادی کمتر از سایر روش‌هاست که این به دلیل تعداد کانال‌های مجازی کمتر است. توان مصرفی ایستا توان حاصل از اجزای روشن مدار است و ربطی به حالت کاری شبکه ندارد. بنابراین مقدار آن برای یک شبکه با مشخصات تعیین‌شده در ترافیک‌های مختلف و نرخ‌های تزریق مختلف همواره ثابت است. اما سیاست‌های مختلف مسیریابی می‌توانند در میزان بافرهای مورد نیاز مستقیماً تأثیرگذار باشند و از آنجا که کانال‌های مجازی از بزرگ‌ترین منابع مصرف توان ایستا در شبکه هستند، مسیریابی‌های مختلف، توان مصرفی مختلفی دارند. به این دلیل مسیریابی پیشنهادی که در هر مسیریاب فقط از سه کانال مجازی اضافه استفاده می‌کند، سربار توان مصرفی کمتری نسبت به سایر روش‌ها دارد؛ در حالی که سایر روش‌ها
از کانال‌های مجازی بیشتری استفاده می‌کنند. برای مثال ELF در هر مسیریاب دارای چهار و d3Reflect نیز دارای شش کانال مجازی اضافه است. ممکن است اختلاف در تعداد کانال‌های مجازی کم به نظر برسد اما از آنجا که مصرف توان این کانال‌ها در شبکه زیاد است، این اختلاف کم در تعداد سبب ذخیره مقدار خوبی توان ایستا شده است.

با اعمال روش قطع تغذیه سیستم، چون بافرها در زمان‌های مختلف خاموش و روشن می‌شوند، توان مصرفی ایستا برعکس حالت قبل که ثابت بود برای ترافیک مصنوعی تغییر می‌کند و مقادیر آن را در نرخ‌های مختلف تزریق و تحت ترافیک‌های مختلف می‌توان روی نمودار نشان داد. در شکل 12 مقادیر توان مصرفی روش‌های مختلف، پس از اعمال فن کاهش توان تحت ترافیک‌های مصنوعی یکنواخت و ترانهاده نشان داده شده است. مقایسه چهار منحنی در شکل 12- الف نشان می‌دهد که روش پیشنهادی توانسته در مقایسه با سه روش دیگر توان بیشتری ذخیره کند؛ زیرا مقدار زیادی از این توان در این روش‌ها به دلیل پراکندگی بار صرف سربار روشن‌کردن متوالی کلیدهای تغذیه در شبکه می‌شود. اما در روش پیشنهادی با سیاست مسیریابی اتخاذشده، هدایت بسته‌ها به‌ گونه‌ای انجام می‌شود که از مسیرهای خلوت کمتر عبور کنند تا منابع خاموش را
به مدت بیشتری بتوان خاموش نگه داشت. این نه‌تنها توان مصرفی ذخیره‌شده را در شبکه افزایش می‌دهد که سربار توان مصرفی بیدارسازی منابع را نیز تا جای ممکن کاهش می‌دهد. به این سبب مسیریابی پیشنهادی در مقایسه با ELF دارای حدود 18% بهبود در توان مصرفی است و نسبت به d3Reflect و TS نیز توان مصرفی را حدود 31% و 29% کاهش می‌دهد. میزان کاهش توان در ELF نسبت به d3Reflect بیشتر است که می‌توان آن را به قطعی‌بودن مسیریابی ELF نسبت داد؛

(الف)

(ب)

شکل 12: مقایسه توان مصرفی ایستا پس از اعمال فن کاهش توان در روش‌های مختلف، (الف) تحت ترافیک یکنواخت و (ب) ترافیک ترانهاده.

(الف)

(ب)

شکل 14: میانگین تأخیر ارسال پیام پس از اعمال قطع تغذیه سیستم در روش‌های مختلف، (الف) ترافیک یکنواخت و (ب) ترافیک ترانهاده.

زیرا در این نوع مسیریابی برخی مسیرها خودبه‌خود کمتر ‌استفاده‌ می‌شوند. اما در d3Reflect که یک مسیریابی وفق‌پذیر است و تدبیری برای استفاده کمتر از منابع پرمصرف ندارد، پراکندگی بار در شبکه و در نتیجه روبه‌رویی بسته‌ها با منابع بیکار نسبت به ELF بیشتر است. در TS نیز مشابه با d3Reflect نظم مشخصی برای جهت حرکت بسته‌ها در نظر گرفته نشده است که سبب پراکندگی آنها در شبکه می‌شود؛ اما سیاست مسیریابی برای دوری از گرمای شبکه سبب مصرف توان کمتری نسبت به d3Reflect شده است.

نتایج به‌ دست ‌آمده تحت ترافیک ترانهاده در شکل 12- ب نیز مشابه با ترافیک یکنواخت می‌باشد. مشابه با ترافیک یکنواخت، افزایش بافرهای بیکار در روش پیشنهادی سبب کاهش بیشتری در توان مصرفی ایستا

(الف)

(ب)

(ج)

شکل 13: میانگین تأخیر ارسال پیام، پیش و پس از قطع تغذیه سیستم تحت ترافیک یکنواخت، (الف)ELF، (ب) d3Reflect و (ج) TS.

شده که نسبت به ELF حدود 19% و در مقایسه با d3Reflect و TS نیز به ترتیب حدود 32% و 28% است.

4-2 تأخیر

همان طور که قبلاً ذکر گردید، مشکل اساسی کاهش توان مصرفی ایستا در مسیریابی‌های سه‌بعدی نیمه‌متصل، افت عملکرد شبکه است؛ چرا که یکی از پیامدهای نامطلوب از روش قطع تغذیه سیستم، کاهش عملکرد شبکه به دلیل تأخیرهای متوالی در بیدارسازی بافرهاست. بنابراین یک هدف مهم از مسیریابی پیشنهادی، کاهش تأخیر و بهبود عملکرد شبکه پس از قطع تغذیه سیستم در کنار مدیریت توان مصرفی می‌باشد. در این قسمت به نتایج حاصل از تأخیر پس از اعمال قطع تغذیه سیستم در مسیریابی پیشنهادی و روش‌های دیگر پرداخته می‌شود. در شکل 13 مقادیر تأخیر پیش و پس از اعمال قطع تغذیه سیستم برای ELF، Reflect و TS تحت ترافیک یکنواخت مقایسه شده است. همان طور که انتظار می‌رفت، اعمال قطع تغذیه سیستم عملکرد شبکه را دچار افت زیادی کرده که برای ELF، Reflect و TS به ترتیب حدود 20%، 33% و 28% است.

شکل 14 مقایسه‌ای از تأخیر مسیریابی‌های مختلف را با مسیریابی پیشنهادی پس از قطع تغذیه سیستم نشان می‌دهد. اعمال روش قطع تغذیه سیستم بر بافرهای ELF، عملکرد شبکه را دچار افت می‌کند و علت آن هم پراکندگی بار و سربار تأخیر بیدارسازی منابع است. این اتفاق در d3Reflect و TS با شدت بیشتری رخ می‌دهد؛ چرا که به علت وفق‌پذیری بیشتر مسیریابی نسبت به ELF و رویارویی بیشتر بسته‌ها با منابع بیکار، تعداد قطع و وصل‌شدن کلیدهای تغذیه بیشتر است که تأخیر

شکل 15: نرمال‌شده توان مصرفی پس از قطع تغذیه سیستم در روش‌های مختلف تحت ترافیک یکنواخت.

بیشتری را برای شبکه رقم می‌زند. در هر صورت تأخیر بیدارسازی بر عملکرد شبکه تأثیر می‌گذارد. مسیریابی پیشنهادی با مدیریت مسیریابی، بسته‌ها را از مسیرهایی که بیشتر استفاده شده‌اند، عبور می‌دهد و این سبب می‌شود تا در قسمت‌هایی از شبکه از حداکثر ظرفیت منابع استفاده گردد و در عوض در باقی قسمت‌ها بیکاری بیشتری در منابع ایجاد شود. این کار تعداد دفعات روشن‌کردن منابع خاموش را کمتر می‌کند که در نتیجه سربار تأخیر کمتری به دنبال می‌آورد. این در کنار دورسازی ازدحام از مرکز شبکه مطابق با شکل 14- الف، نتیجه در کاهش تأخیر تحت ترافیک یکنواخت و بهبود 25% در عملکرد شبکه نسبت به ELF و همین طور بهبود 30% و 32% به ترتیب نسبت به d3Reflect و TS دارد.

شکل 14- ب نتایج تأخیر را تحت ترافیک ترانهاده نشان می‌دهد که مشابه با ترافیک یکنواخت، مقدار بهبود عملکرد شبکه در روش پیشنهادی نسبت به ELF حدود 24% و در مقایسه با d3Reflect و TS حدود 29% است.

4-3 مقایسه با روش‌های کاهش توان

با توجه به این که روش پیشنهادی، یک راه حل برای کاهش توان مصرفی شبکه می‌باشد، برای ارزیابی عملکرد آن در این قسمت با دو روش قطع تغذیه سیستم مقایسه می‌شود. روش اول، روش سنتی قطع تغذیه سیستم یا ConvPG است که در آن، بافرها بلافاصله پس از بیکاری، خاموش و به‌ محض مراجعه بسته‌ها دوباره روشن می‌شوند. روش دوم AFGPG است که بر روی بافرهای ورودی مسیریاب اعمال می‌شود. در AFGPG [21] هنگامی که دو بسته در ورودی مسیریاب هم‌زمان درخواست دسترسی به کانال خروجی یکسان را دارند، به یکی از آنها اجازه داده می‌شود و دیگری در بافر ورودی منتظر می‌ماند. در صورتی که بافر توسط بسته‌ای دیگر اشغال بود، این بسته به خروجی دیگری منحرف می‌شود. AFGPG تعداد بسته‌هایی را که موفق می‌شوند به کانال خروجی مورد نظر راه پیدا کنند با بسته‌هایی که به مسیرهای دیگر منحرف می‌شوند مقایسه می‌کند. اگر تعداد بسته‌های خروجی بیشتر بود، برخی از بافرهای روشن را خاموش می‌کند و در صورتی که تعداد بسته‌های منحرف‌شده بیشتر باشد، تعدادی از بافرهای خاموش را برای ذخیره این بسته‌ها روشن می‌کند.

مقایسه‌ای از توان مصرفی روش پیشنهادی با روش AFGPG و نیز ConvPG تحت ترافیک یکنواخت انجام شده که نتایج آن در شکل 15 آمده است. با اعمال قطع تغذیه سیستم، مسیریابی پیشنهادی دارای 24% بهبود در کاهش توان مصرفی نسبت به ConvPG است. زیرا در روش سنتی، منابع با مراجعه بسته‌ها بلافاصله باید روشن شوند، حتی اگر در سیکل قبل خاموش شده باشند. این بیدارسازی چند سیکل زمان می‌طلبد و مراجعه پیاپی بسته‌ها به منابع خاموش در قسمت‌های مختلف شبکه،

شکل 16: تأخیر ارسال پیام پس از قطع تغذیه سیستم تحت ترافیک یکنواخت.

سبب روشن‌شدن متوالی کلیدهای تغذیه می‌شود و سربار توان مصرفی را به شبکه تحمیل می‌کند. اما با سیاستی که مسیریابی پیشنهادی برای هدایت بسته‌ها در نظر می‌گیرد تا جای ممکن بسته‌ها را از منابع خاموش دور نگه می‌دارد تا از روشن‌شدن آنها اجتناب شود. توان مصرفی در مسیریابی AFGPG و مسیریابی پیشنهادی نزدیک به هم است. با این حال مسیریابی پیشنهادی حدود 6% بهبود بیشتری ایجاد می‌کند زیرا برخلاف AFGPG با ایجاد محدودیت در استفاده از منابع، آنها را برای مدت زمان بیشتری خاموش نگه می‌دارد و در عوض از منابع روشن نهایت استفاده را می‌برد. این سبب افزایش دوره بیکاری در منابع کم‌کار و ذخیره بیشتر توان مصرفی می‌شود.

نتایج حاصل از تأخیر مسیریابی پیشنهادی و دو روش دیگر نیز در شکل 16 آمده است. بدیهی است که تغییرات متوالی کلیدهای تغذیه، سربار تأخیر بیدارسازی منابع را در روش قطع تغذیه سنتی بالا می‌برد. اما مسیریابی پیشنهادی با هدایت مناسب بسته‌ها بیدارسازی منابع را مدیریت می‌کند و حدود 23% تأخیر کمتری به دنبال دارد. در AFGPG نیز هیچ محدودیتی برای استفاده از منابع پرمصرف در نظر گرفته نشده و به همین دلیل، طول دوره بیکاری در منابع کم است. همین طور با انحراف بسته‌ها به مسیرهای دیگر باعث افزایش تأخیر در ارسال می‌شود. اما روش پیشنهادی با ایجاد محدودیت در استفاده از برخی مسیرها سبب افزایش طول دوره بیکاری در منابع کم‌کار شده و توانسته نسبت به AFGPG حدود 13% بهبود در تأخیر ایجاد کند. به این ترتیب مسیریابی پیشنهادی در مقایسه با دو روش دیگر دارای سربار تأخیر کمتری است.

5- نتیجه‌گیری

اگرچه قطع تغذیه سیستم، روشی کارآمد برای کاهش توان مصرفی شبکه روی تراشه است، اما تأثیر مثبت آن در گرو یک الگوریتم مسیریابی مناسب است تا روبه‌رویی متوالی بسته‌ها با منابع خاموش را کم کند و سربار تأخیر و توان مصرفی قطع و وصل‌شدن‌های متوالی منابع را از بین ببرد. با این هدف در این مقاله، یک الگوریتم مسیریابی برای مدیریت توان مصرفی در شبکه‌های روی تراشه سه‌بعدی نیمه‌متصل ارائه شد که با تقسیم شبکه به دو منطقه و محدودیت در انتخاب مسیر برای بسته‌ها، از روبه‌رویی بسته‌ها با منابع کم‌کار تا جای ممکن جلوگیری می‌کند و دوره بیکاری را در بافرهای کم‌کار موجود در سایر مسیرها افزایش می‌دهد. به این ترتیب از روشن و خاموش‌شدن متوالی منابع کم‌کار جلوگیری به عمل می‌آید که سبب ذخیره توان مصرفی بیشتر و نیز کاهش تأخیر بیدارسازی هنگام اعمال روش قطع تغذیه سیستم می‌شود. نتایج به ‌دست‌ آمده از شبیه‌سازی تحت ترافیک یکنواخت و ترانهاده نشان از بهبود عملکرد و توان مصرفی شبکه در روش پیشنهادی نسبت به روش‌های پیشین دارد.

شایان ذکر است که در الگوریتم پیشنهادی، شرط ازدحام برای کل مسیر انتخابی در گره مبدأ بررسی می‌شود. می‌توان شرط ازدحام را هنگام ورود بسته به هر گره از مسیر انتخابی مورد بررسی قرار داد. از طرفی برای بهبود کارایی الگوریتم مسیریابی پیشنهادی می‌توان آن را به الگوریتم تحمل‌پذیری خطا بسط داد تا با تشخیص آسانسورهای خراب و خاموش‌کردن آنها به کاهش بیشتری در توان مصرفی و نیز انتخاب بهتری برای مسیر منجر شود. همچنین تقسیم‌بندی شبکه به مناطق بیشتر و بررسی عملکرد آن از جمله مواردی است که در کارهای آتی مورد بررسی قرار خواهد گرفت.

مراجع

[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.

میترا معلم‌نیا در سال 1393 مدرك كارشناسي مهندسي برق-الکترونیک خود را از دانشگاه شهید چمران اهواز و در سال 1400 مدرك كارشناسي ارشد مهندسي برق-سیستم‌های دیجیتال خود را از دانشگاه علم و صنعت ایران دريافت نمود و هم اکنون در تیم الکترونیک شرکت فنآوران نیک جام مشغول به کار می‌باشد. زمينه‎هاي علمي مورد علاقه ایشان معماري كامپيوتر، شبكه‎هاي روی تراشه، سیستم‌های کممصرف و هوش مصنوعی مي‎باشد.

هادی‌شهریار شاه‌حسینی در سال 1367 مدرك كارشناسي مهندسي برق - الکترونیک خود را از دانشکده فنی دانشگاه تهران و در سال 1372 مدرك كارشناسي ارشد مهندسي برق - الکترونیک را از دانشگاه آزاد تهران و مدرک دکترای مهندسی برق در سال 1378 از دانشگاه علم و صنعت ایران دريافت نمود. وی از همان سال 1378 به عنوان عضو هیات علمی در دانشكده مهندسي برق دانشگاه علم و صنعت ایران مشغول به فعاليت میباشد. زمينه‎هاي علمي مورد علاقه نامبرده پردازش موازی و معماري كامپيوتر، مديريت شبكه‎هاي كامپيوتري، یادگیری ماشین و الگوریتمهای تکاملی و هوشمند مي‎باشد.

[1] این مقاله در تاریخ 20 آذر ماه 1400 دریافت و در تاریخ 7 مهر ماه 1401 بازنگری شد.

میترا معلم‌نیا، دانشكده مهندسي برق، دانشگاه علم و صنعت ايران، تهران، ایران، (email: mi_moalemnia96@elec.iust.ac.ir).

هادی‌شهریار شاه‌حسینی، دانشكده مهندسي برق، دانشگاه علم و صنعت ايران، تهران، ایران، (email: shahhoseini@iust.ac.ir).

[2] . Bus

[3] . Point to Point Network

[4] . Network on Chip

[5] . 3 Dimensional Network on Chip

[6] . Through Silicon Via

[7] . Routing

[8] . Deadlock

[9] . Virtual Channel

[10] . Power Gating

اشتراک گذاری

آدرس مقاله

مسیریابی منطقه‌ای توان‌آگاه برای شبکه‌هایروی تراشه سه‌بعدی نیمه‌متصل

رایمگ

پیوندهای سایت

مراکز مرتبط

پشتیبانی

صفحات رسمی