Circuit block placement using simulated annealing

Abstract

Three classes of placement algorithms for gate array, standard cell and macro cell were implemented using simulated annealing which is one of combinatorial the optimization methods, and the effects of several parameters such as the number of inner loop and the ratio of weights on the final results were investigated. Overall, it was confirmed through wide experimental results that simulated annealing has proven to give consistently good quality layouts. A new constructive placement algorithm called ``Constrained Clustering Placement (CCP)`` was proposed to solve placement problems in a very short time. The results of this algorithm were shown to be comparable to those of the classical methods such as FDR (Force Directed Relaxation) and Min-Cut, while the computation time needed in CCP was much shorter, so that this algorithm can be used as a good initial placement for simulated annealing. By using CCP as initial placement rather than random placement in simulated annealing, we were able to save around 30% of computation time.