Algorithms And Architectures Of Thermal/Traffic-aware Three Dimensional Network-on-Chip Systems

When chip size continues to increase to accommodate for more processing cores or more functionalities,the global interconnect length increases at the same time.This causes a tremendous amount of power to be dissipated unnecessarily in interconnects and repeaters.On-chip signals also require more time to travel across the entire chip as a result of increasing chip size.3D NoC(Network-on-Chip),the combination of the 3D IC and Network-on-Chip,is a promising architecture to overcome these issues as it replaces long inter-block paths with much shorter vertical inter-layer interconnects.Temperature is an important design constraint for 3D NoC.Owing to larger power density,the thermal issue of 3D NoC becomes worse than that of 2D NoC.It has been proven that high temperature and high thermal gradients can cause performance loss,device unreliability and wearout-acceleration.Besides,increasing the number of TSVs can enhance the network bandwidth,but it also increases the area overhead and the risk of failure in chip manufacturing and operation.Because the fabrication yield and the occupied silicon area are functions of the number of TSVs,the number of TSVs to be fabricated in a chip is limited.Thus,it is important to study the optimization of the 3D NoC architecture with a limited number of TSVs.In this paper,the thermal management of 3D NoCs and the optimizations of some temperature-related problems,and the architecture optimization of 3D NoCs with the limited TSVs are studied.The paper focuses on the temperature estimation(temper-ature prediction and reconstruction under measurement noise),thermal modeling,dy-namic thermal management(DTM),thermal-aware routing algorithms,the static place-ment of the vertical links,the dynamic assignment of the vertical links and other key issues.Firstly,the power estimation model and the thermal model of 3D NoCs are studied.We propose a multivariate linear power model for NoC systems and a physically-based state space thermal model for 3D NoC.Based on the state space model and the pow-er model that we proposed,we employ an N-step-ahead Kalman predictor to get the optimal temperature predictions at locations of interest based on a few sensor obser-vations with noise.Compared with the Auto-Regressive-based prediction scheme,the proposed prediction scheme reduces the standard deviations of the prediction error by 46%-53%under sensor noise with ? = 2.Thermal-and traffic-aware routing algorithms are also studied.We propose a congestion-and thermal-aware routing,which can achieve a thermal and load balanced distribution by guiding traffic loads migrations across different nodes.In the intra-layer routing,we employ a dynamic programming network to balance the traffic and temperature.While in the inter-layer routing,we assign more traffic to the layers which have higher thermal efficiencies and are not in the congestion mode as well.The dynamic thermal management strategy of 3D NoCs is also studied in this paper.Dynamic thermal management(DTM)is required to maintain the system tem-perature within a certain thermal limit.Instead of cutting off throttled routers simply,we conduct a quota-based throttling scheme in a proactive manner to cool down near overheated routers in advance.The proposed proactive throttling scheme improves the throughput up to 11.1%compared with the reactive throttling schemes.This paper proposes an offline thermal sensor placement and online reconstruc-tion methods under Gaussian noise and non-Gaussian noise.A greedy placement algo-rithm maximizing the system observability is proposed to determine a subset of ther-mal sensors.Any non-Gaussian distribution can be approximated by a finite sum of known Gaussian distributions sufficiently well.Based on this,a Gaussian-Sum filter is employed to reconstruct full-chip temperatures based on a limited number of ther-mal sensors under non-Gaussian noise at run-time.Compared with the Kalman filter,the Gaussian-Sum filter can reduce the RMSE(Root Mean Square Error)and the Max error by 29.27%?35%and 33.26%?40.6%,respectively.The optimal placement of vertical links for 3D NoCs with a limited number of TSVs is studied.This paper employs the hybrid strategy of Genetic Algorithm and Tabu Search to solve the problem of the optimal vertical link placement.The optimization of the performance and the cost of a 3D NoC system is a multi-objective optimization problem.A reasonable solution to a multi-objective problem is to investigate a set of solutions called Pareto optimal set,each of which cannot be improved with respect to any objective without worsening at least one other objective.Being a population-based approach,Genetic algorithm(GA)can find multiple optimal solutions in one single simulation run.For a given number/locations of elevators for 3D NoC systems,the assignment of elevators can considerably affect the performance of the 3D NoC.To get a static optimal assignment,tabu search is employed.The dynamic vertical link assignment method for 3D NoCs with a limited number of TSVs is studied.This paper proposes a congestion-aware dynamic vertical link as-signment.At design-time,the optimal assignment obtained by using the Tabu Search is static and application-dependent.Thus,it can not be changed dynamically according to application requirements,which may lead to network congestion.To support dynamic assignment,we consider the congestion information of vertical links when we plan the path.The selection criterion of the vertical links used in this paper takes into account both the distance and the network congestion,so it is more suitable for the partially connected 3D NoCs.Experiments show that the proposed Congestion-aware Dynamic Assignment(CDA)algorithm performs better than the other three algorithms(random,SelByDis-1,SelByDis-2)in five traffic patterns:uniform,transpose,shuffle,butterfly and bitreversal.Taking Uniform traffic pattern as an example,the CDA algorithm im-proves performance by 67%-87%compared with the random algorithm,by 8%-25%compared with SelByDis-1 and by 13%-18%compared with SelByDis-2.