International Journal of Intelligent Systems and Applications (IJISA)
IJISA Vol. 8, No. 4, 8 Apr. 2016
Cover page and Table of Contents: PDF (size: 521KB)
Multi-Objective Memetic Algorithm for FPGA Placement Using Parallel Genetic Annealing
Full Text (PDF, 521KB), PP.60-66
Views: 0 Downloads: 0
Author(s)
Praveen T.
1,*
Arun Raj Kumar P.
1
Index Terms
Field Programmable Gate Array (FPGA), Genetic Algorithm (GA), Genetic Annealing (GASA), Parallel Genetic Algorithm (PGA), Simulated Annealing (SA), Non-Dominated Sorting Genetic Algorithm (NSGA-II)
Abstract
Due to advancement in reconfigurable computing, Field Programmable Gate Array (FPGA) has gained significance due to its low cost and fast prototyping. Parallelism, specialization, and hardware level adaptation, are the key features of reconfigurable computing. FPGA is a programmable chip that can be configured or reconfigured by the designer, to implement any digital circuit. One major challenge in FPGA design is the Placement problem. In this placement phase, the logic functions are assigned to specific cells of the circuit. The quality of the placement of the logic blocks determines the overall performance of the logic implemented in the circuits. The Placement of FPGA is a Multi-Objective Optimization problem that primarily involves minimization of three or more objective functions. In this paper, we propose a novel strategy to solve the FPGA placement problem using Non-dominated Sorting Genetic Algorithm (NSGA-II) and Simulated Annealing technique. Experiments were conducted in Multicore Processors and metrics such as CPU time were measured to test the efficiency of the proposed algorithm. From the experimental results, it is evident that the proposed algorithm reduces the CPU consumption time to an average of 15% as compared to the Genetic Algorithm, 12% as compared to the Simulated Annealing, and approximately 6% as compared to the Genetic Annealing algorithm.
Cite This Paper
Praveen T., Arun Raj Kumar P., "Multi-Objective Memetic Algorithm for FPGA Placement Using Parallel Genetic Annealing", International Journal of Intelligent Systems and Applications(IJISA), Vol.8, No.4, pp.60-66, 2016. DOI:10.5815/ijisa.2016.04.07
Reference
[1]Sang-Joon Lee and Dr.Kaamran Raahemifar, “FPGA Placement Optimization Methodology Survey”, CCECE 2008.
[2]J.Rose, A.ElGamal, A.Sangiovanni Vincentelli, "Architecture of field programmable gate arrays", Proc. of the IEEE, vol. 81, no. 7, July 1993.
[3]Zoltan Baruch, Octavian Creţ, And Horia Giurgiu, “Genetic Algorithm for FPGA Placement”,Computer Science Department, Technical University of Cluj-Napoca
[4]Peter Jamieson, “Exploring Inevitable Convergence for a Genetic Algorithm Persistent FPGA Placer”, Oxford, OH, 45056.
[5]Siva NageswaraRaoBorra A. Muthukaruppan S. Suresh V.Kamakoti, “A Parallel Genetic Approach To The Placement Problem For Field Programmable Gate Arrays”, Parallel and Distributed Processing Symposium, 2003. Proceedings. International.
[6]H. Esbensen, P. Mazumder, "SAGA: Unification of genetic algorithm with simulated annealing and its application to macro-cell placement", Proc. of IEEE the Seventh Intl. Conf on VLSI Design,India, 1994.
[7]Yang, Meng, Almaini, A E A, Wang, Lun Yao and Wang, P (2005) FPGA placement using genetic algorithm with simulated annealing. ASICON 2005: Proceedings of the 6th International Conference on ASIC, 2005, 2. pp. 808-811. ISSN 0 7803 9210 8
[8]C.L. Cheng, "RISA: Accurate and Efficient Placement Routability Modeling", Proc. of IEEE/ACM ICCAD, San Jose, Califomia, US, 1994
[9]Alexander Choong, Rami Beidas, Jianwen Zhu,”Parallelizing Simulated Annealing-Based Placement using GPGPU”, International Conference on Field Programmable Logic and Applications, 2010.
[10]Kalyanmoy Deb, Associate Member, IEEE,AmritPratap, Sameer Agarwal, and T. Meyarivan,”A Fast and Elitist Multiobjective Genetic Algorithm: NSGA-II.”, IEEE Transactions on Evolutionary Computation, Vol. 6, No. 2, April 2002
[11]V. Betz and J. Rose, "VPR: A New Packing, Placement and Routing Tool for FPGA Research," Seventh International Workshop on Field-Programmable Logic and Applications, 1997.
[12]Kalyanmoy Deb, Prateek Jain, Naveen Gupta, HemantMaji, Kanpur Genetic Algorithm Laboratory, IIT Kanpur, “Multi-Objective Placement of Electronic Components Using Evolutionary Algorithms”.
[13]Mingjie Lin and John Wawrzynek,”Improving FPGA Placement with Dynamically Adaptive Stochastic Tunneling”, IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2010.
[14]Maeda, Y., Fuzzy Adaptive Search Method for Genetic Programming, International Journal of Advanced Computational Intelligence, Vol.3, No.2, 1999.
[15]Lee., M.A. and Takagi., H., Dynamic Control of Genetic Algorithms Using Fuzzy Logic Techniques,Proc. of 5th International Conference on Genetic Algorithms (ICGA’93),1993.
[16]Maeda, Y., A Method for Improving Search performance of GA with Fuzzy Rules, Proc. of the 6th Intelligent System symposium, Vol.3,1996.
[17]Kleinhans, J.M., Sigl, G., Johannes, F.M., Antreich, K.J, (March 1991). "GORDIAN: VLSI placement by quadratic programming and slicing optimization". IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems 10.
[18]Kahng, A.B, Qinke Wang; (May 2005). "Implementation and extensibility of an analytic placer". IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems 24 (5).
[19]Akoglu, Ali. Application specific reconfigurable architecture design methodology. Arizona State University, 2005.
[20]Gudise, Venu G., and Ganesh K. Venayagamoorthy. "FPGA placement and routing using particle swarm optimization." VLSI, 2004. Proceedings. IEEE Computer society Annual Symposium on. IEEE, 2004.
[21]Chin Hau Hoo, Kumar Akash, Yajun Ha, “ParaLaR: A parallel FPGA router based on Lagrangian relaxation”, 25th IEEE International Conference on Field Programmable Logic and Applications, 2015, pp. 1-6.