18.1 INTRODUCTION

Force-directed methods have been studied over the past four decades as a means of placing cells. These methods employ forces to move cells into positions of shorter wirelength or smaller delay. The use of forces was borne out of the physical analogy with Hooke s law in which cells connected by nets can be viewed as exerting attractive spring forces on one another. If the cells in such a system could move freely, they would move in the direction of their forces until the system achieved equilibrium at a minimum energy state. Unfortunately, a minimum energy placement is most often not valid as cells have physical dimensions that are ignored in the spring analogy. Consequently, additional repulsive forces are applied to perturb the cell positions and remove overlap. Force-directed methods, in general, purge cell overlap over many placement iterations, while trading off attractive and repulsive forces to achieve a placement in which cells are placed with little overlap. For example, the progress made by a force-directed placer on circuit IBM04 from the ICCAD04 mixed-size placement benchmark suite [1] is illustrated in Figure 18.1.

Figure 18.1: Typical progression of a force-directed placement method for the circuit IBM04 from the ICCAD04 mixed-size placement benchmark suite: (a) initial placement, (b) after roughly 1/3 through placement, (c) after roughly 2/3 through placement, and (d) before legalization and detailed improvement. The fairly nonoverlapping placement before legalization is obtained without the use of partitioning.

Force-directed methods differ from...