SYNCHRONIZATION MINIMIZATION IN A SPMD EXECUTION MODEL

This paper presents an algorithm for synchronization placement when us ing a SPMD execution model, where synchronizations are enforced only w hen there exists a cross-processor data dependence. In this paper, we investigate two scheduling techniques, loop-based and data-based, both of which use a SPMD model. Using scheduling information from previous stages in the compilation process, a new technique to determine poten tial cross-processor data dependences is presented. Given the minimum number of cross-processor data dependences that must be satisfied, a n ew optimization is used so as to minimize the number of synchronizatio n points needed to satisfy them. This algorithm has been successfully implemented in an experimental compiler. Initial experimental data sho w this technique to be very effective, outperforming existing methods. (C) 1995 Academic Press, Inc.