Sorting is one of the common problems of data processing and it is generally understood as a problem of placing elements of disordered set of data sets values in order of monotonic increase or decrease [1]. The sorting operation takes on average 25% of machine time [2] and it is most often used in the tasks of digital processing of signals and images, similar to convolution operations, fast Fourier transform, and others [3]. We know many methods of sequential and parallel sorting of binary numbers [1][2][3][4][5][6][7][8][9]. There is a large number of algorithms to organize sorting in modern digital signal processors, and each of these algorithms has its advantages and disadvantages. Performing a software sorting operation is time-consuming and generally used to perform consistent data sorting methods. Particularly effective is the parallel performance of algorithm sorting operations using hardware methods that significantly accelerate the execution time of the algorithm. Such methods of parallel sorting algorithms, in which the sequence of executed operations only depends on the number of input data, are the following: the Batcher's method [2], the modified "bubbles" method [1], the "pairwise-odd" permutation method, the fusion method and other [3].
If we use the hardware method, then there is ensured implementation of the binary number sorting operation in real time and the possibility of applying new circuit design solutions with the use of a modern element base with an orientation towards implementation in the FPGA form.
The implementation of highly efficient conveyor devices for sorting binary arrays requires extensive use of a modern element base, the improvement of existing and the development of new methods, algorithms and device structures.
In this regard, an important t ask is to develop efficient structures for conveyor sorting devices (CSDs), which will improve the time characteristics of multithreaded data processing. The implementation of such devices in the languages of the hardware description and their synthesis in FPGA will enable the designer to choose the optimal hardware cost and time-efficient characteristics of the structure of the CSD.
The conveyor processing principle involves the alignment in time operators of the algorithms sorting on different data [5][6][7][8].
Conveyor structures of sorting devices of binary arrays is developed and analyzed below. They are based on the known parallel sorting algorithms presented in a graphical form, and their hardware and time complexity are estimated. (Their system characteristics)
The hardware implementation of the known parallel sorting algorithms in the conveyor structures involves the full reflection of their flow graphs algorithm (tiered-parallel algorithm forms) [4][5][6][7][8]10,11,13] into the structure of the operating device. The vertices of the graph (functional operators) will correspond to the hardware block (operation) and the arcs will correspond to lines for the transmission of input data of intermediate and final results. The conveyor registers are placed on the lines that connect the operating units of one tier with the operating units of the previous tier.
Tier-parallel algorithm forms determines the degree of parallelism of the graph (the maximum number of vertices in a single tier or the width of the graph), as well as the minimum-possible time of calculation of the given algorithm (number of tiers or height of the graph) [6][7][8].
It is shown the structure of the CSD in Fig. 1, which is based on the numbers sorting by modified "bubbles" sorting method [1,13]. The basis for the above-presented structure of conveyor sorting device is the basic sorting elements (BSE) and conveyor register (Rg).
The structure of this conveyor device consists of the same basic sorting operations (max/min). CSD structure (Fig. 1) contains N(N-1)/2 basic sorting operations and N(2N-3) conveyor registers for input N values.
The time complexity of this conveyor device structure is determined by the critical distribution of the signal through (2N-3) basic operations of sorting and (2N-3)+1 conveyor registers.
It is shown the structure of the CSD in Fig. 2, which is constructed on the basis of sorting algorithm by "pairwiseodd" permutation method [2,13].
CSD structure (Fig. 2) contains N(N-1)/2 basic sorting operations and (N × N) conveyor registers for N input values.
The time complexity of this conveyor device structure is determined by the critical distribution of the signal through N basic operations of sorting and (N+1) conveyor registers.
It is shown the CSD structure in Fig. 3, which is constructed on the basis of the sorting algorithm graph by Batcher's method [3,13]. x conveyor registers.
The conveyor structures of the sorting devices (Fig. 1-3) consist of the same type of basic sorting elements that compare two numbers and more of them are sent to the first output and less to the second output. The internal structure of sorting basic element is presented in Fig. 4. When comparing two numbers (X1, X2) in the comparison scheme "for more" (X1> X2), the output of the scheme is formed a comparison sign, the direct value of which controls the multiplexer M1, to issue a smaller number to the output (Y1) and the inverse value controls the multiplexer M2 to issue a larger number at the output (Y2) [5,13].
The internal structure of the comparison scheme can be constructed on the basis of logical elements [5] or accelerated carry adders [13].
The calculation of the hardware and time complexity of different comparison schemes and 2-input multiplexers is given in paper [6].
With the account to these data, the hardware complexity of the CSD by the modified "bubbles" method for N = 8 and n= 4 equals:
The bubble CSD (Fig. 1) can be improved by performing independent base-sorting operations separately for the first and second half of the input data on the two conveyor structures. It is shown an improved CSD for 4-bit binary numbers (n = 4) for 8 input values (N =8) in Fig. 5. The time complexity of such CSD is equal to:
It is shown a dependence graph of logical elements (valves) number on the input data number for the conveyor structures of the known (classical) and improved sorting devices by the modified "bubbles" method. The graph shows that the number of logical elements for an improved CSD is 1.9 times less than for a classic CSD.
It is shown a graph of the dependence of the time complexity in Fig. 7 expressed in the microtacts on the input data value for the structures of the known (classical) CSD and the improved CSD with the modified "bubbles" method. Table 1 presents the results of the synthesis of implemented CSDs for sorting 8 one-byte numbers on the FPGA of the Xilinx firmware. As can be seen from Table 1, experimental results coincide with analytical calculations.
During the research of CSDs it is determined that they are widely used in multithreaded data processing, and are often used in digital processing of signals, images and sorting networks for the rapid transfer of large data arrays.
The improved structure of the CSD of binary arrays by the modified "bubble" method was developed, the hardware and time complexity calculation was performed.
As a result of the comparison with the classical CSD for binary number array by the modified bubble method it is received decreasing the cost of the equipment in 1.9 times and increasing of speed in 1.5 times, which is confirmed by the results of the practical implementation of the Xilinx FPGA.