# 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:

To download this research report, please select the type of document that fits best your needs. | Attachement Size(s): |

MPI-I-92-149.pdf | 11152 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},`

` ADDRESS = {Im Stadtwald, D-66123 Saarbr{\"u}cken, Germany},`

` NUMBER = {MPI-I-92-149},`

` MONTH = {November},`

` YEAR = {1992},`

` ISSN = {0946-011X},`

`}`