Circuit partitioning and trace assignment in circuit design

• US 9,038,013 B2
• Filed: 06/03/2013
• Issued: 05/19/2015
• 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:
  US13/908,732
• Publication Number:
  US 20130268905A1
• Time in Patent Office: 715 Days
• Field of Search: 716/129, 716/130, 716/131, 716/122, 716/123, 716/124, 716/125, 716/132, 703/16
• US Class Current: 716/129
• 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 circuit design are described. In one embodiment, the method comprises determining a distribution of nets of a circuit, the distribution of the nets comprising numbers of blocks that each of the nets has in each of a plurality of partitions of the circuit in a partitioning solution, moving a first block of the circuit from a source partition to a destination partition to modify the partitioning solution, and updating the distribution of the nets after the moving.

Claims

1. A method for circuit design implemented on a computer upon receipt of a circuit description, the method comprising:

determining, using a processor, a distribution of nets of the circuit, the distribution comprising an array of values representing numbers of blocks that each of the nets has in each of a plurality of partitions of the circuit in a partitioning solution;

moving a first block of the circuit from a source partition to a destination partition to modify the partitioning solution, wherein said moving further comprises

determining whether a transition between 0 blocks and 1 block occurs in one or more of the source partition and the destination partition, wherein when the transition occurs, a first capacity of a source group of a net in the distribution of nets that is coupled to the first block is decreased by one and/or a second capacity of a destination group of the net in the distribution of nets that is coupled to the first block is increased by one; and

updating, based on the moving the first block, the array of values to represent the numbers of blocks that each of the nets has in each of the plurality of partitions of the circuit in the modified partitioning solution.

2. The method as in claim 1, further comprising:

updating a trace assignment solution based on the array of values.

3. The method as in claim 1, further comprising:

determining assignments of nets in one or more net groups, including the destination group of the net in the distribution of nets, to traces in one or more trace groups according to a flow from each net group through a path.

4. The method as in claim 3, the determining assignments of nets further comprising:

determining each possible matching between each net group and a corresponding trace group;

determining the flow from the net groups to the trace groups based on each possible matching, capacities of the net groups, and capacities of the trace groups.

5. The method as in claim 4, wherein the determining the flow uses minimizing/maximizing techniques.

6. The method as in claim 1, further comprising:

using a capacity of the destination group in an incremental flow algorithm to obtain an updated trace assignment solution.

7. The method as in claim 6, wherein the trace assignment solution locates traces on or between one or more Field Programmable Gate Arrays (FPGAs).

8. A non-transitory machine readable medium containing executable computer program instructions which when executed by a digital processing system cause the system to perform a method for circuit design upon receipt of a circuit description, the method comprising:

determining a distribution of nets of the circuit, the distribution comprising an array of values representing numbers of blocks that each of the nets has in each of a plurality of partitions of the circuit in a partitioning solution;

moving a first block of the circuit from a source partition to a destination partition to modify the partitioning solution, wherein said moving further comprises

determining whether a transition between 0 blocks and 1 block occurs in one or more of the source partition and the destination partition, wherein when the transition occurs, a first capacity of a source group of a net in the distribution of nets that is coupled to the first block is decreased by one and/or a second capacity of a destination group of the net in the distribution of nets that is coupled to the first block is increased by one; and

updating, based on the moving the first block, the array of values to represent the numbers of blocks that each of the nets has in each of the plurality of partitions of the circuit in the modified partitioning solution.

9. The non-transitory machine readable medium of claim 8, further comprising:

updating a trace assignment solution based on the array of values.

10. The non-transitory machine readable medium of claim 8, further comprising:

determining assignments of nets in one or more net groups, including the destination group of the net in the distribution of nets, to traces in one or more trace groups according to a flow from each net group through a path.

11. The non-transitory machine readable medium of claim 10, the determining assignments of nets further comprising:

determining each possible matching between each net group and a corresponding trace group;

determining the flow from the net groups to the trace groups based on each possible matching, capacities of the net groups, and capacities of the trace groups.

12. The non-transitory machine readable medium of claim 11, wherein the determining the flow uses minimizing/maximizing techniques.

13. The non-transitory machine readable medium of claim 8, wherein the method further comprises:

using the capacity of the destination group in incremental flow algorithms to obtain a trace assignment solution.

14. The non-transitory machine readable medium of claim 13, wherein the trace assignment solution locates traces on or between one or more Field Programmable Gate Arrays (FPGAs).

15. A data processing system for circuit design and emulation, the data processing system comprising:

a memory; and

a processor coupled to the memory, wherein the processor is configured to, upon receipt of a circuit description, determine a distribution of nets of the circuit, the distribution comprising an array of values representing numbers of blocks that each of the nets has in each of a plurality of partitions of the circuit in a partitioning solution;

wherein the processor is configured to move a first block of the circuit from a source partition to a destination partition to modify the partitioning solution, said moving further comprises determining whether a transition between 0 blocks and 1 block occurs in one or more of the source partition and the destination partition, wherein when the transition occurs, the processor is configured to decrease a first capacity of a source group of a net in the distribution of nets that is coupled to the first block by one and/or the processor is configured to increase a second capacity of a destination group of the net in the distribution of nets that is coupled to the first block by one, the processor configured to update, based on the moving the first block, the array of values to represent the numbers of blocks that each of the nets has in each of the plurality of partitions of the circuit in the modified partitioning solution.

16. The data processing system of claim 15, wherein the processor is further configured to update a trace assignment solution based on the array of values.

17. The data processing system of claim 15, wherein the processor is further configured to determine assignments of nets in one or more net groups, including the destination group of the net in the distribution of nets, to traces in one or more trace groups according to a flow from each net group through a path.

18. The data processing system of claim 17, wherein the processor is further configured to determine each possible matching between each net group and a corresponding trace group, the processor further configured to determine the flow from the net groups to the trace groups based on each possible matching, capacities of the net groups, and capacities of the trace groups.

19. The data processing system of claim 18, wherein the processor is configured to determine the flow using minimizing/maximizing techniques.

20. The data processing system of claim 15, wherein the processor is further configured to use the capacity of the destination group in incremental flow algorithms to obtain a trace assignment solution.

21. The data processing system of claim 20, wherein traces in the trace assignment solution are on or between one or more Field Programmable Gate Arrays (FPGAs).