(Jim Peterman, 1988)
ASIC is an acronym for Application Specific Integrated Circuit. A good way do visualize an ASIC is to imagine condensing all of the components on a printed circuit board or boards onto a single chip. Several design methodologies exist in achieving this end, among them are a) Full custom layout, b) Gate arrays, and c) Standard cells. This paper focuses on standard cells which allow greater flexibility than gate arrays with a design cycle time a fraction of what is required for a full custom layout.
A standard cell is the geometric realization. of an electrical function constrained to have a fixed height but variable width. ``Ports" or the electrical tie points of the cell are situated along the top and bottom boundary of the cell. Rows of cells placed side by side constitute a ``cell placement." A ``net" is an electrical connection between two or more cells. The terms ``net" and ``cell" will be used extensively in this paper.
The objective of a cell placement algorithm is to legally arrange an arbitrarily large (200-100000 gates) group of standard cells in such a way as to minimize total bar area, wire length and signal propagation delays all in a time frame proportional to gate count. The combinatorial nature of this problem presents major obstacles in achieving all these objectives. Cluster placement attempts to satisfy the objective functions by first reducing the effective gate count (over an order of magnitude) by clustering cells, then placing the clusters using a minimal wire length cost function. Clusters of cells are formed utilizing several intelligent heuristics. The clusters are placed and optimized using a ``mean center of gravity" placement technique. The clusters are then replaced by their constituent standard cells. Finally, the resultant placement is locally optimized.
Several new standard cell placement techniques have been proposed over the last five years I among them simulated annealing and min-cut have drawn considerable attention. Simulated annealing (S.A.) is essentially a Monte Carlo technique that has been shown to yield results near optimal with the drawback of the immense amounts of CPU time required. Min-cut performs faster, but has not proven to be as effective as S.A. in producing near optimal placements. This paper describes a new method of cell placement that achieves results comparable to simulated annealing using less CPU time than the faster min-cut algorithms. There are no existing software packages that address the problem of automatic placement of macro blocks. This paper proposes a method of forming macro blocks into ``clusters", then allowing five possible locations on the chip for the placement of macro block ``clusters".