Title :
A comparison of three representative hardware sorting units
Author :
Marcelino, Rui ; Neto, Horácio C. ; Cardoso, João M P
Author_Institution :
UAlg/ISE, Faro, Portugal
Abstract :
Sorting is an important operation for many embedded computing systems. Since sorting large datasets may slowdown the overall execution, schemes to speedup sorting operations are needed. Bearing in mind the hardware acceleration of sorting, we show in this paper an analysis and comparison among three hardware sorting units: sorting network, insertion sorting, and FIFO-based merge sorting. We focus on embedded computing systems implemented with FPGAs, which give us the flexibility to accommodate customized hardware sorting units. We also present a hardware/software solution for sorting data sets with size larger than the size of the sorting unit. This hardware/software solution achieves 20Ã overall speedup over a pure software implementation of the well-known quicksort algorithm.
Keywords :
embedded systems; field programmable gate arrays; sorting; very large databases; FIFO-based merge sorting; FPGA; customized hardware sorting unit; embedded computing system; hardware acceleration; insertion sorting; large dataset sorting; quicksort algorithm; sorting network; Acceleration; Embedded computing; Embedded system; Field programmable gate arrays; Hardware; Microprocessors; Signal processing algorithms; Software algorithms; Sorting; Switches;
Conference_Titel :
Industrial Electronics, 2009. IECON '09. 35th Annual Conference of IEEE
Conference_Location :
Porto
Print_ISBN :
978-1-4244-4648-3
Electronic_ISBN :
1553-572X
DOI :
10.1109/IECON.2009.5415409