Faster Circuits for And-Or Paths and Binary Addition

Abstract

We consider the problem of constructing fast circuits both for binary addition and And-Or paths. And-Or paths are Boolean functions of the form <em>t</em>₀ &and; ( <em>t</em>₁ &or; ( <em>t</em>₂ &and; ( <em>t</em>₃ &or; ... ))) that occur, e.g., as carry bits in adder circuits and as critical paths on computer chips. Motivated by the application in chip design, we aim at optimizing circuit depth or circuit delay, a natural generalization of depth to prescribed input arrival times.<br /> We significantly improve the best known upper bounds on the optimum delay and depth of adder and And-Or path circuits. For instance, regarding adder circuits where the number of gates is linear in the number <em>n</em> of inputs, we reduce the gap to the best known lower bound from O(&radic;<span style="border-top: 1px solid #000000; font-size: 14px;">log₂ <em>n</em></span>) to O(log₂log₂log₂<em>n</em>).<br /> Moreover, we develop an exact algorithm for delay optimization of generalized And-Or paths, a generalization of And-Or paths where &and; and &or; do not necessarily alternate. For the general problem, our algorithm is the first known exact approach; for the special case of depth optimization of And-Or paths, our algorithm is both theoretically and empirically drastically faster than all previous exact algorithms.<br /> Finally, we present an algorithm for delay optimization of And-Or paths that fulfills the best known delay guarantee and computes optimum solutions on almost all practical instances. We demonstrate the successful application of this algorithm in BonnLogic, a logic optimization tool that is used to optimize critical paths during the chip design flow of IBM.