Graph transformations for improved tree height reduction

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; and (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.