HOME
Full Articles List
Search by Author
Title: DESIGN AND RESEARCH OF OPERATIONAL AND PIPELINED BINARY NUMBER SORTING DEVICES
BibTex 
Open this article in the author's DB |
|
DESIGN AND RESEARCH OF OPERATIONAL AND PIPELINED BINARY NUMBER SORTING DEVICES
|
|
|
|
|
|
|
|
||
|
|
|
|
|
|
1314-2704
|
|
|
|
||
|
|
English
|
|
|
|
18
|
|
|
|
2.1
|
|
|
|
|
|
|
|
||
|
|
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. |
|
|
|
conference
|
|
|
|
||
|
|
||
|
|
18th International Multidisciplinary Scientific GeoConference SGEM 2018
|
|
|
|
18th International Multidisciplinary Scientific GeoConference SGEM 2018, 02-08 July, 2018
|
|
|
|
Proceedings Paper
|
|
|
|
STEF92 Technology
|
|
|
|
International Multidisciplinary Scientific GeoConference-SGEM
|
|
|
|
Bulgarian Acad Sci; Acad Sci Czech Republ; Latvian Acad Sci; Polish Acad Sci; Russian Acad Sci; Serbian Acad Sci & Arts; Slovak Acad Sci; Natl Acad Sci Ukraine; Natl Acad Sci Armenia; Sci Council Japan; World Acad Sci; European Acad Sci, Arts & Letters; Ac
|
|
|
|
279-292
|
|
|
|
02-08 July, 2018
|
|
|
|
website
|
|
|
|
cdrom
|
|
|
|
530
|
|
|
|
data flow graph of algorithm; spatio-temporal graph of algorithm; comparison scheme; pipelined operating device; multi-step operating device.
|
|
Download PDF