Abstract：A hybrid genetic simulated annealing algorithm is presented for solving the problem of VLSI standard cell placement with up to millions of cells. Firstly, to make genetic algorithm be capable of handling very large scale of standard cell placement, the strategies of small size population, dynamic updating population, and crossover localization are adopted, and the global search and local search of genetic algorithm are coordinated. Then, by introducing hill climbing (HC) and simulated annealing (SA) into the framework of genetic algorithm and the internal procedure of its operators, an effective crossover operator named Net Cycle Crossover and local search algorithms for the placement problem are designed to further improve the evolutionary efficiency of the algorithm and the quality of its placement results. In the algorithm procedure, HC method and SA method focus on array placement and non-array placement respectively. The experimental results on Peko suite3, Peko suite4 and ISPD04 benchmark circuits show that the proposed algorithm can handle array and non-array placements with 10,000~1,600,000 cells and 10,000~210,000 cells respectively, and can effectively improve the quality of placement results in a reasonable running time.
[1] Tamilarasi A, Anantha Kumar T. An Enhanced Genetic Algorithm with Simulated Annealing for Job-Shop Scheduling. International Journal of Engineering, Science and Technology, 2010, 2(1): 144-151 [2] Nagata Y, Kobayashi S. A Powerful Genetic Algorithm Using Edge Assembly Crossover for the Traveling Salesman Problem. INFORMS Journal on Computing, 2013, 25(2): 346-363 [3] Baghel M, Agrawal S, Silakari S. Survey of Metaheuristic Algorithms for Combinatorial Optimization. International Journal of Computer Applications, 2012, 58(19): 21-31 [4] Guo W Z, Chen G L, Xiong N, et al. Hybrid Particle Swarm Optimization Algorithm for VLSI Circuit Partitioning. Journal of Software, 2011, 22(5): 833-842 (in Chinese) (郭文忠,陈国龙, Xiong Naixu,等.求解VLSI电路划分问题的混合粒子群优化算法.软件学报, 2011, 22(5): 833-842) [5] Kaur J, Kaur M. A Survey on Various Genetic Approaches for Standard Cell Placement. International Journal of Computer Technology and Applications, 2013, 4(3): 533-536 [6] Suman B, Kumar P. A Survey of Simulated Annealing as a Tool for Single and Multiobjective Optimization. Journal of the Operational Research Society, 2006, 57(10): 1143-1160 [7] Chen J L, Zhu W X, Ali M M. A Hybrid Simulated Annealing Algorithm for Nonslicing VLSI Floorplanning. IEEE Trans on Systems, Man, and Cybernetics, Part C: Applications and Reviews, 2011, 41(4): 544-553 [8] Chen J L, Zhu W X, Peng Z. A Heuristic Algorithm for the Strip Packing Problem. Journal of Heuristics, 2012, 18(4): 677-697 [9] Bunglowala A, Singhi B, Verma A. Multi-objective Optimization of Standard Cell Placement Using Memetic Algorithm. International Journal of Computer Applications, 2011, 19(7): 31-34 [10] Tang M L, Yao X. A Memetic Algorithm for VLSI Floorplanning. IEEE Trans on Systems, Man, and Cybernetics, Part B: Cybernetics, 2007, 37(1): 62-69 [11] Markov I L, Jin H, Kim M C. Progress and Challenges in VLSI Placement Research // Proc of the IEEE/ACM International Conference on Computer-Aided Design. San Jose, USA, 2012: 275-282 [12] Chopra V, Singh A. Multi-objective Genetic Algorithm for Testing MCNC FPGA Benchmark Circuits. International Journal of Computer Science and Communication Engineering, 2013, 2(1): 74-78 [13] Wang L T, Chang Y W, Cheng K T. Electronic Design Automation: Synthesis, Verification, and Test. San Francisco, USA: Morgan Kaufmann, 2009 [14] Khawam S, Nousias I, Milward M, et al. The Reconfigurable Instruction Cell Array. IEEE Trans on Very Large Scale Integration (VLSI) Systems, 2008, 16(1): 75-85 [15] Li K. Placement & Constrained Placement Optimization in VLSI Physical Design. Ph.D. Dissertation. Chengdu, China: University of Electronic Science and Technology of China, 2010 (in Chinese) (李 康.VLSI物理设计中布局及有约束的布局优化.博士学位论文.成都:电子科技大学, 2010) [16] Chen J L, Zhu W X. An Analytical Placer for VLSI Standard Cell Placement. IEEE Trans on Computer-Aided Design of Integrated Circuits and Systems, 2012, 31(8): 1208-1221 [17] Chang Y W, Jiang Z W, Chen T C. Essential Issues in Analytical Placement Algorithms. IPSJ Trans on System LSI Design Methodology , 2009, 2: 145-166 [18] Pattanaik S, Bhoi S P, Mohanty R. Simulated Annealing Based Placement Algorithms and Research Challenges: A Survey. Journal of Global Research in Computer Science, 2012, 3(6): 33-37 [19] Garcia-Martínez C, Lozano M. Local Search Based on Genetic Algorithms // Siarry P, Michalewicz Z, eds. Advances in Metaheuristics for Hard Optimization. Berlin, Germany: Springer, 2008: 199-221 [20] Kim M C, Viswanathan N, Alpert C J, et al. MAPLE: Multilevel Adaptive Placement for Mixed-size Designs // Proc of the ACM International Symposium on Physical Design. Napa, USA, 2012: 193-200 [21] Subbaraj P, Sankar S S, Anand S. Parallel Genetic Algorithm for VLSI Standard Cell Placement // Proc of the International Conference on Advances in Computing, Control, and Telecommunication Technologies. Trivandrum, India, 2009: 80-84 [22] Chang C C, Xie M. PEKO Suite (Placement Example with Known Optimal Wire Length) [EB/OL]. [2013-03-20]. http://cadlab.cs.ucla.edu/~pubbench/placement/dw.htm [23] Viswanathan N, Chu C. ISPD04 IBM Standard Cell Benchmarks with Pads [EB/OL]. [2013-03-20]. http://vlsicad.eecs.umich.edu/BK/Slots/cache/www.public.iastate.edu/~nataraj/ISPD04_Bench.html
2014, Vol. 27 
