Efficient optical communication in parallel computers

Abstract

We study the problem of interprocessor communication in a parallel computer model suggested by recent advances in optical technology. The units of the computer (processors with local memory) communicate with each other by transmitting messages. A processor can transmit a message to any other processor, and transmission takes constant time. If two or more processors try to send a message to the same processor no transmission is successful and retransmission must occur. We show how to implement an extremely simple and efficient form of randomized routing in this model. We study, in particular, the problem of realizing arbitrary h-relations. In an h-relation, each processor is the source as well as the destination of at most h messages. We propose a simple and practical distributed randomized algorithm for realizing arbitrary h-relations on an n-processor such network within O(h + log n log log n) parallel communication steps. Our algorithm is pure in the sense that no information aside from actual messages is transmitted between processors. Anderson and Miller [1] and Valiant [19] have derived a @(h + log n) algorithm for the same problem, which achieves optimality for a slightly larger range of h. Their algorithm is complicated as opposed to ours that we believe to be practical. Optimal interprocessor communication algorithms in realistic models of parallel computers are not only interesting in their own sake, they are one of the main components in optimally simulating PRAMs as well aa implementing Valiant's bulk-synchronous parallel model [13, 19, 18].