The week's pick
Reseach Article
Ant System for Routing in FPGA
| International Journal of Computer Applications |
| Foundation of Computer Science (FCS), NY, USA |
| Volume 130 - Number 15 |
| Year of Publication: 2015 |
| Authors: Pawan Kumar Dahiya, J.S. Saini, Shakti Kumar |
10.5120/ijca2015907169
|
Pawan Kumar Dahiya, J.S. Saini, Shakti Kumar . Ant System for Routing in FPGA. International Journal of Computer Applications. 130, 15 ( November 2015), 1-6. DOI=10.5120/ijca2015907169
Abstract
Routing of arbitrary placed blocks has been a long prevailing objective in any circuit in VLSI. In FPGA, the routing problem becomes more complex due to its fixed routing resources. An efficient routing algorithm tries to reduce the lengths of critical-path nets and also the congestion in the channel to improve the performance of the circuit. This paper presents an Ant System based approach, based on the intelligent behavior of ants, for the routing problem in FPGA. It is observed that the results after some iterations, converge towards the optimal solution at a better rate than other comparable techniques.
References
- K. Roy-Neogi and C. Sechen, “Multiple FPGA Partitioning with Performance Optimization,” Proceedings of the 3rd International ACM Symposium on Field-Programmable Gate Arrays, pp. 1-7, 1995.
- Pinaki Mazumdar and E.M. Rudnik, Genetic Algorithm for VLSI Design, Layout and Test Automation. Delhi: Pearson Education, 2003.
- P. Thomson and J.F. Miller, “Optimisation Techniques based on the use of Genetic Algorithms (GAS) for Logic Implementation on FPGAs,” The Institution of Electrical Engineers, pp. 411-414, 1994.
- G.K. Venayagamoorthy and V.G. Gudise, “Swarm Intelligence for Digital Circuits Implementation on Field Programmable Gate Arrays Platforms,” Proceedings of the NASA/DoD Conference on Evolvable Hardware (EH’04), pp. 1-4, 2004.
- Yee Leung, Guo Li, and Zong-Ben Xu, “A Genetic Algorithm for the Multiple Destination Routing Problems,” IEEE Transactions on Evolutionary Computation, Vol. 2, No. 4, pp. 150-161, 1998.
- M. Nakao and K. Izumi, “Circuit Designs and Fabrication of Swarm-Intelligence LSIs based on Modeling Foraging Behaviors of Ants,” The 47th IEEE International Midwest Symposium on Circuits and Systems, IEEE (0-7803-8346-X/04), pp. 97-100, 2004.
- Shakti, Kumar, J.S. Saini and Pawan Dahiya, “GAs for Routing in VLSI,” Proceedings of International Conference on Intelligent System and Networks, ISTK, Jagadhri, pp. 20-25, 2008.
- D. G. Prado and M. Ciesielski, “A Tutorial on FPGA Routing,” Dept. of Electrical and Computer Engg., University of Massachussets, pp.1-16.
- Russell G. Tessier , “Fast Place and Route Approaches for FPGAs,” Ph.D. thesis, Massachussets Institue of Technology, 1999.
- V.K. Jayaraman et.al., “Ant colony framework for optimal design and scheduling of batch plants” Computers and Chemical Engineering-24, pp. 1901-1912, 2000.
- J. E. Bell and P. R. McMullen, “Ant colony optimization techniques for the vehicle routing problem,” Advanced Engineering Informatics-18, pp. 41–48, 2004.
- K. M. Sim and W. H. Sun, “Ant colony optimization for routing and load-balancing: survey and new directions,” IEEE Transactions on Systems, Man, And Cybernetics—Part A: Systems and Humans, Vol. 33, No. 5, pp. 560-572, 2003.
- Marco Dorigo et.al., “Ant system: optimization by a colony of cooperating agents” IEEE Transactions on Systems, Man, And Cybernetics-Part B: Cybernetics, Vol. 26, No. 1, pp. 29-31, 1996.
- Marco Dorigo et.al., “Ant colony system: A cooperative learning approach to the traveling salesman problem,” IEEE Transactions on Evolutionary Computation, I (1), pp. 53-66, 1997.
- Marco Dorigo and Thomas Stutzle, Ant Colony Optimization. New Delhi: Prentice-Hall of India, 2005.
- Pawan Dahiya, J. S. Saini, and Shakti Kumar, “PSO for Routing Problem in VLSI,” International Conference on Intelligent Systems & Networks (ISN-2008), 2008.
- Pawan Dahiya, J. S. Saini, and Shakti Kumar, “Evolutionary Trends in VLSI Design,” Proc. of International Conference on Intelligent Systems & Networks (IISN-2007), 2007.
- Pawan Kumar Dahiya, “Recent Trends in Evolutionary Computation,” Ph.D. dissertation, ECE Dept., M. D. Univ., Rohtak, Haryana, India, 2011.
- Vineet Chaudhary, Parveen Kumar Yadav, and Pawan Kumar Dahiya, “Evaluation of cost optimization for travelling salesman problem (TSP) by comparing various ant colony optimization (ACO) algorithms,” International Journal of Computational Engineering & Management, Vol. 15, No. 5, pp. 38-44, 2012.
- Daniel Gomez-Prado Maciej Ciesielski, “A tutorial on FPGArouting,”Availableat:http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.84.9313&rep=rep1&type=pdf.
- John E. Bella, Patrick R. McMullen, “Ant colony optimization techniques for the vehicle routing problem,” Advanced Engineering Informatics 18, pp. 41–48,2004.
Index Terms
Keywords