Method for placement of circuit components in an integrated circuit

• US 5,208,759 A
• Filed: 12/13/1990
• Issued: 05/04/1993
• Est. Priority Date: 12/13/1990
• Status: Expired due to Fees

• Current Assignee: VLSI Technology, Inc. (Koninklijke Philips N.V.)
• Original Assignee: VLSI Technology, Inc. (Koninklijke Philips N.V.)
• Inventors: Wong, Dale M.
• Primary Examiner(s): Smith, Jerry
• Assistant Examiner(s): TRAMMELL, JAMES P
• Application Number:
  US07/626,816
• Time in Patent Office: 873 Days
• Field of Search: 364/468, 364/488-491, 364/480
• US Class Current: 716/135
• CPC Class Codes: G06F 30/392 Floor-planning or layout, e.g. partitioning or placement

Abstract

In a method for optimizing placement of circuit components on at least one integrated circuit, a list of circuit components is constructed. For each pairing of circuit components on the list, a total cost of the pairing is calculated. The total cost being calculated by first calculating the dead space resulting from the pairing, then estimating the total increase in routing area resulting from the pairing, and finally adding the dead space to the total increase in routing area to obtain the total cost. The estimation of the total increase in routing area resulting from the pairing is done by first estimating an increase in connectivity area resulting from the pairing. Then, a decrease in connectivity area resulting from the pairing is estimated. Finally, the decrease in connectivity area is subtracted from the increase in connectivity area to obtain the total increase in routing area.

Claims

1. A method for optimizing placement of circuit components on at least one integrated circuit, the method comprising the steps of:

(a) constructing a list of circuit components;

(b) while there is more than one circuit component on the list, determining an order for merging circuit components on the list, the determining including the following substeps;

(b1) for each pairing of circuit components on the list, calculating a total cost of the pairing, the total cost being calculated by

calculating the dead space resulting from the pairing,

estimating the total increase in routing area resulting from the pairing, and

adding the dead space to the total increase in routing area to obtain the total cost;

(b2) for a first pairing with a lowest total cost as calculated in step (b1),

merging first circuit components which form the first pairing into a new circuit component,

removing the first circuit components from the list, and

adding the new circuit component to the list; and

,

(c) based on the order for merging determined in step (b), placing the circuit components on the at least one integrated circuit.

2. A method as in claim 1, wherein step (c) includes the following substeps:

(c1) constructing a merge tree based on the order for merging determined in step (b); and

(c2) traversing the merge tree to place the circuit components on the at least one integrated circuit.

3. A method for optimizing placement of circuit components on at least one integrated circuit, the method comprising the steps of:

(a) constructing a list of circuit components;

(b) while there is more than one circuit component on the list, determining an order for merging circuit components on the list, the determining including the following substeps

(b1) for each pairing of circuit components on the list, calculating a total cost of the pairing, the total cost being calculated by

calculating the dead space resulting from the pairing,

estimating the total increase in routing area resulting from the pairing, including

estimating an increase in connectivity area resulting from the pairing,

estimating a decrease in connectivity area resulting from the pairing, and

subtracting the decrease in connectivity area from the increase in connectivity area to obtain the total increase in routing area, and

adding the dead space to the total increase in routing area to obtain the total cost,

(b2) for a first pairing with a lowest total cost as calculated in step (b1),

merging first circuit components which form the first pairing into a new circuit component,

removing the first circuit components from the list, and

adding the new circuit component to the list; and

,

(c) based on the order for merging determined in step (b), placing the circuit components on the at least one integrated circuit.

4. A method as in claim 3 wherein estimating the total increase in routing area includes:

estimating an average length of a connection line routed within the pairing; and

,

producing an estimate of the total increase in routing area by multiplying the estimated average length times a width of the connection line times a number of connection lines which are connected to a circuit component not within the pairing and are connected to only a single circuit component within the pairing.

5. A method as in claim 4 wherein the average length of a connection line routed within the pairing is estimated to be one quarter of a periphery of a bounded area formed by merging circuit components of the pairing.

6. A method as in claim 4 wherein the average length of a connection line routed within the pairing is estimated to be a square root of a bounding area formed by merging circuit components of the pairing.

7. A method as in claim 3 wherein estimating the total decrease in routing area includes:

estimating an average length of a connection line routed within a first area which is equal to twice a bounded are formed by merging circuit components of the pairing; and

,

producing an estimate of the total decrease in routing area by multiplying the estimated average length times a width of the connection line times a number of connection lines which are connected to both circuit components within the pairing.

8. A method as in claim 7 wherein the average length of a connection line routed within the pairing is estimated to be one quarter of a periphery of the first area.

9. A method as in claim 7 wherein the average length of a connection line routed within the pairing is estimated to be a square root of the first area.

10. A method comprising the steps of:

determining total area cost of a pairing of two circuit components in a plurality of circuit components, including the substeps of

(a) calculating the dead space resulting from the pairing,

(b) estimating the total increase in routing area resulting from the pairing, and

(c) adding the dead space to the total increase in routing area to obtain the total cost; and

placing the plurality of circuit components on at least one integrated circuit.

11. A method comprising the steps of:

determining total area cost of a pairing of two circuit components in a plurality of circuit components, including the substeps of

(a) calculating the dead space resulting from the pairing,

(b) estimating the total increase in routing area resulting from the pairing including the substeps of

(b1) estimating an increase in connectivity area resulting from the pairing,

(b2) estimating a decrease in connectivity area resulting from the pairing, and

(b3) subtracting the decrease in connectivity area from the increase in connectivity area to obtain the total increase in routing area, and

(c) adding the dead space to the total increase in routing area to obtain the total cost; and

,

placing the plurality of circuit components on at least one integrated circuit.

12. A method as in claim 11 wherein substep (b2) includes:

estimating an average length of a connection line routed within a first area which is equal to twice a bounded area formed by merging circuit components of the pairing; and

,

producing an estimate of the total decrease in routing area by multiplying the estimated average length times a width of the connection line times a number of connection lines which are connected to both circuit components within the pairing.

13. A method as in claim 12 wherein the average length of a connection line routed within the pairing is estimated to be one quarter of a periphery of the first area.

14. A method as in claim 12 wherein the average length of a connection line routed within the pairing is estimated to be a square root of the first area.

15. A method comprising the steps of:

determining total area cost of a pairing of two circuit components in a plurality of circuit components, including the substeps of

(a) calculating the dead space resulting from the pairing,

(b) estimating the total increase in routing area resulting from the pairing including the substeps of

(b1) estimating an increase in connectivity area resulting from the pairing including the substeps of

estimating an average length of a connection line routed within the pairing, and

producing an estimate of the total increase in routing area by multiplying the estimated average length times a width of the connection line times a number of connection lines which are connected to a circuit component not within the pairing and are connected to only a single circuit component within the pairing,

(b2) estimating a decrease in connectivity area resulting from the pairing, and

(b3) subtracting the decrease in connectivity area from the increase in connectivity area to obtain the total increase in routing area, and

(c) adding the dead space to the total increase in routing area to obtain the total cost; and

placing the plurality of circuit components on at least one integrated circuit.

16. A method as in claim 15 wherein the average length of a connection line routed within the pairing is estimated to be one quarter of a periphery of a bounded area formed by merging circuit components of the pairing.

17. A method as in claim 15 wherein the average length of a connection line routed within the pairing is estimated to be a square root of a bounding area formed by merging circuit components of the pairing.