C&SA | Contents

Volume 58 >>> № 1 JANUARY — FEBRUARY 2022

-->

UDC 004.94.2

T.B. Martyniuk¹, B.I. Krukivskyi²

¹ Vinnytsia National Technical University,
Vinnytsia

martyniuk.t.b@gmail.com

² Vinnytsia National Technical University,
Vinnytsia

smiletex11@gmail.com

PECULIARITIES OF THE PARALLEL SORTING ALGORITHM WITH RANK FORMATION

Abstract. A new approach to parallel sorting of an array of numbers with the formation of their ranks is analyzed. In the process of sorting, such operations are implemented as a decrement operation for the processing of elements of a numerical array and an increment operation for the formation of their ranks. A description of the parallel sorting algorithm with the formation of ranks in the basis of Glushkov’s System of Algorithmic Algebras (SAA) is proposed.

Keywords: system of algorithmic algebras, parallel sorting, numerical slice, rank, mask.

FULL TEXT

REFERENCES

Knuth D.E. The art of computer programming. Vol. 3, Sorting and searching. Reading: Addison-Wesley Longman, Inc., 1998. 800 p.

Pratt W.K. Introduction to digital image processing. Reading: Taylor and Francis Group, Inc., 2014. 371 p.

Osinsky V.I., Martynyuk T.B., Kozlov A.A., Mohamed Salem Nasser Mohamed. Features of the optoelectronic implementation of the sorting neural network. Optiko-elektronnyye informatsionno-silovyye tekhnologii. 2009. Vol. 18, N 2. P. 58–67.

Tseitlin G.E. Designing sequential sorting algorithms: classification, transformation, synthesis. Programmirovaniye. 1989. N 3. P. 3–24.

Tseitlin G.E. Parallelizing sorting algorithms. Kibernetika. 1989. Vol. 24, N 6. P. 67–74.

Yatsenko E.A. Regular schemes of algorithms for address sorting and searching. Upravlyayushchiye sistemy i mashiny. 2004. N 5. P. 61–66.

Kozhemiako V.P., Martyniuk T.B., Khomyuk V.V. Distinctive features of structural programming of synchronous sorting algorithms. Cybernetics and Systems Analysis. 2006. Vol. 42, N 5. P. 714–723.

Tseitlin G.E. Structured programming of symbolic multiprocessing tasks. Kibernetika. 1983. Vol. 19, N 5. P. 22–30.

Tseitlin G.E. Glushkov algebras and clone theory. Kibernetika i sistemnyj analiz. 2003. Vol. 39, N 4. P. 48–58.

Andon F.I., Doroshenko A.E., Tseitlin G.E., Yatsenko E.A. Algebraic algorithmic models and methods of parallel programming [in Russian]. Kiev: Academperiodika, 2007. 634 p.

Andon F.I., Doroshenko A.E., Zhereb K.A. High performance parallel computing programming: formal models and graphics accelerators. Kibernetika i sistemnyj analiz. 2011. Vol. 47, N 4. P. 176–187.

Andon F.I., Doroshenko A.E., Beketov A.G., Iovchev V.A., Yatsenko E.A. Automation tools for parallel programming based on the algebra of algorithms. Kibernetika i sistemnyj analiz. 2015. Vol. 51, N 1. P. 162–170.

Kohonen T. Content-addressable memories. Berlin; Heidelberg: Springer-Verlag, 1987. 388 p.

Thurber K.J. Large scale computer architecture: Parallel and associative processors. NJ.: Hayden Book Company, 1976. 324 p.

Martyniuk T.B. Structure of associative processor with bitwise serial processing of data. Engineering Simulation. 1997. Vol. 14. P. 383–389.

Martyniuk T., Vasilyeva T., Suprigan V., AL-Heyari M. Features of sorting memory realization. Proceedings of SPIE (The International Society for Optical Engineering). 2001. Vol. 4425. P. 89–91.

Martynyuk T., Kuperstein L., Kozhemyako A. Aspects of difference-slice data processing in neurostructures [in Russian]. LAMBERT Academic Publishing RU, 2018. 60 p.

Martyniuk T.B., Khomyuk V.V. Data array multiprocessing by difference slices. Cybernetics and Systems Analysis. 2011. Vol. 47, N 6. P. 948–953. https://doi.org/10.1007/s10559-011-9374-7.

Martyniuk T.B., Kozhemiako A.V., Kupershtein L.M. Formalization of the object classification algorithm. Cybernetics and Systems Analysis. 2015. Vol. 51, N 5. P. 751–756. https://doi.org/10.1007/s10559-015-9767-0.

Lorin H. Sorting and sort systems. Mass.: Addison-Wesley Publishing Company, 1975. 373 p.

Kucherenko K.I., Ochin E.F. Two-dimensional median image filtering processors based on sorting networks. Autometry. 1988. N 2. P. 13–19.

Martyniuk T.B., Denisyuk N.O., Krukivsky B.I. Associative processors with parallel-serial data processing. Information technology and computer engineering. 2019. Vol. 44, N 1. P. 27–36. https://doi.org/10.31649/1999-9941-2019-44-1-27-36.

Martyniuk T.B., Krukivsky B.I. Model of parallel sorter of an array of numbers. Visnyk Vinnytsʹkoho politekhnichnoho instytutu. 2020. Vol. 152, N 5. P. 49–55. https:// doi.org/10.31649/1997-9266-2020-152-5-49-55.