ELEC 7770 Advanced VLSI Design Spring 2012 Timing Verification and OptimizationProof of CorrectnessFalse and True PathsStatic Sensitization of PathAn ExampleExample (Cont.)Slide 7Static Sensitization ConditionAn ATPG MethodOptimism and PessimismTheorem 1Theorem 2Proof of Theorem 2Proof of Theorem 2 (Cont.)Slide 15Speeding Up a CircuitSlide 17Slide 18Slide 19A Delay Optimization AlgorithmExample of a Transformation (1)Example of a Transformation (2)Example of a Transformation (3)32-bit Ripple-Carry AdderOne-bit Full-Adder CircuitSpeeding Up the AdderSpring 2012, Feb 6 . . .Spring 2012, Feb 6 . . .ELEC 7770: Advanced VLSI Design (Agrawal)ELEC 7770: Advanced VLSI Design (Agrawal)11ELEC 7770ELEC 7770Advanced VLSI DesignAdvanced VLSI DesignSpring 2012Spring 2012 Timing Verification and OptimizationTiming Verification and OptimizationVishwani D. AgrawalVishwani D. AgrawalJames J. Danaher ProfessorJames J. Danaher ProfessorECE Department, Auburn University, Auburn, AL 36849ECE Department, Auburn University, Auburn, AL [email protected]@eng.auburn.eduhttp://www.eng.auburn.edu/~vagrawal/COURSE/E7770_Spr12/course.htmlhttp://www.eng.auburn.edu/~vagrawal/COURSE/E7770_Spr12/course.htmlSpring 2012, Feb 6 . . .Spring 2012, Feb 6 . . .ELEC 7770: Advanced VLSI Design (Agrawal)ELEC 7770: Advanced VLSI Design (Agrawal)22Proof of CorrectnessProof of CorrectnessStatic timing analysis proves the timing Static timing analysis proves the timing correctness. That is, the circuit is guaranteed to correctness. That is, the circuit is guaranteed to work at the clock rate determined by the critical work at the clock rate determined by the critical path.path.But the circuit may also work correctly at faster But the circuit may also work correctly at faster speeds.speeds.Because the critical path identified by STA (static Because the critical path identified by STA (static timing analysis) may be a “false path”.timing analysis) may be a “false path”.STA overestimates the delay of the circuit.STA overestimates the delay of the circuit.Spring 2012, Feb 6 . . .Spring 2012, Feb 6 . . .ELEC 7770: Advanced VLSI Design (Agrawal)ELEC 7770: Advanced VLSI Design (Agrawal)33False and True PathsFalse and True PathsA false path cannot propagate an event and hence A false path cannot propagate an event and hence cannot affect the timing of the circuit. False paths are cannot affect the timing of the circuit. False paths are dynamically unsensitizable.dynamically unsensitizable.Dynamically sensitizable path (true path): All off-path Dynamically sensitizable path (true path): All off-path inputs must settle down to their non-controlling values inputs must settle down to their non-controlling values when the event propagates through the path.when the event propagates through the path.1zyabcdef112340101 11True path of length 4True path of length 3Spring 2012, Feb 6 . . .Spring 2012, Feb 6 . . .ELEC 7770: Advanced VLSI Design (Agrawal)ELEC 7770: Advanced VLSI Design (Agrawal)44Static Sensitization of PathStatic Sensitization of PathStatic sensitization of path: All off-path inputs can be Static sensitization of path: All off-path inputs can be simultaneously set to their non-controlling values.simultaneously set to their non-controlling values.Longest path in the following example is statically Longest path in the following example is statically unsensitizable. Such paths are often referred to, though unsensitizable. Such paths are often referred to, though not correctly (why?),not correctly (why?), as false paths.as false paths.1zyabd ef112301False path of length 4True path of length 31111Spring 2012, Feb 6 . . .Spring 2012, Feb 6 . . .ELEC 7770: Advanced VLSI Design (Agrawal)ELEC 7770: Advanced VLSI Design (Agrawal)55An ExampleAn ExampleStatically unsensitizable (false) path.Statically unsensitizable (false) path.P. C. McGeer and R. K. Brayton, P. C. McGeer and R. K. Brayton, Integrating Integrating Functional and Temporal Domains in Logic Functional and Temporal Domains in Logic DesignDesign, Springer, 1991., Springer, 1991.gabdef0011c1False path of delay 3110Spring 2012, Feb 6 . . .Spring 2012, Feb 6 . . .ELEC 7770: Advanced VLSI Design (Agrawal)ELEC 7770: Advanced VLSI Design (Agrawal)66Example (Cont.)Example (Cont.)Another statically unsensitizable false path.Another statically unsensitizable false path.P. C. McGeer and R. K. Brayton, P. C. McGeer and R. K. Brayton, Integrating Integrating Functional and Temporal Domains in Logic Functional and Temporal Domains in Logic DesignDesign, Springer, 1991., Springer, 1991.gabdef1011c1Two false paths of delay 3100Spring 2012, Feb 6 . . .Spring 2012, Feb 6 . . .ELEC 7770: Advanced VLSI Design (Agrawal)ELEC 7770: Advanced VLSI Design (Agrawal)77Example (Cont.)Example (Cont.)Two paths are dynamically sensitizable and will affect the Two paths are dynamically sensitizable and will affect the timing if both are together faulty.timing if both are together faulty.P. C. McGeer and R. K. Brayton, P. C. McGeer and R. K. Brayton, Integrating Functional and Integrating Functional and Temporal Domains in Logic DesignTemporal Domains in Logic Design, Springer, 1991., Springer, 1991.gabdef011c1False paths of delay 312 3Spring 2012, Feb 6 . . .Spring 2012, Feb 6 . . .ELEC 7770: Advanced VLSI Design (Agrawal)ELEC 7770: Advanced VLSI Design (Agrawal)88Static Sensitization ConditionStatic Sensitization ConditionOff-path inputsxyzThere must exist an input vector (PI) that satisfies the following conditions:∂y/∂x = 1,∂z/∂y = 1, . . .Where ∂y/∂x = y(x=1, PI)  y(x=0, PI) is Boolean differenceSpring 2012, Feb 6 . . .Spring 2012, Feb 6 . . .ELEC 7770: Advanced VLSI Design (Agrawal)ELEC 7770: Advanced VLSI Design (Agrawal)99An ATPG MethodAn ATPG MethodxyzStuck-at-0Path is false if this fault is redundantSpring 2012, Feb 6 . . .Spring 2012, Feb 6 . . .ELEC 7770: Advanced VLSI Design (Agrawal)ELEC 7770: Advanced VLSI Design (Agrawal)1010Optimism and PessimismOptimism and PessimismDynamicallysensitizablepathsStaticallysensitizablePaths(optimistic)Structural paths analyzed by STA (pessimistic)Spring 2012, Feb 6 . . .Spring 2012, Feb 6 . . .ELEC 7770: Advanced VLSI Design (Agrawal)ELEC 7770: Advanced VLSI Design (Agrawal)1111Theorem 1Theorem 1Every statically sensitizable path is dynamically Every statically sensitizable path is dynamically sensitizable.sensitizable.Proof: Since a vector exists to sensitize the path,