Method for electric leaf cell circuit placement and timing determination

• US 5,640,328 A
• Filed: 04/25/1994
• Issued: 06/17/1997
• Est. Priority Date: 04/25/1994
• Status: Expired due to Term

• Current Assignee: Cadence Design Systems Incorporated (Cadence Group), Cedence Design Systems, Inc.
• Original Assignee: Cadence Design Systems Incorporated (Cadence Group)
• Inventors: Lam, Jimmy Kwok-Ching
• Primary Examiner(s): Teska, Kevin J.
• Assistant Examiner(s): PHAN, THAI Q
• Application Number:
  US08/232,960
• Time in Patent Office: 1,149 Days
• Field of Search: 364/578, 364/488, 364/489, 395/500, 395/550, 395/650
• US Class Current: 716/113
• CPC Class Codes: G01R 31/3016 Delay or race condition test, e.g. race hazard test
• CPC Class Codes: G06F 30/33 Design verification, e.g. functional simulation or model checking
• CPC Class Codes: G06F 30/3308 using simulation
• CPC Class Codes: G06F 30/392 Floor-planning or layout, e.g. partitioning or placement

Abstract

A method for determining the location of electric leaf cell circuits within the architecture of a semiconductor chip includes determination of the longest signal delays through an electric leaf cell circuit by evaluating independent channel connected components, reorganizing the circuit elements of each channel under evaluation into acyclic form, restructuring the acyclic form of channel connected components within the electric leaf cell circuits being structurally positioned in the chip architecture by selected reduction processes, determining input state vectors for each input and output pin connection pair of the electric leaf cell circuit in which an input pin connection state change is reflected in an output connection pin state change, and determining placement of the leaf cell within a semiconductor circuit module with reference to the greatest delay within each leaf cell.

Claims

1. A method for determining the location of an electric leaf cell circuit to be fabricated within the architecture of a semiconductor chip, wherein the electric leaf cell circuit includes a plurality of input and output connection pins and electric circuits including circuit elements interconnected cyclically and acyclically in one or more circuit channels, the method comprising the steps of:

separating an electric leaf cell circuit into independent electrical channels,

restructuring the circuit elements of each channel under evaluation into acyclic form, by opening feedback paths and inserting state variable at a selected open loop point is each feedback path which has been opened, and representing the point of opening with equal variables representing equality of value variation at the selected circuit position of the open loop which has been severed,

establishing a directed graph of circuit elements of a selected channel of the electric leaf cell circuitry, including assigning input and output directions for all non-internal nodes of the channel circuitry,

reducing the acyclic form of the circuit elements within a channel by series and parallel reduction,

establishing input state vectors representative of the reduced acyclic form of the circuit elements in a channel of the electric leaf cell circuit,

evaluating which input state vectors for particular input/output pin connection pairs of the electric leaf cell circuit are reflected in output connection pin state changes, including making an evaluation order for channel connected components, with the descendant component of the circuit components of the leaf cell being designated for priority evaluation, and further including constructing a binary decision diagram,

making a determination as to the longest delay time for any input state vector in which a simple change produces an output change,

obtaining a timing representation of the leaf cell and electrical connection wires of the leaf cell, and

determining placement of the leaf cell within a semiconductor circuit module based upon the greatest delay within each leaf cell with reference to a timing relationship made and as actually determined based upon a comparison of plural signal paths for selected input vectors at input connections of the circuit channels of a leaf cell circuit.

2. A method for determining the location of an electric leaf cell circuit to be fabricated within the architecture of a semiconductor chip, wherein the electric leaf cell circuit includes a plurality of input and output connection pins and electric circuits including circuit elements interconnected cyclically and acyclically in one or more circuit channels, the method comprising the steps of:

separating an electric leaf cell circuit into independent electrical channels,

restructuring the circuit elements of each channel under evaluation into acyclic form, by opening feedback paths and inserting state variables at a selected open loop point is each feedback path which has been opened, and representing the point of opening with equal variables representing equality of value variation at the selected circuit position of the open loop which has been severed,

establishing a directed graph of circuit elements of a selected channel of the electric leaf cell circuitry, including assigning input and output directions for all non-internal nodes of the channel circuitry,

establishing input state vectors representative of the reduced acyclic form of the circuit elements in a channel of the electric leaf cell circuit,

evaluating which input state vectors for particular input/output pin connection pairs of the electric leaf cell circuit are reflected in output connection pin state changes, including constructing a binary decision diagram, and

determining placement of the leaf cell within a semiconductor circuit with reference to the greatest delay within each leaf cell.