loading...
Graph Transformations for Improved Tree Height Reduction
New Delhi, India January 04-January 08
DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/ICVD.2003.118317916th International Conference on VLSI ...
 This Article 
 
PDF
HTML
 
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
G.N. Mangalam, Cadence Design Systems
Sanjiv Narayan, Cadence Design Systems
Paul van Besouw, Cadence Design Systems
LaNae Avra, Cadence Design Systems
Anmol Mathur, Cadence Design Systems
Sanjeev Saluja, Cadence Design Systems
Tree height reduction helps in minimizing the critical path delay and area in datapath rich designs during synthesis. We introduce in this paper, the necessary conditions to identify height reducible arithmetic expressions and three graph transformations that make Tree Height Reduction more efficient: (a) Bit-width matching - a technique in which input signals that match in their bit-widths are grouped together so that smaller width arithmetic nodes are created in the graph. (b) Carry / Borrow Optimization - a graph transformation by which an optimum number of single bit inputs are distributed as carry / borrow to the add / subtract nodes in the graph. (c) Constant grouping - a graph transformation in which constant inputs are grouped together to form a sub-tree of constants. Experiments on industrial designs with these graph transformations coupled with Tree Height Reduction have shown significant improvement in critical path delay and area.
Citation:
G.N. Mangalam, Sanjiv Narayan, Paul van Besouw, LaNae Avra, Anmol Mathur, Sanjeev Saluja, "Graph Transformations for Improved Tree Height Reduction," vlsid, pp.474, 16th International Conference on VLSI Design, 2003
Usage of this product signifies your acceptance of the Terms of Use.


Suggestions