US5699265A — Physical design automation system and process for…

Claim 1

Independent Claim 123 words

A process for designing an integrated circuit chip, comprising the steps of: (a) specifying a set of cells and a set of wiring nets for interconnecting the cells; (b) specifying a set of regions on the chip in which the cells are to be placed; (c) generating an assignment of the cells of the set to the regions; (d) randomly dividing the set of cells into a first subset of cells which remain in the assignment, and a second subset of cells which are removed from the assignment; (e) computing penalties for assigning the cells of the second subset to the regions respectively; and (f) assigning the cells of the second subset to the regions such that a total penalty thereof is minimized.

Claim 2

Dependent Claim 123 words

A process for designing an integrated circuit chip, comprising the steps of: (a) specifying a set of cells and a set of wiring nets for interconnecting the cells; (b) specifying a set of regions on the chip in which the cells are to be placed; (c) generating an assignment of the cells of the set to the regions; (d) randomly dividing the set of cells into a first subset of cells which remain in the assignment, and a second subset of cells which are removed from the assignment; (e) computing penalties for assigning the cells of the second subset to the regions respectively; and (f) assigning the cells of the second subset to the regions such that a total penalty thereof is minimized.

Claim 3

Dependent Claim 47 words

A process as in claim 1, further comprising the step, performed before step (c), of: (g) specifying capacities of the regions for containing cells respectively; in which step (f) comprises assigning the cells of the second subset to the regions such that the capacities are not exceeded.

Claim 4

Dependent Claim 79 words

A process as in claim 2, further comprising the step, performed between steps (d) and (e), of: (h) computing modified capacities for the regions from which the cells of the second subset were removed as being equal to the capacities specified in step (g) minus the sizes of the cells that were removed in step (d); in which step (f) comprises assigning the cells of the second subset to the regions such that the modified capacities are not exceeded.

Claim 5

Dependent Claim 49 words

A process as in claim 1, further comprising the steps, performed after step (f), of: (g) determining if an end criterion has been reached; (h) if the end criterion has been reached, terminating the process; and (i) if the end criterion has not been reached, jumping to step (d).

Claim 6

Dependent Claim 37 words

A process as in claim 4, further comprising the step, performed between steps (i) and (d), of: (j) reducing a number of cells of the second subset relative to a number of cells of the first subset.

Claim 7

Dependent Claim 29 words

A process as in claim 5, in which the end criterion is such that the number of cells of the second subset has been reduced below a predetermined value.

Claim 8

Dependent Claim 146 words

A process as in claim 4, further comprising the step, performed between steps (i) and (d), of: (j) determining if step (i) has been performed a predetermined number of times without reducing a number of cells of the second subset relative to a number of cells of the first subset; (k) if step (i) has not been performed a predetermined number of times without reducing the number of cells of the second subset relative to the number of cells of the first subset, jumping directly to step (d); and (l) if step (i) has been performed a predetermined number of times without reducing a number of cells of the second subset relative to a number of cells of the first subset, reducing the number of cells of the second subset relative to the number of cells of the first subset and then jumping to step (d).

Claim 9

Dependent Claim 30 words

A process as in claim 1, in which step (e) comprises computing the penalties as wirelengths of all of the nets connected to the cells of the second set respectively.

Claim 10

Dependent Claim 33 words

A process as in claim 1, in which step (f) further comprises computing the total penalty as a total wirelength of all of the nets connected to the cells of the second set.

Claim 11

Dependent Claim 84 words

A process as in claim 1, in which step (f) comprises the substeps of: (g) constructing an initial assignment of the cells of the second subset to the regions; (h) selecting a number of cells of the second subset for movement between the regions; (i) computing an optimal permutation of movement of the selected number of cells between the regions such that the total penalty is minimized; and (j) modifying the initial assignment by moving the selected number of cells through the optimal permutation.

Claim 12

Dependent Claim 24 words

A process as in claim 10, in which step (i) comprises computing the optimal permutation as starting and ending in one of the regions.

Claim 13

Dependent Claim 154 words

A programmed digital computer for designing an integrated circuit chip, comprising: memory means for storing a program including instructions and data; and processing means for executing the program; the processing means, memory means and program operating in combination for performing the steps of: (a) specifying a set of cells and a set of wiring nets for interconnecting the cells; (b) specifying a set of regions on the chip in which the cells are to be placed; (c) generating an assignment of the cells of the set to the regions; (d) randomly dividing the set of cells into a first subset of cells which remain in the assignment, and a second subset of cells which are removed from the assignment; (e) computing penalties for assigning the cells of the second subset to the regions respectively; and (f) assigning the cells of the second subset to the regions such that a total penalty thereof is minimized.

Claim 14

Dependent Claim 154 words

A programmed digital computer for designing an integrated circuit chip, comprising: memory means for storing a program including instructions and data; and processing means for executing the program; the processing means, memory means and program operating in combination for performing the steps of: (a) specifying a set of cells and a set of wiring nets for interconnecting the cells; (b) specifying a set of regions on the chip in which the cells are to be placed; (c) generating an assignment of the cells of the set to the regions; (d) randomly dividing the set of cells into a first subset of cells which remain in the assignment, and a second subset of cells which are removed from the assignment; (e) computing penalties for assigning the cells of the second subset to the regions respectively; and (f) assigning the cells of the second subset to the regions such that a total penalty thereof is minimized.

Claim 15

Dependent Claim 61 words

A programmed digital computer as in claim 12, in which the processing means, memory means and program further operate in combination to perform the step, before step (c), of: (g) specifying capacities of the regions for containing cells respectively; in which step (f) comprises assigning the cells of the second subset to the regions such that the capacities are not exceeded.

Claim 16

Dependent Claim 93 words

A programmed digital computer as in claim 13, in which the processing means, memory means and program further operate in combination to perform the step, between steps (d) and (e), of: (h) computing modified capacities for the regions from which the cells of the second subset were removed as being equal to the capacities specified in step (g) minus the sizes of the cells that were removed in step (d); in which step (f) comprises assigning the cells of the second subset to the regions such that the modified capacities are not exceeded.

Claim 17

Dependent Claim 62 words

A programmed digital computer as in claim 12, in which the processing means, memory means and program further operate in combination to perform the steps, after step (f), of: (g) determining if an end criterion has been reached; (h) if the end criterion has been reached, terminating operation; and (i) if the end criterion has not been reached, jumping to step (d).

Claim 18

Dependent Claim 51 words

A programmed digital computer as in claim 15, in which the processing means, memory means and program further operate in combination to perform the step, between steps (i) and (d), of: (j) reducing a number of cells of the second subset relative to a number of cells of the first subset.

Claim 19

Dependent Claim 31 words

A programmed digital computer as in claim 16, in which the end criterion is such that the number of cells of the second subset has been reduced below a predetermined value.

Claim 20

Dependent Claim 160 words

A programmed digital computer as in claim 15, in which the processing means, memory means and program further operate in combination to perform the steps, between steps (i) and (d), of: (j) determining if step (i) has been performed a predetermined number of times without reducing a number of cells of the second subset relative to a number of cells of the first subset; (k) if step (i) has not been performed a predetermined number of times without reducing the number of cells of the second subset relative to the number of cells of the first subset, jumping directly to step (d); and (l) if step (i) has been performed a predetermined number of times without reducing a number of cells of the second subset relative to a number of cells of the first subset, reducing the number of cells of the second subset relative to the number of cells of the first subset and then jumping to step (d).

Claim 21

Dependent Claim 32 words

A programmed digital computer as in claim 12, in which step (e) comprises computing the penalties as wirelengths of all of the nets connected to the cells of the second set respectively.

Claim 22

Dependent Claim 34 words

A programmed digital computer as in claim 12, in which step (f) comprises computing the total penalty as a total wirelength of all of the nets connected to the cells of the second set.

Claim 23

Dependent Claim 86 words

A programmed digital computer as in claim 12, in which step (f) comprises the substeps of: (g) constructing an initial assignment of the cells of the second subset to the regions; (h) selecting a number of cells of the second subset for movement between the regions; (i) computing an optimal permutation of movement of the selected number of cells between the regions such that the total penalty is minimized; and (j) modifying the initial assignment by moving the selected number of cells through the optimal permutation.

Claim 24

Dependent Claim 26 words

A programmed digital computer as in claim 21, in which step (i) comprises computing the optimal permutation as starting and ending in one of the regions.

Annuity Stage	Window Opens	Payment Deadline	Surcharge Period Until	Estimated Fee	Status
3.5 Years (Year 4)	2000-12-15	2001-06-16	2001-12-16	$2000.00	Window Closed / Lapsed
7.5 Years (Year 8)	2004-12-15	2005-06-16	2005-12-16	$3760.00	Window Closed / Lapsed
11.5 Years (Year 12)	2008-12-15	2009-06-16	2009-12-16	$7700.00	Window Closed / Lapsed

Physical design automation system and process for designing integrated circuit chips using multiway partitioning with constraints

Abstract

Inventors

Bibliographic Details

Claims Analysis

References Cited (Backward Citations)

USPTO Annuity & Maintenance Windows

Assigned Categories & Tags

Assign Category Tag