Digital circuit layout techniques

• US 6,360,352 B2
• Filed: 07/17/1998
• Issued: 03/19/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): Smith, Matthew
• Assistant Examiner(s): THOMPSON, ANNETTE M
• Application Number:
  US09/118,225
• Publication Number:
  US 20020010899A1
• Time in Patent Office: 1,341 Days
• Field of Search: 716/2
• 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

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 fanout-free regions. Quasi-canonical forms or models of the fanout free region are created from which a swap structure is created so that pins swap groups can be identified.

Claims

1. A method comprising:

decomposing an input circuit having logic gates into one or more fanout-free regions;

generating one or more quasi-canonical models for logic gates of the one or more fanout-free regions;

generating a swap structure from the one or more quasi-canonical models to identify symmetric structures;

analyzing the swap structure to identify pin swap groups of input pins; and

swapping one or more input pins to create an equivalent input circuit.

2. The method of claim 1 wherein decomposing the circuit into one of more fanout-free regions further comprises:

identifying the region of the circuit headed by a single gate which may fanout to multiple places;

identifying all other gates to be members of the region if the other gates have only one fanout which is itself a member of the region; and

including input nets within the region which fanout to multiple input pins within the region.

3. The method of claim 1 wherein creating a swap structure further comprises building a swap structure from a digital circuit that computes an equivalent function as the digital circuit and contains points that are identified with external pins of gates in the digital circuit.

4. The method of claim 3 wherein generating a swap structure from the one or more quasi-canonical models to identify symmetric structures further comprises avoiding input rotations to the inputs of symmetric functions which affect genealogical constraints.

5. The method of claim 4 wherein avoiding input rotations which affect genealogical constraints further comprises avoiding the swapping of input and output pins of the same logic function.

6. The method of claim 1 in which identifying pin swap groups within the swap structure further comprises extracting swap groups from the swap structure.

7. The method of claim 6 in which extracting swap groups from the swap structure further comprises recognizing multi-gate input equivalences and/or multi-pin swaps.

8. The method of claim 7 in which recognizing multi-gate input equivalences further comprises identifying two external pins which are both inputs to the same functional block in the swap structure and which do not have multiple fanout.

9. The method of claim 8 wherein identifying the external pins further comprises avoiding input pins of common polarity which are in an ancestor-descendent relationship with each other.

10. The method of claim 7 in which recognizing multi-pin swaps further comprises:

identifying pins input to a large functional block in the swap structure;

expanding an input function associated with each pin until it consists entirely of external gate pins; and

searching for a match among input functions to other external gate pins in the same swap structure.

11. An article comprising a machine-readable medium having stored thereon sequences of instructions that, when executed, cause one or more electronic devices to:

decompose an input circuit having logic gates into one or more fanout-free regions;

generate one or more quasi-canonical models for logic gates of the one or more fanout-free regions;

generate a swap structure from the one or more quasi-canonical models to identify symmetric structures;

analyze the swap structure to identify pin swap groups of input pins; and

swap one or more input pins to create an equivalent input circuit.

12. The article of claim 11 wherein the sequences of instructions that cause the one or more electronic devices to decompose the circuit into one of more fanout-free regions further comprises sequences of instructions that, when executed, cause the one or more electronic devices to:

identify the region of the circuit headed by a single gate which may fanout to multiple places;

identify all other gates to be members of the region if the other gates have only one fanout which is itself a member of the region; and

include input nets within the region which fanout to multiple input pins within the region.

13. The article of claim 11 wherein the sequences of instructions that cause the one or more electronic devices to create a swap structure further comprises sequences of instructions that, when executed, cause the one or more electronic devices to build a swap structure from a digital circuit that computes an equivalent function as the digital circuit and contains points that are identified with external pins of gates in the digital circuit.

14. The article of claim 13 wherein generating a swap structure from the one or more quasi-canonical models to identify symmetric structures further comprises avoiding input rotations to the inputs of symmetric functions which affect genealogical constraints.

15. The article of claim 14 wherein avoiding input rotations which affect genealogical constraints further comprises avoiding the swapping of input and output pins of the same logic function.

16. The article of claim 11 in which identifying pin swap groups within the swap structure further comprises extracting swap groups from the swap structure.

17. The article of claim 16 in which extracting swap groups from the swap structure further comprises recognizing multi-gate input equivalences and/or multi-pin swaps.

18. The article of claim 17 in which recognizing multi-gate input equivalences further comprises identifying two external pins which are both inputs to the same functional block in the swap structure and which do not have multiple fanout.

19. The article of claim 18 wherein identifying the external pins further comprises avoiding input pins of common polarity which are in an ancestor-descendent relationship with each other.

20. The article of claim 17 in which recognizing multi-pin swaps further comprises:

identifying pins input to a large functional block in the swap structure;

expanding an input function associated with each pin until it consists entirely of external gate pins; and

searching for a match among input functions to other external gate pins in the same swap structure.