Advances in the Standards & Applied Sciences

Advances in the Standards & Applied Sciences

Fault Tolerant and Congestion-Aware Routing Algorithm in a Partially Connected 3D Network on Chip

Document Type : Technical Note

Authors
Sina yousefisadr 1
majid nouri 2
1 Department of Electrical and Computer Engineering, Science and Research Branch, Islamic Azad University, Tehran, Iran
2 Vehicle Engineering Research Group, Research Center of Technology and Engineering, Standard Research Institute, Karaj, Iran
10.22034/asas.2024.448026.1054
Abstract
Abstract— Network-on-Chips (NoCs) have been accepted as a viable communication platform in many-core systems. However, they possess high network latency and consume large power. In this paper, we introduce a minimal routing algorithm in partially connected 3D Network-on-Chip, in which a fixed place of TSVs is designed to reduce TSV implementation cost which can be provided as a standard in the automotive electronics industry. This routing algorithm employs network congestion and fault information to find the minimum path while avoiding traversing the faulty paths. The proposed algorithm consists of in-layer routing and interlayer routing. The intra-layer routing algorithm employs an information propagation network to propagate control information between nodes located in the same layer. It uses a parameter called index to select the optimum path between nodes in the same layer. The index value is updated periodically based on a faulty link or a faulty node and published across networks. The interlayer routing algorithm is performed based on the minimum path to the elevator routers. The proposed algorithm reduces the average packet latency and increases the network throughput. The simulation results indicate that our routing algorithm improves network latency by 15.3% compared to two other routing algorithms.
Keywords
Keywords&mdash
Fault-tolerant
Congestion-aware
Index Mechanism
3D-NoC
routing
Subjects
[1]          M Mollajafari, F Kouhyar, “Simultaneous optimization of fuel and electrical energy consumption in forward-looking hybrid electric vehicle”, Automotive Science and Engineering, 2022.
[2]          H. K. Mondal, S. H. Gade, S. Kaushik, and S. Deb, “Adaptive Multi-Voltage Scaling with Utilization Prediction for Energy-Efficient Wireless NoC,” IEEE Transactions on Sustainable Computing, Vol. 2, No. 4, pp. 382–395, August  2017.
[3]          S. H. Mortazavi, R. Akbar, F. Safaei and A. Rezaei, “A Fault-Tolerant and Congestion-Aware Architecture for Wireless Networks-on-Chip”, Wireless Networks, Vol. 25, No. 6, pp. 3675–3687, August 2019.
[4]          D. Park, S. Eachempati, R. Das, A. K. Mishra, Y. Xie, N. Vijaykrishnan and C. R. Das, “MIRA: A Multi-layered On-Chip Interconnect Router Architecture”, Proceedings of International Symposium on Computer Architecture, pp. 251– 261, June 2008.
[5]          M. Momeni, A. Jafari pozveh, “An adaptive Approximation Method for Traffic Reduction in Network on Chip,”2020, 6th Iranian Conference on Signal Processing and Intelligent Systems (ICSPIS), pp. 1-5, 2020.
[6]          M. Nezarat, et.al. “Two-Step Thermal-Aware Routing Algorithm in 3D NoC,” 11th Iranian Conference on Computer Engineering and Knowledge  (ICCKE2021), pp 482-486, 2021.
[7]          X. Chen, Z. Xu, H. Kim, P. Gratz, J. Hu, M. Kishinevsky, and U. Ogras, “In-network monitoring and control policy for DVFS of CMP networks-on-chip and last level caches”, In International Symposium on Networks on Chip (NoCS), pages 43--50, 2012.
[8]          M. Nezarat, et.al, Thermal-aware routing algorithm in partially connected 3D NoC with dynamic availability for elevators, Journal of Ambient Intelligence and Humanized Computing 14 (8), pp 10731- 10744, 2022.
[9]          M. Elahi et al., “LTD-Router: Low Latency Traffic Distributed FPGA Based Router Architecture Using Dedicated Paths,”  26th Iranian Conference on  Electrical Engineering (ICEE2018), pp. 1601-1606, May 2018.
[10]        S.M. Mohtavipour et al., “A Link-Elimination Partitioning Approach for Application Graph Mapping in RC Systems,” The Journal of supercomputing, pp. 726-754, 2020.
[11]        F. Dubois, et.al. “Elevator-first: A Deadlock-Free Distributed Routing Algorithm for Vertically Partially Connected 3D-NoC’s,” IEEE Transactions on Computers, Vol. 62, pp. 609-615, December 2011.
[12]        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 Journal on Emerging Technologies in Computing Systems (JETC), Vol. 26, No. 16, pp. 1-7, August 2020.
[13]        E. Taheri, R. G. Kim, M. Nikdast, “AdEle: An Adaptive Congestion-and-Energy-Aware Elevator Selection for Partially Connected 3D NoCs”. arXiv preprint arXiv:2102.08323, February 2021.
[14]        R. Salamat, M. Khayambashi, M. Ebrahimi, and N. Bagherzadeh, “A Resilient Routing Algorithm with Formal Reliability Analysis for Partially Connected 3D-NoCs,” IEEE Transactions on Computers, Vol. 65, No. 11, pp. 3265-3279, March 2016.
[15]        M. Agyeman, W. Zong, “An Efficient 2d Router Architecture for Extending the Performance of Inhomogeneous 3d NoC-based Multi-core Architectures,” International Symposium on Computer Architecture and High Performance Computing Workshops (SBAC-PADW), pp.79-84, October 2016.
[16]        M.M. Bassiri, et.al, “Mitigating Reconfiguration Overhead in On-line Scheduling for Reconfigurable Computing Systems,” 2nd International Confrence on Computer Engineering and Technology (ICCET), Vol. 4, pp. 397-402, April 2010.
[17]        M.M. Bassiri, et.al. “Configuration Reusing in On-line Task scheduling for Reconfigurable Computing Systems,” Journal of Computer Science and Technology, Vol. 26, pp. 463-473, May 2011.
[18]        M. Momeni, et.al. “Energy Optimization in 3D Networks-on-Chip through Dynamic Voltage Scaling technique,” 28th Iranian Conference on Electrical Engineering (ICEE), Tabriz, pp. 1-4, August 2020.
[19]        C. Rusu, L. Anghel and D. Avresky, “Reconfigurable Inter-Layer Routing Mechanism for 3D Multi-Layer Networks-on-Chip”, 16th International On-Line Testing System (IOLTS), pp. 121-126, July 2010.
[20]        C. Feng, M. Zhang, J. Li, J. Jiang, Z. Lu ,A. Jantsch, “A Low-Overhead Fault-Aware Deflection Routing Algorithm for 3D Network-on-Chip”, IEEE Computer Society Annual Symposium on VLSI, pp. 19–24, July 2011.
[21]        Y. Fu, Q. Chen, G. He, K. Chen, Z. Lut, C. Zhang and L. Li, “Congestion-Aware Dynamic Elevator Assignment for Partially Connected 3D-NoCs”. IEEE International Symposium on Circuits and Systems (ISCAS), pp. 1-5, May 2019.
Advances in the Standards & Applied Sciences
Volume 2, Issue 2
Winter 2024
Pages 58-64