Skip to Main content Skip to Navigation
Conference papers

An Efficient Hardware Implementation of TimSort and MergeSort Algorithms Using High Level Synthesis

Abstract : Sorting algorithms are one of the most commonly used in computer science. They can be seen as a pillar for some applications such as decision support systems, path planning, etc. However, sorting large number of elements needs high computation rate. Consequently, accelerating sorting algorithms using hardware implementation is an interesting solution to speed up computations. The purpose of this paper is to develop a hardware accelerated version of TimSort and MergeSort algorithms from high level descriptions. The algorithms are implemented using Zynq-7000 xilinx platform as part of real time decision support for avionic applications. As experimental results, we compare the performance of two algorithms in terms of execution time and resource utilization. We showed that TimSort ranges from 1.07x to 1.16x faster than MergeSort when optimized hardware is used.
Document type :
Conference papers
Complete list of metadata

https://hal-uphf.archives-ouvertes.fr/hal-03387958
Contributor : Kathleen Torck Connect in order to contact the contributor
Submitted on : Wednesday, October 20, 2021 - 10:20:08 AM
Last modification on : Wednesday, November 3, 2021 - 4:43:29 AM

Identifiers

Collections

Citation

Yomna Ben Jmaa Chtourou, Karim Mohamed Abedallah Ali, David Duvivier, Maher Ben Jemaa, Rabie Ben Atitallah. An Efficient Hardware Implementation of TimSort and MergeSort Algorithms Using High Level Synthesis. 2017 International Conference on High Performance Computing & Simulation (HPCS), Jul 2017, Genoa, Italy. pp.580-587, ⟨10.1109/HPCS.2017.92⟩. ⟨hal-03387958⟩

Share

Metrics

Record views

9