الگوریتم مسیریابی کارا برای شبکه روی تراشه سه‌بعدی با کانال‌های عمودی نیمه‌کامل
الموضوعات :فاطمه وحدت‌پناه 1 , احمد پاطوقی 2
1 - دانشگاه علم و صنعت ايران
2 - دانشگاه علم و صنعت ایران
الکلمات المفتاحية: بن‌بست شبکه روی تراشه سه‌بعدی کانال عمودی نیمه‌کامل کانال مجازی,
ملخص المقالة :
تراشه‌های سه‌بعدی از قرارگرفتن لایه‌های سیلیکون به صورت پشته ساخته می‌شوند و ارتباط بین این لایه‌ها توسط کانال‌های درون‌سیلیکون برقرار می‌شود. هزینه ساخت این تراشه‌ها تابعی از تعداد کانال‌های عمودی است و ساخت آنها با تعداد کامل کانال‌ها از لحاظ هزینه و پیچیدگی ساخت، مقرون به صرفه نیست. ناکامل بودن کانال‌های درون‌سیلیکون، مسأله مسیریابی اطلاعات را در شبکه‌های روی تراشه سه‌بعدی، پیچیده‌تر از شبکه‌های دوبعدی کرده است. در این مقاله یک الگوریتم مسیریابی برای شبکه‌های روی تراشه سه‌بعدی با کانال‌های عمودی ناکامل ارائه شده است که با تقسیم‌بندی لایه‌ای، سطری و ستونی شبکه، یک مسیریابی پویا را با حداکثر تطبیق‌پذیری در اختیار بسته‌ها قرار می‌دهد. این الگوریتم مستقل از مکان قرارگرفتن کانال‌های عمودی است و با در نظر گرفتن شماره لایه‌ای که بسته در آن قرار دارد و زوج یا فرد بودن آن، مدل چرخش خاصی در سطرها و یا ستون‌های زوج یا فرد به کار می‌گیرد. این الگوریتم تنها با استفاده از دو کانال مجازی مسأله بن‌بست و چرخه زنده را مرتفع کرده است. نتایج شبیه‌سازی و مقایسه الگوریتم پیشنهادی با الگوریتم اول- آسانسور نشان می‌دهد که در الگوریتم پیشنهادی، میانگین تأخیر تحویل بسته 8/32% نسبت به الگوریتم اول- آسانسور بهبود داشته است. همچنین قابل ذکر است که بهبود تأخیر و گذردهی با بزرگ‌تر شدن ابعاد شبکه و کاهش تعداد کانال‌های درون‌سیلیکون، افزایش خواهد یافت.
[1] M. Palesi and M. Daneshtalab, Routing Algorithms in Networks-on-Chip, Springer, 2014.
[2] P. Behrooz, Introduction to Parallel Processing: Algorithms and Architectures, Springer Science & Business Media, 2006.
[3] D. Jose, S. Yalamanchili, and L. M. Ni, Interconnection Networks: an Engineering Approach, Morgan Kaufmann, 2003.
[4] X. Yuan, J. Cong, and S. S. Sapatnekar, Three-Dimensional Integrated Circuit Design, Springer, 2010.
[5] M. Fathy, R. Berangi, S. Akbari, and A. Shafieey, "AFRA: a low cost high performance reliable routing for 3D mesh NoCs," in Proc. IEEE Design, Automation & Test in Europe Conf. & Exhibition, DATE'12, pp. 332-337, Dresden, Germany, 12-16 Mar. 2012.
[6] A. Ben Ahmed, A. Ben Ahmed, and A. Ben Abdallah, "Deadlock-recovery support for fault-tolerant routing algorithms in 3D-NoC architectures," in Proc. IEEE 7th Int. Symp. on Embedded Multicore Socs, MCSoC'13, pp. 67-72, Tokyo, Japan, 26-28 Sept. 2013.
[7] A. Ben Ahmed and A. Ben Abdallah, "Low-overhead routing algorithm for 3D network-on-chip," in Proc. Third Int. Conf. on Networking and Computing, ICNC'12, pp. 23-32, Okinawa, Japan, 5-7 Dec. 2012.
[8] A. Ben Ahmed, On the Design of a 3D Network-on-Chip for Many-Core SoC, Ph.D Diss., University of Aizu, 2012.
[9] M. Ebrahimi, M. Daneshtalab, P. Liljeberg, J. Plosila, and H. Tenhunen, "Exploring partitioning methods for 3D networks-on-chip utilizing adaptive routing model," in Proc. ACM/IEEE 5th Int. Symp. on Networks-on-Chip, pp. 73-80, Pittsburgh, PA, USA, 1-4 May 2011.
[10] F. Chaochao, M. Zhang, J. Li, J. Jiang, Z. Lu, and A. Jantsch, "A low-overhead fault-aware deflection routing algorithm for 3D network-on-chip," IEEE Computer Society Annual Symp. on VLSI, ISVLSI'11, pp. 19-24, 4-6 Jul. 2011.
[11] H. Ying, A. Jaiswal, and K. Hofmann, "Deadlock-free routing algorithms for 3-dimension networks-on-chip with reduced vertical channel density topologies," in Proc. IEEE Int. Conf. on High Performance Computingand Simulation, HPCS'12, pp. 268-274, Madrid, Spain, 2-6 Jul. 2012.
[12] R. Claudia, L. Anghel, and D. Avresky, "Message routing in 3D networks-on-chip," in Proc. IEEE NORCHIP, Trondheim, Norway, 16-17 Nov. 2009.
[13] A. Eghbal, P. M. Yaghini, N. Bagherzadeh, and M. Khayambashi, "Analytical fault tolerance assessment and metrics for TSV-based 3D network-on-chip," IEEE Trans. on Computers, vol. 64, no. 12, pp. 3591-3604, Dec. 2015.
[14] I. Loi, F. Angiolini, S. Fujita, S. Mitra, and L. Benini, "Characterization and implementation of fault-tolerant vertical links for 3-D networks-on-chip," IEEE Trans. on Computer-Aided Design of Integrated Circuits and Systems, vol. 30, no. 1, pp. 124-134, Jan. 2011.
[15] I. Loi, S. Mitra, T. H. Lee, S. Fujita, and L. Benini, "A low-overhead fault tolerance scheme for TSV-based 3D network on chip links," in Proc. IEEE/ACM Int. Conf. on Computer-Aided Design, ICCAD'08, pp. 598-602, San Jose, CA, USA, 10-13 Nov. 2008.
[16] I. Loi, P. Marchal, A. Pullini, and L. Benini, "3D NoCs-unifying inter & intra chip communication," in Proc. IEEE Int. Symp. on, Circuits and Systems, ISCAS'10, pp. 3337-3340, Paris, France, 30 May-2 Jun. 2010.
[17] S. Pasricha, Y. Zou, and F. Collins, "A low overhead fault tolerant routing scheme for 3D networks-on-chip," in Proc. 12th Int.l Symp. on Quality Electronic Design, ISQED'11, 8 pp., Santa Clara, CA, USA, 14-16 Mar. 2011.
[18] F. Petrot, M. Bahmani, F. Dubois, and A. Sheibanyrad, "Elevator-first: a deadlock-free distributed routing algorithm for vertically partially connected 3D-NoCs," IEEE Trans.on Computers, vol. 62, no. 3, pp. 609 - 615, Mar. 2013.
[19] M. Ebrahimi, et al., "DyXYZ: fully adaptive routing algorithm for 3D-NoCs," in Proc. 21st Euromicro Int. Conf. on Parallel, Distributedand Network-Based Processing, PDP'13, pp. 499-503, Belfast, UK, 27 Feb.-1 Mar. 2013.
[20] C. Ge-Ming, "The odd-even turn model for adaptive routing," IEEE Trans. on Parallel and Distributed Systems, vol. 11, no. 7, pp. 729-738, Jul. 2000.
[21] D. Nizar, T. Mak, 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.
[22] Z. Jun, "LOFT: a low-overhead fault-tolerant routing scheme for 3D NoCs," Integration, the VLSI J. on, vol. 52, pp. 42-50, Jan. 2016.
