Digital circuit layout techniques using binary decision diagram for identification of input equivalence

• US 7,398,490 B2
• Filed: 01/11/2006
• Issued: 07/08/2008
• 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
• Application Number:
  US11/330,676
• Publication Number:
  US 20060117280A1
• Time in Patent Office: 909 Days
• Field of Search: 716 1- 5, 716/11, 714/733, 714/738, 714/741
• US Class Current: 716/103
• 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/34 for reconfigurable circuits, e.g. field programmable gate arrays [FPGA] or programmable logic devices [PLD]
• CPC Class Codes: G06F 30/347 Physical level, e.g. placement or routing
• CPC Class Codes: G06F 30/39 Circuit design at the physical level physical level design for reconfigurable circuits G06F30/347

Abstract

A technique for analyzing digital circuits to identify pin swaps is provided for circuit layout and similar tasks in which the circuit is first decomposed into regions. Logic functions of the regions are decomposed into a directed graph of the logic functions. A swap structure is created in accordance with the directed graph to facilitate identification of input equivalences.

Claims

1. A computer-implemented method, comprising:

decomposing a circuit representation into fanout-free regions, each of the fanout-free regions corresponding to at least one logic function and each of the fanout-free regions comprising an output;

decomposing the at least one logic function of at least one of the fanout-free regions by generating a binary decision diagram for each output of the at least one of the fanout-free regions;

identifying equivalent pins by matching pins of gates in the circuit representation with points in a ds-prime graph created using the binary decision diagram; and

using the identified pin equivalence information to determine the input equivalence of the at least one of the fanout-free regions.

2. The computer-implemented method of claim 1, further comprising modifying the circuit representation based at least in part on the determined input equivalence.

3. The computer-implemented method of claim 2, wherein modifying the circuit representation comprises swapping two or more of the pins of the gates in the circuit representation.

4. The computer-implemented method of claim 1, further comprising generating a binary decision diagram for each net in the circuit representation.

5. The computer-implemented method of claim 4, wherein matching pins of gates in the circuit representation with points in the ds-prime graph comprises comparing at least one of the binary decision diagram for each output of the fanout-free regions with at least one of the binary decision diagram for each net in the circuit representation.

6. The computer-implemented method of claim 1, wherein decomposing the circuit representation into the fanout-free regions comprises identifying a region head for each of the fanout-free regions, and wherein the region head comprises a first combinational gate.

7. The computer-implemented method of claim 6, wherein decomposing the circuit representation into the fanout-free regions further comprises identifying at least one non-region-head member for each of the fanout-free regions, and wherein the non-head region member comprises a second combinational gate.

8. The computer-implemented method of claim 1, wherein decomposing the circuit representation into the fanout-free regions comprises forming each of the fanout-free regions and identifying a corresponding region head for each of the fanout-free regions.

9. The computer-implemented method of claim 8, further comprising identifying a sub-plurality of fanout-free regions, wherein each of the sub-plurality of fanout-free regions fans out to only one other fanout-free region.

10. The computer-implemented method of claim 9, further comprising coalescing each of the sub-plurality of fanout-free regions into a coalesced region, wherein the coalesced region comprises a coalesced output.

11. The computer-implemented method of claim 10, wherein the binary decision diagram comprises a coalesced binary decision diagram for the coalesced output.

12. One or more computer-readable media comprising computer-executable instructions which, when executed by a processor, perform a method comprising:

decomposing a circuit representation into fanout-free regions, each of the fanout-free regions corresponding to at least one logic function and each of the fanout-free regions comprising an output;

decomposing the at least one logic function of at least one of the fanout-free regions by generating a binary decision diagram for each output of the at least one of the fanout-free regions;

identifying equivalent pins by matching pins of gates in the circuit representation with points in a ds-prime graph created using the binary decision diagram; and

using the identified pin equivalence information to determine the input equivalence of the at least one of the fanout-free regions.

13. The one or more computer-readable media of claim 12, wherein the method further comprises modifying the circuit representation based at least in part on the determined input equivalence.

14. The one or more computer-readable media of claim 13, wherein modifying the circuit representation comprises swapping two or more of the pins of the gates in the circuit representation.

15. The one or more computer-readable media of claim 12, wherein decomposing the circuit representation into the fanout-free regions comprises identifying a region head for each of the fanout-free regions, and wherein the region head comprises a first combinational gate.

16. The one or more computer-readable media of claim 15, wherein decomposing the circuit representation into the fanout-free regions further comprises identifying at least one non-region-head member for each of the fanout-free regions, and wherein the non-head region member comprises a second combinational gate.

17. The one or more computer-readable media of claim 12, wherein decomposing the circuit representation into the fanout-free regions comprises forming each of the fanout-free regions and identifying a corresponding region head for each of the fanout-free regions.

18. The one or more computer-readable media of claim 17, wherein the method further comprises identifying a sub-plurality of fanout-free regions, wherein each of the sub-plurality of fanout-free regions fans out to only one other fanout-free region.

19. The one or more computer-readable media of claim 18, wherein the method further comprises coalescing each of the sub-plurality of fanout-free regions into a coalesced region, wherein the coalesced region comprises a coalesced output.

20. The one or more computer-readable media of claim 19, wherein the binary decision diagram comprises a coalesced binary decision diagram for the coalesced output.