Digital circuit layout techniques using identification of input equivalence

• US 7,020,855 B2
• Filed: 08/16/2002
• Issued: 03/28/2006
• Est. Priority Date: 07/17/1998
• Status: Expired due to Term

• Current Assignee: Siemens Industry Software Inc. (Siemens AG)
• Original Assignee: Mentor Graphics Corporation (Siemens AG)
• Inventors: Wallace, David E
• Primary Examiner(s): THOMPSON, ANNETTE M
• Application Number:
  US10/222,429
• Publication Number:
  US 20030009731A1
• Time in Patent Office: 1,320 Days
• Field of Search: 716/2, 716/3, 716/4
• 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 within a circuit, the method comprising:

grouping the circuit into one or more regions, each region corresponding to a logic function;

decomposing the logic function of each of the regions into a directed graph of logic functions;

identifying equivalent pins by matching pins of the cells in the circuit with points in the directed graph; and

using the identified pin equivalence information to determine input equivalence, wherein said grouping the circuit into one or more regions comprises decomposing the circuit into fanout-free regions.

2. The method of claim 1, wherein said decomposing the logic function of each of the regions into a directed graph of functions compnses:

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

creating a swap structure.

3. The method of claim 2, wherein said identifying equivalent pins by matching pins of the cell in the circuit with points in the directed graph comprises determining which pins can be matched during creation of the swap structure, and identifying and filtering pin swap groups through analysis of the swap structure.

4. The method of claim 3, wherein said using the identified pin equivalence information to determine input equivalence comprises writing the filtered swap group to a file.