Name
Abstract | ||
|---|---|---|
A recent trend in hardware development is producing computing systems that are stretching the number of cores and size of shared-memory beyond where most fundamental serial algorithms perform well. The expectation is that this trend will continue. So it makes sense to rethink our fundamental algorithms such as sorting. There are many situations where data that needs to be sorted will actually fit into the shared memory so applications could benefit from an efficient parallel sorting algorithm. When sorting large data (at least hundreds of Gigabytes) in a single shared memory, there are two factors that affect the algorithm choice. First, does the algorithm sort in-place? And second, does the algorithm scale well beyond tens of threads? Surprisingly, existing algorithms possess either one of these factors, but not both. We present an approach that gracefully degrades in performance as the amount of available working memory decreases relative to the size of the input. |
Year | DOI | Venue |
|---|---|---|
2013 | 10.1109/IPDPSW.2013.74 | Parallel and Distributed Processing Symposium Workshops & PhD Forum |
Keywords | Field | DocType |
single shared memory,large data,fundamental algorithm,shared memory,fundamental serial algorithm,algorithm sort in-place,algorithm choice,algorithm scale,available working memory,recent trend,instruction sets,multi threading,memory management,sorting,parallel processing | Sorting network,Timsort,Computer science,In-place algorithm,Parallel computing,Adaptive sort,Sorting,External sorting,Distributed shared memory,Sorting algorithm,Distributed computing | Conference |
ISBN | Citations | PageRank |
978-0-7695-4979-8 | 1 | 0.35 |
References | Authors | |
10 | 3 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| David J. Haglin | 1 | 112 | 19.45 |
| Robert D. Adolf | 2 | 1 | 0.35 |
| Greg E. Mackey | 3 | 1 | 0.35 |