Startseite > Publikationen > Publikationen

Publikationen

Meyer auf der Heide, Friedhelm;Wigderson, Avi:

The Complexity of Parallel Sorting.

FOCS 1985 : S. 532-540, Jul. 1985

Abstract

We consider PRAM's with arbitrary computational power for individual processors, infinitely large shared memory and "priority" write-conflict resolution.
The main result is that sorting n integers with n processors require Ω(√(log n)) steps in this strong model.
We also show that computing any symmetric polynominal (e.g. the sum or product) of n integers requires exactly log_2(n) steps, for any finite number of processors.

Bibtex

@article{hniid=1935,
author = {Meyer auf der Heide, Friedhelm and Wigderson, Avi},
title = {The Complexity of Parallel Sorting},
journal = {FOCS 1985},
pages = {532-540},
month = jul,
year = {1985},
}

BibTeX in die Zwischenablage kopieren

Permalink

https://www.hni.uni-paderborn.de/pub/1935