Adaptive cluster growth (ACG); a new algorithm for circuit packing in rectilinear region

A new algorithm for circuit packing (or detailed placement) in any rectilinear region called adaptive cluster growth (ACG) is described in analogy to the growth of a low-stress crystal in a cavity of any given shape. ACG is an algorithm suitable for packing of circuit modules, either standard cell or macro cell, in a rectilinear region by refining the result of global placement obtained by such techniques as force-directed relaxation or force and cut placement. The overlaps among modules or overlaps between any module and chip boundary are removed in ACG in such a way that the estimation of the total routing length is kept as low as possible. An experiment with standard cell circuits in benchmark data has shown that AGG outperforms or performs dose to other packing techniques. Examples are shown to demonstrate the packing of standard cell circuits in arbitrary-shaped regions. An efficient tiling scheme for representing the rectilinear-shaped cluster and region boundary is also described