Method and apparatus for circuit partitioning and trace assignment in circuit design

• US 8,176,452 B2
• Filed: 11/09/2010
• Issued: 05/08/2012
• Est. Priority Date: 03/04/2003
• Status: Active Grant

• Current Assignee: Synopsys Incorporated
• Original Assignee: Synopsys Incorporated
• Inventors: Pandey, Awartika, Borkovic, Drazen, McElvain, Kenneth S.
• Primary Examiner(s): Kik, Phallaka
• Application Number:
  US12/942,961
• Publication Number:
  US 20110055792A1
• Time in Patent Office: 546 Days
• Field of Search: 716/105, 716/106, 716/113, 716/122, 716/123, 716/129, 716/130, 716/132, 703/16
• US Class Current: 716/105
• 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 machine implemented method for designing at least one integrated circuit (IC), the method comprising:

partitioning a circuit design into portions which represent a partitioning solution;

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

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

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

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

4. The machine implemented method as in claim 3, wherein the design parameter is a cost function;

the cost function increases as a number of unassigned nets that cannot be assigned to the 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.

5. The machine implemented method as in claim 2, wherein the design parameter is a cost function;

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

6. The machine implemented 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. The machine implemented 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 a first one of the modification candidates based on the gains; and

performing the first one of the modification candidates selected.

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

partitioning a circuit design into portions which represent a partitioning solution;

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

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

9. The non-transitory machine readable medium as in claim 8, wherein the optimizing is through a modification to both the partitioning solution and the trace assignment solution.

10. The non-transitory machine readable medium as in claim 9, wherein the design parameter is further based on the partitioning solution.

11. The non-transitory machine readable medium as in claim 10, wherein the design parameter is a cost function;

the cost function increases as a number of unassigned nets that cannot be assigned to the 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.

12. The non-transitory machine readable medium as in claim 9, wherein the design parameter is a cost function;

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

13. The non-transitory machine readable 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 a first one of the modification candidates based on the gains; and

performing the first one of the modification candidates selected.

14. The non-transitory machine readable 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.

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

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

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

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

16. The 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. The data processing system as in claim 16, wherein the design parameter is further based on the partitioning solution.

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

the cost function increases as a number of unassigned nets that cannot be assigned to the 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.

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

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

20. The 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. The 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 a first one of the modification candidates based on the gains; and

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