The Library
Doubly logarithmic communication algorithms for opticalcommunication parallel computers
Tools
UNSPECIFIED (1997) Doubly logarithmic communication algorithms for opticalcommunication parallel computers. SIAM JOURNAL ON COMPUTING, 26 (4). pp. 11001119.
Research output not available from this repository, contact author.Abstract
In this paper, we consider the problem of interprocessor communication on parallel computers that have optical communication networks. We consider the completely connected opticalcommunication parallel computer (OCPC), which has a completely connected optical network, and also the meshofopticalbuses parallel computer (MOBPC), which has a mesh of optical buses as its communication network. The particular communication problem that we study is that of realizing an hrelation. In this problem, each processor has at most h messages to send and at most h messages to receive. It is clear that any 1relation can be realized in one communication step on an OCPC. However, the best previously known pprocessor OCPC algorithm for realizing an arbitrary hrelation 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 GerebGraus 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)communicationstep randomized algorithm that realizes an arbitrary hrelation on a pprocessor 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)communicationstep randomized algorithm that realizes an arbitrary hrelation on a p x pprocessor MOBPC. 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:  00975397  
Official Date:  August 1997  
Dates: 


Volume:  26  
Number:  4  
Number of Pages:  20  
Page Range:  pp. 11001119  
Publication Status:  Published 
Data sourced from Thomson Reuters' Web of Knowledge
Request changes or add full text files to a record
Repository staff actions (login required)
View Item 