A New Class of Depth-Size Optimal Parallel Prefix Circuits |
| |
Authors: | Lin Yen-Chun Shih Chao-Cheng |
| |
Affiliation: | (1) Department of Electronic Engineering, National Taiwan University of Science and Technology, P.O. Box 90-100, Taipei, 106, Taiwan |
| |
Abstract: | Given n values x1, x2, ... ,xn and an associative binary operation o, the prefix problem is to compute x1 o x2 o ··· o xi, 1 i n. Many combinational circuits for solving the prefix problem, called prefix circuits, have been designed. It has been proved that the size s(D(n)) and the depth d(D(n)) of an n-input prefix circuit D(n) satisfy the inequality d(D(n))+s(D(n)) 2n–2; thus, a prefix circuit is depth-size optimal if d(D(n))+s(D(n))=2n–2. In this paper, we construct a new depth-size optimal prefix circuit SL(n). In addition, we can build depth-size optimal prefix circuits whose depth can be any integer between d(SL(n)) and n–1. SL(n) has the same maximum fan-out lg n +1 as Snir's SN(n), but the depth of SL(n) is smaller; thus, SL(n) is faster. Compared with another optimal prefix circuit LYD(n), d(LYD(n))+2 d(SL(n)) d(LYD(n)). However, LYD(n) may have a fan-out of at most 2 lg n –2, and the fan-out of LYD(n) is greater than that of SL(n) for almost all n 12. Because an operation node with greater fan-out occupies more chip area and is slower in VLSI implementation, in most cases, SL(n) needs less area and may be faster than LYD(n). Moreover, it is much easier to design SL(n) than LYD(n). |
| |
Keywords: | Combinational circuits depth-size optimal parallel prefix unbounded fan-out VLSI |
本文献已被 SpringerLink 等数据库收录! |
|