Розробка різнотипних операційних пристроїв сортування двійкових даних

Автор(и)

  • Володимир Михайлович Грига Прикарпатський національний університет імені Василя Стефаника, Україна https://orcid.org/0000-0001-5458-525X
  • Богдан Степанович Дзундза Прикарпатський національний університет імені Василя Стефаника, Україна https://orcid.org/0000-0002-6657-5347
  • Степан Іванович Мельничук Івано-Франківський національний технічний університет нафти і газу, Україна https://orcid.org/0000-0002-6973-4235
  • Ірина Зіновіївна Мануляк Івано-Франківський національний технічний університет нафти і газу, Україна https://orcid.org/0000-0002-0072-1532
  • Андрій Іванович Терлецький Прикарпатський національний університет імені Василя Стефаника, Україна https://orcid.org/0000-0003-2091-0362
  • Михайло Васильович Дейчаківський Прикарпатський національний університет імені Василя Стефаника, Україна https://orcid.org/0000-0001-7574-7772

DOI:

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

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

метод «парно-непарної» перестановки, багатотактовий операційний пристрій, просторово-часовий граф, потоковий граф, алгоритм, синтез, функціональний оператор, пристрій сортування, двійкові дані, моделювання

Анотація

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

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

Розроблено нові структури багатотактових операційних пристроїв, для заданого алгоритму сортування та наведено аналітичні вирази для розрахунку затрат обладнання та їх швидкодії. Проведено порівняльний аналіз апаратної та часової складності розроблених структур пристроїв сортування двійкових чисел різних типів з відомими реалізаціями алгоритмічних та конвеєрних операційних пристроїв. В результаті запропоновані структури при сортуванні великих масивів двійкових даних (N>128) мають на порядок меншу апаратну складність за рахунок послідовного виконання однотипних операцій. Часова складність багатотактових операційних пристроїв комбінованого і послідовного типів при великих значеннях вхідних даних є в 2,3 і 3,4 рази меншою ніж у відомих конвеєрних операційних пристроях.

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

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

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

Володимир Михайлович Грига, Прикарпатський національний університет імені Василя Стефаника

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

Кафедра комп’ютерної інженерії та електроніки

Богдан Степанович Дзундза, Прикарпатський національний університет імені Василя Стефаника

Кандидат фізико-математичних наук, доцент

Кафедра комп’ютерної інженерії та електроніки

Степан Іванович Мельничук, Івано-Франківський національний технічний університет нафти і газу

Доктор технічних наук, професор

Кафедра комп’ютерних систем і мереж

Ірина Зіновіївна Мануляк, Івано-Франківський національний технічний університет нафти і газу

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

Кафедра комп’ютерних систем і мереж

Андрій Іванович Терлецький, Прикарпатський національний університет імені Василя Стефаника

Кандидат фізико-математичних наук, доцент

Кафедра комп’ютерної інженерії та електроніки

Михайло Васильович Дейчаківський, Прикарпатський національний університет імені Василя Стефаника

Аспірант

Кафедра комп'ютерної інженерії та електроніки

Посилання

  1. Knuth, D. E. (2011). The Art of Computer Programming, Volume 4A: Combinatorial Algorithms, Part 1. Addison-Wesley Professional, 912. Available at: https://ia804701.us.archive.org/2/items/B-001-001-251/B-001-001-251.pdf
  2. Siewiorek, D., Robert, S. (2017). Reliable Computer Systems: Design and Evaluation. CRC Press, 908. doi: https://doi.org/10.1201/9781439863961
  3. Dobre, C., Xhafa, F. (2013). Parallel Programming Paradigms and Frameworks in Big Data Era. International Journal of Parallel Programming, 42 (5), 710–738. doi: https://doi.org/10.1007/s10766-013-0272-7
  4. Cormen, T. H., Leiserson, C. E., Rivest, R. L., Stein, C. (2009). Introduction to algorithms: third edition. Massachusetts Institute of Technology. Available at: https://pd.daffodilvarsity.edu.bd/course/material/book-430/pdf_content
  5. Hanyu, T., Endoh, T., Suzuki, D., Koike, H., Ma, Y., Onizawa, N. et al. (2016). Standby-Power-Free Integrated Circuits Using MTJ-Based VLSI Computing. Proceedings of the IEEE, 104 (10), 1844–1863. doi: https://doi.org/10.1109/jproc.2016.2574939
  6. Michailov, D. (2011). Hardware implementation of recursive sorting algorithms using tree-like structures and HFSM Models. Tallin: TUT Press, 114. Available at: https://digikogu.taltech.ee/en/Download/eb5d073c-02e5-46b9-83de-71fa17bd572a
  7. Akl, S. G. (1985). Parallel sorting algorithms. Academic Press. doi: https://doi.org/10.1016/c2013-0-10281-4
  8. Melnyk, A. O. (2008). Arkhitektura kompiutera. Lutsk: Volynska oblasna drukarnia, 470.
  9. Melnyk, A. O. (2014). Pamiat iz vporiadkovanym dostupom. Lviv: Vydavnytstvo NU «Lvivska politekhnika», 296.
  10. Yakovlieva, I. D. (2008). Otsinka variantiv syntezu paralelnykh obchysliuvalnykh prystroiv sortuvannia. Visnyk Natsionalnoho universytetu «Lvivska politekhnika», 630, 124–130. Available at: https://ena.lpnu.ua/handle/ntb/880
  11. Tsmots, I. G., Antoniv, V. Ya. (2016). Algorithms and Parallel Structures for Data Sorting Using Insertion Method. Scientific Bulletin of UNFU, 26 (1), 340–350. doi: https://doi.org/10.15421/40260153
  12. Tsmots, I. G., Antoniv, V. Y. (2020). Improvement of parallel sorting by method of merging. Scientific Bulletin of UNFU, 30 (4), 134–142. doi: https://doi.org/10.36930/40300422
  13. Gryga, V., Nykolaichuk, Y., Vozna, N., Krulikovskyi, B. (2017). Synthesis of a microelectronic structure of a specialized processor for sorting an array of binary numbers. 2017 XIIIth International Conference on Perspective Technologies and Methods in MEMS Design (MEMSTECH). doi: https://doi.org/10.1109/memstech.2017.7937560
  14. Dunets, R., Gryga, V. (2015). Spatio-temporal synthesis of transformation matrix of reverse fast cosine transformation. The Experience of Designing and Application of CAD Systems in Microelectronics. doi: https://doi.org/10.1109/cadsm.2015.7230792
  15. Gryga, V., Kolosov, I., Danyluk, O. (2016). The development of a fast iterative algorithm structure of cosine transform. 2016 13th International Conference on Modern Problems of Radio Engineering, Telecommunications and Computer Science (TCSET). doi: https://doi.org/10.1109/tcset.2016.7452100
  16. Gryga, V. (2018). Design and research of operational and pipelined binary number sorting devices. 18th International Multidisciplinary Scientific GeoConference SGEM2018, Informatics, Geoinformatics and Remote Sensing. doi: https://doi.org/10.5593/sgem2018/2.1/s07.036
  17. Alotaibi, A., Almutairi, A., Kurdi, H. (2020). OneByOne (OBO): A Fast Sorting Algorithm. Procedia Computer Science, 175, 270–277. doi: https://doi.org/10.1016/j.procs.2020.07.040
  18. Alaparthi, S., Gulati, K., Khatri, S. P. (2009). Sorting binary numbers in hardware - A novel algorithm and its implementation. 2009 IEEE International Symposium on Circuits and Systems. doi: https://doi.org/10.1109/iscas.2009.5118240
  19. Kobayashi, R., Miura, K., Fujita, N., Boku, T., Amagasa, T. (2022). An Open-source FPGA Library for Data Sorting. Journal of Information Processing, 30, 766–777. doi: https://doi.org/10.2197/ipsjjip.30.766
  20. Mihhailov, D., Sklyarov, V., Skliarova, I., Sudnitson, A. (2011). Hardware implementation of recursive sorting algorithms. 2011 International Conference on Electronic Devices, Systems and Applications (ICEDSA). doi: https://doi.org/10.1109/icedsa.2011.5959040
  21. Deo, N. (1974). Graph theory with applications to engineering and computer science. Dover Publications. Available at: https://www.shahucollegelatur.org.in/Department/Studymaterial/sci/it/BCS/FY/book.pdf
  22. Kogut, I. T., Druzhinin, A. A., Holota, V. I. (2011). 3D SOI Elements for System-on-Chip Applications. Advanced Materials Research, 276, 137–144. doi: https://doi.org/10.4028/www.scientific.net/amr.276.137
  23. Novosiadlyi, S., Kotyk, M., Dzundza, B., Gryga, V., Novosiadlyi, S., Mandzyuk, V. (2017). Formation of carbon films as the subgate dielectric of GaAs microcircuits on Si-substrates. Eastern-European Journal of Enterprise Technologies, 5 (5 (89)), 26–34. doi: https://doi.org/10.15587/1729-4061.2017.112289
  24. Kehret, O., Walz, A., Sikora, A. (2016). Integration of hardware security modules into a deeply embedded tls stack. International Journal of Computing, 15 (1), 22–30. doi: https://doi.org/10.47839/ijc.15.1.827
  25. Gryga, V., Dzundza, B., Dadiak, I., Nykolaichuk, Y. (2018). Research and implementation of hardware algorithms for multiplying binary numbers. 2018 14th International Conference on Advanced Trends in Radioelecrtronics, Telecommunications and Computer Engineering (TCSET). doi: https://doi.org/10.1109/tcset.2018.8336427
  26. Giachetti, R. (2016). Design of enterprise systems: Theory, architecture, and methods. CRC Press. doi: https://doi.org/10.1201/9781439882894
  27. Hryha, V. M., Nykolaichuk, Ya. M., Hryha, L. P. (2022). Pat. No. 151889. Prystriy porivniannia bahatorozriadnykh dviykovykh danykh. No. u202200478; declareted: 07.02.2022, published: 28.09.2022. Available at: https://sis.ukrpatent.org/uk/search/detail/1707803/
Розробка різнотипних операційних пристроїв сортування двійкових даних

##submission.downloads##

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

2023-08-31

Як цитувати

Грига, В. М., Дзундза, Б. С., Мельничук, С. І., Мануляк, І. З., Терлецький, А. І., & Дейчаківський, М. В. (2023). Розробка різнотипних операційних пристроїв сортування двійкових даних. Eastern-European Journal of Enterprise Technologies, 4(4 (124), 6–18. https://doi.org/10.15587/1729-4061.2023.285997

Номер

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

Розділ

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

Ліцензія

Авторське право (c) 2023 Volodymyr Hryha, Bogdan Dzundza, Stepan Melnychuk, Iryna Manuliak, Andrii Terletsky, Mykhailo Deichakivskyi

Creative Commons License

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

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

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