A depth-decreasing heuristic for combinational logic: or how to convert a ripple-carry adder into a carry-lookahead adder or anything in-between
A depth-decreasing heuristic for combinational logic: or how to convert a ripple-carry adder into a carry-lookahead adder or anything in-between
复制标题
组合逻辑的深度递减启发式：或者如何将行波进位加法器转换为超前进位加法器或介于两者之间的任何东西
DOI：
10.1145/123186.123305
复制
发表时间：
1990
期刊：
影响因子：
--
通讯作者：
J. Fishburn
中科院分区：
文献类型：
--
作者：
J. Fishburn
本文描述了一种通过降低逻辑深度来加速组合逻辑的启发式方法，其代价是电路规模有极小的增加。该启发式方法通过对延迟输入使用香农分解，迭代地加速关键路径的各个部分。经验发现，这一过程能够重现甚至超越几种经典的全局优化：将一个关联运算符链转换为一棵树，将一个行波前缀电路转换为一个并行前缀电路，以及将一个行波进位加法器转换为一个比超前进位加法器略小且更快的电路。
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 iteratively speeds up sections of the critical path 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.