Scheduling Parallel Communication: The h-Relation Problem

TitleScheduling Parallel Communication: The h-Relation Problem
Publication TypeTechnical Report
Year of Publication1995
AuthorsAdler, M., Byers J. W., & Karp R. M.
Other Numbers972

This paper is concerned with the efficient scheduling and routing of point-to-point messages in a distributed computing system with n processors. We examine the h-relation problem, a routing problem where each processor has at most h messages to send and at most h messages to receive. Communication is carried out in rounds. Direct communication is possible from any processor to any other, and in each round a processor can send one message and receive one message. The off-line version of the problem arises when every processor knows the source and destination of every message. In this case the messages can be routed in at most h rounds. More interesting, and more typical, is the on-line version, in which each processor has knowledge only of h and of the destinations of those messages which it must send. The on-line version of the problem is the focus of this paper.The difficulty of the h-relation problem stems from message conflicts, in which two or more messages are sent to the same processor in a given round, but at most one can be received. The problem has been well studied in the OCPC optical network model, but not for other contemporary network architectures which resolve message conflicts using other techniques. In this paper, we study the h-relation problem under alternative models of conflict resolution, most notably a FIFO queue discipline motivated by wormhole routing and an arbitrary write discipline motivated by packet-switching networks. In each model the problem can be solved by a randomized algorithm in an expected number of rounds of the form ch + o(h) + log^{?(1)}n, and we focus on obtaining the smallest possible asymptotic constant factor c. We first present a lower bound, proving that a constant factor of 1 is not achievable in general. We then present a randomized algorithm for each discipline and show that they achieve small constant factors.

Bibliographic Notes

ICSI Technical Report TR-95-032

Abbreviated Authors

M. Adler, J. W. Byers, and R. M. Karp

ICSI Publication Type

Technical Report