Parallel FPGA-Based Implementation of Recursive Sorting Algorithms
Dmitri Mihhailov, Valery Sklyarov, Iouliia Skliarova, Alexander Sudnitson · 2010
The paper describes the hardware implementation and optimization of parallel recursive algorithms that sort data using binary trees. Since recursive calls are not directly supported by hardware description languages, they are implemented using the model of a hierarchical finite state machine (HFSM). Parallel processing is achieved by constructing N binary trees (N>;1) and applying concurrent sorting to N trees at the same time with the aid of N communicating HFSMs. The paper presents new results in: 1) parallel sorting algorithms, 2) FPGA-based parallel architectures, and 3) the analysis and comparison of alternative and competitive techniques for implementing parallel recursive algorithms. Experiments demonstrate that the performance of sorting operations is increased compared to previous implementations.