Name
Abstract | ||
|---|---|---|
Sorting long sequences of keys is a problem that occurs in many different applications. For embedded systems, a uniprocessor software solution is often not applicable due to the low performance, while realizing multiprocessor sorting methods on parallel computers is much too expensive with respect to power consumption, physical weight, and cost.We investigate cost/performance tradeoffs for hybrid sorting algorithms that use a mixture of sequential merge sort and systolic insertion sort techniques. We propose a scalable architecture for integer sorting that consists of a uniprocessor and an FPGA-based parallel systolic co-processor. Speedups obtained analytically and experimentally and depending on hardware (cost) constraints are determined as a function of time constants of the uniprocessor and the co-processor. |
Year | DOI | Venue |
|---|---|---|
2000 | 10.1109/ASAP.2000.862400 | ASAP |
Keywords | Field | DocType |
coprocessors,parallel algorithms,shared memory systems,sorting,systolic arrays,FPGA-based parallel systolic coprocessor,architecture design,cost constraints,cost/performance tradeoffs,embedded systems,hardware constraints,hybrid hardware/software sorter,integer sorting,long key sequences,scalable architecture,sequential merge sort,systolic insertion sort technique,time constants,tradeoff analysis,uniprocessor | Uniprocessor system,Merge sort,Computer science,Parallel algorithm,Insertion sort,Parallel computing,Sorting,Multiprocessing,Real-time computing,Integer sorting,Sorting algorithm | Conference |
ISSN | ISBN | Citations |
1063-6862 | 0-7695-0716-6 | 11 |
PageRank | References | Authors |
1.65 | 3 | 4 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Marcus Bednara | 1 | 119 | 10.99 |
| Oliver Beyer | 2 | 31 | 3.16 |
| Juergen Teich | 3 | 90 | 18.01 |
| Martin Lukasiewycz | 4 | 261 | 28.99 |