A comparative Study of Sorting Algorithms with FPGA Acceleration by High Level Synthesis

Yomna Ben Jmaa Chtourou , David Duvivier (1) , Ahmed Ben Atitallah , Maher Ben Jemaa

1 LAMIH - Laboratoire d'Automatique, de Mécanique et d'Informatique industrielles et Humaines - UMR 8201

Nowadays, sorting is an important operation for several real-time embedded applications. It is one of the most commonly studied problems in computer science. It can be considered as an advantage for some applications such as avionic systems and decision support systems because these applications need asorting algorithm for their implementation. However, sorting a big number of elements and/or real-time decision making need high processing speed. Therefore, accelerating sorting algorithms using FPGA can be an attractive solution. In this paper, we propose an efficient hardware implementation for different sorting algorithms (BubbleSort, InsertionSort, SelectionSort, QuickSort, HeapSort, ShellSort, MergeSort and TimSort) from high-level descriptions in the zynq-7000 platform. In addition, we compare the performance of different algorithms in terms of execution time, standard deviationand resource utilization. From the experimental results, we show that the SelectionSort is 1.01-1.23 times faster than other algorithms when N < 64; Otherwise, TimSortis the best algorithm.

Mots clés: FPGA; sorting algorithms; heterogeneous architecture CPU/FPGA; zynq platform

Domaines: Informatique [cs]

Yomna Ben Jmaa Chtourou, David Duvivier, Ahmed Ben Atitallah, Maher Ben Jemaa. A comparative Study of Sorting Algorithms with FPGA Acceleration by High Level Synthesis. Computación y sistemas, 2019, 23 (1), pp.213-230. ⟨10.13053/cys-23-1-2999⟩. ⟨hal-03479553⟩