Efficient and effective placement for very large circuits

Abstract

We present two major extensions to the implementation of simulated annealing for row-based placement which have enabled it to obtain the best results ever reported for a large set of MCNC benchmark circuits while using the least computation time ever reported for remotely comparable results. Our results indicate that chip area reductions up to 16% can be expected, compared with TimberWolfSC v6.0. Our new hierarchical annealing-based placement program yields total wire length reductions of up to 9% while consuming up to 7.5 times less CPU time in comparison to TimberWolfSC v6.0. In comparison to the Gordian/Domino program, our new program yields total wire lengths which are always lower (up to 9% lower) and our program is always faster for circuits with more than 5000 cells (which represents the range of circuit sizes of interest).