Theory and Practice of VLSI Placement

Abstract

Placement is a crucial step in the design process of VLSI chips as it has a strong influence on the most important optimization goals, e.g., die size, routability, and cycle time. State-of-the-art logic chips consist of several millions of modules (circuits) that have to be placed, so efficient automated tools are mandatory for that task. In this thesis, we describe new ideas for VLSI placement that are combined in the placement tool BonnPlace which has been used by IBM Microelectronis for the design of many challenging logic chips. <br /> From a very global point of view, BonnPlace consists of three parts: a macro placement phase in which the largest circuits are placed, a global placement phase in which the remaining circuits are spread over the chip area, and a legalization phase in which all overlaps between the circuits are removed and all technological constraints are met. <br /> As we follow a recursive top-down partitioning approach for global placement, we have to distribute several times a (possibly large) set of circuits to a small number of regions. This motivates the consideration of the Transportation Problem which is an uncapacitated minimum cost flow problem on a bipartite graph where one side of the bipartition contains all supply nodes and the other side all demand nodes. We present a new algorithm that solves this problem to optimality in time O(nk²(log n + k log k)) where n and k are the numbers of elements in the two sides of the bipartition. This improves the fastest previously known algorithm on the instances we are interested in. Our global placement algorithm makes use of the transportation algorithm in several ways when assigning circuits to subregions of the chip area. As the transportation algorithm is fast in practice and much more flexibel than previous approaches, it helps improving both running time and quality of result of BonnPlace.<br /> For the legalization phase, we propose a new method that allows to find a legal placement with a very small total circuit movement. The approach is mainly based on a new minimum-cost flow formulation. We can show that our minimum-cost flow formulation is best possible in a natural, well-defined way. Moreover, we can compare our results to lower bounds that we compute by solving a relaxation of an integer linear program formulation of the legalization problem. Our experiments demonstrate that at least on instances where the given placement was spread out well enough, the circuit movement in our legalization is quite close to the optimum. <br /> Our algorithms for global placement and legalization are together a complete placement tool that could be applied to any VLSI placement instance. However, the global placer is mainly designed for instances consisting of a large number of small circuits. On instances with bigger objects (macros) it may produce weak results. Hence, BonnPlace contains a new and more sophisticated approach to macro placement. BonnPlace first divides all bigger macros into small fragments and places the fragments together with the remaining circuits. This way, we compute desired locations for all macros, and then a branch-and-bound algorithm is applied to place the macros disjointly close to their desired locations. <br /> Another contribution of this thesis is a framework for congestion-driven placement. This method enables BonnPlace to detect routability problems in an early phase of the global placement process and to solve them by adjusting the placement density locally. <br /> Experiments that compare our placement tool as a whole to previous approaches conclude this thesis. We use artificial benchmarks and real-word chips for these experiments showing that BonnPlace is arguably one of the most effective and efficient placement tools.