A Depth-Decreasing Heuristic for Combinational Logic; or How to Convert a Ripple-Carry Adder into a Carry-Lookahead Adder or Anything in Between.

This paper describes a heuristic for speeding up combinational logic by decreasing the logic depth, at the expense of a minimal increase in circuit size. The heuristic operates by iteratively identifying sections of the critical path for resynthesis, which are speeded up by the use of Shannon factorization on the late input. This procedure is empirically found to be capable of reproducing or even beating several classic global optimizations: A chain of an associative operator is transformed into a tree, a ripple prefix circuit into a parallel prefix circuit, and a ripple-carry adder into a slightly smaller and faster circuit than the carry-lookahead adder.