max planck institut
informatik

# MPI-I-92-149

## 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.
Acknowledgement:
References to related material:

MPI-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: http://domino.mpi-inf.mpg.de/internet/reports.nsf/NumberView/1992-149
BibTeX
@TECHREPORT{Hagerup92,
AUTHOR = {Hagerup, Torben},
TITLE = {Fast deterministic processor allocation},
TYPE = {Research Report},
INSTITUTION = {Max-Planck-Institut f{\"u}r Informatik},