New Ant Colony Algorithm Method based on Mutation for FPGA Placement Problem

محورهای موضوعی : مهندسی هوشمند برق

Setareh Shafaghi ¹ (Electrical Engineering Department, Central Tehran Branch, Islamic Azad University,)
Fardad Farokhi ² (Electrical Engineering Department, Central Tehran Branch, Islamic Azad University,)
Reza Sabbaghi-Nadooshan ³ (Electrical Engineering Department, Central Tehran Branch, Islamic Azad University,)

تاریخ دریافت : 1394/01/24 تاریخ پذیرش : 1394/01/24 تاریخ انتشار : 1392/09/10

کلید واژه: Optimization, Ant Colony Algorithm, Mutation, FPGA placement,

چکیده مقاله :

Many real world problems can be modelled as an optimization problem. Evolutionary algorithms are used to solve these problems. Ant colony algorithm is a class of evolutionary algorithms that have been inspired of some specific ants looking for food in the nature. These ants leave trail pheromone on the ground to mark good ways that can be followed by other members of the group. Ant colony optimization uses a similar mechanism to solve the optimization problem. Usually the main difficulties of evolutionary algorithm for solving the optimization problem are: early convergence, loss of population diversity, and placing in a local minimum .Therefore, it needs the way that preserves the variation and tries to avoid trapping in local minimum. In this paper by combining ant colony algorithm and mutation hybrid algorithms that leads to the better solution for optimization of FPGA (Field Programmable Gate Array) placement problem is made. They are different types of swarm intelligence algorithm. After designing the algorithm, its parameters tuning have been done by solving several problems, and then the proposed methods have been compared with the other approaches. The results show that in most problems, the proposed hybrid method is able to obtain better solutions and makes fewer errors.

منابع و مأخذ:

[1]

B. Premalatha and S. Umamaheswari “survey of online hardware task scheduling and placement algorithm for partially reconfigurable computing systems” International Journal of computing and Corporate Research, Vol.2, Issie.3, 2012.

[2]

E. M .Vasconcelos de Lima, A. C. Cavalcanti and L. dos Anjos Formiga Cabral, “A New Approach to VPR Tool’s FPGA Placement”, Proceedings of the World Congress on Engineering and Computer Science (WCECS), 2007.

[3]

M. Yang, A.E.A. Almaini, L. Wang and P.J .Wang, “FPGA Placement Using Genetic Algorithm with Simulated Annealing”, 6th international conference on ASIC, Vol.2, pp.808-810, 2005.

[4]

V. Chopra, and A. Singh, “Solving FPGA Routing using Ant Colony Optimization with Minimum CPU Time” International Journal of Computer Science & Technology (IJCST), Vol.2,

Issue.4, pp.223-226, 2011.

[5]

X. Shi, “FPGA Placement Methodologies: A Survey” Dept. of Computing Science, University of Alberta, 2009.

[6]

X. Wenyao, K. Xu and X. Xinmin, “A Novel Placement Algorithm for Symmetrical FPGA” Institute of Electronic Circuit and Information System, Zhejiang University”, 7th international conference, IEEE press, pp. 1281- 1284, 2007.

[7]

S. J .Lee and K. Raahemifar, “FPGA Placement Optimization Methodology Survey”, Canadian Conference on Electrical and Computer Engineering (CCECE), pp.001981- 001986, 2008.

[8]

M. Dorigo and T. Stützle, “Ant Colony Optimization”,2nd edition, Vol.146, In International Series in Operations Research and Management Science, pp.227-263, Springer Verlag, NewYork, 2010.

[9]

K.E Parsopoulos and M.N. Vrahatis. “Particle Swarm Optimization and Intelligence: Advances and Applications”, IGI Global: Hershey, PA, 2010.

[10]

K. Wang, N Xu, “Ant Colony Optimization for Symmetrical FPGA Placement”, 11th IEEE international conference on Computer Aided Design and Computer Graphics, pp.561-563, 2009.

[11] M. Dorigo, M. Zlochin, N. Meuleau and M. Birattari. "Updating ACO pheromones using stochastic gradient and cross-entropy methods." In Applications of Evolutionary Computing, Springer Berlin Heidelberg, pp.21-30, 2002.

[12]

M. Dorigo, G. Di Caro and L. M. Gambardella, “Ant algorithms for discrete optimization”, Artificial life 5, No.2, pp.137-172, 1999.

[13] F. Ducatelle, “Adaptive routing in ad hoc wireless multi-hop networks”, Universita della Svizzera italiana, Lugano, Switzerland, 2007.

[14]

M. Shokouhifar, Sh. Sabet, “PMACO: A Pheromone-Mutation based Ant Colony Optimization for Traveling Salesman Problem”, International Symposium on Innovations in Intelligent Systems and Applications (INISTA), 2012.

[15]

Z. Baruch, O. Creţ, H. Giurgiu, “Genetic Algorithm for FPGA Placement”, In Proceedings of the 12th International Conference on Control Systems and Computer Science (CSCS12), Vol. 2, pp.121-126, 1999.

[16]

M. Dorigo and G. Caro, “The Ant Colony Optimization Meta-Heuristic”, Universit e Libre de Bruxelles.

[17] www.cse.wustl.edu/~jain/cse567-08/ftp/fpga/

[18]

S. Yang, “Logic Synthesis and Optimization Benchmarks User Guide Version 3.0”, 1991.

[19] www.datasheetcatalog.org/datasheets/400/287785_DS.pdf.

[20]

P.K .Rout and D.P. Acharya, “Novel PSO based FPGA Placement Techniques”, International Conference on Computer & Communication Technology (ICCCT’10), pp.630-634, 2010.

[21]

P.K .Rout, D.P Acharya and G. Panda, “Digital Circuit Placement in FPGA based on Efficient Particle Swarm Optimization Techniques”, 5th International Conference on Industrial and Information Systems, pp.224-227, 2010