2020/12/10 by Brenner, Ulrich, Hermann, Anna, Silvanus, Jannik
#68R01 #68W35 #94C99 #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #Hardware Architecture (cs.AR)
paper · doi:10.48550/arxiv.2012.05550
We examine the fundamental problem of constructing depth-optimum circuits for binary addition. More precisely, as in literature, we consider the following problem: Given auxiliary inputs t0, \dotsc, tm-1, so-called generate and propagate signals, construct a depth-optimum circuit over the basis AND2, OR2 computing all n carry bits of an n-bit adder, where m=2n-1. In fact, carry bits are AND-OR paths, i.e., Boolean functions of the form t0 ∨ ( t1 ∧ (t2 ∨ ( … tm-1) … )). Classical approaches construct so-called prefix circuits which do not achieve a competitive depth. For instance, the popular construction by Kogge and Stone is only a 2-approximation. A lower bound on the depth of any prefix circuit is 1.44 log2 m + const, while recent non-prefix circuits have a depth of log2 m + log2 log2 m + const. However, it is unknown whether any of these polynomial-time approaches achieves the optimum depth for all m. We present a new exponential-time algorithm solving the problem optimally. The previously best exact algorithm with a running time of \mathcal O(2.45m) is viable only for m ≤ 29. Our algorithm is significantly faster: We achieve a running time of \mathcal O(2.02m) and apply sophisticated pruning strategies to improve practical running times dramatically. This allows us to compute optimum circuits for all m ≤ 64. Combining these computational results with new theoretical insights, we derive the optimum depths of 2k-bit adder circuits for all k ≤ 13, previously known only for k ≤ 4. In fact, we solve a more general problem occurring in VLSI design: delay optimization of a generalization of AND-OR paths where AND and OR do not necessarily alternate. Our algorithm arises from our new structure theorem which characterizes delay-optimum generalized AND-OR path circuits.