Development and Research of Conveyor Structures of Binary Number Sorting Algorithms

Abstract

The characteristics of the structures complexity of conveyor sorting devices, constructed on the basis of parallel algorithms for sorting binary arrays are analyzed. The improved structure of the conveyor sorting device, which compared to the known one had 1.9 times less hardware complexity and 1.5 times higher performance, was developed and researched. Modeling of VHDL models of conveyor sorting devices was carried out, their synthesis and implementation was made in the Xilinx FPGA by automated designing Vivado system applications. The received practical results of the complexity characteristic of the developed conveyor devices coincide with theoretical calculations. There are also determined the relevant areas of application of the developed devices.

I. INTRODUCTION

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-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.

II. CONVEYOR STRUCTURES ANALYSIS OF PARALLEL ALGORITHMS FOR BINARY NUMBERS SORTING The conveyor processing principle involves the alignment in time operators of the algorithms sorting on different data [ 5-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-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-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 ].

x1 Rg1 x2 Rg2 x3 Rg3 x4

Rg4 Rg13

Rg14

Rg15

Rg16 Rg37

Rg38

Rg39

Rg40

Rg41

Rg42 Rg5

Rg6

Rg7

Rg8

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].

x1 Rg1 x2 Rg2 x3 Rg3 x4 Rg4 x5 Rg5 x6 Rg6 BSE1

BSE2

BSE3 Rg7

Rg8

Rg9

Rg10

Rg11

Rg12 BSE4

BSE5 Rg13

Rg14

Rg15

Rg16

Rg17

Rg18 BSE6

BSE7

BSE8 Rg19

Rg20

Rg21

Rg22

Rg23

Rg24 BSE9

BSE10 Rg25

Rg26

Rg27

Rg28

Rg29

Rg30 BSE11

BSE12

BSE13 Rg31

Rg32

Rg33

Rg34

Rg35

Rg36 BSE14

BSE15 y1 y2 y3 y4 y5 y6 Fig.2. The structure of Conveyor sorting device for 6 values by "pairwise-odd" permutation method. x1 x2 x3 x4 x5 x6 x7 x8 Rg1

Rg2

Rg3

Rg4

Rg5

Rg6

Rg7

Rg8 BSE1

BSE2

BSE3

BSE4 Rg9

Rg10

Rg11

Rg12

Rg13

Rg14

Rg15

Rg16 BSE5

BSE6

BSE7

BSE8 Rg17

Rg18

Rg19

Rg20

Rg21

Rg22

Rg23

Rg24 BSE9

BSE10 Rg25

Rg26

Rg27

Rg28

Rg29

Rg30

Rg31

Rg32 BSE11

BSE12

BSE13

BSE14 Rg33

Rg34

Rg35

Rg36

Rg37

Rg38

Rg39

Rg40 BSE15

BSE16

BSE17 Rg41

Rg42

Rg43

Rg44

Rg45

Rg46

Rg47

Rg48 BSE18

BSE19 Rg49

Rg50

Rg51

Rg52

Rg53

Rg54

Rg55

Rg56 y1 y2 y3 y4 y5 y6 y7 y8

CSD structure (Fig. 3) contains 0, 48Nln2 N basic sorting operations and 1 (log2 N ) ([log2 N + 1]) × N conveyor 2 registers for N input values.

The time complexity of this conveyor device structure is determined by the critical distribution of the signal through 1 (log2 N ) (log2 N +1) basic operations of sorting and (N-1) 2 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.

М1 Y1(Min)

X1

X 2 Comparison

Scheme 1 М2 Y (Max) 2

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:

ACCSD = N × (N -1)/2 × (ACS + 2 × AMP )+(n × AREG × ×LREG ) = 28 × (24 + 56)+(4 × 4 ×112) = 4032 (gates), where ACCSD - hardware complexity of classical CSD, ACS - hardware complexity of comparison scheme, τ CS - time complexity of comparison scheme, τ MP - time complexity of multiplexer,

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.

Values X

i

are already ordered by recession and need to be further applied to (( N 2)2 − N 2) / 2 + N 2 basic sorting elements and 4N conveyor registers.

It is shown an improved CSD for 4-bit binary numbers (n = 4) for 8 input values (N =8) in Fig. 5.

x8 x7 x6 x5 x4 x3 x2 x1 Rg8

Rg7

Rg6

Rg5

Rg4

Rg3

Rg2

Rg1 BSE2

BSE1 Rg16

Rg15

Rg14

Rg13

Rg12

Rg11

Rg10

Rg9 BSE3

BSE9 BSE4

BSE10 Rg24

Rg23

Rg22

Rg21

Rg20

Rg19

Rg18

Rg17 BSE8

BSE7

BSE6

BSE5 Rg32

Rg31

Rg30

Rg29

Rg28

Rg27

Rg26

Rg25 Rg40

Rg39

Rg38

Rg37

Rg36

Rg35

Rg34

Rg33 BSE12

BSE11 Rg48

Rg47

Rg46

Rg45

Rg44

Rg43

Rg42

Rg41 BSE16

BSE15

BSE14

BSE13 Rg56

Rg55

Rg54

Rg53

Rg52

Rg51

Rg50

Rg49 BSE19

BSE18

BSE17 Rg64

Rg63

Rg62

Rg61

Rg60

Rg59

Rg58

Rg57 BSE20

BSE21

BSE22 Rg72

Rg71

Rg70

Rg69

Rg68

Rg67

Rg66

Rg65 Rg80

Rg79

Rg78

R77

Rg76

Rg75

Rg74

Rg73 y8 y7 y6 y5 y4 y3 y2

Fig.5. An improved structure of the CSD

y1

The number of basic sorting elements for this CSD for the binary numbers is equal to 3(( N 2)2 − N 2)) / 2 + N 2 , and the number of conveyor registers is 6N + 4N for N input values.

The hardware complexity of an improved CSD for N = 8 and n = 4 is equal to:

AICSD = 22 × (ACS + 2 × AMP )+(n × AREG × LREG ) = =22 × (16 + 24)+(4 × 4 × 80) =2160 (gates), AMP where AICSD - hardware complexity of improved CSD, ACS - hardware complexity of improved comparison scheme [ 13 ],

- hardware complexity of improved multiplexer [ 13 ], AREG - hardware complexity of register, LREG -quantity of conveyor register.

The time complexity of such CSD is equal to: τ ICSD = (τ CS +τ MP ) + (10 ×τ REG ) =

= (3 + 2) + (10 × 2) = 25ν (micro − cycles), where τ CCSD - time complexity of classical CSD; τ CS - time complexity of comparison scheme; τ MP - time complexity of multiplexer; τ REG - time complexity of register.

So, in comparison with the classic device, we get a reduction in the hardware complexity in K =4032 2160 =1,9 times and increase the speed in K

τ IV. RESULTS OF THE CONVEYOR SORTING DEVICES

RESEARCH

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.

A =37 25 =1, 5 time.

It is shown in the graph that the time complexity of an improved CSD requires about 1.5 times less microtacts than the classical CSD.

V. RESULTS OF CSD’S SIMULATION AND SYNTHESIS

ON FPGA

Structures of classical and improved CSD for 8 input –onebyte numbers are described in VHDL (Virtual Hardware Description Language). The simulation of the developed CSDs on the functional level was carried out, their RTL circuits were obtained and the Xilinx FPGA synthesis was performed.

It is shown in Fig. 8 a functional diagram of the improved

CSD operation for 8 input one-byte numbers.

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.

The diagram shows that an array of unsorted 8-bit values is given at the inputs of the CSD (D_in1, ..., D_in8) on the 1st cycle. Then we get a sorted descending order at the outputs (D_out1, ..., D_out8) at the 9th cycle.

It is shown in Fig. 9 the topology view of improved CSD with the VHDL implementation model on the xc7a100tcsg324-1 crystal (Artix-7 family) of the Xilinx firmware by Vivado CAD.

Classic CSD

Blocks

quantity

FPGA (CLB)

Clock frequency (MHz)

Improved CSD

Blocks

quantity

FPGA (CLB)

Clock

frequency

(MHz) 475 174,7 Fig.9. View of the crystal topology of CSD during implementation at the FPGA

Vivado CAD tools placed the implemented VHDL project of the improved CSD almost in the center of the crystal.

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.

VI. CONCLUSION

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.

References

[1] D. Knuth , The art of computer programming, V.3: Transl. from eng . М.: “Peace”, pp. 841 , 1978 .

[2] Thomas Braunl ,. Parallel Programming: Transl. from german ,К.: Vyscha Shkola., pp. 358 , 1997 .

[3] S.Y. Kung , VLSI array processors . Trans. from English - М.: “Peace” , pp. 672 , 1991 .

[4] Thomas H. Cormen , Charles E. Leiserson, Ronald L. Rivest and Clifford Stein . Introduction to algorithms, 3rd edition , Massachusetts Institute of Technology, pp. 1313 , 2009 .

[5] A. Melnyk , Memory with ordered access: monograph , Lviv: Press Lviv Polytechnic, pp. 296 , 2014 .

[6] A. Melnyk , Computer Architecture, Lutsk:Regional publisher, pp. 470 , 2008 .

[7] V. Voevodin , Parallel Computing . Textbook for high schools , BHV:Peter , pp. 608 , 2002 .

[8] Andrew S. Tanenbaum Computer Architecture Austin. 6th ed., St . Petersburg: “Peter”, pp. 816 , 2013 .

[9] O. Kehret , A. Walz and A. Sikora , “ Integration of hardware security modules into a deeply embedded TLS stack ” International Journal of Computing , vol. 15 , issue 1, pp. 24 - 32 , 2016 .

[10] V. Zadiraka , Ya. Nykolaichuk. Methods of effective protection of information flows , Ternopil: Terno-graf, pp. 308 , 2014 .

[11] S. Melnychuk , A. Voronych , L. Nykolaichuk and B. Krulikovskyi “ The Structure and Components of Embedded Special Processors for Determination of Entropy Signals and Random Massages” Perspective technologies and methods in MEMS design . Proceedings of XIIIth International Conference. MEMSTECH 2017 , Lviv- Svalyava , Ukraine, pp. 81 - 84 , February, 2017 .

[12] B. Krulikovskyi , A. Davletova , V. Gryga and Y. Nykolaichuk “Synthesis of Components of High Performance Special Proccessors of Execution of Arithmetic and Logical Operations Dsts Proccessing in Theoretical and Numerical Basis Rademacher” , Proceedings of XIVth International Conference. CADSM' 2017 , Lviv-Poljana , Ukraine, pp. 214 - 217 , February, 2017 .

[13] V. Gryga , Y. Nykolaichuk , N. Vozna and B. Krulikovskyi “ Synthesis of a microelectronic structure of a specialized processor for sorting an array of binary numbers” Perspective technologies and methods in MEMS design . Proceedings of XIIIth International Conference. MEMSTECH 2017 , Lviv- Svalyava , Ukraine, pp. 170 - 173 , April, 2017 .

[14] V. Gryga , I. Kolosov and O. Danyluk “ The development of a fast iterative algorithm structure of cosine transform” The Experience of Designing and Application of CAD System in Microelectronics . Proceedings of XIIIth International Conference. TCSET' 2016 , Lviv-Poljana , Ukraine, pp. 506 - 509 , February, 2016 .

[15] R. Dunets and V. Gryga “ Spatio-temporal synthesis of transformation matrix of reverse fast cosine transformation” , Proceedings of XIIIth International Conference. CADSM' 2015 , Lviv-Poljana , Ukraine, pp. 45 - 49 , February, 2015 .