hide
Free keywords:
-
Abstract:
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.
