Digital circuit layout techniques using circuit decomposition and pin swapping

• US 6,473,885 B1
• Filed: 12/22/1999
• Issued: 10/29/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): THOMPSON, ANNETTE M
• Application Number:
  US09/470,540
• Time in Patent Office: 1,042 Days
• Field of Search: 716/4, 716/11
• 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
• 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 method of analyzing a digital circuit to identify input equivalences comprising:

decomposing the circuit into one or more fanout-free regions;

creating a modified circuit structure from the decomposed regions; and

identifying pin swap groups within the modified circuit structure.

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

identifying a region or regions of the circuit headed by a single gate which may fan out to multiple places;

identifying all other gates to be members of each identified region, each of said all other gates having only one fanout which is itself a member of the region; and

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

3. The method of claim 1 wherein said decomposing of the digital circuit further comprises:

identifying regions that fan out to only one other region; and

coalescing the identified regions together.

4. A method of analyzing a digital circuit to identify input equivalences comprising:

decomposing the digital circuit into one or more regions having a first set of specified characteristics;

creating a modified circuit structure from the decomposed regions by decomposing logic functions of the decomposed regions into a directed graph of logic functions, said decomposing of logic functions of the decomposed regions including;

generating quasi-canonical models for cells of the circuit; and

creating a swap structure for the circuit using said models; and

identifying pin swap groups within the modified circuit structure.

5. A method of analyzing a digital circuit to identify input equivalences comprising:

decomposing the digital circuit into one or more regions having a first set of specified characteristics;

creating a modified circuit structure from the decomposed regions by decomposing logic functions of the decomposed regions into a directed graph of logic functions, said decomposing including;

generating quasi-canonical models for cells of the circuit; and

creating a swap structure for the circuit using said models by;

modifying the initial circuit structure to include large symmetric functions present in the initial circuit structure in the form of large functional blocks; and

avoiding input rotations to inputs of the symmetric functions that affect genealogical constraints;

identifying pin swap groups within the modified circuit structure.

6. The method of claim 5 wherein said avoiding of input rotations that affect genealogical constraints comprises:

avoiding swapping of input and output pins of the same logic function.

7. A method of analyzing a digital circuit to identify input equivalences comprising:

decomposing the digital circuit into one or more regions having a first set of specified characteristics;

creating a modified circuit structure from the decomposed regions; and

identifying pin swap groups within the modified circuit structure, said identifying comprising extracting swap groups from the modified circuit structure.

8. The method of claim 7 in which said extracting of swap groups from the modified structure comprises:

recognizing at least one of multi-gate input equivalences and multi-pin swaps.

9. The method of claim 8 in which said recognizing of at least one of multi-gate input equivalences and multi-pin swaps comprises:

identifying two external pins which are both inputs to a functional block in the swap structure and which do not have multiple fanouts.

10. The method of claim 8 in which said recognizing of multi-pin swaps comprises:

identifying pins input to functional blocks in the swap structure;

expanding the function blocks to the pins until each function block consists entirely of external gate pins;

then looking for a match with function blocks to other pins.

11. The method of claim 9 wherein said identifying of the external pins comprises:

avoiding pins which are in an ancestor-descendent relationship with each other.

12. A computer system comprising:

a storage medium having stored therein programming instructions designed to decompose a digital circuit design into one or more fanout-free regions, to create a modified circuit design from the decomposed regions, and to identify pin swap groups within the modified circuit design; and

a processor coupled to the storage medium to execute the programming instructions.

13. The computer system of claim 12, wherein the programming instructions are further designed to decompose the digital circuit design by identifying regions that fan out to only one other region, and coalescing the identified regions together.

14. A computer system comprising:

a storage medium having stored therein programming instructions designed to decompose a digital circuit design into one or more regions having a first set of specified characteristics, to create a modified circuit design from the decomposed regions, and to identify pin swap groups within the modified circuit design, the instructions to identify pin swap groups comprising instructions to extract swap groups from the modified circuit design; and

a processor coupled to the storage medium to execute the programming instructions.

15. An article of manufacture comprising:

a recordable medium having recordable thereon programming instructions used to program a computer system, wherein the programming instructions, when executed, are designed to decompose a digital circuit design into one or more fanout-free regions, to create a modified circuit design from the decomposed regions, and to identify pin swap groups within the modified circuit design.

16. The article of manufacture of claim 15, wherein the programming instructions are further designed to decompose the digital circuit design by identifying regions that fan out to only one other region, and coalescing the identified regions together.

17. An article of manufacture comprising:

a recordable medium having recordable thereon programming instructions used to program a computer system, wherein the programming instructions, when executed, are designed to decompose a digital circuit design into one or more regions having a first set of specified characteristics, to create a modified circuit design from the decomposed regions, and to identify pin swap groups within the modified circuit design, the programming instructions to identify pin swap groups comprising instructions to extract swap groups from the modified circuit design.