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

Authors

  • Yomna Ben Jmaa LAMIH-University of Valenciennes ReDCAD ENIS -University of Sfax
  • Rabie Ben Atitallah LAMIH-University of Valenciennes
  • David Duvivier LAMIH-University of Valenciennes
  • Maher Ben Jemaa ReDCAD-ENIS University of Sfax

DOI:

https://doi.org/10.13053/cys-23-1-2999

Keywords:

FPGA, sorting algorithms, heterogeneous architecture CPU/FPGA, zynq platform

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 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.

Author Biographies

Yomna Ben Jmaa, LAMIH-University of Valenciennes ReDCAD ENIS -University of Sfax

Is a Ph.D. student at the National School of Engineering of Sfax, Tunisia, and university of valenciennes and Hainaut-Cambresis (UVHC), France. She is a researcher in Real-Time Embedded system at the ReDCAD and LAMIH Laboratory at the University of Sfax and University of Valenciennes respectively. Yomna obtained her Engineering degree in Computer Science from National School of Engineering of Sfax (ENIS) in 2011 and M.S. degree in Computer Science in 2013 from ENIS. Currently, her research interests are concentrated in Real time embedded system.

Rabie Ben Atitallah, LAMIH-University of Valenciennes

Received his PhD degree in Computer Science from University of Lille1 in March 2008. In September 2009, Rabie Ben Atitallah obtained a full-time position as an Associate Professor in Computer Science at UVHC and a member of LAMIH laboratory (UMR CNRS/UVHC 8201) within the DIM (Decision, Interaction, and Mobility) team. In December 2014, he received the Habilitation degree in Computer Science from the UVHC. In addition, he had the status of Associated Researcher at INRIA Lille Nord Europe within the DaRT and DreamPal team-projects until the end of 2016. Currently, Rabie Ben Atitallah is the scientific animator of the OPTIMOB theme (stands for Optimization and Mobility). Rabie Ben Atitallah was the task manager of INRIA Lille in the frame of the ANR OpenPeople (2009 - 2013). In addition, he was managing several industrial collaborations (more than 10 projects) with Airbus Group Innovation, Airbus Helicopters, Navya, Nolam Embedded Systems, etc. He co-authored more than 80 publications (patents, journals, and international conferences). Due to his significant scientific contributions, he holds the scientific award of excellence and he is nominated as a member of the National University Committee (CNU) in computer science. His research domain covers embedded system design for intelligent transportation.

David Duvivier, LAMIH-University of Valenciennes

Since 2017/09, Dr. David DUVIVIER is a Full Professor in Computer Science at the UVHC (now UPHF,  Polytechnical University of Hauts-de-France), LAMIH. From 2012/01 to 2017/08, he was an Associate Professor at the University of Valenciennes and Hainaut-Cambrésis (UVHC), in the Laboratory of Industrial and Human Automation control, Mechanical engineering and Computer Science (LAMIH). He obtained an accreditation to supervise research ("Habilitation à Diriger des Recherches") in 2015. From 2005 to 2011, he was an Associate Professor at the ULCO. From 2000 to 2005 he was a researcher at the "Centre de Recherches et d’Etudes en Gestion Industrielle" of the Catholic University of Mons, Belgium. He received the Master’s degree in Computer Science from the "Université des Sciences et Technologies de Lille", France, in 1994. He obtained a Ph.D degree in Computer Science at the "Université du Littoral-Côte d'Opale" (ULCO), Calais, France, in 2000. He has been involved in several R&D projects in Belgium and in France. His main research interests are modeling, simulation, optimization, metaheuristics, multicriteria limited time decision making, hybridization, planning and scheduling. His current research areas include Computer science, Discrete Event Simulation, optimization, metaheuristics, multicriteria limited time decision making, hybridization (optimization & simulation)

Maher Ben Jemaa, ReDCAD-ENIS University of Sfax

Obtained his diploma of Engineer in Computer Science from the National School of Computer Sciences ENSI (Tunisia) in 1989, his Ph.D. from the National Institute of Applied Sciences (INSA) Rennes (France) in 1993 and his HdR from the National School of Engineers of Sfax in 2011. He joined the National School of Engineers of Sfax (ENIS) as Assistant Professor of Computer Science in the Department of Computer Science and Applied Mathematics in 1995. He became an Assistant Professor in 1997, an Associate Professor in 2011 and he is a professor since March 2015. He was the head of the Computer Science and Applied Mathematics in the National School of Engineers of Sfax (ENIS) from 2011 to 2017. His current research areas include algorithms, Real Time Operating Systems, Data clustering, Fault Tolerance of distributed systems, and Quality of Service in Ad hoc Networks and routing issue in Wireless Sensor Networks.

Downloads

Published

2019-03-24

Issue

Vol. 23 No. 1 (2019): Recent Advances in Optics and Photonics (Guest Editors: J. J. Sánchez Mondragón, M. Torres Cisneros, R. Guzmán Cabrera)

Section

Articles

License 

Hereby I transfer exclusively to the Journal "Computación y 
Sistemas", published by the Computing Research Center (CIC-IPN),
the Copyright of the aforementioned paper. I also accept that these 
rights will not be transferred to any other publication, in any other 
format, language or other existing means of developing.
I certify that the paper has not been previously disclosed or simultaneo
usly submitted to any other publication, and that it does not contain 
material whose publication would violate the Copyright or other 
proprietary rights of any person, company or institution. I certify that 
I have the permission from the institution or company where I work or 
study to publish this work.
The representative author accepts the responsibility for the publication
of this paper on behalf of each and every one of the authors. 
This transfer is subject to the following conditions:
  • The authors retain all ownership rights (such as patent rights) of this work, except for the publishing rights transferred to the CIC, through this document.
  • Authors retain the right to publish the work in whole or in part in any book they are the authors or publishers. They can also make use of this work in conferences, courses, personal web pages, and so on.
  • Authors may include working as part of his thesis, for non-profit distribution only.