Deutsch
 
Hilfe Datenschutzhinweis Impressum
  DetailsucheBrowse

Datensatz

DATENSATZ AKTIONENEXPORT
  Waste makes haste: tight bounds for loose parallel sorting

Hagerup, T., & Raman, R.(1992). Waste makes haste: tight bounds for loose parallel sorting (MPI-I-92-141). Saarbrücken: Max-Planck-Institut für Informatik.

Item is

Dateien

einblenden: Dateien
ausblenden: Dateien
:
MPI-I-92-141.pdf (beliebiger Volltext), 19MB
Name:
MPI-I-92-141.pdf
Beschreibung:
-
OA-Status:
Sichtbarkeit:
Öffentlich
MIME-Typ / Prüfsumme:
application/pdf / [MD5]
Technische Metadaten:
Copyright Datum:
-
Copyright Info:
-
Lizenz:
-

Externe Referenzen

einblenden:

Urheber

einblenden:
ausblenden:
 Urheber:
Hagerup, Torben1, Autor           
Raman, Rajeev1, Autor           
Affiliations:
1Algorithms and Complexity, MPI for Informatics, Max Planck Society, ou_24019              

Inhalt

einblenden:
ausblenden:
Schlagwörter: -
 Zusammenfassung: Conventional parallel sorting requires the $n$ input keys to be output in an array of size $n$, and is known to take $\Omega({{\log n}/{\log\log n}})$ time using any polynomial number of processors. The lower bound does not apply to the more ``wasteful'' convention of {\em padded sorting}, which requires the keys to be output in sorted order in an array of size $(1 + o(1)) n$. We give very fast randomized CRCW PRAM algorithms for several padded-sorting problems. Applying only pairwise comparisons to the input and using $kn$ processors, where $2\le k\le n$, we can padded-sort $n$ keys in $O({{\log n}/{\log k}})$ time with high probability (whp), which is the best possible (expected) run time for any comparison-based algorithm. We also show how to padded-sort $n$ independent random numbers in $O(\log^*\! n)$ time whp with $O(n)$ work, which matches a recent lower bound, and how to padded-sort $n$ integers in the range $ 1..n $ in constant time whp using $n$ processors. If the integer sorting is required to be stable, we can still solve the problem in $O({{\log\log n}/{\log k}})$ time whp using $kn$ processors, for any $k$ with $2\le k\le\log n$. The integer sorting results require the nonstandard OR PRAM; alternative implementations on standard PRAM variants run in $O(\log\log n)$ time whp. As an application of our padded-sorting algorithms, we can solve approximate prefix summation problems of size~$n$ with $O(n)$ work in constant time whp on the OR PRAM, and in $O(\log\log n)$ time whp on standard PRAM variants.

Details

einblenden:
ausblenden:
Sprache(n): eng - English
 Datum: 1992
 Publikationsstatus: Erschienen
 Seiten: 185 p.
 Ort, Verlag, Ausgabe: Saarbrücken : Max-Planck-Institut für Informatik
 Inhaltsverzeichnis: -
 Art der Begutachtung: -
 Identifikatoren: Reportnr.: MPI-I-92-141
BibTex Citekey: HagerupRaman92
 Art des Abschluß: -

Veranstaltung

einblenden:

Entscheidung

einblenden:

Projektinformation

einblenden:

Quelle 1

einblenden:
ausblenden:
Titel: Research Report / Max-Planck-Institut für Informatik
Genre der Quelle: Reihe
 Urheber:
Affiliations:
Ort, Verlag, Ausgabe: -
Seiten: - Band / Heft: - Artikelnummer: - Start- / Endseite: - Identifikator: -