A Comparative Study of Sorting Algorithms with FPGA Acceleration by High Level Synthesis
Abstract: 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 a sorting 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 deviation and 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, TimSort is the best algorithm.
Auteurs principaux: | Ben Jmaa,Yomna, Ben Atitallah,Rabie, Duvivier,David, Ben Jemaa,Maher |
---|---|
Format: | Digital revista |
Langue: | English |
Publié: |
Instituto Politécnico Nacional, Centro de Investigación en Computación
2019
|
Accès en ligne: | http://www.scielo.org.mx/scielo.php?script=sci_arttext&pid=S1405-55462019000100213 |
Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
Documents similaires
-
A New Approach For Hand Gestures Recognition Based on Depth Map Captured by RGB-D Camera
par: Ben Jmaa,Ahmed, et autres
Publié: (2016) -
FPGA implementation of the AES-128 algorithm in non-feedback modes of operation
par: Guzmán,Ian Carlo, et autres
Publié: (2016) -
Efficiency of Phase Unwrapping and Image Filtering Algorithms Implemented in a Fpga Applied on Holographic Interferometry
par: Juárez Núñez,Víctor Manuel, et autres
Publié: (2019) -
Non-dominated Sorting Genetic Algorithm-II
par: The Forage Seed and Cereal Research (17480601)
Publié: (2019) -
Data Structures and Algorithms 1 [electronic resource] : Sorting and Searching /
par: Mehlhorn, Kurt. author., et autres
Publié: (1984)