article · 1992

Optimal Deterministic Sorting on Parallel Disks

Cited by 11Abstract and details only

Abstract

We present a load balancing technique that leads to an optimal deterministic algorithm called Balance Sort for external sorting on multiple disks. Our measure of performance is the number of input/output (I/O) operations. In each I/O, each of the D disks can simultaneously transfer a block of data. Our algorithm improves upon the randomized optimal algorithm of Vitter and Shriver as well as the (non-optimal) commonly-used technique of disk striping. It also improves upon our earlier mergebased sorting algorithm in that it has smaller constants hidden in the big-oh notation, and it is possible to implement using only striped writes (but independent reads). In a companion paper, we show how to modify the algorithm to achieve optimal CPU time, even on parallel processors and parallel memory hierarchies.

Cite this paper

APA 7

Nodine, M. H., & Vitter, J. S. (1992). Optimal Deterministic Sorting on Parallel Disks.

MLA 9

Nodine, Mark H., and Jeffrey Scott Vitter. “Optimal Deterministic Sorting on Parallel Disks.” 1992.

Chicago

Nodine, Mark H., and Jeffrey Scott Vitter. 1992. “Optimal Deterministic Sorting on Parallel Disks.”

Harvard

Nodine, M.H. and Vitter, J.S. (1992) ‘Optimal Deterministic Sorting on Parallel Disks’.

BibTeX

@article{nodine1992optimal,
  title = {{Optimal Deterministic Sorting on Parallel Disks}},
  author = {Nodine, Mark H. and Vitter, Jeffrey Scott},
  year = {1992}
}

Made from the index record. Check names, capitalisation and page numbers against the paper. Need another style? AI for Research has over 10,000.