Periodic Updates in Processor Networks
In implementing parallel scientific applications, the crux is often efficiency in communication. So, it becomes important to abstract out and study frequently occurring patterns of communication. We describe one such abstraction, periodic update, which arises in such diverse areas as computational molecular dynamics, distributed systems and n-body simulations. Consider a synchronous network of processors. Every processor needs to know the status of every other processor. The status keeps changing and it is more important to know the correct status of nearer processors. The work done in maintenance of status information should be as little as possible. The periodic update problem is that of sending (and receiving) periodic status updates from every processor to every other processor in the network in order to maintain status information. The time interval between successive updates from one processor to another is given by some increasing function (the periodicity function) of the distance between them. Given a network and a periodicity function, we wish to find efficient protocols for the periodic update problem which have minimum delay (time elapsed between the sending of an update and its receipt) and minimum peak bandwidth (maximum number of updates sent across any edge in one time-step). We present a general design paradigm and construct periodic update protocols for the one and two dimensional mesh networks for both polynomial and exponential periodicity functions. Given a periodicity function, we demonstrate a trade-off between delay and peak bandwidth. Then, using two general techniques, we transform minimum delay protocols into families of highly efficient protocols with performances spanning the entire spectrum from minimum delay to minimum peak bandwidth.
computer science; technical report
Previously Published As