# US 5,349,536 A · Method for optimally placing components of a VLSI circuit > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 5,349,536 A - Document ID: US5349536A - Status: Granted - Kind: A - Application number: 07/747,542 - Filed: 1991-08-20 - Granted: 1994-09-20 - Earliest claimed: 1991-08-20 - Assignees: VLSI Technology, Inc. - Inventors: Sunil V. Ashtaputre; Dale M. Wong - Web page: https://patentgrep.com/patent/US5349536A ## CPC - G06F 30/392: Floor-planning or layout, e.g. partitioning or placement - G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N) ## 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. ## Claims ### Claim 1 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. ### Claim 2 (depends on 1) A method as in claim 1 wherein in step (b) the partial performance of the greedy optimization performed is a single pass through a greedy optimization algorithm in which for each pass, the following substeps are performed for each component: determining, based on a local cost metric, a best location for the component; and, moving the component to the best location when doing so improves a current value for the global cost metric. ### Claim 3 (depends on 2) A method as in claim 2 wherein in step (a) the initial number is approximately equal to a total number of components in the circuit and in step (c) approximately half the current placements are selected to be the new current placements. ### Claim 4 (depends on 2) A method as in claim 2 wherein in step (a) the initial number is significantly less than a total number of components in the circuit and in step (c) a percentage of the current placements are selected to be the new current placements, the percentage increasing when the number of current placements decreases. ### Claim 5 (depends on 4) A method as in claim 4 wherein in step (e) the optimization performed is a completion of the greedy optimization performed in step (b). ### Claim 6 (depends on 2) A method as in claim 2 wherein in step (e) the optimization performed is a completion of the greedy optimization performed in step (b). ### Claim 7 (depends on 2) A method as in claim 2 wherein the global cost metric is based on total length of all connection lines of the circuit. ### Claim 8 (depends on 7) A method as in claim 7 wherein the local cost metric is based on total length of all connection lines connected to the component. ### Claim 9 (depends on 1) A method as in claim 1 wherein in step (a) the initial number is approximately equal to a total number of components in the circuit and in step (c) approximately half the current placements are selected to be the new current placements. ### Claim 10 (depends on 1) A method as in claim 1 wherein in step (a) the initial number is significantly less than a total number of components in the circuit and in step (c) a percentage of the current placements are selected to be the new current placements, the percentage increasing when the number of current placements decreases. ### Claim 11 (depends on 1) A method as in claim 1 wherein in step (e) the optimization performed is a completion of the greedy optimization performed in step (b). ### Claim 12 (depends on 1) A method as in claim 1 wherein the global cost metric is based on total length of connection lines for the circuit. ### Claim 13 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. ### Claim 14 (depends on 13) A computer implemented method as in claim 13 wherein in step (b) the partial performance of the greedy optimization performed is a single pass through a greedy optimization algorithm in which for each pass, the following substeps are performed for each component; determining, based on a local cost metric, a best location for the component; and, moving the component to the best location when doing so improves a current value for the global cost metric. ### Claim 15 (depends on 14) A computer implemented method as in claim 14 wherein in step (a) the initial number is approximately equal to a total number of components in the circuit and in step (c) approximately half the current placements are selected to be the new current placements. ### Claim 16 (depends on 14) A computer implemented method as in claim 14 wherein in step (a) the initial number is significantly less than a total number of components in the circuit and in step (c) a percentage of the current placements are selected to be the new current placements, the percentage increasing when the number of current placements decreases. ### Claim 17 (depends on 14) A computer implemented method as in claim 14 wherein in step (e) the optimization performed is a completion of the greedy optimization performed in step (b). ### Claim 18 (depends on 14) A computer implemented method as in claim 14 wherein the local cost metric is based on total length of all connection lines connected to the component. ### Claim 19 (depends on 13) A computer implemented method as in claim 13 wherein in step (a) the initial number is approximately equal to a total number of components in the circuit and in step (c) approximately half the current placements are selected to be the new current placements. ### Claim 20 (depends on 12) A computer implemented method as in claim 12 wherein in step (a) the initial number is significantly less than a total number of components in the circuit and in step (c) a percentage of the current placements are selected to be the new current placements, the percentage increasing when the number of current placements decreases.