论文标题
构造加盖器和和或路径的深度最高电路
Constructing Depth-Optimum Circuits for Adders and AND-OR Paths
论文作者
论文摘要
我们研究了为二进制添加构建深度电路的基本问题。更准确地说，与文献一样，我们考虑以下问题：给定辅助输入$ t_0，\ dotsc，t_ {m-1} $，所谓的生成和传播信号，在基础上构建一个深度 - 上的电路{and2，or2}计算所有$ n $ n $ n $ n $ - $ - $ -BIT $ -BIT ADDER，$ m = 2n $ n $ n $ n $ n $ n $ m = 2n。实际上，随身携带的位是和或路径，即形式的布尔函数$ t_0 \ lor（t_1 \ land（t_2 \ lor（\ dots t_ {m-1}）\ dots））$。经典方法构建了未达到竞争深度的所谓前缀电路。例如，Kogge and Stone的流行建筑仅是$ 2 $ approximation。任何前缀电路深度的下限为$ 1.44 \ log_2 m $ + const，而最近的非前缀电路的深度为$ \ log_2 m $ + $ + $ \ log_2 \ log_2 \ log_2 m $ $ + const。但是，尚不清楚这些多项式时间方法是否可以达到所有$ m $的最佳深度。 我们提出了一种新的指数时间算法，以最佳的方式解决该问题。以前最佳的精确算法（2.45^m）$的运行时间仅适用于$ M \ leq 29 $。我们的算法要快得多：我们达到了$ \ Mathcal O（2.02^m）$的运行时间，并应用复杂的修剪策略来大大提高实际运行时间。这使我们能够计算所有$ M \ leq 64 $的最佳电路。将这些计算结果与新的理论见解相结合，我们得出了所有$ k \ leq 13 $的最佳深度$ 2^k $ -bit加法电路，以前仅以$ k \ leq 4 $而闻名。 实际上，我们解决了VLSI设计中发生的更一般的问题：$ delay $优化$和或不一定要替代的$ pressional $ and-or path。我们的算法来自我们的新结构定理，该定理表征了延迟最佳的通用和或路径电路。
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 $t_0, \dotsc, t_{m-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 $t_0 \lor ( t_1 \land (t_2 \lor ( \dots t_{m-1}) \dots ))$. 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 \log_2 m$ + const, while recent non-prefix circuits have a depth of $\log_2 m$ + $\log_2 \log_2 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.45^m)$ is viable only for $m \leq 29$. Our algorithm is significantly faster: We achieve a running time of $\mathcal O(2.02^m)$ and apply sophisticated pruning strategies to improve practical running times dramatically. This allows us to compute optimum circuits for all $m \leq 64$. Combining these computational results with new theoretical insights, we derive the optimum depths of $2^k$-bit adder circuits for all $k \leq 13$, previously known only for $k \leq 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.
