(12) United States Patent
`Craven et al.
`
`111111
`
`1111111111111111111111111111111111111111111111111111111111111
`US006237127Bl
`US 6,237,127 Bl
`May 22,2001
`
`(10) Patent No.:
`(45) Date of Patent:
`
`(54) STATIC TIMING ANALYSIS OF DIGITAL
`ELECTRONIC CIRCUITS USING NON(cid:173)
`DEFAULT CONSTRAINTS KNOWN AS
`EXCEPTIONS
`
`Primary Examiner-Matthew Smith
`Assistant Examiner-Jibreel Speight
`(74) Attorney, Agent, or Firm-Brown Raysman Millstein
`Felder & Steiner LLP; Jonathan T. Kaplan
`
`(75)
`
`Inventors: Ted L. Craven, Santa Clara; Denis M.
`Baylor, San Jose; Yael Rindenau,
`Cupertino, all of CA (US)
`
`(73) Assignee: Synopsys, Inc., Mountain View, CA
`(US)
`
`( *) Notice:
`
`Subject to any disclaimer, the term of this
`patent is extended or adjusted under 35
`U.S.C. 154(b) by 0 days.
`
`(21) Appl. No.: 09/093,817
`
`(22) Filed:
`
`Jun. 8, 1998
`
`(51)
`
`Int. Cl? .............................. G06F 17/50; G06F 1!04;
`G06F 1/06; G06F 1/08
`(52) U.S. Cl. ..................................... 716/6; 703/2; 703/15;
`703/19; 716/1; 716/3; 716/5; 716/7; 716/2;
`713/500
`(58) Field of Search ................................. 703/2; 716/2, 1,
`716/3, 5, 6, 7; 713/500
`
`(56)
`
`References Cited
`
`U.S. PATENT DOCUMENTS
`4,698,760 * 10/1987 Lembach eta!. ........................ 716/6
`5,210,700 * 5/1993 Tom ......................................... 716/6
`5,282,147 * 1!1994 Goetz eta!. ............................. 716/2
`5,339,253 * 8/1994 Carrig et a!. ............................. 716/6
`
`(List continued on next page.)
`
`01HER PUBLICATIONS
`
`Krishna P. Belkhale et al., "Timing Analysis with Known
`False Sub Graphs", 1995 IEEE pp. 736-740.*
`
`(57)
`
`ABSTRACT
`
`Exceptions allow a circuit designer, working with a circuit
`synthesis system, to specify certain paths through the circuit
`to be synthesized as being subject to non-default timing
`constraints. The additional information provided by the
`exceptions can allow the synthesis system to produce a more
`optimal circuit. A tag-based timing analysis tool is
`presented, which implements exceptions, and can be used in
`a synthesis system. A circuit is analyzed in "sections," which
`comprise a set of "launch" flip flops, non-cyclic combina(cid:173)
`tional circuitry and a set of "capture" flip flops. The tag(cid:173)
`based static timing analysis of the present invention is
`performed in four main steps: preprocessing, pin-labeling,
`RF timing table propagation and relative constraint analysis.
`Preprocessing converts the exceptions written by the circuit
`designer into a certain standard form in which paths through
`the circuit to be synthesized are expressed in terms of circuit
`"pins." Pin-labeling causes the particular circuit pins, which
`are the subject of exceptions, to be marked. During RF
`timing table propagation, "RF timing tables" with rise and
`fall times are propagated onto all pins of the circuit section.
`Rise and fall times in the RF timing tables are based on
`"timing arcs" describing the delay characteristics of each of
`the state (flip flop) and combinational (logic gate) devices.
`Each RF timing table has a tag which indicates: i) a launch
`flip flop clock, and ii) the exception pins through which the
`RF timing table has propagated. During relative constraint
`analysis, each RF timing table at the input to a capture flip
`flop is analyzed for meeting certain relative constraints.
`These relative constraints may be either defaults, or the
`defaults may be modified according to an exception satisfied
`by the contents of the RF timing table's tag.
`
`(List continued on next page.)
`
`13 Claims, 22 Drawing Sheets
`
`I
`I
`10~
`
`L _______ _j
`
`Exhibit 1001 - Page 1 of 40
`
`

`

`US 6,237,127 Bl
`Page 2
`
`U.S. PATENT DOCUMENTS
`5,508,937 * 4/1996 Abato et a!. ............................. 716/6
`5,535,145 * 7/1996 Hathaway ................................ 703/2
`5,602,754 * 2/1997 Beatty eta!. ............................ 716/6
`5,615,127 * 3/1997 Beatty et a!.
`............................ 716/7
`5,636,372 * 6/1997 Hathaway et a!. ................... 713/500
`5,648,913 * 7/1997 Bennett eta!. .......................... 716/6
`5,696,694 * 12/1997 Khouja et a!. ........................... 716/5
`5,740,067 * 4/1998 Hathaway ................................ 716/6
`5,864,487 * 1!1999 Merryman et a!. ...................... 716/6
`5,910,897 * 6/1999 Dangelo et a!.
`......................... 716/1
`5,956,256 * 9/1999 Rezek et a!. ............................. 716/6
`6,014,510 * 1!2000 Burks eta!. ............................. 716/3
`
`6,023,567 * 2/2000 Osler et a!. .............................. 716/6
`
`OTHER PUBLICATIONS
`
`IBM Corporation, "Using Special Path Exclusions and
`Adjusts", Web pages of edition of Eins Timer: User's Guide
`and Reference, 4th ed., Nov. 26, 1997, 10 pages.*
`Krishna P. Belkhale et al., "Timing Analysis with Known
`False Sub Graphs", 1995 IEEE, pp. 736-740.
`IBM Corporation, "Using Special Path Exclusions and
`Adjusts", Web pages of edition of Eins Timer: User's Guide
`and Reference, Fourth Edition, Nov. 26, 1997, 10 pages.
`
`* cited by examiner
`
`Exhibit 1001 - Page 2 of 40
`
`

`

`U.S. Patent
`
`May 22,2001
`
`Sheet 1 of 22
`
`US 6,237,127 Bl
`
`100
`
`HIGH-LEVEL
`HDL
`DESIGN
`
`I
`I
`10~
`
`HDL
`COMPILER
`
`107
`
`108
`
`DESIGN
`COMPILER
`
`FINAL
`CIRCUIT
`
`USER
`ANALYSIS
`
`L - -
`
`_j
`
`FIG. 1
`
`Exhibit 1001 - Page 3 of 40
`
`

`

`U.S. Patent
`
`May 22,2001
`
`Sheet 2 of 22
`
`US 6,237,127 Bl
`
`202
`
`201
`
`200
`
`204
`
`FIG. 2A
`
`TIMING ARC 202
`
`a
`OUTPUT
`
`t
`I D1
`
`CLOCK INPUT
`204
`
`!
`
`NOT
`APPLICABLE
`
`NOT
`APPLICABLE
`
`02
`
`FIG. 28
`
`Exhibit 1001 - Page 4 of 40
`
`

`

`1--"
`~
`""-l
`N
`1--"
`"'""-l
`~
`'N
`0'1
`rJ'l
`
`e
`
`N
`N
`0 ......,
`~
`
`~ .....
`'JJ. =-
`
`~
`
`N
`~N
`N
`'-<
`~
`~
`
`'"""'
`c c
`
`~ = ......
`~ ......
`~
`•
`\Jl
`d •
`
`FIG. 3C
`
`FIG. 38
`
`DB
`
`I
`
`07
`
`I
`
`! I 06
`t I
`
`05
`
`OUTPUTC
`
`04
`
`APPLICABLE
`
`NOT
`
`APPLICABLE
`
`! NOT
`t 03
`
`OUTPUTC
`
`t INPUTA !
`
`XOR ""'
`IF GATE 300 IS
`TIMING ARC 302
`
`t INPUTA !
`
`AND OR OR ...
`IF GATE 300 IS
`TIMING ARC 302
`
`301
`
`FIG. 3A
`
`B~ _/ I
`
`c
`A~ ~~
`
`Exhibit 1001 - Page 5 of 40
`
`

`

`U.S. Patent
`
`May 22, 2001
`
`Sheet 4 of 22
`
`US 6,237,127 Bl
`
`I CLK 1}-408
`
`-+-....406
`
`402
`
`FIG. 4A
`
`CLK1
`
`~409
`
`CLK2
`
`t CLK INPUT ~
`NOT
`APPL.
`
`01
`
`02
`
`NOT
`APPL.
`
`FIG. 4B
`
`TIMING
`ARC
`403
`
`l
`Q
`OUTPUT
`~
`
`t CLK INPUT ~
`
`03
`
`04
`
`NOT
`APPL.
`
`NOT
`APPL.
`
`FIG. 4C
`
`TIMING
`ARC
`402
`
`Q
`OUTPUT
`
`l
`~
`
`Exhibit 1001 - Page 6 of 40
`
`

`

`1-"
`~
`""-l
`N
`1-"
`-..""-l
`~
`N
`-..a-..
`rJ'l
`e
`
`N
`N
`0 ......,
`Ul
`~ .....
`'JJ. =-~
`
`'"""'
`N c c
`
`~N
`N
`'-<
`~
`~
`
`~ = ......
`~ ......
`~
`•
`\Jl
`d •
`
`I 08
`
`APPLICABLE
`
`I NOT
`501
`ARC ~ INPUT B +
`TIMING
`I
`
`514
`· r!
`t APPLICABLE
`I I NOT
`t I 07
`t
`
`OUTPUT C
`
`06
`
`APPLICABLE
`
`NOT
`
`..... _1 04+08
`MINFTI 04+08
`MAXRTI 03+07 I
`MINRTI 03+07 I
`
`I
`
`U£1-UOJ
`
`I
`
`Ull\1/n'J_._n~
`
`UII\ICT
`
`MAXH I MMtUHUo,
`
`01+07
`
`MINFT
`MAXRT
`MINRT~ MINRT~
`
`I
`
`04
`03
`
`MINFT
`MAXRT
`
`02
`01
`
`1 t APPLICABLE
`
`·
`
`NOT
`
`I
`OUTPUT C
`
`MAxFTI o2 1 !AI ~ 1
`MINFT
`MAXRT
`MINRTEE--1
`
`1 ~ (
`500
`502
`
`503
`
`-.
`01
`
`INPUT A +
`1
`
`05
`
`t
`
`513\.... t
`
`502
`ARC
`TIMING
`
`Exhibit 1001 - Page 7 of 40
`
`

`

`U.S. Patent
`
`May 22, 2001
`
`Sheet 6 of 22
`
`US 6,237,127 Bl
`
`600
`
`601
`602
`
`CPU
`
`MEMORY
`
`603
`
`~604
`
`606
`
`~
`
`605
`
`FIG. 6
`
`Exhibit 1001 - Page 8 of 40
`
`

`

`U.S. Patent
`
`May 22,2001
`
`Sheet 7 of 22
`
`US 6,237,127 Bl
`
`FIGURE 7
`
`for (k = 1; k <= i; ++k) {I* LOOP1 *I
`for (q = 1; q <= tk; ++q) {I* LOOP2 *I
`
`RF_tab/ek,q' is given same tag as RF_tablek,q;
`
`01 = timing_arcJrising,rising);
`D2 = timing_arcJfalling,rising);
`
`RF_tab/ek,q'· minRT= minimum(
`01 + RF _tab/ek,q· minRT,
`D2 + RF _tablek,q· minFT);
`
`RF_tablek,q'· maxRT= maximum(
`D1 + RF_tablek,q· maxRT,
`02 + RF_tab/ek,q· maxFT);
`
`03 = timing_arck(rising,falling);
`D4 = timing_arcJfalling,falling);
`
`RF_tab/ek,q'· minFT= minimum(
`D3 + RF_tablek,q· minRT,
`D4 + RF_tablek,q· minFT);
`
`RF_tab/ek,q'· maxFT= maximum(
`D3 + RF_tab/ek,q· maxRT,
`D4 + RF _tablek,q· maxFT);
`
`} I* end LOOP2 *I
`} /* end LOOP1 *I
`
`Exhibit 1001 - Page 9 of 40
`
`

`

`U.S. Patent
`
`May 22,2001
`
`Sheet 8 of 22
`
`US 6,237,127 Bl
`
`RF _ TABLE1, 1
`
`RF-TABLE1 ,2 RF-TABLE1 ,t1
`TIMING_ARC1
`
`INPUT2 -----1------
`
`INPUT3 -~---___ _;
`
`RF _ TABLEi,2
`
`TIMING_ARCi
`
`RF _ TABLEi,ti
`
`FIG. 8
`
`Exhibit 1001 - Page 10 of 40
`
`

`

`U.S. Patent
`
`May 22,2001
`
`Sheet 9 of 22
`
`US 6,237,127 Bl
`
`FIGURE9A
`
`Identify groups of intermediate preprocessed exception statements which have
`the same timing alteration;
`
`For each such group of exception statements, produce a sum-of-products
`expression, in terms of the pin names in the path specifications, and put these
`sum-of-products expressions (along with the type of timing alteration) as items
`on a list called LIST;
`
`I* LOOP10 *I for (each ITEM on LIST)
`{
`
`SUM_ OF _PRODUCTS= get_SOP _portion(ITEM)
`TIMING_ALTERATION = get_timing_alteration(ITEM);
`factor("1", SUM_ OF _PRODUCTS, TIMING_ALTERATION);
`
`}
`
`I* Each top-level, non-recursive, call to "factor" by LOOP10 produces an
`exception statement or statements which implement REMAINDER with a timing
`alteration of type TIMING_ALTERATION *I
`void factor(PROD_2_DATE, REMAINDER, TIMING_ALTERATION)
`{
`
`Divide REMAINDER into groups of a Type 1 and put these groups on a
`list called LIST1 (Type 1 means that each product term of the group
`begins with same pin name);
`
`{Group the groups on LIST1 to produce a list called LIST2; The groups
`on LIST2 are of Type 2; A Type 2 group is one in which all of its groups of
`Type 1 have the same remainder; Taking the "remainder'' of a group of
`Type1 means removing the first pin name from each of its product terms;}
`
`I* LOOP11 *I for (each group GROUP _SR on LIST2)
`{
`
`COM_REMAINDER =the remainder common to all the groups of
`Type 1 in GROUP _SR;
`
`OR_ TERM = the sum of the pin names beginning each group of
`Type 1 in GROUP_ SR;
`
`if (COM_REMAINDER = null set then) {
`create an exception statement whose path specification
`implements the following product-of-sums:
`and(PROD_2_DATE, OR_ TERM);
`
`Exhibit 1001 - Page 11 of 40
`
`

`

`U.S. Patent
`
`May 22,2001
`
`Sheet 10 of 22
`
`US 6,237,127 Bl
`
`FIGURE 98
`
`In creating the exception statement, each "sums" term, of
`the product-of-sums, must become the argument of with the
`appropriate type of path specifier;
`
`In creating the exception statement, its timing alteration will
`be of type TIMING_ALTERATION;
`}
`
`I* else recursively call "factor" *I
`else factor( and(PROD_2_DATE, OR_ TERM),
`COM_REMAINDER, TIMING_AL TERATION);
`
`} I* end LOOP11 *I
`
`} I* end "factor"*/
`
`Exhibit 1001 - Page 12 of 40
`
`

`

`U.S. Patent
`
`May 22,2001
`
`Sheet 11 of 22
`
`US 6,237,127 Bl
`
`FIGURE 9C
`
`Input exceptions statements from circuit designer:
`set_ false _path -from { Z Q} -through { A T } -to { B G }
`set_ false _path -through {0 E} -through H
`set_mufticycfe_path -through {T G} -through F
`
`Intermediate preprocessed exception statements:
`set_false_path -from Z -through A -to B
`set_ false _path -from Z -through A -to G
`set_false_path -from Z -through T -to B
`set_ false _path -from Z -through T -to G
`set_ false _path -from Q -through A -to B
`set_ false _path -from Q -through A -to G
`set_false_path -from Q -through T -to B
`set_false_path -from Q -through T -toG
`set_false_path -through 0 -through H
`set_false _path -through E -through H
`set_multicycle_path -through T -through F
`set_multicycle_path -through G -through F
`
`Identify groups of intermediate preprocessed exception statements with same
`timing alteration:
`group1:
`set_false_path -from Z -through A -to B
`set_false_path -from Z -through A -toG
`set_false_path -from Z -through T -to B
`set_false_path -from Z -through T -toG
`set_ false _path -from Q -through A -to B
`set_ false _path -from Q -through A -to G
`set_false_path -from Q -through T -to B
`set_false_path -from Q -through T -toG
`set_ false _path -through 0 -through H
`set_false_path -through E -through H
`
`group2:
`set_multicycle_path -through T -through F
`set_multicycle_path -through G -through F
`
`Produce sum-of-products expressions:
`LIST= { "set_false_path", {ZAB +ZAG+ ZTB + ZTG + QAB + QAG + QTB +
`QTG + OH + EH} }, { "set_multicycle_path", {TF + GF} }
`
`Exhibit 1001 - Page 13 of 40
`
`

`

`U.S. Patent
`
`May 22,2001
`
`Sheet 12 of 22
`
`US 6,237,127 Bl
`
`FIGURE SO
`
`LOOP10. iteration 1:
`ITEM = { "set_false_path", {ZAB +ZAG + ZTB + ZTG + QAB + QAG + QTB +
`QTG + DH + EH}}
`
`SUM_ OF _PRODUCTS= ZAB +ZAG+ ZTB + ZTG + QAB + QAG + QTB + QTG
`+ DH + EH
`
`TIMING_ALTERATION = "set_false_path"
`
`"factor" is called with the following arguments:
`REMAINDER = ZAB + ZAG + ZTB + ZTG + QAB + QAG + QTB + QTG +
`DH+EH
`
`PROD 2 DATE= 1
`
`TIMING ALTERATION= "set_false_path"
`
`LIST1 contains four groups of Type 1:
`LIST1 = { {ZAB + ZAG + ZTB + ZTG} + {QAB + QAG + QTB + QTG} +
`{DH} + {EH} }
`
`LIST2 contains two groups of Type 2:
`LIST2 = {
`
`{ {ZAB + ZAG + ZTB + ZTG} + {QAB + QAG + QTB + QTG}}
`+
`{ {DH} + {EH} }
`
`}
`
`LOOP11. iteration 1 :
`GROUP _SR = { {ZAB +ZAG+ ZTB + ZTG} + {QAB + QAG + QTB + QTG}}
`
`COM_REMAINDER = {AB + AG + TB + TG}
`
`OR_ TERM = (Z + Q)
`
`Exhibit 1001 - Page 14 of 40
`
`

`

`U.S. Patent
`
`May 22,2001
`
`Sheet 13 of 22
`
`US 6,237,127 Bl
`
`FIGURE9E
`
`"factor" is called recursively with the following arguments:
`REMAINDER = {A8 + AG + T8 + TG}
`
`PROD_2_DATE = 1 * (Z + Q)
`
`TIMING_ALTERATION = "set_false_path"
`
`LIST1 contains two groups of Type 1:
`LIST1 = { {A8 + AG} + {T8 + TG} }
`
`LIST2 contains one group of Type 2:
`LIST2 = { { {A8 + AG} + {T8 + TG} } }
`
`LOOP11 (of 1st recursion). iteration 1:
`GROUP _SR = { {AB + AG} + {T8 + TG}}
`
`COM_REMAINDER = {8 + G}
`
`OR_ TERM= (A+ T)
`
`"factor" is called recursively, for 2nd time. with the following arguments:
`REMAINDER = {8 + G}
`
`PROD_2_DATE = 1 * (Z + Q) *(A+ T)
`
`TIMING_ALTERATION = "set_false_path"
`
`LIST1 contains two groups of Type 1:
`LIST1 = { {8} + {G} }
`
`LIST2 contains one group of Type 2 (share null set as common remainder):
`LIST2 = { {{B} + {G}} }
`
`Exhibit 1001 - Page 15 of 40
`
`

`

`U.S. Patent
`
`May 22,2001
`
`Sheet 14 of 22
`
`US 6,237,127 Bl
`
`FIGURE 9F
`
`LOOP11 (of 2nd recursion), iteration 1:
`GROUP_ SR = {{8} + {G}}
`
`COM_REMAINDER = { }
`
`OR_TERM = (8 +G)
`
`create an exception statement, with a "set_false_path" timing alteration, whose
`path specification implements the following product of sums:
`1 * (Z + Q) * (A + T) * (8 + G)
`
`LOOP11 (of 2nd recursion) ends and 2nd recursion of "factor" returns to 1st
`recursion of "factor"
`
`LOOP11 (of 1st recursion) ends and 1st recursion of "factor" returns to "factor"
`
`LOOP11, iteration 2:
`GROUP_ SR = { {DH} + {EH} }
`
`COM_REMAINDER = {H}
`OR_ TERM = (0 + E)
`
`"factor" is called recursively for 3rd time with the following arguments:
`REMAINDER = {H}
`
`PROD_2_DATE = 1 * (D +E)
`
`TIMING_AL TERATION = "set_false_path"
`
`LIST1 contains one group of Type 1:
`LIST1 = { {H} }
`
`LIST2 contains one group of Type 2:
`LIST2 = { { {H}} }
`
`Exhibit 1001 - Page 16 of 40
`
`

`

`U.S. Patent
`
`May 22,2001
`
`Sheet 15 of 22
`
`US 6,237,127 Bl
`
`FIGURE 9G
`
`LOOP11 (of 3rd recursion). iteration 1:
`GROUP _SR = { {H}}
`COM_REMAINDER = {}
`
`OR TERM=H
`
`create an exception statement, with a "set_false_path" timing alteration, whose
`path specification implements the following product of sums:
`1 * (D +E)* H
`
`LOOP11 (of 3rd recursion) ends and 3rd recursive call of "factor" returns to
`"factor"
`
`LOOP11 ends and call of "factor" returns
`
`LOOP10. iteration 2:
`ITEM= { "set_multicycle_path", {TF + GF} }
`
`TIMING _ALTERATION = "set_multicycle _path"
`
`SUM OF PRODUCTS = TF + GF
`
`"factor" is called with the following arguments:
`REMAINDER = TF + GF
`
`PROD 2 DATE= 1
`TIMING_ALTERATION = "set_multicycle_path"
`
`In a like manner to that described above, "factor" proceeds to find the
`product-of-sums "1 * (T + G) * F ,"and creates an exception statement,
`with a "set_multicycle_path 2" timing alteration, whose path specification
`implements "1 * (T +G)* F."
`
`Exhibit 1001 - Page 17 of 40
`
`

`

`U.S. Patent
`
`May 22,2001
`
`Sheet 16 of 22
`
`US 6,237,127 Bl
`
`FIGURE 10
`
`Identify groups of intermediate preprocessed exception statements which have
`the same timing alteration;
`
`For each such group of exception statements, produce a sum-of-products
`expression, in terms of the pin names in the path specifications, and put these
`sum-of-products expressions on a list called LIST;
`
`I* LOOP12 *I for (each SUM_ OF _PRODUCTS on LIST)
`{
`
`TIMING_ALTERATION = get_timing_alteration(SUM_OF _PRODUCTS);
`factor_order_indep(SUM_OF _PRODUCTS, TIMING_ALTERATION);
`
`}
`
`I* Each top-level call to "factor_order_indep" by LOOP12 produces an exception
`statement or statements which implement SUM_ OF _PRODUCTS with a timing
`alteration of type TIMING_ALTERATION */
`void factor_order_indep(SUM_OF _PRODUCTS, TIMING_ALTERATION)
`{
`
`Use standard multi-level logic boolean equation manipulation algorithms
`to convert SUM_OF _PRODUCTS into a LIST of"possible solutions,"
`where a "possible solution" is a logically equivalent form of
`SUM_OF _PRODUCTS which is in the form of a sum of a product-of-sums
`(such boolean equation manipulation algorithms include those resulting
`from the multi-level logic optimization system of the late 1980's entitled
`"MIS," from the University of California, Berkeley, Department of Electrical
`Engineering and Computer Science, by R. Brayton, et al.);
`
`For each possible solution count the total number of "sums" amongst all of
`its product-of-sums and call this value, for each possible solution, its
`"metric;"
`
`Choose as the "solution" the possible solution with the smallest metric
`since a smaller metric means that exception pins will be indicated with a
`smaller number of different labels;
`
`For each product-of-sums in the chosen solution, create an exception
`statement, with a timing alteration of type TIMING_ALTERATION, and
`being sure that each "sums" in a product-of-sums becomes the argument
`of the appropriate path specifier;
`
`} I* end "factor_order_indep" */
`
`Exhibit 1001 - Page 18 of 40
`
`

`

`1--"
`~
`""-l
`N
`1--"
`-..""-l
`~
`N
`-..a-..
`rJ'l
`e
`
`N
`N
`0 ......,
`'"""'
`-..J
`~ .....
`'JJ. =(cid:173)~
`
`'"""'
`N c c
`
`~N
`N
`'-<
`~
`~
`
`~ = ......
`~ ......
`~
`•
`\Jl
`d •
`
`I x2 I I X~, I
`
`x1 1
`
`11tiCLK1I112alclK11
`
`1116
`
`L2
`
`CLK1
`
`1101 -
`
`CLK1
`
`I
`
`1100
`
`~
`x1,
`
`x2
`
`x1
`
`I CLK1 I I CLK1 II CLK1 II CLK111 CLK1
`
`1125~ 1127~ 1136~ 1137, 1138~139,
`
`x2
`
`~
`x1 ,
`CLK1
`
`' ... '
`'
`
`Exhibit 1001 - Page 19 of 40
`
`

`

`1--"
`~
`""-l
`N
`1--"
`"'""-l
`~
`'N
`0'1
`rJ'l
`
`e
`
`N
`N
`0 ......,
`'"""' 00
`~ .....
`'JJ. =-~
`
`'"""'
`N c c
`
`~N
`N
`'-<
`~
`~
`
`~ = ......
`~ ......
`~
`•
`\Jl
`d •
`
`1224
`
`1223
`
`FIG. 12
`
`~103
`
`' CLK3
`
`.-------.
`
`L...---1
`
`llU~/
`
`...____..
`-~ 1
`
`t----1
`
`x6
`
`1201
`\
`
`x5
`
`'1200
`
`I L.A.J -11 02
`
`V
`
`I I \XJ
`
`I I \X~.
`
`I
`
`II yJu~"
`
`1206 ICLK1
`
`\.....
`
`,--I
`
`X4
`
`-~-~~"7 I
`I
`
`,
`)
`
`L2
`
`CLK1
`1101'IAI
`
`1100' 4-J Ll
`
`CLK1
`
`1219
`
`1212
`
`1204
`
`Exhibit 1001 - Page 20 of 40
`
`

`

`U.S. Patent
`
`May 22, 2001
`
`Sheet 19 of 22
`
`US 6,237,127 Bl
`
`L2
`
`CLK1
`
`---/---
`
`;
`
`CLK3
`
`'
`,
`'
`C2[ 1] -:!--' ---.---......;.,...' -
`C2[2]
`,
`! ...
`
`\
`
`I
`
`:
`
`-1307
`
`1314
`
`~
`1318
`.--C:-:-L-:-~-:-K 1__, • • • t---=-=~
`L1 [1]
`
`1319
`
`1321
`
`FIG.13
`
`Exhibit 1001 - Page 21 of 40
`
`

`

`U.S. Patent
`
`May 22, 2001
`
`Sheet 20 of 22
`
`US 6,237,127 Bl
`
`'-;
`L1
`
`32
`
`CLK1
`
`L2
`
`CLK2 1303
`
`FIG.14
`
`Exhibit 1001 - Page 22 of 40
`
`

`

`U.S. Patent
`
`May 22,2001
`
`Sheet 21 of 22
`
`US 6,237,127 Bl
`
`FIGURE 15
`
`Input exceptions statements from circuit designer:
`set_ false _path -from { Z Q} -through { A * {B + C} } -to Y
`
`Convert "-through" to sum-of-products:
`set_ false _path -from { Z Q} -through { A *B + A *C} -to Y
`
`Determine cross product:
`set_ false _path -from Z -through {A *B} -to Y
`set_false_path -from Z -through {A*C} -toY
`set_false_path -from Q -through {A*B} -toY
`set_false_path -from Q -through {A*C} -toY
`
`Substitute single-pin "-through"s for products to produce intermediate
`preprocessed exception statements:
`set_false_path -from Z -through A -through B -toY
`set_false_path -from Z -through A -through C -toY
`set_false_path -from Q -through A -through B -toY
`set_false_path -from Q -through A -through C -toY
`
`Exhibit 1001 - Page 23 of 40
`
`

`

`U.S. Patent
`
`May 22,2001
`
`Sheet 22 of 22
`
`US 6,237,127 Bl
`
`FIGURE 16
`
`Preprocessed exception statements resulting from second-way preprocessing:
`set_false_path -through {Q + Z} -through {A+ 1} -through {8 + G}
`set_false_path -through {N + M} -through {B + G}
`
`Pattern-matching higher-level exception statements:
`set_false_path -through { {Q + Z}*{A + 1} + {N + M}} -through {8 + G}
`
`Exhibit 1001 - Page 24 of 40
`
`

`

`US 6,237,127 Bl
`
`1
`STATIC TIMING ANALYSIS OF DIGITAL
`ELECTRONIC CIRCUITS USING NON(cid:173)
`DEFAULT CONSTRAINTS KNOWN AS
`EXCEPTIONS
`
`FIELD OF THE INVENTION
`
`5
`
`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 excep- 10
`tions.
`
`2
`The static tlmmg 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 combinational logic connected together, at
`their pins, by wire objects.
`The tag -based static timing analysis of the present
`invention, implementing exceptions statements, is per(cid:173)
`formed 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 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 analy-
`SIS.
`For a second-way of implementing exception statements,
`these four steps are referred to as: second-way
`preprocessing, second-way pin-labeling, second-way modi(cid:173)
`fied 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 prepro(cid:173)
`cessed exceptions statements which has their path specifi(cid:173)
`cations 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 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.
`In pin-labeling, the pins of the circuit network, specifi(cid:173)
`cally 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 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 the argument container is attached. The
`purpose of a label is to provide a data item which can be
`matched against the argument 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 is put
`in the argument container. For those path specifier argu(cid:173)
`ments 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 devices are represented by "timing arcs." For
`the purposes of the set of launch flip flops, we are interested
`
`15
`
`20
`
`25
`
`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 such circuits, particu(cid:173)
`larly 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 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 30
`devices or sequential logic which store data upon application
`of a clock signal, and ii) combinational logic. The state
`devices typically act as either: i) an interface between
`conceptually distinct circuit systems, or ii) storage for the
`results of functional evaluation performed by the combina- 35
`tional logic.
`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 40
`reasons, it would be useful to apply, as efficiently as
`possible, static timing analysis to the synthesis process.
`
`SUMMARY OF THE INVENTION
`The present invention may be used in the hardware 45
`synthesis environment known as the "Design Compiler
`shell" produced by Synopsys, Inc., of Mountain View, Calif.
`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. 50
`This is because exceptions allow the designer, for example,
`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 55
`for further analysis, by the designer, of the final circuit netlist
`produced by Design Compiler.
`Exceptions are specified by the circuit designer as indi(cid:173)
`vidual syntactic units called "exception statements" which
`are comprised of a "timing alteration" and a "path specifi- 60
`cation." 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 specifica(cid:173)
`tion. The path specification consists of one or more "path
`specifiers," with each path specifier taking an" argument." In 65
`order for a path specification to be satisfied, each argument
`of each of its path specifiers must be satisfied.
`
`Exhibit 1001 - Page 25 of 40
`
`

`

`US 6,237,127 Bl
`
`3
`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 and s
`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), maxi(cid:173)
`mum rise time (maxRT), minimum fall time (minFT) and 10
`maximum fall time (maxFT). RF timing tables each have
`their own "tag" which, in accordance with the present
`invention, has two parts: i) a first 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" 15
`(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 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 indi(cid:173)
`eating the particular clock driving the clock input of the flip
`flop for which the RF timing table is being created.
`At this point, first-way modified RF timing table propa(cid:173)
`gation 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 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 35
`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 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 com(cid:173)
`binational unit, is modified, according to the timing arc
`associated with that input, to produce a temporary RF timing
`table pointed to by 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 to produce a final RF timing
`table.
`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 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, second-way modified RF timing table propa(cid:173)
`gation checks to see if the output pin of the combinational 65
`unit has an argument container. If the argument container
`exists, then each label in it is considered for possible
`
`4
`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, or can possibly satisfy, a
`path specification of at least one of the preprocessed excep-
`tion 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 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 refer to 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 the wire across which it has