A new approach to constructing optimal parallel prefix circuits with small depth |
| |
Affiliation: | 2. International Medical College, Münster, Germany |
| |
Abstract: | Parallel prefix circuits are parallel algorithms performing the prefix operation for the combinational circuit model. The size of a prefix circuit is the number of operation nodes in the circuit, and the depth is the maximum level of operation nodes. A circuit with n inputs is depth-size optimal if its depth plus size equals 2n−2. Smaller depth implies faster computation, while smaller size implies less power consumption, smaller VLSI area, and less cost. A circuit should have a small fan-out and small depth for it to be of practical use. In this paper, we present a new approach to easing the design of parallel prefix circuits, and construct a depth-size optimal parallel prefix circuit, named WE4, with fan-out 4. In many cases of n, WE4 has the smallest depth among all known depth-size optimal prefix circuits with bounded fan-out. |
| |
Keywords: | |
本文献已被 ScienceDirect 等数据库收录! |
|