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

Autores/as

  • Yomna Ben Jmaa NIS University of Sfax, ReDCAD
  • Rabie Ben Atitallah Polytechnical University Hauts-de-France
  • David Duvivier Polytechnical University Hauts-de-France
  • Maher Ben Jemaa NIS University of Sfax, ReDCAD

DOI:

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

Palabras clave:

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

Resumen

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 deviation and resource utilization. From the experimental results, we show that the Selection Sort is 1.01-1.23 times faster than other algorithms when N < 64; Otherwise, TimSortis the best algorithm.

Biografía del autor/a

Yomna Ben Jmaa, NIS University of Sfax, ReDCAD

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, Polytechnical University Hauts-de-France

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, Polytechnical University Hauts-de-France

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, NIS University of Sfax, ReDCAD

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.

Descargas

Publicado

2019-03-24

Número

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

Sección

Artículos

Licencia

Transfiero exclusivamente a la revista “Computación y Sistemas”, editada por el Centro de Investigación en Computación (CIC), los Derechos de Autor del artículo antes mencionado, asimismo acepto que no serán transferidos a ninguna otra publicación, en cualquier formato, idioma, medio existente (incluyendo los electrónicos y multimedios) o por desarrollar.

Certifico que el artículo, no ha sido divulgado previamente o sometido simultáneamente a otra publicación y que no contiene materiales cuya publicación violaría los Derechos de Autor u otros derechos de propiedad de cualquier persona, empresa o institución. Certifico además que tengo autorización de la institución o empresa donde trabajo o estudio para publicar este Trabajo.

El autor, representante acepta la responsabilidad por la publicación del Trabajo en nombre de todos y cada uno de los autores.

Esta Transferencia está sujeta a las siguientes reservas:

  • Los autores conservan todos los derechos de propiedad (tales como derechos de patente) de este Trabajo, con excepción de los derechos de publicación transferidos al CIC, mediante este documento.
  • Los autores conservan el derecho de publicar el Trabajo total o parcialmente en cualquier libro del que ellos sean autores o editores y hacer uso personal de este trabajo en conferencias, cursos, páginas web personal, etc.