Abstract

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.

Keywords:

Dijkstra algorithm, dynamic programming, K-step look ahead, network-on-chip,

References

1. Abraham, I., A. Fiat, A.V. Goldberg and R.F.F. Werneck, 2012. Highway dimension, shortest paths and provably efficient algorithms. Proceeding of ACM-SIAM Symposium on Discrete Algorithms, pp: 782-793.
   PMid:23044577    
2. Ascia, G., V. Catania, M. Palesi and D. Patti, 2008. Implementation and analysis of a new selection strategy for adaptive routing in networks-on-chip. IEEE T. Comput., 57(6): 809-820.
   CrossRef    
3. Bellman, R., 1957. Dynamic Programming. Princeton University Press, Princeton, NJ.
   
4. Biswas, S.S., B. Alam and M.N. Doja, 2013. Generalization of Dijkstra's algorithm for extraction of shortest paths in directed multigraphs. J. Comput. Sci., 9(3): 377-382.
   CrossRef    
5. Cherkassky, B.V., A.V. Goldberg and T. Radzik, 1996. Shortest paths algorithms: Theory and experimental evaluation. Math. Program., 73(2): 129-174.
   CrossRef    
6. Dally, W. and B. Towles, 2004. Principles and Practices of Interconnection Networks. Morgan Kaufmann, San Mateo, CA.
   PMCid:PMC1810099    
7. Kroger, M., 2005. Shortest multiple disconnected path for the analysis of entanglements in two-and three-dimensional polymeric systems. Comput. Phys. Commun., 168: 209-232.
   CrossRef    
8. Lai, D.T., A. Shilton, E. Charry, R. Begg and M. Palaniswami, 2009. A machine learning approach to k-step look-ahead prediction of gait variables from acceleration data. Proceeding of the 31st Annual International Conference of the IEEE Engineering in Medicine and Biology Society, 2009: 384-387.
   CrossRef    
9. Mak, T., K.P. Lam, H.S. Ng and G. Rachmuth, 2010. A CMOS current-mode dynamic programming circuit. IEEE T. Circuits Syst., 57(12): 3112-3123.
   CrossRef    
10. Mak, T., P.Y.K. Cheung, K.P. Lam and W. Luk, 2011. Adaptive routing in network-on-chips using a dynamic-programming network. IEEE T. Ind. Electron., 58(8): 3701-3716.
    CrossRef    
11. Mak, T.S.T., P. Sedcole, P.Y.K. Cheung and W. Luk, 2007. A hybrid analog-digital routing network for NoC dynamic routing. Proceeding of 1st International Symposium Networks-on-Chip (NOCS, 2007), pp: 173-182.
    CrossRef    
12. Miskiewicz, J., 2010. Analysis of time series correlation. the choice of distance metrics and network structure. Proceeding of the 5th Symposium on Physics in Economics and Social Sciences. Warszawa, Poland.
    PMCid:PMC4360321    
13. Noxim, 2008. Network-on-Chip Simulator. Retrieved form: http://sourceforge.net/projects/noxim.
    Direct Link
14. Sergey, I., J. Midtgaard and D. Clarke, 2012. Calculating graph algorithms for dominance and shortest path. In: Gibbons, J. and P. Nogueira (Eds.), MPC 2012. LNCS 7342, Springer-Verlag, Berlin, Heidelberg, pp: 132-156.
    CrossRef    
15. Wang, Z. and J. Crowcroft, 1992. Analysis of shortest-path routing algorithms in a dynamic network environment. ACM Comput. Commun. Rev., 22(2): 63-71.
    CrossRef    
16. Zuo, Y., Z. Ling and Y. Yuan, 2013. A hybrid multi-path routing algorithm for industrial wireless mesh networks. EURASIP J. Wirel. Comm., 2013: 82.
    CrossRef    

Competing interests

The authors have no competing interests.

Open Access Policy

This article is distributed under the terms of the Creative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/), which permits unrestricted use, distribution, and reproduction in any medium, provided you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons license, and indicate if changes were made.

Copyright

The authors have no competing interests.