Cross-layer Congestion Avoidance Scheme For Network On Chip

In order to address the growing computing demands,more and more processing elements(PEs)are integrated into the many-core embedded systems.Due to its efficient communication and high scalability,Network-on-Chip(NoC)has become mainstream many-core interconnect facility.However,as the increase of the scale of NoC and intercore communication traffic,the congestion of NoC becomes more and more serious.Because the on-chip networks connect different system components within the chip,they should provide good communication capacity and have low implementation complexity.Due to the difference to the internet,the congestion control and congestion avoidance policies proposed for the traditional computer networks can not be directly applied to the on-chip network.At present,the congestion solutions for the on-chip networks mainly optimize the router structures or improve the routing algorithms at the network level.Some researchers make attampts to reduce network congestion by enhancing application mapping algorithms.However,few researchers combine these two methods together.In this thesis,an application mapping algorithm is proposed by cross-layer design methodology.The mapping algorithm considers informations provided by network-level to balance the network traffic and proactively avoid congestion.Thus,this algorithm reduces network congestion effectively.Firstly,this thesis presents a network congestion evaluation method based on the application information and system status at the application level.This method calculates the factor which is the number of communication flows that interfere with the given flow.The factor reflects both intra-application and inter-application congestion.In addition,under the impacts from congestions,the performance of application mapping algorithms can be evaluated by the mean of the congestion factors among all communication flows.The simulation shows that the congestion factor has a strong correlation with network congestion.Secondly,this thesis proposes an application mapping algorithm to avoid avoidance based on the congestion factor.This algorithm effectively reduces the network congestion and average packet delay.During the task sorting phase,the algorithm presents the concept of "affinity list" and appends affinity lists to each task to improve better mapping location.During the task mapping,the congestion factor is used to avoid congestion.A “benefit function” is proposed to balance the contradiction between congestion avoidance and distance increase.The benefit function greatly reduces the search range.Finally,this thesis designs and implements a multi-core system simulator for network behavior researches in multi-core systems.The simulator builds a behavior-level task execution model for the processors and uses the existing clock-cycle accuracy simulator for network behavior.Due to the combination of such coarse-grained and finegrained simulation methods,the simulator gives out simulation results fast and accurately.The application mapping algorithm proposed in this paper is evaluated by the simulator.Comparing with the existing mapping algorithm with XY routing algorithm,the simulation results show that the proposed algorithm reduces the average packet latency by 10.1% and the average Manhattan distance by 5.0%.When using the DyXY routing algorithm,the proposed algorithm reduces the average packet Delay by 8.2% and the average Manhattan distance by 4.4%.