Document Type

Technical Report

Department

Computer Science and Engineering

Publication Date

1994-01-01

Filename

WUCS-94-3.PDF

Technical Report Number

WUCS-94-3

Abstract

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.

Comments

Permanent URL: http://dx.doi.org/10.7936/K7SB43Z4

Download

Share

COinS