Technical Report Number
Communication latencies and delays are a major source of performance degradation in parallel computing systems. It is importnat to "mask" these communication delays by overlapping them with useful computation in order to obtain good parallel performance. This paper proposes speculative computation as a technique to mask communication latencies. Speculative computation is discussed in the context of synchronous iterative algorithms. Processors speculate the contents of messages that are not hyet received and perform computation based on the speculated values. When the messages are received, they are compared with the speculated values and, if the error is unacceptable, the resulitng computation is corrected or recomputed. If the error is small, the speculated value is accepted and the processor has masked the communication delay. The technique is discussed in detail and is incorporated on to a N-body simulation example; the techniques result in a performance improvement of up to 34%. An empirical performance model is developed to estimate the performance of speculative computing. Model and measured values are compared and shown to be in good agreement.
Govindan, Vasudha and Franklin, Mark A., "Speculative Computation: Overcoming Communication Delays in Parallel Algorithms" Report Number: WUCS-94-3 (1994). All Computer Science and Engineering Research.