Spatial-temporal Transformation of Sorting Algorithm with 'Perfect Interleaving'

Autor: Yaroslav Nykolaichuk, Artur Voronych, Volodymyr Gryga, Ihor Pitukh, Orest Volynskyi
Rok vydání: 2019
Předmět:
Zdroj: 2019 IEEE 15th International Conference on the Experience of Designing and Application of CAD Systems (CADSM).
DOI: 10.1109/cadsm.2019.8779341
Popis: The optimal binary number sorting algorithms for hardware realization are analyzed. Spatial-temporal synthesis of the parallel structure of the sorting algorithm of 16th binary numbers by the method of "perfect interleaving" with the use of spatial and temporal graphs has been carried out. Stream, conveyor and recursive structures of binary number sorting devices are constructed. The analytical expressions for determining of the hardware and time complexity of these devices were obtained and their comparative analysis was carried out. As a result of the theoretical studies, it has been shown that the recursive sorting device has 10,8 times less hardware complexity than the conveyor structure. In the practical implementation of these devices in the VHDL language of and their synthesis on the FPGA, the results of experimental studies are close to theoretical calculations.
Databáze: OpenAIRE