Efficient communication scheme for solving the S(sub n) equations on message-passing multiprocessors.

摘要

Early models of Intel's hypercube multiprocessors, e.g. the IPSC/I and iPSC/2, were characterized by the high latency of message-passing. This relatively weak dependence of the communication penalty on the size of messages, in contrast to its strong dependence on the number of messages, justified using the Fan-in Fan-out algorithm to perform global operations, such as global sums, etc. Recent models of message passing computers, such as the iPSC/860 and the Paragon, have been found to possess much smaller latency, thus forcing a re-examination of the issue of performance optimization with respect to communication schemes. Essentially, the Fan-in Fan-out scheme minimizes the number of nonsimultaneous messages sent but not the volume of data traffic across the network. Furthermore, if a global operation is performed in conjunction with the message-passing, a large fraction of the attached nodes remains idle as the number of utilized processors is halved in each step of the process. On the other hand, the Recursive Halving scheme offers the smallest communication cost for global operations, but has some drawbacks. First, it requires the simultaneous exchange of messages between adjacent nodes, which while permissible on many message-passing computers, requires additional programing on the iPSC/860, the target platform in this work. Second, full utilization of the processors requires that the message length be a multiple of two, resulting in significant idleness of the processors if this is not the case. In this paper we present an alternative scheme that eliminates the first drawback by communicating along a monodirectional ring, and reduces the impact of the second drawback by requiring only that the number of nodes divides the message length, a standard requirement for retaining load balance.