Evolutionary Meta-Heuristic Routing Algorithm for Network on Chip

Abstract

As the number of cores on a single chip increases with each generation of CMOS technology, Network on Chip has become a new System on Chip paradigm. In this thesis, a latency optimized routing algorithm for Network on Chip (NoC) is presented. The algorithm proposed, is called as Ant System based Routing Algorithm for Network on Chip (ASRA). Proposed algorithm is based on Ant Colony Optimization (ACO) meta-heuristic algorithm. ACO algorithms are widely proven as preferred routing algorithm in telecommunication network. ACO algorithms are used in solving Travelling Salesmen Problem (TSP). Various Ant algorithms that are used to solve TSP were analyzed in MATLAB and then travelling salesmen problem is mapped with routing algorithm in network on chip. Two algorithms that had proven best results for TSP are modified to provide routing in NoC and simulated in MATLAB. Performance of ASRA is evaluated by simulating a 2D mesh based system with well-known synthetic traffic patterns and Embedded application traffic types by using NoC Tweak simulator. The results show that ASRA reduces the latency of the network compared to XY and odd-even algorithms even in high flit injection rate with non-uniform traffic patterns.