DocumentCode :
3513714
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
fYear :
2009
fDate :
3-5 Nov. 2009
Firstpage :
2805
Lastpage :
2810
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;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
Industrial Electronics, 2009. IECON '09. 35th Annual Conference of IEEE
Conference_Location :
Porto
ISSN :
1553-572X
Print_ISBN :
978-1-4244-4648-3
Electronic_ISBN :
1553-572X
Type :
conf
DOI :
10.1109/IECON.2009.5415409
Filename :
5415409
Link To Document :
بازگشت