الگوریتم مسیریابی با قابلیت تحمل‌پذیری اشکال برای شبکه روی تراشه سه‌بعدی
محورهای موضوعی : مهندسی برق و کامپیوترمصطفی تقی‌زاده فیروزجایی 1 * , مجتبی ولی‌نتاج 2 , مجتبی منصوری 3
1 - دانشگاه صنعتي نوشیروانی بابل
2 - مهندسی برق و کامپیوتر
3 - دانشگاه صنعتي نوشیروانی بابل
کلید واژه: شبکه روی تراشه شبکه روی تراشه سه‌بعدی الگوریتم مسیریابی تحمل‌پذیری اشکال قابلیت اطمینان,
چکیده مقاله :
کارایی شبکه‌های روی تراشه به طور گسترده‌ای به الگوریتم‌های مسیریابی به کار رفته در آنها وابسته است. در سالیان اخیر، الگوریتم‌های مسیریابی زیادی برای شبکه‌های روی تراشه دوبعدی و سه‌بعدی طراحی‌شده است. شبکه روی تراشه سه‌بعدی که برای افزایش کارایی شبکه روی تراشه دوبعدی معرفی گردیده، از ترکیب مفاهیم شبکه روی تراشه و مجتمع‌سازی سه‌بعدی به وجود آمده است. در این گونه مدارها عناصر نیمه‌هادی به روشی خاص به صورت پشته‌ای روی یکدیگر قرار می‌گیرند. به دلیل تأثیرات قابل توجهی که اشکال‌های لینک‌ها یا گره‌های شبکه روی تراشه بر عملکرد مدار می‌گذارند، الگوریتم‌های مسیریابی بایستی روش‌هایی را به کار گیرند تا از تأثیرات اشکال جلوگیری نمایند. این ویژگی خصوصاً در شبکه روی تراشه سه‌بعدی که احتمال رخداد اشکال در لینک‌های عمودی آن قابل توجه است، اهمیت بیشتری دارد. در این مقاله، یک روش جدید برای مسیریابی در شبکه روی تراشه سه‌بعدی به نام FT-ZXY معرفی می‌شود که بدون استفاده از کانال‌های مجازی و در نتیجه با سربار سخت‌افزاری ناچیز، قابلیت تحمل اشکال‌های منفرد در لینک‌های افقی و اشکال‌های چندگانه در لینک‌های عمودی را دارد. نتایج شبیه‌سازی نشان می‌دهد که الگوریتم مسیریابی پیشنهادی از نظر پارامترهای ارزیابی مانند تأخیر، قابلیت اطمینان، سربار سخت‌افزاری و توان مصرفی، عملکرد بهتری نسبت به الگوریتم‌های مطرح‌شده قبلی دارد.
The performance of Networks-on-Chip is highly dependent to the incorporated routing algorithms. In recent years, many routing algorithms have been proposed for 2D and 3D Networks-on-Chip. In 3D integrated circuits, different devices are stacked through silicon via in which the vertical connections are vulnerable to manufacturing process variations. Therefore, because of the high impact of faulty links or nodes on the performance of a Network-on-Chip, utilizing a fault-tolerant routing algorithm is of great importance especially for 3D Networks-on-Chip in which the vertical links are more vulnerable. In this paper, a new fault-tolerant routing algorithm called FT-ZXY is proposed to be used in 3D Networks-on-Chip. This routing method is capable of tolerating multiple vertical faulty links in addition to single horizontal faulty links without using any virtual channels thus incurs a very low hardware overhead. Experimental results reveal that the proposed routing algorithm has more reliability compared to the previous designs while incurs less latency and requires lower area and power overheads.
[1] A. Agarwal, C. Iskander, and R. Shankar, "Survey of network on chip (NoC) architectures and contributions," J. Eng. Comput. Arch., vol. 3, no. 1, pp. 1-15, 2009.
[2] D. Wentzlaff, et al., "On-chip interconnection architecture of the tile processor," IEEE Micro, vol. 27, no. 5, pp. 15-31, Sep. 2007.
[3] A. Hemani, et al., "Network on chip: an architecture for billion transistor era," in Proc. of the 18th IEEE NORCHIP Conf., 8 pp., Nov. 2000.
[4] S. Murali, et al., "Analysis of error recovery schemes for networks on chips," IEEE Design & Test of Computers, vol. 22, no. 5, pp. 434-442, Sep./Oct.. 2005.
[5] C. Grecu, L. Anghel, P. P. Pande, A. Ivanov, and R. Saleh, "Essential fault-tolerance metrics for NoC infrastructures," in Proc. 13th IEEE Int. On-line Testing Symp., pp. 37-42, Crete, Greece, 8-11 Jul. 2007.
[6] C. Rusu, L. Anghel, and D. Avresky, "RILM: reconfigurable inter-layer routing mechanism for 3D multi-layer networks-on-chip," in Proc. 16th. IEEE Int. On-Line Testing Symp., pp. 121-126, Corfu, Greece, 5-7 Jul. 2010.
[7] C. Feng, et al., "A low-overhead fault-aware deflection routing algorithm for 3D network-on-chip," in Proc. IEEE Computer Society Annual Symp. on VLSI, pp. 19-24, 4-6 Jul. 2011.
[8] A. M. Rahmani, et al., "Design and management of high-performance, reliable and thermal-aware 3D networks-on-chip," IET Circuits, Devices & Systems, vol. 6, no. 5, pp. 308-321, Sep. 2012.
[9] S. Akbari, et al, "AFRA: a low cost high performance reliable routing for 3D mesh NoCs," in Proc. of 15th ACM/IEEE Design, Automation, and Test in Europe, DATE'12, pp. 332-337, Dresden, Germany, 12-16 Mar. 2012.
[10] M. Ebrahimi, M. Daneshtalab, and J. Plosila, "Fault-tolerant routing algorithm for 3D NoC using hamiltonian path strategy," in Proc. of 16th ACM/IEEE Design, Automation, and Test in Europe, DATE'13, pp. 1601-1605, Grenoble, France, 18-22 Mar. 2013.
[11] C. J. Glass and L. M. Ni, "The turn model for adaptive routing," in Proc. of the 19th Annual Int. Symp. on Computer Architecture, ISCA'92, pp. 278-287, 1992.
[12] C. Grecu, et al., "BIST for network-on-chip interconnect infrastructures," in Proc. 24th IEEE VLSI Test Symp, 6 pp., Berkeley, CA, USA, 30 Apr.- 4 May 2006.
[13] N. Dahir, T. Mak, R. Al-Dujaily, and A. Yakovlev, "Highly adaptive and deadlock-free routing for three-dimensional networks-on-chip," IET Computers & Digital Techniques, vol. 7, no. 6, pp. 255-263, Nov. 2013.
[14] Fazzino, F. Palesi, M. Patti, 2008 Noxim: Network-on-Chip Simulator," URL:http://sourceforge.net/projects/noxim.