VLSI Placement Algorithm Based On Genetic And Simulated Annealing Algorithm

With the dramatic increase in the complexity of very large scale integrated circuits (VLSI), people have proposed higher standards for the modules'placement problem. However, artificial design has been far from meeting the demands of this problem, so automatic layout design is becoming more and more important in the role of computer-aided design. The modules'placement problem of VLSI is an NP-complete problem and many heuristic algorithms have been developed to solve it. Now the problem has been widely and deeply studied, and many efficient algorithms are available, such as the genetic algorithm and the simulation annealing algorithm, etc. But the placement quality of those algorithms is not very satisfactory, especially when this question includes some constraints, such as boundary constraints, obstacles or soft modules, the layout result's "area" or "length breadth ratio" is bad. This problem is still one of the most challenging problems in VLSI.In this paper, we propose a new placement algorithm based on the existing tradition's simulation annealing and genetic algorithm. The new algorithm represents each placement topology by a sequence-pair, and it can solve the modules'placement problem successfully. In order to verify the effectiveness of the new algorithm, our experiment uses several standard examples of MCNC and two randomly generated module sets as experimental data. After a series of tests, the results show that our algorithm has a big advantage in placement quality.