Редукція та оптимальна швидкодія ациклічних суматорів бінарних кодів

Автор(и)

  • Mykhailo Solomko Національний університет водного господарства та природокористування вул. Соборна, 11, м. Рівне, Україна, 33028, Україна https://orcid.org/0000-0003-0168-5657
  • Petro Tadeyev Національний університет водного господарства та природокористування вул. Соборна, 11, м. Рівне, Україна, 33028, Україна https://orcid.org/0000-0002-2885-6674
  • Yaroslav Zubyk Національний університет водного господарства та природокористування вул. Соборна, 11, м. Рівне, Україна, 33028, Україна https://orcid.org/0000-0002-0802-3552
  • Olena Hladka Національний університет водного господарства та природокористування вул. Соборна, 11, м. Рівне, Україна, 33028, Україна https://orcid.org/0000-0003-4728-0663

DOI:

https://doi.org/10.15587/1729-4061.2019.157150

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

ациклічна модель додавання бінарних кодів, префіксна модель, Ling Adder, Kogge-Stone Adder, Han-Carlson Adder

Анотація

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

Застосування ациклічної моделі розраховано на:

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

– встановлення оптимального числа обчислювальних кроків.

Експериментально доведено припущення про те, що число обчислювальних кроків орієнтованого ациклічного графа з двома логічними операціями AND і XOR визначає оптимальне число перенесень у схемі n-bit паралельного суматора бінарних кодів. Зокрема, це підтверджується наявністю 8-bit паралельного ациклічного суматора з глибиною схеми 8 типових 2-входових логічних елементів. Зв’язок між числом обчислювальних кроків ациклічного графа і числом перенесень одиниці до старшого розряду спричиняє процес співставлення структури суматора з відповідним ациклічним графом. Метою зазначеного співставлення є встановлення мінімально достатнього числа перенесень для операції додавання бінарних кодів у схемі паралельного суматора з паралельним способом перенесення.

Використання ациклічної моделі вигідніше у порівнянні з аналогами за такими чинниками:

– меншою вартістю розробки, оскільки ациклічна модель визначає простішу структуру суматора;

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

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

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

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

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

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

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

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

Кандидат фізико-математичних наук, доктор педагогічних наук, професор

Кафедра вищої математики

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

Старший викладач

Кафедра прикладної математики

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

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

Кафедра комп'ютерних наук

Посилання

  1. Brent, Kung (1982). A Regular Layout for Parallel Adders. IEEE Transactions on Computers, C-31 (3), 260–264. doi: https://doi.org/10.1109/tc.1982.1675982
  2. Han, T., Carlson, D. A. (1987). Fast area-efficient VLSI adders. 1987 IEEE 8th Symposium on Computer Arithmetic (ARITH). doi: https://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, C-22 (8), 786–793. doi: https://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: https://doi.org/10.1145/322217.322232
  5. Choi, Y., Swartzlander, E. E. (2005). Parallel Prefix Adder Design with Matrix Representation. 17th IEEE Symposium on Computer Arithmetic (ARITH'05). doi: https://doi.org/10.1109/arith.2005.35
  6. 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.
  7. Srinivasarao, B. N., Prathyusha, Ch. (2018). Power Efficient Parallel Prefix Adders. International Journal of Research, 5 (4), 472–477. Available at: https://pen2print.org/index.php/ijr/article/view/12158/11483
  8. Class ECE6332 Fall 12 Group-Fault-Tolerant Reconfigurable PPA. Available at: http://venividiwiki.ee.virginia.edu/mediawiki/index.php/ClassECE6332Fall12Group-Fault-Tolerant_Reconfigurable_PPA
  9. Ganesh Senthil, R., Kalaimathi, R. (2018). Design and Analysis of Kogge-Stone and Han-Carlson Adders in 130nm CMOS Technology. International Journal of Research, 05 (07), 1063–1068. Available at: https://pen2print.org/index.php/ijr/article/view/13190/
  10. Ananda Kumari, M., Loknadh, Ch. (2018). Design an Efficient Fault Tolerant Kogge Stone Adder. International Journal of Research, 05 (16), 1446–1449. Available at: https://pen2print.org/index.php/ijr/article/view/15599/
  11. Karthik, K., Rajeshwar, B. (2017). A New Design for Variable Latency Speculative E.C&D Han-Carlson Adder. International Journal of Research, 04 (13), 975–980. Available at: https://pen2print.org/index.php/ijr/article/view/9332/8980
  12. Hima, B. C., Srujana, G., Rao, M. V. (2018). Design of a novel BCD adder using parallel prefix technique. International Journal of Research in Electronics and Computer Engineering, 6 (2), 2213–2219. doi: http://doi.org/10.13140/RG.2.2.26923.49443
  13. Suvarna, P., Murali krishna, M. (2017). FPGA implementation of the carry select adder without using multiplexer. Global Journal for Research Analysis, 6 (3), 642–643. Available at: https://wwjournals.com/index.php/gjra/article/view/15467
  14. Balasubramanian, P., Jacob Prathap Raj, C., Anandi, S., Mastorakis, N., Bhavanidevi, U. (2013). Mathematical Modeling of Timing Attributes of Self-Timed Carry Select Adders. Conference: 4th European Conference of Circuits Technology and Devices (in the Book, “Recent Advances in Circuits, Systems, Telecommunications and Control,” Included in ISI/SCI Web of Science and Web of Knowledge. Paris, 228–243. Available at: https://www.researchgate.net/publication/265684833_Mathematical_Modeling_of_Timing_Attributes_of_Self-Timed_Carry_Select_Adders
  15. Revanna, N., Swartzlander, E. E. (2018). Memristor Adder Design. 2018 IEEE 61st International Midwest Symposium on Circuits and Systems (MWSCAS). Windsor. doi: https://doi.org/10.1109/MWSCAS.2018.8623864
  16. Soares, L. B., da Rosa, M. M. A., Diniz, C. M., da Costa, E. A. C., Bampi, S. (2019). Design Methodology to Explore Hybrid Approximate Adders for Energy-Efficient Image and Video Processing Accelerators. IEEE Transactions on Circuits and Systems I: Regular Papers, 1–14. doi: https://doi.org/10.1109/tcsi.2019.2892588
  17. Nagaraj, S., Reddy, G. M. S., Mastani, S. A. (2017). Analysis of different Adders using CMOS, CPL and DPL logic. 2017 14th IEEE India Council International Conference (INDICON). doi: https://doi.org/10.1109/indicon.2017.8487636
  18. Nykolaichuk, Ya. M., Davletova, A. Ya., Krulikovskyi, B. B., Vozna, N. Ya. (2016). Pat. No. 109142 UA. Odnorozriadnyi sumator. No. u201602165; declareted: 04.03.2016; published: 10.08.2016, Bul. No. 15.
  19. Parhomenko, P. P. (1976). Osnovy tekhnicheskoy diagnostiki. Moscow: Energiya, 464.
  20. Logic Friday 1.02. Available at: http://www.f1cd.ru/soft/base/logic_friday/logic_friday_102/
  21. Orlov, S. P., Martem'yanov, B. V. (2005). Arifmetika EVM i logicheskie osnovy pereklyuchatel'nyh funkciy. Moscow: Mashinostroenie -1, 256. Available at: http://vt.samgtu.ru
  22. 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: https://doi.org/10.15587/1729-4061.2016.70355
  23. 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. Available at: http://www.acsel-lab.com/Publications/Papers/energy_efficient_adders.pdf
  24. Govindarajulu, S., Vijaya Durga Royal, T. (2014). Design of Energy-Efficient and High-Performance VLSI Adders. International Journal of Engineering Research, 3, 55–59. Available at: https://pdfs.semanticscholar.org/a54c/5727cdc2be7830ea734f15eb1ba9ecfc2110.pdf
  25. 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.
  26. Two-Operand Addition. Available at: https://pubweb.eng.utah.edu/~cs5830/Slides/addersx6.pdf
  27. Knowles, S. (1999). A family of adders. Proceedings 14th IEEE Symposium on Computer Arithmetic (Cat. No.99CB36336). doi: https://doi.org/10.1109/arith.1999.762825
  28. Sklansky, J. (1960). Conditional-Sum Addition Logic. IEEE Transactions on Electronic Computers, EC-9 (2), 226–231. doi: https://doi.org/10.1109/tec.1960.5219822

##submission.downloads##

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

2019-02-20

Як цитувати

Solomko, M., Tadeyev, P., Zubyk, Y., & Hladka, O. (2019). Редукція та оптимальна швидкодія ациклічних суматорів бінарних кодів. Eastern-European Journal of Enterprise Technologies, 1(4), 40–53. https://doi.org/10.15587/1729-4061.2019.157150

Номер

Том 1 № 4 (2019): Математика та кібернетика - прикладні аспекти

Розділ

Математика та кібернетика - прикладні аспекти

Ліцензія

Авторське право (c) 2019 Mykhailo Solomko, Petro Tadeyev, Yaroslav Zubyk, Olena Hladka

Creative Commons License

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

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

Ліцензійний договір – це документ, в якому автор гарантує, що володіє усіма авторськими правами на твір (рукопис, статтю, тощо).
Автори, підписуючи Ліцензійний договір з ПП «ТЕХНОЛОГІЧНИЙ ЦЕНТР», мають усі права на подальше використання свого твору за умови посилання на наше видання, в якому твір опублікований. Відповідно до умов Ліцензійного договору, Видавець ПП «ТЕХНОЛОГІЧНИЙ ЦЕНТР» не забирає ваші авторські права та отримує від авторів дозвіл на використання та розповсюдження публікації через світові наукові ресурси (власні електронні ресурси, наукометричні бази даних, репозитарії, бібліотеки тощо).
За відсутності підписаного Ліцензійного договору або за відсутністю вказаних в цьому договорі ідентифікаторів, що дають змогу ідентифікувати особу автора, редакція не має права працювати з рукописом.
Важливо пам’ятати, що існує і інший тип угоди між авторами та видавцями – коли авторські права передаються від авторів до видавця. В такому разі автори втрачають права власності на свій твір та не можуть його використовувати в будь-який спосіб.