Application of simulated annealing to cluster-boundary search algorithm for macrocell placement optimization

This paper presents a hybrid technique for macrocell placement optimization. The presented technique integrates the probabilistic hill-climbing feature of simulated annealing with the (deterministic) cluster-boundary search algorithm in order to minimize the likelihood of local optimal solutions. It optimizes the placement as well as orientation of macrocells and produces overlap-free designs satisfying constraints on interconnect length bounds. The technique is computationally efficient and can generate high-quality solutions for large-sized placement problems. Test results for placement optimization problems involving up to 100 macrocells are presented and analyzed to determine the effectiveness of the presented hybrid technique.