A key measure of the performance of a distributed memory parallel program is the communication overhead. On most current parallel systems, sending data from a local to a remote processor still takes one or two orders of magnitude longer than the time to access data on a local processor. The behavior of the communication overhead of a parallel program can be strongly influenced by program transformations and data distribution strategies. For instance, loop distribution may break a data dependence, and consequently eliminate communication. Loop interchange may allow pulling communication statements out to a higher loop level. Inherently, it is the data distribution scheme which determines the degree of parallelism of a program, and when interprocessor communication is required to carry out a computation. Therefore, providing both programmer and compiler with an automatic communication cost function can considerably alleviate performance tuning of parallel codes.
This paper describes an analytical approach to communication cost estimation of distributed memory regular parallel codes. We will show how to estimate the number of transfers, the amount of data transferred, transfer time, and the network contention. These parameters can be selectively obtained for statements, loops, procedures, and the entire program; furthermore, their effect with respect to individual processors can be examined. Our method is based on modeling loop iteration spaces, array access patterns, and data distributions by intersection and volume operations on n-dimensional polytopes. Additional architecture specific factors are incorporated for transfer times and network contention. It is assumed that problem size and machine parameters are known at compile time which is a common assumption made for many state-of-the-art performance estimators. Program unknowns (e.g., statement execution counts) are derived by a single profile run based on the original sequential program. Large portions of the profile data can be automatically adapted for many important program changes without redoing the profile run.
Clearly, improving other performance parameters such as load balance, cache performance, computation overhead, and execution time can be as important as an efficient communication behavior. The importance of different parameters with respect to the performance of a program is