An Integrated Compiler/Run-Time System for Global Data Distribution in Distributed Shared Memory Systems
Gregory M.S. Howard, David K. Lowenthal · 2000
A software distributed shared memory (DSM) provides the illusion of shared memory on a distributed-memory machine; communication occurs implicitly via page faults. For efficient execution of DSM programs, the threads and their implicitly associated data must be distributed to the nodes to balance the computational workload and minimize communication due to page faults. The focus of this paper is on finding effective data distributions in DSM systems both within and across all computational phases. Our model takes into account data redistribution between phases. We have designed and implemented an integrated compiler/runtime system called SUIF-Adapt. The compiler, which is an extended version of SUIF, divides the program into phases, analyzes each, and communicates important information to the run-time system. We use an extended version of Adapt, a run-time data distribution system, to take measurements on an iteration of a loop consisting of one or more phases. It then finds the global data distribution for the loop (over a reasonable set of distributions) that leads to the best completion time. Performance results indicate that programs that use SUIF-Adapt can outperform programs with predetermined data distributions when phase behavior is dependent on run-time values of input data; in such cases, statically determining an effective data distribution requires (generally unavailable) prior knowledge of run-time behavior of an application.