VLSI placement and area optimization using a genetic algorithm to breed normalized postfix expressions
Tóm tắt
We present a genetic algorithm (GA) that uses a slicing tree construction process for the placement and area optimization of soft modules in very large scale integration floorplan design. We have overcome the serious representational problems usually associated with encoding slicing floorplans into GAs and have obtained excellent (often optimal) results for module sets with up to 100 rectangles. The slicing tree construction process used by our GA to generate the floorplans has a runtime scaling of O(n lg n). This compares very favorably with other recent approaches based on nonslicing floorplans that require much longer runtimes. We demonstrate that our GA outperforms a simulated annealing implementation with the same representation and mutation operators as the GA.
Từ khóa
#Genetic algorithms #Very large scale integration #Shape #Encoding #Runtime #Simulated annealing #Binary trees #Computer science #Flexible printed circuits #Modular constructionTài liệu tham khảo
oliver, 1987, a study of permutation crossover operators on the traveling salesman problem, Proc Second Int Conf Genetic Algorithms, 224
pan, 1995, area minimization for floorplans, IEEE Trans on Computer-Aided Design, 14, 123, 10.1109/43.363119
10.1109/GLSV.1994.290002
schnecke, 1995, genetic design of vlsi-layouts, Proceedings of 1st International Conference on Genetic Algorithms in Engineering Systems Innovations and Applications, 430
stockmeyer, 1983, optimal orientations of cells in slicing floorplan designs, information, and control, Inform Control, 57, 91, 10.1016/S0019-9958(83)80038-2
syswerda, 1989, uniform crossover in genetic algorithms, Proc Third Int Conf Genetic Algorithms, 2
valenzuela, 2000, a genetic algorithm for vlsi floorplanning, Parallel Problem Solving in Nature VI, 1917, 671, 10.1007/3-540-45356-3_66
valenzuela, 2001, breeding normalized postfix expressions for the facility layout problem, Proc Fourth Metaheuristic Int Conf, 261
10.1109/43.149770
wong, 1988, Simulated Annealing for VLSI Design, 10.1007/978-1-4613-1677-0
garces-perez, 1996, solving facility layout problems using genetic programming, Proc 1st Annu Conf Genetic Programming, 182
10.1016/0377-2217(95)00029-P
kirkpatrick, 1983, optimization by simulated annealing, Science, 220, 671, 10.1126/science.220.4598.671
kado, 1995, a study of genetic algorithm hybrids for facility layout problems, Proc 7th Int Conf Genetic Algorithms, 498
nakatake, 1995, rectangle-packing-based module placement, Proc IEEE Int Conf Computer‐ Aided Design, 143
murata, 1998, sequence-pair based placement method for hard/soft /pre-placed modules, Proc Int Symp Physical Design, 167
cohoon, 1991, distributed genetic algorithms for the floorplan design problem, IEEE Trans on Computer-Aided Design, 10, 483, 10.1109/43.75631
10.1109/ICCAD.1996.569870
cavicchio, 1970, Adaptive search using simulated evolution
10.1016/S0167-9260(97)00014-X
10.1109/ASPDAC.1999.759699
10.1109/ICCAD.1998.144275
young, 1999, slicing floorplans with range constraints, Proc Int Symp Physical Design, 97