FPGA PLACEMENT OPTIMIZATION BY TWO-STEP UNIFIED GENETIC ALGORITHM AND SIMULATED ANNEALING ALGORITHM  

作　　者：Yang Meng A.E.A. Almaini Wang Pengjun 

机构地区：[1]School of Engineering, Napier University, 10 Colinton Road.Edinburgh, EH10 5DT, UK [2]State Key Lab of ASIC ＆ System, Microelectronics Dept, Fudan University, Shanghai 201203, China [3]Institute of Circuits and Systems, Ningbo University, Ningbo 315211. China

出　　处：《Journal of Electronics(China)》2006年第4期632-636,共5页电子科学学刊（英文版）

基　　金：Supported by School of Engineering, Napier University, United Kingdom, and partially supported by the National Natural Science Foundation of China (No.60273093).

摘　　要：Genetic Algorithm (GA) is a biologically inspired technique and widely used to solve numerous combinational optimization problems. It works on a population of individuals, not just one single solution. As a result, it avoids converging to the local optimum. However, it takes too much CPU time in the late process of GA. On the other hand, in the late process Simulated Annealing (SA) converges faster than GA but it is easily trapped to local optimum. In this letter, a useful method that unifies GA and SA is introduced, which utilizes the advantage of the global search ability of GA and fast convergence of SA. The experimental results show that the proposed algorithm outperforms GA in terms of CPU time without degradation of performance. It also achieves highly comparable placement cost compared to the state-of-the-art results obtained by Versatile Place and Route (VPR) Tool.Genetic Algorithm （GA） is a biologically inspired technique and widely used to solve numerous combinational optimization problems. It works on a population of individuals, not just one single solution. As a result, it avoids converging to the local optimum. However, it takes too much CPU time in the late process of GA. On the other hand, in the late process Simulated Annealing （SA） converges faster than GA but it is easily trapped to local optimum. In this letter, a useful method that unifies GA and SA is introduced, which utilizes the advantage of the global search ability of GA and fast convergence of SA. The experimental results show that the proposed algorithm outperforms GA in terms of CPU time without degradation of performance. It also achieves highly comparable placement cost compared to the state-of-the-art results obtained by Versatile Place and Route （VPR） Tool.

关 键 词：Genetic Algorithm （GA） Simulated Annealing （SA） PLACEMENT FPGA EDA 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]