(An) implementation of floorplanner using simulated annealing

Abstract

The automatic placement becomes more and more important in Computer Aided Design (CAD) as the integrated-circuit density increases. However, the placement problem has been known NP-complete, and thus several heuristic algorithms have been developed. In this thesis, the simulated annealing algorithm, a general-purpose method of combinatorial optimization problem, is applied to the following placement problems, i.e., fixed grid placement, rigid random block placement and printed circuit boards placement. For each of these problems, the generation method of a new configuration, the definition of a cost function and the control philosophies of various parameters, which are considered on applying the algorithm, are presented and their effects to the convergence of the algorithm are analyzed.