Synthesis of parallel adders from if-decision diagrams

Addition is one of the timing critical operations in most of modern processing units. For decades, extensive research has been done devoted to designing higher speed and less complex adder architectures, and to developing advanced adder implementation technologies. Decision diagrams are a promising approach to the efficient many-bit adder design. Since traditional binary decision diagrams does not match perfectly with the task of modelling adder architectures, other types of diagram were proposed. If-decision diagrams provide a parallel many-bit adder model with the time complexity of Ο(log2n) and area complexity of Ο(n×log2n). The paper propose a technique, which produces adder diagrams with such properties by systematically cutting the diagram’s longest paths. The if-diagram based adders are competitive to the known efficient Brent-Kung adder and its numerous modifications. We propose a blocked structure of the parallel if-diagram-based adders, and introduce an adder table representation, which is capable of systematic producing if-diagram of any bit-width. The representation supports an efficient mapping of the adder diagrams to VHDL-modules at structural and dataflow levels. The paper also shows how to perform the adder space exploration depending on the circuit fan-out. FPGA-based synthesis results and case-study comparisons of the if-diagram-based adders to the Brent-Kung and majority-invertor gate adders show that the new adder architecture leads to faster and smaller digital circuits.

1. T.-K. Liu, K. R. Hohulin, L.-E. Shiau, S. Muroga. «Optimal One-Bit Full-Adders with Different Types of Gates». IEEE Transactions on Computers. Bell Laboratories: IEEE, 1974, C-23 (1): 63–70.

2. Rosenberger, G. B. «Simultaneous Carry Adder». U. S. Patent 2,966,305. (1960–12–27).

3. P. M. Kogge, H. S. Stone. «A Parallel Algorithm for the Efficient Solution of a General Class of Recurrence Equations». IEEE Transactions on Computers. 1973, C-22 (8): 786–793.

4. R. P. Brent, H. Te Kung, «A Regular Layout for Parallel Adders». IEEE Transactions on Computers. 1982, C-31, (3): 260–264.

5. N. Poornima, V. S. Kanchana Bhaaskaran. «Area Efficient Hybrid Parallel Prefix Adders». Procedia Materials Science 10 (2015), pp. 371–380.

6. L. Amarú, P.-E. Gaillardon, G. De Micheli, «Majority-Inverter Graph: A New Paradigm for Logic Optimization» IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 35, no. 5, pp. 806–819, May 2016.

7. L. Amarú, P.-E. Gaillardon, A. Chattopadhyay, G. De Micheli, «A Sound and Complete Axiomatization of Majority-n Logic» IEEE Transactions on Computers, vol. 65, no. 9, pp. 2889–2895, September 2016.

8. V. Tenace, A. Calimera, E. Macii, M. Poncino. «Pass-XNOR logic: A new logic style for P-N junction based graphene circuits». DATE, 2014, pp.1–4.

9. Prihozhy, A.A. If-Diagrams: Theory and Application / A.A. Prihozhy // Proc. 7th Int. Workshop PATMOS’97. – UCL, Belgium, 1997. – P. 369–378.

10. Prihozhy, A.A. Parallel Computing with If-Decision-Diagrams / A.A. Prihozhy, P. U. Brancevich // Proc. Int. Conference PARELEC’98. – Poland, Technical University of Bialystok. – 1998. – P. 179–184.

11. Prihozhy А. А. Incompletely Specified Logical Systems and Algorithms / А. А. Prihozhy / Minsk, Technical Literature. – 2013. – 343 с.

12. Prihozhy A.A. «Generalization of the Shannon Expansion for Incompletely Specified Functions: Theory and Application». System analysis and applied information science». 2013; (1–2): 6–11.

13. C. Y. Lee, Representation of Switching Circuits by Binary-Decision Programs, Bell Systems Technical Journal, 1959, Vol. 38, No 4, pp. 985–999.

14. L. Amarú, P.-E. Gaillardon, G. De Micheli. «Biconditional BDD: a novel canonical BDD for logic synthesis targeting XOR-rich circuits» in DATE’13, 2013, pp. 1014–1017.

15. A. Bernasconi et al., «On decomposing Boolean functions via extended cofactoring» in DATE, 2009, pp. 1464–1469.

16. V. Tenace, A. Calimera, E. Macii, M. Poncino. One-pass logic synthesis for graphene-based Pass-XNOR logic circuits. DAC, 2015: 128:1–128:6.

17. Prihozhy, A.A. If-Decision Diagram Based Synthesis of Digital Circuits / A.A. P rihozhy // Proc. Int. Conf. «Information Technologies for Education, Science and Business». – Minsk, Belarus. – 1999. – P. 65–69.

18. Prihozhy, A.A. If-Decision Diagram Based Modeling and Synthesis of Incompletely Specified Digital Systems / A.A. Prihozhy, B. Becker // Electronics and communications, Electronics Design. – Kyiv. – 2005, pp. 103–108.

19. Prihozhy, A.A. Analysis, transformation and optimization for high performance parallel computing / A.A. Prihozhy // Minsk, BNTU. – 2019. – 229 p.

20. IEEE Standard VHDL Language Reference Manual. The Institute of Electrical and Electronics Engineers, Inc. – 2000. – 299 p.

21. Prihozhy, A.A. High-Level Synthesis through Transforming VHDL Models / A.A. Prihozhy // Chapter in Book «Systemon-Chip Methodologies and Design Languages». – Kluwer Academic Publishers. – 2001. – P. 135–146.

22. Quartus Prime Lite Edition [Electronic resource]. – Access mode: https://fpgasoftware.intel.com/?edition=lite. – Date of access: 24.04.2020.