MPI-INF/SWS Research Reports 1991-2021

2. Number - All Departments


Asynchronous parallel disk sorting

Sanders, Peter and Dementiev, Roman

February 2003, 22 pages.

Status: available - back from printing

We develop an algorithm for parallel disk sorting, whose I/O cost approaches the lower bound and that guarantees almost perfect overlap between I/O and computation. Previous algorithms have either suboptimal I/O volume or cannot guarantee that I/O and computations can always be overlapped. We give an efficient implementation that can (at least) compete with the best practical implementations but gives additional performance guarantees. For the experiments we have configured a state of the art machine that can sustain full bandwidth I/O with eight disks and is very cost effective.

  • Attachement: (447 KBytes)

URL to this document:

Hide details for BibTeXBibTeX
  AUTHOR = {Sanders, Peter and Dementiev, Roman},
  TITLE = {Asynchronous parallel disk sorting},
  TYPE = {Research Report},
  INSTITUTION = {Max-Planck-Institut f{\"u}r Informatik},
  ADDRESS = {Stuhlsatzenhausweg 85, 66123 Saarbr{\"u}cken, Germany},
  NUMBER = {MPI-I-2003-1-001},
  MONTH = {February},
  YEAR = {2003},
  ISSN = {0946-011X},