Guided Local Search for Final Placement in VLSI design

A new heuristic is presented for the general cell placementproblem where the objective is to minimize total bounding boxnetlength. The heuristic is based on the Guided Local Search(GLS) metaheuristic. GLS modifies the objective function in aconstructive way to escape local minima. Previous attempts touse local search on final (or detailed) placement problems haveoften failed as the neighborhood quickly becomes too exces-sive for large circuits. Nevertheless, by combining GLS withFast Local Search it is possible to focus the search on appro-priate sub-neighborhoods, thus reducing the time complexityconsiderably.Comprehensive computational experiments with the devel-oped algorithm are reported on small, medium and large in-dustrial circuits, and for standard cell and general cell variantsof the problem. The experiments demonstrate that the devel-oped algorithm is able to improve the estimated routing lengthof large-sized general cell layouts with as much as 20 percent.The general nature of the proposed method makes it easyto incorporate other goals, such as routability and timing con-straints, into the objective function. Current layout algorithmsuse a feedback approach in which a placement is evaluatedby performing (partial) routing and timing analysis; the outputof this analysis is then used to construct an improved place-ment. This iterative nature of the design process calls forplacement algorithms that take an existingplacement and con-struct an improved placement that resembles the original one,but in which the information from the routing/timing analysisis taken into account