Optimization of the acyclic adders of binary codes

Mykhailo Solomko

doi:10.15587/2312-8372.2018.133694

Автор(и)

Mykhailo Solomko Національний університет водного господарства та природокористування, вул. Соборна, 11, м. Рівне, Україна, 33028, Україна https://orcid.org/0000-0003-0168-5657

DOI:

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

Ключові слова:

ациклічна модель, префіксна модель, направлений ациклічний граф, Ling Adder, Kogge-Stone Adder, Brent-Kung Adder

Анотація

Об'єктом дослідження є префіксна модель обчислення сигналів суми і перенесення у схемі паралельного суматора з паралельним способом перенесення. Одним з найбільш проблемних місць префіксної моделі є процес вироблення сигналів суми і перенесення, у якому початок обчислення префікса передбачено з першого розряду схеми. Це приводить, у підсумку, до надлишкового нагромадження і ускладнення апаратної частини пристрою.

У ході дослідження використовувалась математична модель обчислення сигналів суми і перенесення у схемі паралельного суматора, що ґрунтується на властивостях направленого ациклічного графа з двома типовими операціями.

Отримано зменшення складності логічної структури суматора бінарних кодів, зменшення глибини схеми та зменшення загальної протяжності з’єднувальних проводів. Це пов'язано з тим, що запропонований метод обчислення сигналів суми і перенесення має ряд особливостей синтезу схеми пристрою, зокрема застосування математичної моделі, що ґрунтується на властивостях ациклічного графа, розраховано на:

процес послідовного (для молодших розрядів схеми пристрою) і паралельного обчислення сигналів суми і перенесення, що, у підсумку, дає зменшення складності апаратної частини пристрою та не збільшує глибину схеми;
співставлення числа обчислювальних кроків орієнтованого ациклічного графа з числом перенесень одиниці до старшого розряду у схемі суматора, що дозволяє встановлювати оптимальне число обчислювальних кроків для структури пристрою.

Завдяки цьому забезпечується можливість отримання оптимальних значень показників складності структури та глибини схеми суматора. Зв’язок між числом обчислювальних кроків орієнтованого ациклічного графа і числом перенесень у схемі паралельного суматора з паралельним способом перенесення вказує на доцільність співставлення структури суматора з відповідним орієнтованим ациклічним графом.

У порівнянні з аналогічними відомими структурами 8-bit префіксних суматорів це забезпечує збільшення показника якості 8-bit ациклічних суматорів, наприклад, за енергоспоживанням, площею чіпа, у залежності від обраної структури, на 10–40 %.

Біографія автора

Mykhailo Solomko, Національний університет водного господарства та природокористування, вул. Соборна, 11, м. Рівне, Україна, 33028

Кандидат технічних наук, доцент

Кафедра обчислювальної техніки

Посилання

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 14^th 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