###
F. Dehne, A. Fabri, and A. Rau-Chaplin, "Scalable parallel computational geometry for coarse grained
multicomputers"

###
Abstract

We study {\em scalable parallel computational geometry} algorithms for
the {\em coarse grained multicomputer} model: $p$ processors solving a
problem on $n$ data items, were each processor has $O(\frac{n}{p}) \gg
O(1) $ local memory and all processors are connected via some
arbitrary interconnection network (e.g. mesh, hypercube, fat tree).
We present $O(\frac{T_{sequential}}{p} + T_s(n,p))$ time scalable
parallel algorithms for several computational geometry problems.
$T_s(n,p)$ refers to the time of a global sort operation.
Our results are independent of the multicomputer's interconnection
network. Their time complexities become optimal when
$\frac{T_{sequential}}{p}$ dominates $T_s(n,p)$ or when $T_s(n,p)$ is
optimal. This is the case for several standard architectures,
including meshes and hypercubes, and a wide range of ratios
$\frac{n}{p}$ that include many of the currently available machine
configurations.
Our methods also have some important {\em practical} advantages: For
interprocessor communication, they use only a small fixed number of
one global routing operation, global sort, and all other programming
is in the sequential domain. Furthermore, our algorithms use only a
small number of very large messages, which greatly reduces the
overhead for the communication protocol between processors. (Note
however, that our time complexities account for the lengths of
messages.) Experiments show that our methods are easy to implement
and give good timing results.

Home* Publications