Hybrid Adaptive Routing in Network-on-chips Using KLSA with Dijkstra Algorithm

摘要

The aim of this study is to analyse dynamic programming in large scale, complex networks is more important in the fields of scientific and engineering. Recent applications needs the analysis of scale-free networks with many millions of nodes and edges; presenting a huge computational challenge. Employing distributed networks on-chip infrastructure presents a unique opportunity of delivering power efficient and massive parallel accelerations. Dynamic Programming (DP) network is a massive parallel and high throughput network architecture, which provides real-time computation for shortest path problems. This network combines with the NoC to enable optimal traffic control based on the online network status and, provides optimal path planning and dynamic routing with proposed novel routing mechanics heuristic K-Step Look Ahead (KLSA) in deadlock free architecture. K-step look ahead routing algorithm based calculating the Manhattan distance has some disadvantages and it affects the overall performance of the routing algorithm. In order to overcome aforementioned disadvantages of manhattan distance and improving the efficiency of K-step looks ahead algorithm proposing a dijkstra algorithm for calculating the distance between two nodes. Here in implementation, the results are compared with existing routing schemas or algorithms like XY, DyAD, odd-even, odd-even routing with an NoP selection scheme. The DP network presents a simple, reliable and efficient methodology to enable adaptive routing in NoCs.