Abstract | ||
---|---|---|
The sort operation is a core part of many critical applications (e.g., database management systems). Despite the large efforts
to parallelize it, the fact that it suffers from high data-dependencies vastly limits its performance. Multithreaded architectures
are emerging as the most demanding technology in leading-edge processors. These architectures include simultaneous multithreading,
chip multiprocessors, and machines combining different multithreading technologies. In this paper, we analyze the memory behavior
and improve the performance of the most recent parallel radix and quick integer sort algorithms on modern multithreaded architectures.
We achieve speedups up to 4.69× for radix sort and up to 4.17× for quicksort on a machine with 4 multithreaded processors
compared to single threaded versions, respectively. We find that since radix sort is CPU-intensive, it exhibits better results
on chip multiprocessors where multiple CPUs are available. While quicksort is accomplishing speedups on all types of multithreading
processers due to its ability to overlap memory miss latencies with other useful processing. |
Year | DOI | Venue |
---|---|---|
2010 | https://doi.org/10.1007/s11227-009-0294-5 | The Journal of Supercomputing |
Keywords | Field | DocType |
Multithreading,Internal database,Simultaneous multithreading,Chip multiprocessor,Database operations,Sorts,Quicksort,Radix sort | Multithreading,Computer science,Radix sort,Parallel computing,sort,Quicksort,Multiprocessing,Simultaneous multithreading,Multi-core processor,Sorting algorithm,Distributed computing | Journal |
Volume | Issue | ISSN |
53 | 2 | 0920-8542 |
Citations | PageRank | References |
4 | 0.42 | 13 |
Authors | ||
3 |
Name | Order | Citations | PageRank |
---|---|---|---|
Layali K. Rashid | 1 | 5 | 1.13 |
Wessam M. Hassanein | 2 | 13 | 2.33 |
Moustafa A. Hammad | 3 | 297 | 19.61 |