An Efficient Routing Algorithm for Three-Dimensional Networks On-Chip with Partially Vertical Links
Subject Areas : electrical and computer engineeringF. Vahdat Panah 1 , Ahmad patooghy 2 *
1 - University of Science and Technology
2 -
Keywords: Deadlock 3D NOC partially connected TSVs virtual channel,
Abstract :
Three-Dimensional Chips are made of stacking silicon layers which communicate with each other by Through-Silicon-Via (TSV) links. Manufacturing cost of Three-Dimensional chips is a function of the number of TSVs because the fabricating of a three-dimensional chip with fully vertical links is of high cost and high fabrication complexity. The packet routing strategies in the 3D NoCs with partially TSVs is more complex than that in the 2D NoCs. In this paper, we proposed a routing algorithm for the 3D NoCs with partial TSVs, which provides a dynamic routing with maximum adaptivity for packets by dividing the network into three groups of layers, rows and columns. This algorithm is independent of vertical channel's position but related to layer number of the current packet and based on the layer number, odd or even, uses a special turn strategy to route packets on rows and columns with odd or even numbers. The proposed routing algorithm mitigates deadlock and livelock with only two virtual. The experiments show that average packet latency in proposed algorithm is 32.8% smaller than that in Elevator_First which is a well-known algorithm for packet routing in 3D chips. Also, this improvement on average packet latency and network throughput will be more with increasing on network size and reduction on TSV number.
[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.