Study On Load-Balanced Routing Algorithm Of NoC

Compared with traditional communicate architecture based on bus, network on chip(NoC) has potential of efficient parallel communication. However, with the expanding of the NoC scale and the increasing of application complexity, network confliction becomes more complex. Traditional dimension-order routing may lead to unbalanced network load distribution. Nodes which are overloaded for a long time may become network "hotspots", and cause stability problem. On the other hand, if some links are always occupied, it may cause partial congestion, where communication flows can’t be transmitted in time,and lead to excessive network latency.Focusing on these problems, this thesis studies a load-balanced routing algorithm based on monitoring mechanism, which can balance global load of network and reduce network latency. The thesis mainly includes the following work:(1) A load-balanced routing algorithm based on monitor mechanism is designed.According to the monitoring results of historical traffic within a certain period of time of every node, an appropriate rout that has the lighter load globally from source node to target node is allocated for target flow.In the presence of the load-balanced routing algorithm for NoC, target flow can keep away from the overloaded nodes and transmit packets through nodes that bear lighter load in the past time. Compared to the original NoC, load of the node with the highest traffic can be reduced by 30%.(2) A delay-reduced and load-balanced routing algorithm is designed.For a given application,according to the linear superposed parameter of congest and load, an appropriate rout that has the lighter load globally as well as smaller delay is allocated for target flow.This routing algorithm can not only balance load of network, but also reduce transmit delay of the flows, and improve the network performance. Compared to the original NoC, delay optimization of NoC with this routing algorithm is up to 56% when packet and flow length are both 4, and 19% when packet length is 4 and flow length is 128.Transmit delay is reduced by 35% when number of conflict flow is 2 and 55% when number of conflict flow is 10.