gj
`~
`~ al
`0
`v.' .&J
`:I
`en
`
`~CD
`
`II)
`II)
`
`-
`==
`=CJ\
`='
`~ ....... - al w
`~CD ...::;
`-o
`=ID
`f' 0
`===o
`~ -
`~ '
`
`z
`0
`~·
`(,)
`u::
`Zi)
`en
`:5
`0
`
`;::)
`en
`!!?
`
`PATENT NUMBER
`
`8237127
`
`1111111 IIIII 11m llllllllllllllllllllllllll
`6237127
`
`U.S. UTILITY PATENT APPLICATION
`O.I.P.E.
`PATENT DATE
`
`SCANNED c c a.A. (Lf{Y-,
`
`M~Y 2 2 1U0t
`
`SECTOR
`
`SUBCLASS
`
`ART UNIT
`
`FILED WITH: D DISK (CRF) D FICHE
`
`(Attached in pocket on right inside flap)
`
`PREPARED AND APPROVED FOR ISSUE
`..,...
`
`ISSU~ASSIFICATION
`/
`
`CROSS REFERENCE(S)
`
`ORIGINAL
`
`CLASS
`
`CLASS
`
`}I!> "
`
`SUBCLASS .,./
`~L' 7D3
`~~~
`INTERNATIONAL CLAS~CATION
`II~
`a p k f
`l/ /.:?"/ .)2)
`- I otf
`b (;. r
`6
`a; D ';. f
`I o~
`I o <,S
`(:, r
`/
`
`SUBCLASS (ONE SUBCLASS PER BLC"JCK)
`l)'
`
`~
`l
`~CD
`
`"3
`
`,q
`s-
`
`9-
`
`;:l.
`
`0 Continued on Issue Slip Inside File Jacket
`
`Sheets Drwg.
`
`;!;~
`
`DRAWING~·
`Fi~rwg. Print Fig.
`I
`A~~. '~~r-
`!h~-f~P 7f,
`
`MATTHEW SMITH
`SUPERVISORY ?A TENT EXAMINER
`
`;/
`
`l
`"'
`
`/
`
`Total Claims
`I
`/3
`NOTICE pF ALLOWANCE MAILED
`~rr- &-o _ vu
`.
`
`CLAIMS ALLOWED
`
`Print Claim for O.G.
`
`":$'
`
`.
`
`ISSUE FEE
`
`rhl
`~-~-()]
`
`'bate Paid
`
`ISSUE B,Jii"CH NUMBER
`
`U,so 1/
`
`(
`l
`. (
`
`(1 0
`
`' DTERMINAL
`
`DISCLAIMER
`
`(date)
`
`0 a) The term of this patent
`subsequent to
`has been disclaimed.
`0 b) The term of this patent shall
`not extend beyond the expiration date
`of U.S Patent. No.
`
`0 c) The terminal _months of
`this patent have been disclaimed.
`
`11&fij7f!J/:M~ Amount Due
`nf_.,;::
`
`(Primary Examiner)
`
`~~~t}. /
`
`\ i
`:.;
`
`\/..;,/ < .
`
`'
`f,
`(Legal Instruments Examiner)
`
`(Dale)
`I
`
`!
`
`(Date)
`
`WAR.NING:
`The Information disclosed herein may be restricted. Unauthorized disclosure may be prohibited by the United StatGs Code Title 35, Sections 122, 181 and 368.
`Possession outside the U.S. Patent & Trademark Office Is restricted to authorized employees and contractors only.
`
`,_/
`
`Form PT0-436A
`(Rev. 10197)
`
`/
`
`Fonnai Dr&wioosf
`shts)set_
`.. (CABEL AREA)
`
`(FACE)
`
`Exhibit 1002 - Page 1 of 245
`
`

`
`~
`
`PATENT APPLICATION
`11111111111111111111111111111\i\ \1111·1~~ \illllll
`~~-
`
`09093817
`
`;
`i
`'' ''
`\i.
`"·
`
`'
`'
`
`I
`I
`
`,
`
`..
`
`CONTENTS
`
`Date recel119d
`(Incl. C. of M.)
`or
`Date Mailed
`
`.
`
`.
`
`JC511 U.S. PTO
`. S9'/Q)l17
`· !
`~D..- I
`•.
`•.
`. --·· . \ ~UN 1 '/ 9 8 2 6
`. . . .
`
`'
`
`miTIALS
`
`- _./
`
`Date received
`(Incl. C. of M.)
`or
`Date Maiied
`
`--
`
`42.
`
`43.
`
`44.
`
`45.
`
`46.
`
`47.
`
`48.
`
`49.
`
`50.
`
`51.
`
`52.
`
`53.
`
`54.
`
`55.
`
`56.
`
`57.
`
`58.
`
`59.
`
`60.
`
`61.
`
`62.
`
`63.
`
`64.
`
`65.
`
`66.
`
`67.
`
`68.
`
`69.
`
`70.
`
`71.
`
`72.
`
`73.
`
`74.
`
`75.
`
`76.
`
`77.
`
`78.
`
`79.
`
`80.
`
`1) -J-1- oo
`~-2(-00
`,,tao k
`If- '?:f- ov
`Jv 8J-(\(
`
`16. ___ ______ - - - -
`
`17 . - - - - - - - - - - - -
`18. __ ______ _
`
`19. __ ____ ___ _
`
`20. __ _______ - - - -
`
`21. __ _______ - - - -
`
`22. __ _______ - - - -
`
`23. __ _______ - - - -
`
`24. _________ - - - -
`
`25. _________ - - - -
`26. __ ______ _
`
`27. __ ______ _
`
`28. __ ______ _
`
`29. __ ______ _
`
`30. _ _ ___ __ __ - - - -
`31. _ _______ _
`
`32·----~---- - - - -
`33. ____ _____ - - - -
`
`34 . - - - - - . . , . - - - - -
`35. _ _______ _
`
`36. - - - - - - - - - ' - - - - -
`37. __ ______ _
`
`38. __ ______ _
`
`39. ________ _
`
`40. _ _______ ~
`
`41·---~-----
`
`81.
`82. _ _ __ _ _ _ _ _
`
`(FRONT)
`
`Exhibit 1002 - Page 2 of 245
`
`

`
`SERIAL NUMBER
`
`FILING DATE
`
`CLASS
`
`GROUP ART UNIT
`
`A TTORNE'I' DOCKET 1\tb ..
`
`09/093,817
`
`06/08/98
`
`364
`
`2764
`
`34175.00085
`
`~ TED L. CRAVEN, SANTA CLARA, CA; DENIS M. BAYLOR, SAN JOSE, CA; YAEL
`(5 RINDENAU, CUPERTINO, CA.
`~ <
`
`G DOMESTIC DATA*********************
`
`DATA*********************
`
`I
`I ~
`
`JI
`/
`' l
`~
`
`\
`
`**FOREIGN APPLICA ONS************
`VERIFIED
`
`Foreign Priority
`35 USC 119 (a
`
`Verified and Acknowledged
`
`STATE OR
`COUNTRY
`CA
`
`SHEETS
`DRAWING
`221
`
`TOTAL
`CLAIMS
`13
`
`INDEPENDENT
`CLAIMS
`1
`
`(/)
`(/) w
`a:
`0
`0 <
`
`w
`
`~
`
`eNG FEE
`~~IVED
`
`$790
`
`FEES: Authority has been given in Paper
`No.
`to charge/credit DEPOSIT ACCOUNT
`NO.
`for the following:
`
`0 All Fees
`
`§ 1. 16 Fees (Filing)
`B ~~~~- ---
`
`. 1. 17 Fees (Processing Ext. of timje
`1.18 Fees (Issue)
`
`1 1
`
`0
`
`Exhibit 1002 - Page 3 of 245
`
`

`
`t',•
`
`PATENT APPLICATION SERIAL NO . - - - - - - - -
`
`U.S. DEPARTMENT OF COMMERCE
`PATENT AND TRADEMARK OFFICE
`FEE RECORD SHEET
`
`06/15/1998 DTHOftAS 00000008 09093817
`01 FC:101
`
`790.00 OP
`
`PT0-1556
`(5/87)
`
`·········------- ·----------·
`
`---- ···---- ----~~
`
`Exhibit 1002 - Page 4 of 245
`
`

`
`PATENT APPLICA'. ~TRANSMITTAL LETTER
`
`Docket No.
`34175.00085(A1998-015)
`
`TO THE ASSISTANT COMMISSIONER FOR PATENTS
`
`herewith for filing under 35 U.S.C. 111 and 37 C.F.R. 1.53 is the patent application of:
`
`METHOD AND APPARATUS FOR TAG-BASED STATIC TIMING ANALYSIS WITH EXCEPTIONS
`
`Enclosed are:
`181 Certificate of Mailing with Express Mail Mailing Label No.
`181 22
`sheets of drawings.
`0 A certified copy of a
`181
`181 Signed.
`li)eclaration
`181
`r:>ower of Attorney
`0 ~formation Disclosure Statement
`•
`0 preliminary Amendment
`· .: Other: Assignment
`
`0 Unsigned.
`
`EM320545708US
`
`application.
`
`For
`
`#Filed
`
`13
`
`1
`
`CLAIMS AS FILED
`
`#Allowed
`-20 =
`- 3 =
`
`#Extra
`
`0
`
`0
`
`X
`
`X
`
`Rate
`
`$22.00
`
`$82.00
`
`pie Dependent Claims (check if applicable) 0
`
`BASIC FEE
`
`TOTAL FILING FEE
`
`181 A check in the amount of
`to cover the filing fee is enclosed.
`$790.00
`181 The Commissioner is hereby authorized to charge and credit Deposit Account No.
`as described below. A duplicate copy of this sheet is enclosed.
`0 Charge the amount of
`as filing fee.
`181 Credit any overpayment.
`181 Charge any additional filing fees required under 37 C. F. R. 1.16 and 1.17.
`0 Charge the issue fee set in 37 C.F.R. 1.18 at the mailing of the Notice of Allowance,
`pursuant to 37 C.F.R. 1.311 (b).
`
`05-0150
`
`Fee
`
`$0.00
`
`$0.00
`
`$0.00
`
`$790.00
`
`$790.00
`
`cc:
`
`Laura A. Majerus, Reg. No. 33,417
`Attorney for Applicant(s)
`Graham & James LLP
`600 Hansen Way
`Palo Alto, CA 94304-1043
`Tel: (650) 856-6500
`Fax: (650) 856-3619
`
`P01 LARGEIREV06
`
`Exhibit 1002 - Page 5 of 245
`
`

`
`··.
`
`APPLICATION FOR
`UNITED STATES PATENT
`IN THE NAMES OF
`
`Ted Lewis Craven,
`Denis Murray Baylor
`and
`Yael Rindenau
`
`for
`
`Method and Apparatus For Tag-Based Static
`Timing Analysis With Exceptions
`
`DOCKET NO. 34175.00085 (A1998-015)
`
`Please direct communications to:
`GRAHAM & JAMES LLP
`600 Hansen Way
`Palo Alto, CA 94304
`(650) 856-6500
`Express Mail Number EM320545708US
`
`Exhibit 1002 - Page 6 of 245
`
`

`
`Method and Apparatus For Tag-eased Static
`Timing Analysis With Exceptions
`
`5
`
`FIELD OF THE INVENTION
`
`The present invention relates generally to the static timing analysis of
`
`digital electronic circuits. More specifically, the present invention relates to
`
`analyzing certain paths of a circuit under non-default timing constraints known as
`
`exceptions.
`
`1 0
`
`~~=-g
`~!:::::'
`
`~;::;c:,
`
`~~~
`'
`'
`I;,.;
`~J~.
`Li
`
`;:~
`
`:;.::~
`~::J.
`~t::i~
`'::.!:
`7.3
`
`::
`
`-::.;;~
`
`~~j
`.~ ....
`:t":«:. hl:
`~:~
`~~
`::·l;t'i
`·=:=:
`:':::=':
`~~~=
`
`BACKGROUND OF THE INVENTION
`
`To tackle the increasing complexity of digital electronic circuits, designers
`
`need faster and more accurate methods for statically analyzing the timing of
`
`1 5
`
`such circuits, particularly in light of ever-shrinking product development times.
`
`The complexity of designing such circuits is often handled by expressing
`
`the design in a high-level hardware description language (HLHDL).
`
`HLHDLs allow the designer to save design time by permitting him or her
`
`to express the desired functionality at the register transfer level (RTL) of
`
`20
`
`abstraction or higher. The high-level HDL description is then converted into an
`
`actual circuit through~ a process, well known to those of ordinary skill in the art as
`
`"synthesis," involving translation and optimization.
`
`HLHDLs describe, directly or indirectly,
`
`the two main kinds of circuit
`
`entities of an RTL circuit description: i) state devices or sequential logic which
`
`25
`
`store data upon application of a clock signal, and ii) combinational logic. The
`
`state devices typically act as either: i) an interface between conceptua11y distinct
`
`circuit systems, or ii) storage for the results of functional evaluation performed by
`
`the combinational logic.
`
`1311143605.04.00
`060598/1321134175.00085
`
`2
`2
`
`Exhibit 1002 - Page 7 of 245
`
`

`
`In the process of digital circuit design, static timing analysis is often useful
`
`in order to verify that the design produced, in addition to being functionally
`
`correct, will perform correctly at the target clock speeds. For similar reasons,. it
`
`would be useful to apply, as efficiently as possible, static timing analysis to the
`
`5
`
`synthesis process.
`
`SUMMARY OF THE INVENTION
`
`The present
`
`invention may be used
`
`the hardware synthesis
`. -
`environment known as the "Design Compiler shell" produced by Synopsys, Inc.,
`
`in
`
`\:::J
`
`10
`
`of Mountain View, California.
`
`Exceptions can be a very powerful tool for guiding the Design Compiler
`
`~:::::
`
`\,~
`
`portion of the Design Compiler shell towards the synthesis of a more efficient
`
`final circuit netlist. This is because exceptions allow the designer, for example,
`
`15
`
`to inform Design Compiler that despite default timing constraints, certain paths
`
`through the circuit are subject to less demanding performance requirements in
`
`the context of the design's actual application. Exceptions are also useful for
`
`· further analysis, by the designer, of the final circuit netlist produced by Design
`
`Compiler.
`
`20
`
`Exceptions are specified by the. circuit designer as individual syntactic
`
`units called "exception statements" which are comprised of a "timing alteration"
`
`and a "path specification." The timing alteration instructs the timing analyzer how
`
`to alter the default timing constraints for paths through the circuit to be analyzed
`
`which satisfy the· path specification .. The path specification consists of one or
`
`25 more "path specifiers," with each path specifier taking an "argument."
`
`In order
`
`for a path specification to be satisfied, each argument of each of its path
`
`specifiers must be satisfied.
`
`131/143605.04.00
`060598/1321134175.00085
`
`3
`.~
`
`Exhibit 1002 - Page 8 of 245
`
`

`
`The static timing analysis of the present invention is performed upon units
`
`of the circuit, referred to as "sections", which comprise a set of "launch" flip flops,
`
`non-cyclic combinational circuitry and a set of "capture" flip flops.
`
`The section to be analyzed is represented by a netlist of flip flops and
`
`5
`
`combinational logic connected together, at their pins, by wire objects.
`
`The
`
`tag-based static
`
`timing analysis of
`
`the present
`
`invention,
`
`implementing exceptions statements,
`
`is performed
`
`in
`
`four main steps:
`
`preprocessing, pin-labeling, RF timing table propagation and relative constraint
`
`analysis. Each of these four steps can be accomplished in one of two main
`
`1 0
`
`ways, depending upon how exception statements are to be implemented.
`
`. For a first-way of implementing exception statements, these four steps are
`
`referred to as: first-way preprocessing, first-way pin-labeling, first-way modified'
`
`RF timing table propagation and first-way modified relative constraint analysis.
`
`For a second-way of implementing exception statements, these four steps
`
`1 5
`
`are
`
`referred
`
`to as: second-way preprocessing, second-way pin-labeling,
`
`second-way modified RF timing table propagation and second-way modified
`
`relative constraint analysis.
`
`Preprocessing accepts the exception statements written by the circuit
`
`designer and converts them into a set of preprocessed exceptions statements
`
`20
`
`which has their path specifications expressed in a certain standard form. Both
`
`first-way and second-way preprocessing convert the path specification of an
`
`exception statement into a form expressed literally in terms of pins of the circuit
`
`description netlist. For the first-way of implementing exception statements, each
`
`pin is specified independently in the path specifications by being its own path
`
`25
`
`specifier argument. For the second-way of implementing exception statements,
`
`a group of pins may be specified as being logically equivalent, in terms of their
`
`ability to satisfy a path specification, by their being grouped into an OR-type path
`
`specifier argument.
`
`:~:::;
`
`b::?
`~Jj
`~~j
`. ~:;:;~
`~~::?
`;,\,!
`~;~
`
`~:::~
`
`:::
`
`:=::z~
`~!:::~
`~11
`~~:j
`~UJ
`: :::~
`;~-:::.~
`
`~~~
`
`131/143605.04.00
`060598/1321134175.00085
`
`4
`
`Exhibit 1002 - Page 9 of 245
`
`

`
`In pin-labeling, the pins of the circuit network, specifically referred to by
`
`the preprocessed exception statements, are marked to indicate their being. the
`
`subject of an exception statement or statements.
`
`In first-way pin labeling, each pin, referred to by a preprocessed exception
`
`5
`
`statement, is marked with.an "exception flag."
`
`In second-way pin labeling, each pin, referred to by a preprocessed
`
`exception statement, is given an "argument container" which can contain a
`
`collection of "labels." A label in an argument container is a copy of the "form" in
`
`which a preprocessed exception statement has referred to the circuit pin to which
`
`10
`
`the argument container is attached. The purpose of a label is to provide a data
`
`item which can be matched against the arg.ument of a. path specifier in a·
`
`preprocessed exception statement. Any form of label, which allows this
`
`matching to be accomplished, is suitable. For those path specifier arguments
`
`. which refer only to a single pin, a label which can match that single-pin reference
`
`15
`
`is put in the argument container. For those path specifier arguments which refer
`
`to an OR-expression of several pins, a label which can represents, and can
`
`therefore match, the entire OR-expression is put in the argument container.
`
`RF timing table propagation is accomplished as follows.
`
`Delays between the inputs and outputs of either state or combinational
`
`20
`
`devices are represented by "timing arcs." For the purposes of the set of launch
`
`flip flops, we are interested in the delay between a clock edge being applied to
`
`the flip flop and a subsequent change, if in fact such a change is caused to
`
`occur, at the flip flop's outputs. For the purposes of combinational logic, we are
`
`interested in the delay between a change being applied to an input of the logic
`
`25
`
`and a subsequent change, if in fact such a change is caused to occur, at the
`
`output.
`
`The RF timing tables propagated are comprised of the following four
`
`values: minimum rise time (minRT), maximum rise time (maxRD. minimum fall
`
`time (minFD and maximum fall time (maxFT). RF timing tables eaGh have their
`'
`own "tag" which, in accordance with the present invention, has two parts: i) a first
`
`30
`
`131/143605.04;00
`060598/1321134175.00085
`
`5
`
`Exhibit 1002 - Page 10 of 245
`
`

`
`part which is loaded with a unique identifier for the clock of a launch flip flop, and
`
`ii) a second part which can contain a variety of "labels" (described below).
`
`The RF timing tables, for a section of circuitry to be analyzed, are initially
`
`created as follows. An RF timing table is created for every output of every
`
`5
`
`launch flip flop. The values for minRT, maxRT, minFT and maxFT of each RF
`
`timing table are determined from the timing arc from the flip flop's clock to the
`
`output of the flip flop for which the RF timing table is being created. A first part of
`
`the tag created for each RF timing table is loaded with an identifier indicating the
`
`particular clock driving the clock input of the flip flop for which the RF timing table
`
`1
`0
`
`is being created.
`
`~~~
`. ~:""':
`~~:J
`~!:.:.;:~
`~=:=r
`
`~~1:.~
`~;~
`~~::::
`
`~:~
`
`::
`
`~!:=;
`~!~::
`
`~;J1
`.:c:r::.
`~:.~~
`
`~-~~i
`~:ij
`~fi
`::::r,'l
`
`At this point; first-way modified RF timing table propagation checks to see
`
`if any of the output pins of the launch flip flops have an exception flag. For each
`
`output pin with an exception flag, a label, representing that pin as the only
`
`argument of a path specifier, is added to the second part of the tag for the RF
`
`1
`5
`
`timing table for that output pin.
`
`At this same point, second-way modified RF timing table propagation
`
`checks to see if any of the output pins of the launch flip flops have argument
`
`containers. For each output pin with an argument container, all of the labels in
`
`that container are added to the second part of the tag for the RF timing table for
`
`20
`
`that output pin.
`
`Propagation of the tagged RF timing tables, through the combinational
`
`units of a circuitry section, is accomplished as follows. Each RF timing table, at
`
`each input of a combinational unit, is modified, according to the timing arc
`
`associated with that input, to produce a temporary RF timing table pointed to by
`
`25
`
`the combinational unit's output pin. Each temporary RF timing table is initially
`
`given the same tag as the RF timing table, at the combinational unit's input, it is
`
`based upon.
`
`Once all temporary RF timing tables have been computed at the
`
`combinational unit's output, those having tags of the same "type" are combined
`
`30
`
`to produce a final RF timing table.
`
`1311143605.04.00
`060598/1321134175.00085
`
`6
`
`Exhibit 1002 - Page 11 of 245
`
`

`
`At this point, after the creation of each final RF timing table, first-way
`
`modified RF timing table propagation checks to see if the output pin of the
`
`combinational unit has an exception flag.
`
`If the exception flag exists, then .a
`
`label, representing that output pin as the only argument of a path specifier, is
`
`5
`
`added to the second part of the tag for the final RF timing table for that output pin
`if that label, by itself or in conjunction with any selection of labels already on the
`tag, satisfies, or can possibly satisfy, a path specification of at least one of the
`
`preprocessed exception statements.
`
`At this same point, after the creation of each final RF timing table,
`
`0
`1
`
`second-way modified RF timing table propagation checks to see if the output pin
`
`of the combinational unit has an argument container.
`
`If the argument container
`- "
`exists, then each label in it is considered for possible addition to the second part
`
`of the tag for the final RF timing table of the output pin. A label is added to the
`second part of the tag .for the final RF timing table for that output pin if that label,
`by itself or in conjunction with any selection of labels already on the tag, satisfies,
`
`1
`5
`
`or can possibly satisfy, a path specification of at least one of the preprocessed
`
`exception statements. For second-way modified RF timing table propagation,
`
`the label may be either: i) a representation of that output pin as the only
`
`argument of a path specifier, or ii) a representation of an OR-expression of
`
`·::~:::-
`
`¥~:J
`;Jj
`~~
`n
`~:§J
`~~~
`~~=
`:::::4
`
`::l
`
`~:~
`~~~1
`~j
`~~~
`~j:i
`f:ij
`
`20
`
`several pins, of which the output pin is one, as the argument of a path specifier.
`
`Propagation of an RF timing table across a wire, to the input pin of a
`
`combinational unit or capture flip flop, is accomplished as follows. The RF timing
`
`table, which we shall referto as "RFTT_input_pin," created at the input pin of a
`
`combinational unit or capture flip flop has its rise and fall time values delayed by
`
`25
`
`the wire across which it has just traveled. For first-way modified RF timing table
`
`propagation·,
`
`the pin to which RFTT _input_pin is attached is checked for an
`
`exception flag. If an exception flag is found, a label may be added to the second
`
`part of the tag of RFTT_input_pin, but only after the same determination is
`
`m;;~de according. to the same procedure described above with respect to the
`
`30
`
`point after the creation of ail final RF timing table at a combinational unit output.
`
`1311143605.04.00
`060598/1321134175.00085
`
`7
`
`Exhibit 1002 - Page 12 of 245
`
`

`
`For second-way modified RF timing table propagation,
`
`the pin to which
`
`RFTT_input_pin is attached is checked for an argument container.
`
`If an
`
`argument container is found, a label may be added to the second part of the tag
`
`of RFTT _input_pin, but only after the same determination is made according to
`
`5
`
`the same procedure described above with respect to the point after the creation
`
`of an final RF timing table at a combinational unit output.
`
`Generally, first-way and second-way modified relative constraint analysis
`
`both proceed as follows. Every RF timing table, which we shall refer to as
`
`C_FF1_RF_TABLE, at the input of every capture flip flop, which we shall refer to
`
`10
`
`as C_FF1, is looped over. For each RF timing table C_FF1_RF_TABLE, the
`
`capture clock driving it, which we shall refer to as C_CLOCK1, is identified.
`
`Based upon the launch clock identified in the first part of the tag for
`
`C_FF1_RF_TABLE, and capture clock C_CLOCK1, a pair of default relative
`
`constraints are identified. These two default relative constraints are called the
`
`i'"'
`
`15
`
`maximum allowable path delay (MAPD) and the shortest allowable path delay
`
`(SAPO). Based upon the labels contained in the second part of the tag for
`
`C_FF1_RF_TABLE, a set of preprocessed exception statements, which we shall
`
`refer to as C_FF1_EXCEPS, may have their path specifications satisfied. A
`
`variety of precedence rules, either user-specified and/or predetermined, are then
`
`20
`
`applied such that a single exception statement, with a single timing alteration, is
`
`selected. The timing alteration of this single selected exceptio~ statement is
`
`then applied to alter the default values of either MAPD and/or SAPD. Finally, the
`
`values of C_FF1_RF_TABLE are determined to have met, or not met, its
`
`corresponding pair of MAPD (modified or unmodified, depending upon
`
`25
`
`exceptions) and/or SAPD (modified or unmodified, depending upon exceptions):
`
`minRT and minFT of C_FF1_RF_TABLE must be greater than SAPD, and
`
`maxRT and maxFT of C_FF1_RF_TABLE must be less than MAPD.
`
`Advantages of the invention will be set forth, in part, in the description that
`follows and, in part, will be understood by those skilled in the art from the
`
`30
`
`description or may be learned by practice of the invention. The advantages of
`8
`131/143605.04.00
`060598/1321134175.00085
`
`1
`
`Exhibit 1002 - Page 13 of 245
`
`

`
`the invention will be realized and attaine~ by means of the elements and
`
`combinations particularly pointed out in the appended claims and equivalents.
`
`BRIEF DESCRIPTION OF THE DRAWINGS
`
`5
`
`The accompanying drawings, that are incorporated in and constitute a
`
`part of this specification, illustrate several embodiments of the invention and,
`
`together with the description, serve to explain the principles of the invention:
`
`Figure 1 depicts an overview of the design environment utilizing the
`
`principles of the present invention;
`
`1
`0
`
`Figures 2A-B render timing arcs, as utilized in accordance with the
`
`present invention, for a 0-type flip flop;
`
`Figures 3A-C illustrates timing arcs, as utilized in accordance with the
`
`present invention, for a combinational gate;
`
`Figures 4A-C depict the initial determination of RF timing tables, as
`
`1
`5
`
`utilized in accordance with the present invention, for 0-type flip flops;
`
`Figure 5 renders the propagation of tagged RF
`
`timing
`
`tables,
`
`in
`
`accordance with the present invention, through a combinational gate;
`
`Figure 6 illustrates the typical hardware computing environment in which
`
`the software in accordance with a preferred embodiment of the present invention
`
`~JJ
`
`~bj
`
`~ i ;
`~X¥
`'' :::=
`
`"':;:
`
`.;~=~
`
`-·
`;::;:J
`~jr1
`~:J
`..:.;..:.
`~·?::~
`~Jj
`~~
`
`20
`
`is executed;
`
`Figure 7 depicts, in part, the general propagation of RF timing tables from
`
`a gate's inputs to its outputs in pseudo code (based on the C Programming
`
`Language);
`
`Figure 8 renders schematically, in part, the general propagation of RF
`
`25
`
`timing tables from a gate's inputs to its outputs;
`
`131/143605.04.00
`060598/1321134175.00085
`
`9
`
`Exhibit 1002 - Page 14 of 245
`
`

`
`Figures 9A-B presents a procedure in accordance with the present
`
`invention
`
`for determining, as part of a second phase of second-way
`
`preprocessing, for order dependent "-through"s, product-of-sums expressions;
`
`Figures 9C-G present a simulation, step-by-step, of the execution of the
`
`5
`
`first phase of second-way preprocessing and second phase of second-way
`
`preprocessing as described in Figures 9A-B;
`
`Figure 10 presents a procedure
`
`for determining product-of-sums
`
`expressions for order independent "-through"s;
`
`Figure 11 shows an example circuit section which has been processed in
`
`10
`
`accordance with a first way of implementing the exception statement input
`
`~:::::::
`
`language;
`
`Figure 12 shows an example circuit section which has been processed in
`
`accordance with a second way of implementing the exception statement input
`
`language;
`
`15
`
`Figure 13 shows an example circuit section which has been processed in
`
`accordance with a . first way of implementing the exception statement input
`
`language;
`
`Figure 14 shows an example circuit section which has been processed in
`
`accordance with a second way of implementing the exception statement input
`
`20
`
`language;
`
`Figure 15 depicts an example of the exception statement input language
`
`augmented to accept an arbitrary boolean equation as the argument of a
`
`"-through" path specifier and
`
`its subsequent processing according
`
`to a
`
`modification of the first phase of second-way preprocessing; and
`
`25
`
`Figure 16 illustrates a specific example of finding higher-level equivalency
`
`between pins by further processing preprocessed exception statements to
`
`produce an additional set of pattern-matching higher-level exception statements.
`
`1311143605.04.00
`060598/1321134175.00085
`
`10
`/D
`
`Exhibit 1002 - Page 15 of 245
`
`

`
`DETAILED DESCRIPTION OF PREFERRED EMBODIMENTS
`
`Reference will now be made in detail to preferred embodiments of the
`
`invention, examples of which are illustrated in the accompanying drawings.
`
`5 Wherever possible, the same reference numbers will be used throughout the
`
`drawings to refer to the same or like parts.
`
`The present
`
`invention may be used
`
`in
`
`the hardware synthesis
`
`environment known as the "Design Compiler shell" produced by Synopsys, Inc.,
`
`of Mountain View, California. An overview of this design environment is shown
`
`10
`
`in Figure 1. Design Compiler shell 106, is shown as being composed, from a
`
`functional perspective, of major subsections 101
`
`to 1 05.
`
`These major-
`
`subsections will now be described.
`
`HDL Compiler 101 translates a high-level description of a circuit to be
`
`implemented (high-level HDL Design 1 00), which has been described in the
`
`l 5
`
`standard HLHDL such as VHDL (for example VHDL Institute of Electrical and
`
`Electronic Engineers Standard 1076-1993, herein incorporated by reference) or
`
`Verilog HDL (for example Verilog Institute of Electrical and Electronic Engineers
`
`Standard 1364-1995, herein
`
`incorporated by
`
`reference),
`
`into a generic
`
`technology circuit netlist 102. The HLHDL input is organized into high-level
`
`~d
`
`~=-
`~::..~
`
`;~_j
`~=~
`~Jj
`~=
`:
`:.
`-=~:
`
`..
`
`.;.:;.=
`;;:.:=:;
`~}.~
`::x:::
`h~
`~:g
`
`~;~
`
`20
`
`sections known a "blocks."
`
`Design Compiler 103
`
`then
`
`translates, automatically,
`
`the generic
`
`technology circuit description into an optimized implementation in a particular
`
`circuit technology (final circuit netlist 104). Design Compiler accomplishes this
`
`translation in accordance with:. i) the technology dependent cell library 107
`
`.25
`
`selected by the designer (discussed below), and ii) designer specified constraints
`
`108 (also discussed below). Design Compiler accomplishes this translation and
`
`opti~ization in four main steps: i) technology independent optimization, ii)
`
`technology mapping, iii) timing correction and iv) area recovery. Technology
`
`independent optimization is accomplished by performing transformations on the
`
`131/143605.04.00
`060598/1321/34175.00085
`
`11
`I (
`
`Exhibit 1002 - Page 16 of 245
`
`

`
`~:~=3
`::.::::::
`
`~~
`.::r:.
`~J.j
`
`~hf
`
`'.
`~=
`·;-=:..;
`
`::
`
`,;::;:;::,
`
`;::J
`.:~::.
`~i §
`§:X::i
`::If~~
`
`~Jg
`~J;j
`~;~
`
`initial generic technology circuit which result in an optimized generic technology
`
`circuit. The initial part of technology independent optimization uses the timing
`
`analyzer of the present invention to calculate the worst case constraint on each
`
`critical path.
`
`ln the course of performing technology independent optimizations,
`
`5
`
`however, another form of timing analysis is used which is faster than the present
`
`invention but does not take into account exceptions. The goal of technology
`
`independent optimization is area minimization, but timing analysis is used to
`
`keep the circuit produced closely enough within the worst case constraint on
`
`each critical path such that any timing violations introduced during technology
`
`0
`1
`
`independent optimization can be corrected in the subsequent step of timing
`
`correction. Technology mapping matches pieces of the generic technology
`
`circuit description with "cells" that are available in a particular technology.: "
`
`dependent cell library 1 07. CeiLiibraries are typically of two main types: gate
`
`array library or standard cell library. The cells of the cell library are implemented
`
`5
`1
`
`in a specific circuit technology (such as CMOS, BiCMOS, bipolar, ECL or
`
`NMOS). Technology mapping, like technology independent optimization, uses
`
`another form of timing analysis which is faster than the present invention but
`
`does not
`
`take
`
`into account exceptions.
`
`Like
`
`technology
`
`independent
`
`optimization, technology mapping also uses the timing analyzer of the present
`
`20
`
`invention only initially in order to calculate the worst case constraint on each
`
`critical path. The goal of technology mapping is area minimization, but timing
`
`analysis is used to keep the circuit produced closely enough within the worst
`
`case constraint on each critical path such that any timing violations introduced
`
`during technology mapping can be corrected in the next step of timing correction.
`
`25
`
`Timing correction identifies timing violations, with respect to user-specified
`
`constraints 108, or with respect to constraints due. to the cell library chosen, and
`then corrects them by performing local transformations. The transformations
`
`used by timing correction do not change the design from being composed of
`
`cells from the selected cell library 107. Timing violations are identified during
`timing correction by utilizing the timing analyzer of the present invention. Finally,
`
`30
`
`1311143605.04.00
`060598/1321134175.00085
`
`12
`
`;t~
`
`Exhibit 1002 - Page 17 of 245
`
`

`
`~:j
`d~
`~=
`~:::::.a
`~~J
`\;!=~
`~:g
`~:;~i~
`'··
`~
`-~
`..
`~~j
`
`~=J
`~!iJ
`~~ ·:::;::o
`~~~
`
`area recovery is performed to produce the final circuit description. The designer
`
`may specify, as part of constraints 108, the maximum area desired for the final
`
`circuit description. Area recovery determines whether timing correction may
`
`have introduced a violation of this maximum area constraint.
`
`If area recovery
`
`5
`
`finds such a violation, it will perform local transformations in an effort to bring the
`
`design within the maximum area desired. The transformations used by area
`
`recovery do not change the design from being composed of cells from the
`
`selected cell library 107. During area recovery, the timing analyzer of the
`
`present invention is utilized to prevent timing violations from being introduced.
`
`0
`1
`
`Connecting to all of these four stages is the "timing backbone" which contains
`
`the timing analyzer of the present invention.
`
`The final circuit description 104 may then be subjected to further analysis
`
`by the designer (user analysis 1 05), in order to explore aspects of the final
`
`circuit's performance which may not have been directly addressed by Design
`
`1
`5
`
`Compiler.
`Constraints 1 08 allow the user to specify the following three types of
`
`constraints: i) the maximum area desired (as discussed above), ii) timing
`
`constraints and iii) boundary constraints. Timing constraints are of two main
`
`types: waveforms and ~xceptions.
`
`20
`
`"Waveforms" are user-specified clock waveforms which are applied to
`
`certain points of the circuit design. Waveforms may be applied to the circuit
`
`design at either the HLHDL level (of high-level HDL design 1 00) or at the level of
`
`generic technology circui