Design of various operating devices for sorting binary data

Authors

DOI:

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

Keywords:

«even-odd» permutation method, multi-cycle operating device, space-time graph, flow graph, algorithm, synthesis, functional operator, sorting device, binary data, simulation

Abstract

The object of research is the process of designing hardware devices for sorting arrays of binary data using the methodology of space-time graphs.

The main task that is solved in the work is the development and research of multi-cycle operating devices for sorting binary data in order to choose the optimal structure with predetermined technical characteristics for solving the sorting problem. As an example, the development of different types of structures of multi-cycle operating sorting devices by the method of «even-odd» permutation is shown and their system characteristics are determined.

New structures of multi-cycle operating devices have been designed for a given sorting algorithm, and analytical expressions for calculating equipment costs and their performance have been given. A comparative analysis of the hardware and time complexity of the developed structures of devices for sorting binary numbers of various types with known implementations of algorithmic and pipeline operating devices was carried out. As a result, the proposed structures, when sorting large arrays of binary data (N>128), have an order of magnitude less hardware complexity due to sequential execution of the same type of operations. The time complexity of multi-cycle operating devices of combined and sequential types with large values of input data is 2.3 and 3.4 times less than that of known pipeline operating devices.

A feature of the research results is the possibility of finding the optimal ratio between the hardware and time characteristics of the resulting structures of sorting devices. Owing to this, the designer will be able to choose the necessary type of device for the implementation of the corresponding task with optimal system characteristics.

The field of application of the designed sorting devices is the tasks of digital processing of signals and images. The practical use of the developed sorting devices can be carried out in the form of their synthesis on software integrated logic circuits

Author Biographies

Volodymyr Hryha, Vasyl Stefanyk Precarpathian National University

PhD, Associate Professor

Department of Computer Engineering and Electronics

Bogdan Dzundza, Vasyl Stefanyk Precarpathian National University

PhD, Associate Professor

Department of Computer Engineering and Electronics

Stepan Melnychuk, Ivano-Frankivsk National Technical University of Oil and Gas

Doctor of Technical Sciences, Professor

Department of Computer Systems and Networks

Iryna Manuliak, Ivano-Frankivsk National Technical University of Oil and Gas

PhD, Associate Professor

Department of Computer Systems and Networks

Andrii Terletsky, Vasyl Stefanyk Precarpathian National University

PhD, Associate Professor

Department of Computer Engineering and Electronics

Mykhailo Deichakivskyi, Vasyl Stefanyk Precarpathian National University

Postgraduate Student

Department of Computer Engineering and Electronics

References

  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/
Design of various operating devices for sorting binary data

Downloads

Published

2023-08-31

How to Cite

Hryha, V., Dzundza, B., Melnychuk, S., Manuliak, I., Terletsky, A., & Deichakivskyi, M. (2023). Design of various operating devices for sorting binary data. Eastern-European Journal of Enterprise Technologies, 4(4 (124), 6–18. https://doi.org/10.15587/1729-4061.2023.285997

Issue

Vol. 4 No. 4 (124) (2023): Mathematics and Cybernetics - applied aspects

Section

Mathematics and Cybernetics - applied aspects

License

Copyright (c) 2023 Volodymyr Hryha, Bogdan Dzundza, Stepan Melnychuk, Iryna Manuliak, Andrii Terletsky, Mykhailo Deichakivskyi

Creative Commons License

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

The consolidation and conditions for the transfer of copyright (identification of authorship) is carried out in the License Agreement. In particular, the authors reserve the right to the authorship of their manuscript and transfer the first publication of this work to the journal under the terms of the Creative Commons CC BY license. At the same time, they have the right to conclude on their own additional agreements concerning the non-exclusive distribution of the work in the form in which it was published by this journal, but provided that the link to the first publication of the article in this journal is preserved.

A license agreement is a document in which the author warrants that he/she owns all copyright for the work (manuscript, article, etc.).
The authors, signing the License Agreement with TECHNOLOGY CENTER PC, have all rights to the further use of their work, provided that they link to our edition in which the work was published.
According to the terms of the License Agreement, the Publisher TECHNOLOGY CENTER PC does not take away your copyrights and receives permission from the authors to use and dissemination of the publication through the world's scientific resources (own electronic resources, scientometric databases, repositories, libraries, etc.).
In the absence of a signed License Agreement or in the absence of this agreement of identifiers allowing to identify the identity of the author, the editors have no right to work with the manuscript.
It is important to remember that there is another type of agreement between authors and publishers – when copyright is transferred from the authors to the publisher. In this case, the authors lose ownership of their work and may not use it in any way.