Max-Planck-Institut für Informatik
max planck institut
mpii logo Minerva of the Max Planck Society


Fast deterministic processor allocation

Hagerup, Torben

MPI-I-92-149. November 1992, 11 pages. | Status: available - back from printing | Next --> Entry | Previous <-- Entry

Abstract in LaTeX format:
Interval allocation has been suggested as a possible
formalization for the PRAM
of the (vaguely defined) processor allocation
problem, which is of fundamental importance
in parallel computing.
The interval allocation problem is, given $n$ nonnegative
integers $x_1,\ldots,x_n$, to allocate $n$ nonoverlapping
subarrays of sizes $x_1,\ldots,x_n$ from within a base
array of
$O(\sum_{j=1}^n x_j)$ cells.
We show that interval allocation problems of size $n$
can be solved in $O((\log\log n)^3)$ time with
optimal speedup on a deterministic CRCW PRAM.
In addition to a general solution to the
processor allocation problem,
this implies an improved deterministic
algorithm for the problem of approximate summation.
For both interval allocation and approximate
summation, the fastest previous deterministic
algorithms have running times of
$\Theta({{\log n}/{\log\log n}})$.
We also describe an application to the problem of
computing the connected components of an
undirected graph.
References to related material:

To download this research report, please select the type of document that fits best your needs.Attachement Size(s):
MPI-I-92-149.pdfMPI-I-92-149.pdf11152 KBytes
Please note: If you don't have a viewer for PostScript on your platform, try to install GhostScript and GhostView
URL to this document:
Hide details for BibTeXBibTeX
  AUTHOR = {Hagerup, Torben},
  TITLE = {Fast deterministic processor allocation},
  TYPE = {Research Report},
  INSTITUTION = {Max-Planck-Institut f{\"u}r Informatik},
  ADDRESS = {Im Stadtwald, D-66123 Saarbr{\"u}cken, Germany},
  NUMBER = {MPI-I-92-149},
  MONTH = {November},
  YEAR = {1992},
  ISSN = {0946-011X},