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(logp) 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