Logic equivalence leveraged placement and routing of an IC design

• US 6,477,688 B1
• Filed: 12/22/1999
• Issued: 11/05/2002
• Est. Priority Date: 07/17/1998
• Status: Expired due to Term

• Current Assignee: Mentor Graphics Corporation (Siemens AG)
• Original Assignee: Mentor Graphics Corporation (Siemens AG)
• Inventors: Wallace, David E.
• Primary Examiner(s): Siek, Vuthe
• Assistant Examiner(s): Kik, Phallaka
• Application Number:
  US09/470,086
• Time in Patent Office: 1,049 Days
• Field of Search: 716/1-21
• US Class Current: 716/107
• CPC Class Codes: G06F 30/327 Logic synthesis; Behaviour synthesis, e.g. mapping logic, HDL to netlist, high-level language to RTL or netlist

Abstract

At least one EDA tool is provided with first and second plurality of programming instructions. The first plurality of programming instructions are designed to determine equivalent logic in an IC design, and the second plurality of programming instructions are designed to place and route the IC design. The place and route operation includes performance of at least one place and route operation selected from a group of place and route operations consisting of choosing coupling assignments for nets and logically equivalent input pins of the IC design, and choosing coupling assignments for logically equivalent output pins and loads of the IC design.

Claims

1. A machine implemented IC design method comprising:

(a) determining equivalent logic in an IC design; and

(b) performing place and route operations to place and route the IC design, including performing at least one place and route operation selected from a group of place and route operations consisting of choosing coupling assignments for nets and logically equivalent input pins of the IC design, and choosing coupling assignments for logically equivalent output pins to loads of the IC design.

2. The method of claim 1, wherein said choosing of coupling assignments for nets and logically equivalent input pins comprises choosing coupling assignments for said nets and logically equivalent input pins that minimize aggregate contributions to total wire length of the IC design.

3. The method of claim 2, wherein said choosing of coupling assignments for nets and logically equivalent input pins that minimize aggregate contributions to total wire length of the IC design comprises formulating a bi-partite matching problem for said nets and logically equivalent input pins, assigning weights reflective of wiring lengths to arcs representing candidate coupling assignments between said nets and logically equivalent input pins, and determining a solution to a weighted bipartite matching problem.

4. The method of claim 3, wherein said assignment of weights reflective of wiring lengths to arcs representing candidate coupling assignments between said nets and logically equivalent input pins comprises determining Manhattan distances between drivers of said nets and said logically equivalent input pins.

5. The method of claim 3, wherein said assignment of weights reflective of wiring lengths to arcs representing candidate coupling assignments between said nets and logically equivalent input pins comprises determining Manhattan distances between remainders of said nets and said logically equivalent input pins.

6. The method of claim 2, wherein said choosing of coupling assignments for nets and logically equivalent input pins that minimize aggregate contributions to total wire length of the IC design further comprises assigning penalty cost to selected ones of said arcs representing candidate coupling assignments between said nets and logically equivalent input pins that go through congested areas.

7. The method of claim 1, wherein said choosing of coupling assignments for nets and logically equivalent input pies comprises choosing a set of coupling assignments for a group of nets and a group logically equivalent input pins that minimize total delay time between said group of nets and said group of logically equivalent input pins.

8. The method of claim 7, wherein said choosing of a set of coupling assignments for a group of nets and a group of logically equivalent input pins that minimize total delay time between the group of nets and the group of logically equivalent input pins comprises assigning arrival times to a first set of nodes representing the group of nets, assigning required times to a second set of nodes representing the group of logically equivalent input pins, sorting the first and second set of nodes in accordance with the assigned arrival and required times respectively, and corresponding matching the two sets of nodes.

9. The method of claim 7, wherein said choosing of a set of coupling assignments for a group of nets and a group of logically equivalent input pins that minimize total delay time between the group of nets and the group of logically equivalent input pins comprises formulating a max-min matching problem for the group of nets and the group of logically equivalent input pins, assigning a slack value to each arc representing a candidate coupling assignment for a net and a logically equivalent input pin based on arrival and required times of the net and the logical equivalent input pin, and solving the max-min matching problem.

10. The method of claim 7, wherein said choosing of coupling assignments for nets and logically equivalent input pins further comprises choosing coupling assignments for said nets and logically equivalent input pins that minimize aggregate contributions to total wire length of the IC design, after performing said choosing of a set of coupling assignments for a group of nets and a group logically equivalent input pins that minimize total delay time.

11. The method of claim 1, wherein said choosing of coupling assignments for nets and logically equivalent input pins comprises choosing coupling assignments for said nets and logically equivalent input pins that minimize an interconnect resource consumption cost function.

12. The method of claim 1, wherein said choosing of coupling assignments for logically equivalent output pins and loads comprises choosing coupling assignments for said logically equivalent output pins and said loads that minimize aggregate contributions to total wire length of the IC design.

13. The method of claim 12, wherein said choosing of coupling assignments for logically equivalent output pins and loads that minimize aggregate contributions to total wire length of the IC design comprises formulating a bi-partite matching problem for said logically equivalent output pins and said loads, assigning weights reflective of wiring lengths to arcs representing candidate coupling assignments between said logically equivalent output pins and said loads, and determining a solution to the weighted bi-partite matching problem.

14. The method of claim 13, wherein said assignment of weights reflective of wiring lengths to arcs representing candidate coupling assignments between said logically equivalent output pins and loads comprises determining Manhattan distances between said logically equivalent output pins and said loads.

15. The method of claim 13, wherein said choosing of coupling assignments for logically equivalent output pins and loads that minimize aggregate total wire length of the IC design further comprises assigning penalty cost to selected ones of said arcs representing candidate coupling assignments between said logically equivalent output pins and loads that go through congested areas.

16. The method of claim 12, wherein said choosing of coupling assignments for logically equivalent output pins and loads comprises choosing a set of coupling assignments for a group of logically equivalent output pins and a group of loads that minimize total delay time between said group of logically equivalent output pins and said loads.

17. The method of claim 16, wherein said choosing of a set of coupling assignments for a group of logically equivalent output pins and a group of loads that minimize total delay time between the group of logically equivalent output pins comprises assigning arrival times to a first set of nodes representing the group of logically equivalent output pins, assigning required times to a second set of nodes representing the group of loads, sorting the first and second set of nodes in accordance with the assigned arrival and required times respectively, and corresponding matching the two sets of nodes.

18. The method of claim 16, wherein said choosing of a set of coupling assignments for a group of logically equivalent output pins and a group of loads that minimize total delay time between the group of logically equivalent output pins comprises formulating a max-min matching problem for the group of logically equivalent input pins and the group of loads, assigning a slack value to each arc representing a candidate coupling assignment for a logically equivalent output pin and a load based on arrival and required times of the logical equivalent output pin and load, and solving the max-min matching problem.

19. The method of claim 16, wherein said choosing of coupling assignments for logically equivalent output pins and loads further comprises choosing coupling assignments for said logically equivalent output pins and said loads that minimize aggregate contributions to total wire length of the IC design, after performing said choosing of a set of coupling assignments for a group of logically equivalent output pins and a group of loads that minimize total delay time.

20. The method of claim 1, wherein said choosing of coupling assignments for logically equivalent output pins and loads comprises choosing coupling assignments for said logically equivalent output pins and said loads that minimize an interconnect resource consumption cost function.

21. An apparatus comprising:

(a) a storage medium having stored therein-first plurality of programming instructions, with the first plurality of programming Instructions designed to place and route an IC design, including performance of at least one place and route operation selected from a group of place and route operations consisting of choosing coupling assignments for nets and logically equivalent input pins of the IC design, and choosing coupling assignments for logically equivalent output pins and loads of the IC design; and

(b) a processor coupled to the storage medium to execute said first plurality of programming instructions.

22. The apparatus of claim 21, wherein said first plurality of programming instructions are further designed to choose coupling assignments for said nets and logically equivalent input pins that minimize aggregate contributions to total wire length of the IC design.

23. The apparatus of claim 21, wherein said first plurality of programming instructions are further designed to choose a set of coupling assignments for a group of nets and a group of logically equivalent input pins that minimize total delay time between said group of nets and said group of logically equivalent input pins.

24. The apparatus of claim 21, wherein said first plurality of programming instructions are further designed to choose coupling assignments for said nets and logically equivalent input pins that minimize an interconnect resource consumption cost function.

25. The apparatus of claim 21, wherein said first plurality of programming instructions are further designed to choose coupling assignments for said logically equivalent output pins and said loads that minimize aggregate contributions to total wire length of the IC design.

26. The apparatus of claim 21, wherein said first plurality of programming instructions are further designed to choose a set of coupling assignments for a group of logically equivalent output pins and a group of loads that minimize total delay time between said group of logically equivalent output pins and said loads.

27. The apparatus of claim 21, wherein said first plurality of programming instructions are further designed to choose coupling assignments for said logically equivalent output pins and said loads that minimize an interconnect resource consumption cost function.

28. The apparatus of claim 21, wherein

the storage medium further having stored therein a second plurality of programming instructions, with the second plurality of programming instructions designed to determine equivalent logic in the IC design; and

the processor further executes said second plurality of programming instructions.

29. An article of manufacture comprising:

a recordable medium having recorded thereon machine executable first plurality of programming instructions, with the first plurality of programming instructions designed to place and route an IC design, including performance of at least one place and route operation selected from a group of place and route operations consisting of choosing coupling assignments for nets and logically equivalent input pins of the IC design, and choosing coupling assignments for logically equivalent output pins and loads of the IC design.

30. The article of manufacture claim 29, wherein first plurality of programming instructions are further designed to choose coupling assignments for said nets and logically equivalent input pins that minimize aggregate contributions to total wire length of the IC design.

31. The article of manufacture of claim 29, wherein first plurality of programming instructions are further designed to choose a set of coupling assignments for a group of nets and a group of logically equivalent input pins that minimize total delay time between said group of nets and said group of logically equivalent input pins.

32. The article of manufacture claim 29, wherein first plurality of programming instructions are further designed to choose coupling assignments for said nets and logically equivalent input pins that minimize an interconnect resource consumption cost function.

33. The article of manufacture of claim 29, wherein first plurality of programming instructions are further designed to choose coupling assignments for said logically equivalent output pins and said loads that minimize aggregate contributions to total wire length of the IC design.

34. The article of manufacture of claim 29, wherein first plurality of programming instructions are further designed to choose a set of coupling assignments for a group of logically equivalent output pins and a group of loads that minimize total delay time between said group of logically equivalent output pins and said loads.

35. The article of manufacture of claim 29, wherein first plurality of programming instructions are further designed to choose coupling assignments for said logically equivalent output pins and said loads that minimize an interconnect resource consumption cost function.

36. The article of claim 29, wherein the recordable medium further having recorded thereon machine executable second plurality of programming instructions, designed to determine logic equivalents in the IC design.