Оптимізація ациклічних суматорів бінарних кодів

Автор(и)

  • 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

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

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

Посилання

  1. 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
  2. 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
  3. 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
  4. 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
  5. 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.
  6. 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
  7. 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
  8. 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
  9. 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
  10. 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
  11. 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
  12. 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
  13. 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
  14. 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
  15. 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
  16. 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
  17. 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
  18. 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
  19. 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
  20. 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
  21. 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
  22. 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
  23. 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
  24. 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

##submission.downloads##

Опубліковано

2018-01-23

Як цитувати

Solomko, M. (2018). Оптимізація ациклічних суматорів бінарних кодів. Technology Audit and Production Reserves, 3(2(41), 55–65. https://doi.org/10.15587/2312-8372.2018.133694

Номер

Том 3 № 2(41) (2018): Інформаційно-керуючі системи

Розділ

Математичне моделювання: Оригінальне дослідження

Ліцензія

Авторське право (c) 2018 Mykhailo Solomko

Creative Commons License

Ця робота ліцензується відповідно до Creative Commons Attribution 4.0 International License.

Закріплення та умови передачі авторських прав (ідентифікація авторства) здійснюється у Ліцензійному договорі. Зокрема, автори залишають за собою право на авторство свого рукопису та передають журналу право першої публікації цієї роботи на умовах ліцензії Creative Commons CC BY. При цьому вони мають право укладати самостійно додаткові угоди, що стосуються неексклюзивного поширення роботи у тому вигляді, в якому вона була опублікована цим журналом, але за умови збереження посилання на першу публікацію статті в цьому журналі.