Empirical Studies in Parallel Sorting

Loading...
Thumbnail Image

Files

CS-TR-4038.ps (2.33 MB)
No. of downloads: 97
CS-TR-4038.pdf (1.52 MB)
No. of downloads: 186

Publication or External Link

Date

1999-08-25

Advisor

Citation

DRUM DOI

Abstract

I examine different parallel algorithms for sorting in rounds. Most of these algorithms use a graph to indicate the comparisons to be made. The primary difference between the algorithms is how these graphs are chosen.
One uses graphs that are shown to exist using non-constructive techniques, several yield constructions of the required graphs, and one uses a randomized algorithm. The constructive algorithms would traditionally be preferred even though the processor requirements are higher. It is shown that the non- constructive algorithms can actually be used by generating the needed graphs using random number generators skewed appropriately.

Notes

Rights