Scholarly record

DESIGN AND RESEARCH OF OPERATIONAL AND PIPELINED BINARY NUMBER SORTING DEVICES

Volodymyr Gryga

Abstract

There is carried out the analysis of parallel methods of binary numbers sorting, which allows to represent the algorithm in a graphical form. Particular attention is paid to the methods of binary numbers sorting, which are subject to hardware implementation, namely: the Batcher?s method, the method of "even-odd" permutation, the merging method, the method of "ideal shuffling" and the modified "bubbles" method. The theory of data flow graph of algorithm is studied, which is the basis of graphically specified sorting algorithm and can be paralleled by tiers in the so-called "tier-parallel form", which is the basis for constructing operational and pipelined operating device of binary numbers from the graphical representation of executable algorithms. When applying this theory, the functional operators of the algorithm are replaced by the operating blocks, and arcs - by the lines of data transmission. The theory of spatio-temporal graphs is considered, which allows the same type of functional operators of the data flow graph of the sorting algorithm to combine, using compression along the width and height of the graph, resulting in the corresponding type of spatio-temporal graph with improved computational complexity, which makes it possible to design sequential, serial-parallel, iterative and combined multi-step operating devices with significant reduction of hardware costs and reduced area of the crystal of the integrated circuit for it implementation. There is developed the structures of algorithmic, pipelined and multi-step operating devices of the studied methods of parallel binary numbers sorting and their complexity characteristics are calculated. The advanced circuit design solutions for constructing components of data structures have been proposed, which made it possible to reduce the hardware complexity and increase their time complexity. The analytical expressions for the evaluation of the complexity of the developed operating devices are obtained. It has been determined that algorithmic and pipelined operating devices have high performance and require significant hardware costs, and multi-step operating devices have significantly lower performance, but the hardware costs and the occupied area on the crystal are minimal. There is executed the synthesis of VHDL-models of the developed structures of algorithmic, pipelined and multi-step operating devices of sorting on the FPGA of Xilinx with the use of the system of Vivado automated designing. As a result, a comparative analysis of the characteristics of the complexity of the obtained structures of the sorting operating devices compared with the known ones was made, the useful areas of their application were determined and the results of the practical implementation on the FPGA were provided.

Publication Impact Profile

• Citations
• CrossRef - Citation Indexes: 1
• Scopus - Citation Indexes: 2

• Captures
• Mendeley - Readers: 1

PLUMX see details

DOI resolver: doi.org/10.5593/sgem2018/2.1/s07.036

Publication details

Back to publication list