An efficient history-based routing algorithm for interconnection networks

Network-on-chip (NoC) approach has been proposed as a solution to the complex on-chip communication problems by scaling down the concepts of macro- and tele-networks, and applying them to the system-on-chip domain. In this paper, an efficient routing algorithm for two-dimensional mesh network-on-chips is presented. The algorithm, which is based on Odd-Even turn model, is called History-Based Odd-Even (HB-OE). It is more fair and efficient in load balancing compared to the typical Odd-Even turn model algorithm. In this routing, based on the location of the current node, the network is divided into four sub-networks and the history of each sub-network regarding the direction of the last forwarded packet is saved using a flag register. We further enhance this routing by using a technique named Free-Channel to check the availability of the output ports as well as their history. To assess the latency of the proposed algorithm, transpose traffic profile for packet injection is used. The simulation results reveal that the HB-OE + Free-Channel routing policy can achieve lower latency compared to the conventional Odd-Even turn model with negligible area overhead.