Accurate data redistribution cost estimation in software distributed shared memory systems

Distributing data is one of the key problems in implementing efficient dist ributed-memory parallel programs. The problem becomes more difficult in pro grams where data redistribution between computational phases is considered. The global data distribution problem is to find the optimal distribution i n multi-phase parallel programs. Solving this problem requires accurate kno wledge of data redistribution cost. We are investigating this problem in the context of a software distributed shared memory (SDSM) system, in which obtaining accurate redistribution cos t estimates is difficult. This is because SDSM communication is implicit: I t depends on access patterns, page locations, and the SDSM consistency prot ocol. We have developed integrated compile- and run-time analysis for SDSM system s to determine accurate redistribution cost estimates with low overhead. Ou r resulting system,, SUIF-Adapt, can efficiently and accurately estimate ex ecution time, including redistribution, to within 5% of the actual time in all of our test cases and is often much closer. These precise costs enable SUIF-Adapt to find efficient global data distributions in multiple-phase pr ograms.