Guided Local Search for Final Placement in VLSI Design

The design of a VLSI circuit consists of two main parts: First, the logical functionality of the circuit is described, and then the physical layout of the modules and connections is settled. In the latter process one wishes to place the modules such that the necessary wiring becomes as small as possible in order to minimize area usage and delays on signal paths. The placement problem is the subproblem of the layout problem which considers the geometric locations of the modules. A new heuristic is presented for the general cell placement problem where the objective is to minimize total bounding box netlength. The heuristic is based on the Guided Local Search (GLS) metaheuristic. GLS modifies the objective function in a constructive way to escape local minima. Previous attempts to use local search on final (or detailed) placement problems have often failed as the neighbourhood quickly becomes too excessive for large circuits. Nevertheless, by combining GLS with Fast Local Search it is possible to focus the search on appropriate sub-neighbourhoods, thus reducing the time complexity considerably. Comprehensive computational experiments with the developed algorithm are reported on a broad range of industrial circuits. The experiments demonstrate that the developed algorithm is able to improve the estimated routing length of large-sized layouts with as much as 20 percent when compared to existing algorithms.