Design and Evaluation of High-Performance and Fault-tolerant Routing Algorithms for 3D-NoCs

2D Network-on-Chips (NoCs) have been the mainstream interconnection technology for multi-core systems. In this dissertation, different aspect of the alternative 3D-NoC technology have been investigated. The 3D technology compensates for the deficiencies of 2D-NoCs such as long latency, power overhead and lack of scalability. While the routers in a traditional 3D-NoC are fully-connected using Through-Silicon-Via (TSV), we consider partially-connected 3d-NoCs to mitigate the silicon area overhead of a fully-connected architecture. The TSV fault sources such as thermal stress, warpage, impurities and misalignment have been reviewed. We investigate the delicacies of designing routing algorithms for partially connected networks. Several high-performance, fault-tolerant and adaptive routing algorithms have been suggested and proved to be livelock- and deadlock-free. The proposed algorithms are capable of tolerating faults on vertical links. The algorithms are then extended to be reconfigurable to tolerate both fabrication-time and run-time TSV failures. Both simulation and analytical models are applied to evaluate the performance of the algorithms. An analytical model, tailored to the adaptivity of the algorithm and under low traffic scenarios, has been developed and the results have been verified by simulation. The algorithms are tested under different traffic patterns, different number of elevators and different elevator assignment mechanisms and shown to outperform the previous work in terms of both network latency and fault-tolerance