## A Sub-logarithmic Communication Algorithm for the Completely
Connected Optical Communication Parallel Computer

**Leslie Ann Goldberg and Mark Jerrum**
*Abstract:* In this paper we consider the problem of
interprocessor communication on a *Completely Connected Optical
Communication Parallel Computer* (OCPC). The particular problem
we study is that of realizing an *h-relation.* In this
problem, each processor has at most *h* messages to send and
at most *h* messages to receive. It is clear that any
1-relation can be realized in one step on an OCPC. However, the
best known *p*-processor OCPC algorithm for realizing an
arbitrary *h*-relation for *h*>1 runs in
Theta(*h* + log *p*) expected time. (This algorithm is
due to Valiant and is based on earlier work of Anderson and
Miller.) Geréb-Graus and Tsantilas have asked whether there
is a faster algorithm for *h = o(*log *p)*, in
particular, whether a 2-relation can be realized in
*o(*log*p)* expected time on a *p*-processor OCPC.
In this paper we show that a 2-relation can indeed be realized in
sub-logarithmic time. More generally, we give an algorithm that
realizes an arbitrary *h*-relation on a *p*-processor
OCPC. We show that if *h = O(*log*^{1/2} p)* then the
expected running time of the algorithm is *Theta(h*
log*^{1/2} p)* and the probability that it takes more than
*Theta(h* log*^{1/2} p)* steps can be made as small as
*p^{-alpha}* for any positive constant alpha. Our algorithm is
*pure* in the sense of Geréb-Graus and Tsantilas.

*LFCS report
ECS-LFCS-92-234*

Previous |

Index |

Next