Method and Apparatus for Circuit Partitioning and Trace Assignment in Circuit Design

• US 20110055792A1
• Filed: 11/09/2010
• Published: 03/03/2011
• Est. Priority Date: 03/04/2003
• Status: Active Grant

• Current Assignee: Awartika Pandey, Drazen Borkovic, Kenneth S. Mcelvain
• Original Assignee: Awartika Pandey, Drazen Borkovic, Kenneth S. Mcelvain
• Inventors: Pandey, Awartika, McElvain, Kenneth S., Borkovic, Drazen
• Granted Patent: US 8,176,452 B2
• Time in Patent Office: Days
• US Class Current: 716/131
• CPC Class Codes: G06F 30/327 Logic synthesis; Behaviour synthesis, e.g. mapping logic, HDL to netlist, high-level language to RTL or netlist
• CPC Class Codes: G06F 30/392 Floor-planning or layout, e.g. partitioning or placement
• CPC Class Codes: G06F 30/394 Routing G06F30/396 takes precedence

Abstract

Methods and apparatuses for incremental circuit partitioning and incremental trace assignment. In one embodiment of the present invention, a cost function based on both the partitioning solution and the trace assignment solution is used for the partitioning of a circuit; in reducing the cost function, blocks of circuits are moved among partitions and the trace assignment are updated accordingly to evaluate the cost function. In one embodiment, the traces and nets are grouped according to the partitions they connect for trace assignment. In one embodiment, a flow diagram is constructed for assigning nets to traces; and, maximum flow algorithms are used. In one embodiment, a flow diagram includes feedthrough solutions, in which flow conservation is not preserved at certain nodes. In one embodiment, integer linear programming techniques are used for assigning nets to traces. In one embodiment, a distribution of nets, which defines the numbers of blocks that each net has in each partition, is computed and maintained for efficient determination of the number of nets in net groups.

Claims

1. A method for designing at least one integrated circuit (IC), the method comprising:

partitioning a circuit into portions which represent a partitioning solution;

assigning traces to interconnect the portions to generate a trace assignment solution; and

optimizing the circuit through a modification of at least one of the partitioning solution and the trace assignment solution, the optimizing based on evaluating a design parameter which is based at least in part on the trace assignment solution.

2. A method as in claim 1, wherein the optimizing is through a modification to both the partitioning solution and the trace assignment solution.

3. A method as in claim 2, wherein the design parameter is further based on the partitioning solution.

4. A method as in claim 2, wherein the design parameter is a cost function;

and, the cost function increases as a number of nets that cannot be assigned to traces in the trace assignment solution increases.

5. A method as in claim 3, wherein the design parameter is a cost function;

the cost function increases as a number of nets that cannot be assigned to traces in the trace assignment solution increases; and

, the cost function increases as an area of circuits in a partition in the partitioning solution that excesses a threshold increases.

6. A method as in claim 1, wherein the optimizing comprises:

first evaluating the design parameter;

modifying the partitioning solution after the first evaluating the design parameter;

modifying the trace assignment solution after the modifying the partitioning solution;

second evaluating the design parameter after the modifying the trace assignment solution; and

determining if the design parameter is improved through the modifying the partitioning solution and the modifying the trace assignment solution.

7. A method as in claim 6, wherein the optimizing further comprises:

determining gains in the design parameter for a plurality of modification candidates for the partitioning solution;

selecting first one from the modification candidates based on the gains; and

performing the first one selected from the modification candidates.

8. A machine readable medium containing executable computer program instructions which when executed by a digital processing system cause said system to perform a method for designing at least one integrated circuit (IC), the method comprising:

partitioning a circuit into portions which represent a partitioning solution;

assigning traces to interconnect the portions to generate a trace assignment solution; and

optimizing the circuit through a modification of at least one of the partitioning solution and the trace assignment solution, the optimizing based on evaluating a design parameter which is based at least in part on the trace assignment solution.

9. A medium as in claim 8, wherein the optimizing is through a modification to both the partitioning solution and the trace assignment solution.

10. A medium as in claim 9, wherein the design parameter is further based on the partitioning solution.

11. A medium as in claim 9, wherein the design parameter is a cost function;

and, the cost function increases as a number of nets that cannot be assigned to traces in the trace assignment solution increases.

12. A medium as in claim 10, wherein the design parameter is a cost function;

the cost function increases as a number of nets that cannot be assigned to traces in the trace assignment solution increases; and

, the cost function increases as an area of circuits in a partition in the partitioning solution that excesses a threshold increases.

13. A medium as in claim 8, wherein the optimizing comprises:

first evaluating the design parameter;

modifying the partitioning solution after the first evaluating the design parameter;

modifying the trace assignment solution after the modifying the partitioning solution;

second evaluating the design parameter after the modifying the trace assignment solution; and

determining if the design parameter is improved through the modifying the partitioning solution and the modifying the trace assignment solution.

14. A medium as in claim 9, wherein the optimizing further comprises:

determining gains in the design parameter for a plurality of modification candidates for the partitioning solution;

selecting first one from the modification candidates based on the gains; and

performing the first one selected from the modification candidates.

15. A data processing system for designing at least one integrated circuit (IC), the data processing system comprising:

means for partitioning a circuit into portions which represent a partitioning solution;

means for assigning traces to interconnect the portions to generate a trace assignment solution; and

means for optimizing the circuit through a modification of at least one of the partitioning solution and the trace assignment solution, the circuit being optimized based on evaluating a design parameter which is based at least in part on the trace assignment solution.

16. A data processing system as in claim 15, wherein the circuit is optimized through a modification to both the partitioning solution and the trace assignment solution.

17. A data processing system as in claim 16, wherein the design parameter is further based on the partitioning solution.

18. A data processing system as in claim 16, wherein the design parameter is a cost function;

and, the cost function increases as a number of nets that cannot be assigned to traces in the trace assignment solution increases.

19. A data processing system as in claim 17, wherein the design parameter is a cost function;

the cost function increases as a number of nets that cannot be assigned to traces in the trace assignment solution increases; and

, the cost function increases as an area of circuits in a partition in the partitioning solution that excesses a threshold increases.

20. A data processing system as in claim 15, wherein the means for optimizing comprises:

means for first evaluating the design parameter;

means for modifying the partitioning solution after the design parameter is first evaluated;

means for modifying the trace assignment solution after the partitioning solution is modified;

means for second evaluating the design parameter after the trace assignment solution is modified; and

means for determining if the design parameter is improved through modifying the partitioning solution and modifying the trace assignment solution.

21. A data processing system as in claim 20, wherein the means for optimizing further comprises:

means for determining gains in the design parameter for a plurality of modification candidates for the partitioning solution;

means for selecting first one from the modification candidates based on the gains; and

means for performing the first one selected from the modification candidates.