10-05-2013, 04:27 PM
Timing Optimization
Timing Optimization.ppt (Size: 187.5 KB / Downloads: 40)
Problem Statement
Given:
Initial circuit function description
Library of primitive functions
Performance constraints (arrival/required times)
Generate:
an implementation of the circuit using the primitive functions, such that:
performance constraints are met
circuit area is minimized
Overview of Solutions for Delay
Circuit re-structuring
(technology mapping)
SelectioRescheduling operations to reduce time of computation
Implementation of function trees n of gates from library
Minimum delay (load independent model - Kukimoto)
Minimize delay and area (Jongeneel, DAC’00)
(combines Lehman-Watanabe and Kukimoto)
Implementation of buffer trees
Touati (LT-trees)
Singh
Resizing
Constant delay synthesis
Restructuring Methods
Performance measured by
levels,
sensitizable paths,
technology dependent delays
Level based optimizations:
Tree height reduction (Singh ‘88)
Partial collapsing and simplification (Touati ‘91)
Generalized select transform (Berman ‘90)
Sensitizable paths
Generalized bypass transform (McGeer ‘91)
Technology Independent Delay Reductions
Generally THR, GBX, GST (critical path based methods) work OK,
but very greedy and computationally expensive
Why are technology independent delay reductions hard?
Lack of fast and accurate delay models
# levels, fast but crude
# levels + correction term (fanout, wires,… ): a little better, but still crude (what coefficients to use?)
Technology mapped: reasonable, but very slow
Place and route: better but extremely slow
Silicon: best, but infeasibly slow (except for FPGAs)
Conclusions
Variety of methods for delay optimization
No single technique dominates
When applied to ripple-carry adder get
Carry-lookahead adder (THR)
Carry-bypass adder (GBX)
Carry-select adder (GST)
Clustering/Partial collapse
All techniques ignore false paths when assessing the delay and critical regions
Can use KMS transform to eliminate false paths without increasing delay (Caveat: potentially large increase in area)