# The Library

### Doubly logarithmic communication algorithms for optical-communication parallel computers

Tools

UNSPECIFIED.
(1997)
*Doubly logarithmic communication algorithms for optical-communication parallel computers.*
SIAM JOURNAL ON COMPUTING, 26
(4).
pp. 1100-1119.
ISSN 0097-5397

**Full text not available from this repository.**

## Abstract

In this paper, we consider the problem of interprocessor communication on parallel computers that have optical communication networks. We consider the completely connected optical-communication parallel computer (OCPC), which has a completely connected optical network, and also the mesh-of-optical-buses parallel computer (MOB-PC), which has a mesh of optical buses as its communication network. The particular communication problem that 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 communication step on an OCPC. However, the best previously known p-processor OCPC algorithm for realizing an arbitrary h-relation for h > 1 requires -(h + log p) expected communication steps. (This algorithm is due to Valiant and is based on earlier work of Anderson and Miller.) Valiant's algorithm is optimal only for h = Omega(log p), and it is an open question of Gereb-Graus and Tsantilas whether there is a faster algorithm for h = Omega(log p). In this paper, we answer this question in the affirmative and we extend the range of optimality by considering the case in which h less than or equal to log p. In particular, we present a -(h + log log p)-communication-step randomized algorithm that realizes an arbitrary h-relation on a p-processor OCPC. We show that if h less than or equal to log p, then the failure probability can be made as small as p(-alpha) for any positive constant alpha. We use the OCPC algorithm as a subroutine in a -(h + log log p)communication-step randomized algorithm that realizes an arbitrary h-relation on a p x p-processor MOB-PC. Once again, we show that if h less than or equal to log p, then the failure probability can be made as small as p(-alpha) for any positive constant alpha.

Item Type: | Journal Article |
---|---|

Subjects: | Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software Q Science > QA Mathematics |

Journal or Publication Title: | SIAM JOURNAL ON COMPUTING |

Publisher: | SIAM PUBLICATIONS |

ISSN: | 0097-5397 |

Official Date: | August 1997 |

Volume: | 26 |

Number: | 4 |

Number of Pages: | 20 |

Page Range: | pp. 1100-1119 |

Publication Status: | Published |

URI: | http://wrap.warwick.ac.uk/id/eprint/16528 |

Data sourced from Thomson Reuters' Web of Knowledge

Request changes or add full text files to a record

### Actions (login required)

View Item |