DOI: https://doi.org/10.15587/2312-8372.2018.133694

Optimization of the acyclic adders of binary codes

Mykhailo Solomko

Abstract


The object of research is a prefix model for calculating adding and transport signals in a parallel adder circuit with a parallel transfer method. One of the most problematic places in the prefix model is the process of generating adding and carry signals, in which the beginning of the prefix calculation is provided from the first bit of the circuit. This leads, in the end, to excessive accumulation and complications of the hardware part of the device.

In the course of the research, a mathematical model is used to calculate the adding and carry signals in a parallel adder circuit based on the properties of a directed acyclic graph with two typical operations.

The complexity of the logical structure of the adder of binary codes is reduced, the depth of the circuit is reduced and the total length of the connecting wires is reduced. This is due to the fact that the proposed method for calculating adding and transport signals has a number of features of the device circuit synthesis, in particular, the application of a mathematical model based on the properties of an acyclic graph is calculated for:

  • process of sequential (for lower order devices) and parallel calculation of adding and carry signals, which, in the end, reduces the complexity of the hardware of the device and does not increase the depth of the circuit;
  • comparison of the number of computational steps of an oriented acyclic graph with the number of transfers of one to the high-order bit in the adder circuit, which allows to determine the optimal number of computational steps for the structure of the device.

Due to this, it is possible to obtain optimal values for the complexity of the structure and the depth of the adder circuit. The connection between the number of computational steps of an oriented acyclic graph and the number of transfers in the parallel adder circuit with a parallel transport method indicates the expediency of comparing the structure of the adder with the corresponding oriented acyclic graph.

In comparison with similar known structures of 8-bit prefix adders, this provides an increase in the quality index of 8-bit acyclic adders, for example, by power consumption, the chip area, depending on the chosen structure, by 10–40 %.


Keywords


acyclic model; prefix model; directed acyclic graph; Ling Adder; Kogge-Stone Adder; Brent-Kung Adder

References


Brent, R. P., Kung, H. T. (1982). A regular layout for parallel adders. IEEE Transactions on Computers, 31 (3), 260–264. doi: http://doi.org/10.1109/tc.1982.1675982

Han, T., Carlson, D. A. (1987). Fast area-efficient VLSI adders. IEEE 8th Symposium on Computer Arithmetic (ARITH). doi: http://doi.org/10.1109/arith.1987.6158699

Kogge, P. M., Stone, H. S. (1973). A Parallel Algorithm for the Efficient Solution of a General Class of Recurrence Equations. IEEE Transactions on Computers, 22 (8), 786–793. doi: http://doi.org/10.1109/tc.1973.5009159

Ladner, R. E., Fischer, M. J. (1980). Parallel Prefix Computation. Journal of the ACM, 27 (4), 831–838. doi: http://doi.org/10.1145/322217.322232

Solomko, M., Olshansky, P. (2017). The Parallel Acyclic Adder. 2017 14th International Conference The Experience of Designing and Application of CAD Systems in Microelectronics (CADSM). Lviv, 125–129.

Balasubramanian, P., Jacob Prathap Raj, C., Anandi, S., Bhavanidevi, U., Mastorakis, N. E. (2013). Mathematical Modeling of Timing Attributes of Self-Timed Carry Select Adders. Recent Advances in Circuits, Systems, Telecommunications and Control, 228–243. Available at: http://www.wseas.us/e-library/conferences/2013/Paris/CCTC/CCTC-34.pdf

Venkatanaga Kumar, G., Pushpalatha, C. H. (2016). Implementation of Carry Tree Adders and Compare with RCA and CSLA. International Journal of Emerging Engineering Research and Technology, 4 (1), 1–11. Available at: http://www.ijeert.org/pdf/v4-i1/1.pdf

Gedam, K. S., Zode, P. P. (2014). Parallel prefix han-carlson adder. International Journal of Research in Engineering and Applied Sciences, 2 (2), 81–84. Available at: http://mgijournal.com/pdf_new/electronics/swapna%20gedam-1.pdf

Krishna Kumari, V., Sri Chakrapani, Y., Kamaraju, M. (2013). Design and Characterization of Kogge-Stone, Sparse Kogge-Stone, Spanning tree and Brent-Kung Adders. International Journal of Scientific & Engineering Research, 4 (10), 1502–1506. Available at: https://www.ijser.org/researchpaper/Design-and-Characterization-of-Koggestone-Sparse-Koggestone-Spanning-tree-and-Brentkung-Adders.pdf

Ramanathan, P., Vanathi, P. T. (2009). Hybrid Prefix Adder Architecture for Minimizing the Power Delay Product. World Academy of Science, Engineering and Technology International Journal of Electrical, Computer, Energetic, Electronic and Communication Engineering, 3 (4), 869–873. Available at: https://waset.org/publications/5272/hybrid-prefix-adder-architecture-for-minimizing-the-power-delay-product

Kaarthik, K., Vivek, C. (2016). Hybrid Han Carlson Adder Architecture for Reducing Power and Delay Middle-East. Journal of Scientific Research, 24, 308–313. Available at: https://www.idosi.org/mejsr/mejsr24(IIECS)16/48.pdf

Yagain, D., Vijaya, K. A., Baliga, A. (2012). Design of High-Speed Adders for Efficient Digital Design Blocks. ISRN Electronics, 2012, 1–9. doi: http://doi.org/10.5402/2012/253742

Krishna, B., Siva Durga Rao, P., Prasad, N. V. G. (2012). High Speed and Low Power Design of Parallel Prefix Adder. International Journal of Electronics & Communication Technology, 3 (4), 472–475. Available at: http://www.iject.org/vol34/3/a572

Aktan, M., Baran, D., Oklobdzija, V. G. (2015). Minimizing Energy by Achieving Optimal Sparseness in Parallel Adders. 2015 IEEE 22nd Symposium on Computer Arithmetic, 10–17. doi: http://doi.org/10.1109/arith.2015.13

Anitha, R., Bagyaveereswaran, V. (2012). High performance parallel prefix adders with fast carry chain logic. International Journal of Advanced Research in Engineering and Technology (IJARET), 3 (2). Available at: https://www.slideshare.net/iaemedu/high-performance-parallel-prefix-adders-with-fast-carry-chain-logic

Vozna, N. Ya., Krulikovskyi, B. B., Hryha, V. M., Davletova, A. Ya., Nykolaichuk, Ya. M. (11.12.2017). Kombinatsiinyi sumator. Patent 115751 UA, MPK G 06 F 7/501 (2006.01). Filed: 13.02.2017. Bul. No. 23. Available at: http://uapatents.com/6-115751-kombinacijjnijj-sumator.html

Gurkayna, F. K., Leblebicit, Y., Chaouati, L., McGuinness, P. J. (2000). Higher radix Kogge-Stone parallel prefix adder architectures. 2000 IEEE International Symposium on Circuits and Systems. Emerging Technologies for the 21st Century. Proceedings (IEEE Cat No. 00CH36353). Presses Polytech. Univ. Romandes. doi: http://doi.org/10.1109/iscas.2000.857516

Knowles, S. (1999). A family of adders. Proceedings 14th IEEE Symposium on Computer Arithmetic (Cat. No. 99CB36336). IEEE Comput. Soc. doi: http://doi.org/10.1109/arith.1999.762825

Beaumont-Smith, A., Lim, C.-C. (2001). Parallel prefix adder design. Proceedings 15th IEEE Symposium on Computer Arithmetic. ARITH-15 2001. IEEE Comput. Soc. doi: http://doi.org/10.1109/arith.2001.930122

Zimmermann, R. (1999). Efficient VLSI implementation of modulo (2/sup n/±1) addition and multiplication. Proceedings 14th IEEE Symposium on Computer Arithmetic (Cat. No. 99CB36336). IEEE Comput. Soc. doi: http://doi.org/10.1109/arith.1999.762841

Zeydel, B. R., Baran, D., Oklobdzija, V. G. (2010). Energy-Efficient Design Methodologies: High-Performance VLSI Adders. IEEE Journal of Solid-State Circuits, 45 (6), 1220–1233. doi: http://doi.org/10.1109/jssc.2010.2048730

Govindarajulu, S., Vijaya Durga Royal, T. (2014). Design of Energy-Efficient and High-Performance VLSI Adders. International Journal of Engineering Research, 3 (2), 55–59. Available at: http://ijer.irponline.in/ijer/publication/v3si2/IJER_2014_NCSC%2013.pdf

Pinto, R., Shama, K. (2016). Efficient shift-add multiplier design using parallel prefix adder. International Journal of Control Theory and Applications, 9 (39), 45–53. Available at: http://serialsjournals.com/serialjournalmanager/pdf/1500377875.pdf

Solomko, M., Krulikovskyі, B. (2016). Study of carry optimization while adding binary numbers in the rademacher number-theoretic basis. Eastern-European Journal of Enterprise Technologies, 3 (4 (81)), 56–63. doi: http://doi.org/10.15587/1729-4061.2016.70355


GOST Style Citations


Brent R. P., Kung H. T. A regular layout for parallel adders // IEEE Transactions on Computers. 1982. Vol. 31, No. 3. P. 260–264. doi: http://doi.org/10.1109/tc.1982.1675982 

Han T., Carlson D. A. Fast area-efficient VLSI adders // IEEE 8th Symposium on Computer Arithmetic (ARITH). 1987. doi: http://doi.org/10.1109/arith.1987.6158699 

Kogge P. M., Stone H. S. A Parallel Algorithm for the Efficient Solution of a General Class of Recurrence Equations // IEEE Transactions on Computers. 1973. Vol. 22, No. 8. P. 786–793. doi: http://doi.org/10.1109/tc.1973.5009159 

Ladner R. E., Fischer M. J. Parallel Prefix Computation // Journal of the ACM. 1980. Vol. 27, No. 4. P. 831–838. doi: http://doi.org/10.1145/322217.322232 

Solomko M., Olshansky P. The Parallel Acyclic Adder // 2017 14th International Conference The Experience of Designing and Application of CAD Systems in Microelectronics (CADSM). Lviv, 2017. P. 125–129.

Mathematical Modeling of Timing Attributes of Self-Timed Carry Select Adders / Balasubramanian P. et al. // Recent Advances in Circuits, Systems, Telecommunications and Control. 2013. P. 228–243. URL: http://www.wseas.us/e-library/conferences/2013/Paris/CCTC/CCTC-34.pdf

Venkatanaga Kumar G., Pushpalatha C. H. Implementation of Carry Tree Adders and Compare with RCA and CSLA // International Journal of Emerging Engineering Research and Technology. 2016. Vol. 4, No. 1. P. 1–11. URL: http://www.ijeert.org/pdf/v4-i1/1.pdf

Gedam K. S., Zode P. P. Parallel prefix han-carlson adder // International Journal of Research in Engineering and Applied Sciences. 2014. Vol. 2, No. 2. P. 81–84. URL: http://mgijournal.com/pdf_new/electronics/swapna%20gedam-1.pdf

Krishna Kumari V., Sri Chakrapani Y., Kamaraju M. Design and Characterization of Kogge-Stone, Sparse Kogge-Stone, Spanning tree and Brent-Kung Adders // International Journal of Scientific & Engineering Research. 2013. Vol. 4, No. 10. P. 1502–1506. URL: https://www.ijser.org/researchpaper/Design-and-Characterization-of-Koggestone-Sparse-Koggestone-Spanning-tree-and-Brentkung-Adders.pdf

Ramanathan P., Vanathi P. T. Hybrid Prefix Adder Architecture for Minimizing the Power Delay Product // World Academy of Science, Engineering and Technology International Journal of Electrical, Computer, Energetic, Electronic and Communication Engineering. 2009. Vol. 3, No. 4. P. 869–873. URL: https://waset.org/publications/5272/hybrid-prefix-adder-architecture-for-minimizing-the-power-delay-product

Kaarthik K., Vivek C. Hybrid Han Carlson Adder Architecture for Reducing Power and Delay Middle-East // Journal of Scientific Research. 2016. Vol. 24. P. 308–313. URL: https://www.idosi.org/mejsr/mejsr24(IIECS)16/48.pdf

Yagain D., Vijaya K. A., Baliga A. Design of High-Speed Adders for Efficient Digital Design Blocks. ISRN Electronics. 2012. Vol. 2012. P. 1–9. doi: http://doi.org/10.5402/2012/253742 

Krishna B., Siva Durga Rao P., Prasad N. V. G. High Speed and Low Power Design of Parallel Prefix Adder // International Journal of Electronics & Communication Technology. 2012. Vol. 3, No. 4. P. 472–475. URL: http://www.iject.org/vol34/3/a572

Aktan M., Baran D., Oklobdzija V. G. Minimizing Energy by Achieving Optimal Sparseness in Parallel Adders // 2015 IEEE 22nd Symposium on Computer Arithmetic. 2015. P. 10–17. doi: http://doi.org/10.1109/arith.2015.13 

Anitha R., Bagyaveereswaran V. High performance parallel prefix adders with fast carry chain logic // International Journal of Advanced Research in Engineering and Technology (IJARET). 2012. Vol. 3, No. 2. URL: https://www.slideshare.net/iaemedu/high-performance-parallel-prefix-adders-with-fast-carry-chain-logic

Kombinatsiinyi sumator: Patent 115751 UA, MPK G 06 F 7/501 (2006.01) / Vozna N. Ya. et al. Appl. No. a201701347; Filed: 13.02.2017; Published: 11.12.2017; Bul. No. 23. URL: http://uapatents.com/6-115751-kombinacijjnijj-sumator.html

Gurkayna F. K. et al. Higher radix Kogge-Stone parallel prefix adder architectures // 2000 IEEE International Symposium on Circuits and Systems. Emerging Technologies for the 21st Century. Proceedings (IEEE Cat No. 00CH36353). Presses Polytech. Univ. Romandes, 2000. doi: http://doi.org/10.1109/iscas.2000.857516 

Knowles S. A family of adders // Proceedings 14th IEEE Symposium on Computer Arithmetic (Cat. No. 99CB36336). IEEE Comput. Soc., 1999. doi: http://doi.org/10.1109/arith.1999.762825 

Beaumont-Smith A., Lim C.-C. Parallel prefix adder design // Proceedings 15th IEEE Symposium on Computer Arithmetic. ARITH-15 2001. IEEE Comput. Soc., 2001. doi: http://doi.org/10.1109/arith.2001.930122 

Zimmermann R. Efficient VLSI implementation of modulo (2/sup n/±1) addition and multiplication // Proceedings 14th IEEE Symposium on Computer Arithmetic (Cat. No. 99CB36336). IEEE Comput. Soc., 1999. doi: http://doi.org/10.1109/arith.1999.762841 

Zeydel B. R., Baran D., Oklobdzija V. G. Energy-Efficient Design Methodologies: High-Performance VLSI Adders // IEEE Journal of Solid-State Circuits. 2010. Vol. 45, No. 6. P. 1220–1233. doi: http://doi.org/10.1109/jssc.2010.2048730 

Govindarajulu S., Vijaya Durga Royal T. Design of Energy-Efficient and High-Performance VLSI Adders // International Journal of Engineering Research. 2014. Vol. 3, No. 2, P. 55–59. URL: http://ijer.irponline.in/ijer/publication/v3si2/IJER_2014_NCSC%2013.pdf

Pinto R., Shama K. Efficient shift-add multiplier design using parallel prefix adder // International Journal of Control Theory and Applications. 2016. Vol. 9, No. 39. P. 45–53. URL: http://serialsjournals.com/serialjournalmanager/pdf/1500377875.pdf

Solomko M., Krulikovskyі B. Study of carry optimization while adding binary numbers in the rademacher number-theoretic basis // Eastern-European Journal of Enterprise Technologies. 2016. Vol. 3, No. 4 (81). P. 56–63. doi: http://doi.org/10.15587/1729-4061.2016.70355 







Copyright (c) 2018 Mykhailo Solomko

Creative Commons License
This work is licensed under a Creative Commons Attribution 4.0 International License.

ISSN (print) 2664-9969, ISSN (on-line) 2706-5448