Constructing zero-deficiency parallel prefix adder of minimum depth

ABSTRACT

Parallel prefix adder is a general technique for speeding up binary addition. In unit delay model, we denote the size and depth of an n-bit prefix adder C(n) as S_C(n) and d_C(n) respectively. Snir proved that s_C(n) + d_C(n) ≥ 2n - 2 holds for arbitrary prefix adders. Hence, a prefix adder is said to be of zero-deficiency if s_C(n) + d_C(n) = 2n - 2. In this paper, we first propose a new architecture of zero-deficiency prefix adder dubbed Z(d), which provably has the minimal depth among all kinds of zero-deficiency prefix adders. We then design a 64-bit prefix adder Z64, which is derived from Z(d)|_d=8, and compare it against several classical prefix adders of the same bit width in terms of area and delay using logical effort method. The result shows that the proposed Z(d) adder is also promising in practical VLSI design.

References

1. B. Parhami, Computer Arithmetic--Algorithm and Hardware Designs, Oxford University Press, 2000.
2. M. Snir, "Depth-size trade-offs for parallel prefix computation," in Journal of Algorithms 7, pp.185--201, 1986.
3. J. Sklansky, "Conditional sum addition logic", in IRE Tran. Electron. Comput., vol. EC-9, no. 6, pp.226--231, June 1960
4. Y-C Lin and C-C Shih, "A new class of depth-size optimal parallel prefix circuits," in The Journal of Supercomputing, 14, pp.39--52, 1999.
5. S. Lakshmivarahan, C. M. Yang, and S. K. Dhall, "On a new class of optimal parallel prefix circuits with (size+depth)=2n - 2 and {log n} ≤ depth ≤ (2{log n} - 3)," in Proc. of the 1987 International Conference on Parallel Processing", pp.58--65, 1987.
6. Reto Zimmermann, "Non-heuristic optimization and synthesis of parallel-prefix adders," in International Workshop on Logic and Architecture Synthesis (IWLAS'96), Grenoble, December 1996.
7. F. E. Fich, "New bounds for parallel prefix circuits," in Proc. of the 15th Annu. ACM Sympos. Theory of Comput., 1983, pp. 100--109.
8. S. Lakshmivarahan, S. K. Dhall, Parallel Computing: Using the Prefix Problem, Oxford University Press, 1994.
9. Reto Zimmermann, Java applet for adder synthesis, http://www.iis.ee.ethz.ch/ zimmi/applets/prefix.html
10. Haikun Zhu, Chung-Kuan Cheng, Ronald Graham, "Constructing Zero-deficiency Parallel Prefix Adder of Minimum Depth," ACM Transactions on Design Automation of Electronic Systems, submitted.
11. Yen-Chun Lin and Jun-Wei Hsiao, "A new Approach to construct optimal prefix circuits with small depth," in Procedding of the Int. Symp. on Parallel Architectures, Algorithms and Networks, ISPAN'02
12. Y.-C. Lin and Y.-H. Hsu, "Constructing H4, a fast depth-size optimal prefix circuit," in The Journal of Supercomputing, 24, 279--304, 2003.
13. R. Brent and H. Kung, "A regular layout for parallel adders," in IEEE Trans. Computers, vol. C-31, no. 3, pp.260--264, March 1982.
14. P. Kogge and H. Stone, "A parallel algorithm for the efficient solution of a general class of recurrence relations," in IEEE Trans. Computers, vol. C-22, no. 8, pp. 786--793, Aug. 1973.
15. T. Han and D. Carlson, "Fast area-efficient VLSI adders," in Proc. 8-th Symp. Arith., pp.49--56, Sep. 1987.
16. M. Smith, Application Specific Integrated Circuits, Chap. 3.3, Addison-Wesley, 1997.
17. D. Harris and I. Sutherland, "Logical effort of carry propagate adders," in Proc. 37th Asilomar Conf. Signals, Systems, and Computers, vol. 1, pp.873--878, 2003
18. Z. Huang and M. Ercegovac, "Effect of wire delay on the design of prefix adders in deep submicron technology," in Proc. 35th Asilomar Conf. Signals, Systems, and Computers, vol. 2, pp.1713--1717, 2000.