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

رضایی راوری, مریم; ستاری نائینی, وحید

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

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

نویسندگان

¹ دانشگاه تحصیلات تکمیلی صنعتی و فناوری پیشرفته کرمان

² دانشگاه شهید باهنر کرمان، دکترای مهندسی کامپیوتر

چکیده

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

کلیدواژه‌ها

موضوعات

سیستم‌های دیجیتال و معماری کامپیوتر

عنوان مقاله [English]

Reliability-Enabled Routing in Congestion-Aware Networks-on-Chip

نویسندگان [English]

Maryam Rezaei-Ravari ¹
Vahid Sattari-Naeini ²

چکیده [English]

The efficiency of networks on chip (NoC) is affected by related routing algorithms. Network congestion has a negative impact on the performance of on-chip networks due to the increased packet latency. One of the key objectives design of NoC is reliability against failure. For a NoC to be robust, achieving better performance, and tolerating faults, two key functions need to be investigated: (a) the ability to avoid congested paths and balancing the traffic workloads, and (b) the ability to tolerate faults as well as proceeding to provide system functionality against physical impairment. For this purpose, a cost model for route selection with greater reliability and less congestion has been proposed. In this model, at first a congestion-aware routing algorithm is deployed based on the Q-learning approach to check congested areas in the network, then adjacent links are considered to deal with reliability. Finally, given the importance of the reliability, high weight is assigned to this parameter, and the path with the lowest cost is selected to forward packets. Simulation results show that the proposed approach outperforms state-of-the-art Bi-LCQ algorithm under two traffic patterns.

کلیدواژه‌ها [English]

Q-learning
Reliability
Network-on-Chip
Fault tolerance
Congestion-aware routing algorithm

مراجع

[1] R. Marculescu, U. Y. Ogras, L.-S. Peh, N. E. Jerger, and Y. Hoskote, "Outstanding research problems in NoC design: system, microarchitecture, and circuit perspectives," IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 28, no. 1, pp. 3-21, 2009.

[2] W. J. Dally and B. Towles, "Route packets, not wires: on-chip interconnection networks," in Proceedings of the 38th Design Automation Conference (IEEE Cat. No.01CH37232), 2001, pp. 684-689.

[3] A. Jantsch and H. Tenhunen, Networks on chip. Springer, 2003.

[4] P. Gratz, B. Grot, and S. W. Keckler, "Regional congestion awareness for load balance in networks-on-chip," in High Performance Computer Architecture, 2008. HPCA 2008. IEEE 14th International Symposium on, 2008, pp. 203-214: IEEE.

[5] M. Li, Q.-A. Zeng, and W.-B. Jone, "DyXY: a proximity congestion-aware deadlock-free dynamic routing method for network on chip," in Proceedings of the 43rd annual Design Automation Conference, 2006, pp. 849-852: ACM.

[6] G. Ascia, V. Catania, M. Palesi, and D. Patti, "Implementation and analysis of a new selection strategy for adaptive routing in networks-on-chip," IEEE Transactions on Computers, vol. 57, no. 6, pp. 809-820, 2008.

[7] M. Ebrahimi, M. Daneshtalab, P. Liljeberg, J. Plosila, and H. Tenhunen, "Agent-based on-chip network using efficient selection method," in VLSI and System-on-Chip (VLSI-SoC), 2011 IEEE/IFIP 19th International Conference on, 2011, pp. 284-289: IEEE.

[8] S. Ma, N. Enright Jerger, and Z. Wang, "DBAR: an efficient routing algorithm to support multiple concurrent applications in networks-on-chip," in ACM SIGARCH Computer Architecture News, 2011, vol. 39, no. 3, pp. 413-424: ACM.

[9] C. J. Watkins and P. Dayan, "Q-learning," Machine learning, vol. 8, no. 3-4, pp. 279-292, 1992.

[10] S. P. Choi and D.-Y. Yeung, "Predictive Q-routing: A memory-based reinforcement learning approach to adaptive traffic control," in Advances in Neural Information Processing Systems, 1996, pp. 945-951.

[11] S. Kumar and R. Miikkulainen, "Dual reinforcement Q-routing: An on-line adaptive routing algorithm," in Proceedings of the artificial neural networks in engineering Conference, 1997, pp. 231-238.

[12] S. Kumar and R. Miikkulainen, "Confidence based dual reinforcement q-routing: An adaptive online network routing algorithm," in IJCAI, 1999, vol. 99, pp. 758-763: Citeseer.

[13] M. K. Puthal, V. Singh, M. S. Gaur, and V. Laxmi, "C-Routing: An adaptive hierarchical NoC routing methodology," in VLSI and System-on-Chip (VLSI-SoC), 2011 IEEE/IFIP 19th International Conference on, 2011, pp. 392-397: IEEE.

[14] F. Farahnakian, M. Ebrahimi, M. Daneshtalab, J. Plosila, and P. Liljeberg, "Optimized Q-learning model for distributing traffic in on-Chip Networks," in Networked Embedded Systems for Every Application (NESEA), 2012 IEEE 3rd International Conference on, 2012, pp. 1-8: IEEE.

[15] F. Farahnakian, M. Ebrahimi, M. Daneshtalab, P. Liljeberg, and J. Plosila, "Bi-LCQ: A low-weight clustering-based Q-learning approach for NoCs," Microprocessors and Microsystems, vol. 38, no. 1, pp. 64-75, 2014.

[16] آ. امیدوار. ک. محمدی, "الگوریتم مسیریابی با افزایش قابلیت اطمینان در شبکههای تحملپذیر تاخیر," فصلنامه صنایع الکترونیک , vol. 5, no. 1, 1393.

[17] J. Kim, D. Park, C. Nicopoulos, N. Vijaykrishnan, and C. R. Das, "Design and analysis of an NoC architecture from performance, reliability and energy perspective," in Proceedings of the 2005 ACM symposium on Architecture for networking and communications systems, 2005, pp. 173-182: ACM.

[18] M. Ebrahimi, M. Daneshtalab, J. Plosila, and F. Mehdipour, "MD: minimal path-based fault-tolerant routing in on-chip networks," in Design Automation Conference (ASP-DAC), 2013 18th Asia and South Pacific, 2013, pp. 35-40: IEEE.

[19] J.-x. Wang, F.-f. Fu, T.-S. Zhang, and Y.-P. Chen, "A small-granularity solution on fault-tolerant in 2D-mesh network-on-chip," in Solid-State and Integrated Circuit Technology (ICSICT), 2010 10th IEEE International Conference on, 2010, pp. 382-384: IEEE.

[20] Z. Zhang, A. Greiner, and S. Taktak, "A reconfigurable routing algorithm for a fault-tolerant 2D-mesh network-on-chip," in Design Automation Conference, 2008. DAC 2008. 45th ACM/IEEE, 2008, pp. 441-446: IEEE.

[21] D. Fick, A. DeOrio, G. Chen, V. Bertacco, D. Sylvester, and D. Blaauw, "A highly resilient routing algorithm for fault-tolerant NoCs," in Proceedings of the Conference on Design, Automation and Test in Europe, 2009, pp. 21-26: European Design and Automation Association.

[22] M. Valinataj, S. Mohammadi, J. Plosila, P. Liljeberg, and H. Tenhunen, "A reconfigurable and adaptive routing method for fault-tolerant mesh-based networks-on-chip," AEU-International Journal of Electronics and Communications, vol. 65, no. 7, pp. 630-640, 2011.

[23] R. J. Behrouz, M. Modarressi, and H. S. Azad, "A Reconfigurable Fault-Tolerant Routing Algorithm to Optimize the Network-on-Chip Performance and Latency in Presence of Intermittent and Permanent Faults," in 2011 IEEE 29th International Conference on Computer Design (ICCD), 2011, pp. 433-434: IEEE.

[24] J. Duato, S. Yalamanchili, and L. M. Ni, Interconnection networks: an engineering approach. Morgan Kaufmann, 2003.

[25] E. Wachter, V. Fochi, F. Barreto, A. Amory, and F. Moraes, "A Hierarchical and Distributed Fault Tolerant Proposal for NoC-based MPSoCs," IEEE Transactions on Emerging Topics in Computing, pp. 1-1, 2018.

[26] A. B. Gabis, P. Bomel, and M. Sevaux, "Application-aware Multi-Objective Routing based on Genetic Algorithm for 2D Network-on-Chip," Microprocessors and Microsystems, 2018.

[27] C. Wu et al., "An efficient application mapping approach for the co-optimization of reliability, energy, and performance in reconfigurable NoC architectures," IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 34, no. 8, pp. 1264-1277, 2015.

[28] Y. Ben-Itzhak, E. Zahavi, I. Cidon, and A. Kolodny, "HNOCS: modular open-source simulator for heterogeneous NoCs," in Embedded Computer Systems (SAMOS), 2012 International Conference on, 2012, pp. 51-57: IEEE.

[29] A. Varga, "Using the OMNeT++ discrete event simulation system in education," IEEE Transactions on Education, vol. 42, no. 4, p. 11 pp., 1999.