US 5,349,536 AGranted

Method for optimally placing components of a VLSI circuit

AssigneeVLSI Technology, Inc.

InventorsSunil V. Ashtaputre, Dale M. Wong

Life of this patent

Estimating the term…

Loading patent…

Abstract

In a method for placement of components for a VLSI circuit, an initial number of current placements are selected. A greedy optimization is partially performed on each of the current placements. Then, a subset of the current placements which have been partially optimized is selected to be the new current placements. This selection is based on a global cost metric for the current placements. The global cost metric is, for example, based on the total length of all connection line networks for the circuit. The partial optimization and selection are repeated until there is only one current placement. Then, an optimization is performed on the remaining placement to obtain an optimized placement. The optimization is, for example, a completion of the partially performed greedy optimization.

Claims20

Dependent claims

A method comprising the steps of:

(a) selecting an initial number of current placements of components for a VLSI circuit, including, for each of the initial current placements, selecting locations within the VLSI circuit for placement of each of the components;
(b) for each of the current placements, changing locations of the components to improve the current placement so that the current placement is partially optimized in accordance with partial performance of a greedy optimization;
(c) selecting a subset of the current placements partially optimized in step (b) to be new current placements, the selection being based on a global cost metric for the current placements;
(d) when there are more than one new current placements, repeating steps (a) through (d) with the new current placements being the current placements;
(e) when there is only one new current placement, performing an optimization on the new current placement to obtain an optimized placement;
and,
(f) manufacturing the VLSI circuit with the components of the VLSI circuit arranged in accordance with the optimized placement.

4 more elements

A computer implemented method for placement of components for a VLSI circuit, the method comprising the steps, performed by a computer, of:

(a) selecting an initial number of current placements, including for each of the initial current placements selecting locations within the VLSI circuit for placement of each of the components;
(b) for each of the current placements, changing locations of the components to improve the current placement so that the current placement is partially optimized in accordance with partial performance of a greedy optimization;
(c) selecting a subset of the current placements partially optimized in step (b) to be new current placements, the selection being based on a global cost metric for the current placements;
(d) when there are more than one new current placements, repeating steps (a) through (d) with the new current placements being the current placements;
and,
(e) when there is only one new current placement, performing an optimization on the new current placement to obtain an optimized placement.

3 more elements

Dependencies are inferred from the claim text.