COMMUNICATION OPTIMIZATIONS FOR PARALLEL-C PROGRAMS

This paper presents algorithms for reducing the communication overhead for parallel C programs that use dynamically-allocated data structure s. The framework consists of an analysis phase called possible-placeme nt analysis, and a transformation phase called communication selection . The fundamental idea of possible-placement analysis is to find all p ossible points for insertion of remote memory operations. Remote reads are propagated upwards, whereas remote writes are propagated downward s. Based on the results of the possible-placement analysis, the commun ication selection transformation selects the ''best'' place for insert ing the communication, and determines if pipelining or blocking of com munication should be performed. The framework has been implemented in the EARTH-McCAT optimizing/parallelizing C compiler, and experimental results are presented for five pointer-intensive benchmarks running on the EARTH-MANNA distributed-memory parallel architecture. These exper iments show that the communication optimization can provide performanc e improvements of up to 16% over the unoptimized benchmarks.