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
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 to a record

Actions (login required)

View Item