This paper discusses our experience with fine-grain synchronization for a variant of the preconditioned conjugate gradient method. This algorithm represents a large class of algorithms that have been widely used but traditionally difficult to implement efficiently on vector and parallel machines. Through a series of experiments conducted using a simulator of a distributed shared-memory multiprocessor, this paper addresses two major questions related to tine- One of the challenges in such a design methodology lies in tinding appropriate applications which will provide meaningful information concerning a specific set of mechanisms. The problem of finding an application that is both important and suitable for investigating fine-grain synchronization is particularly difficult because most parallel application studies for MIMD multiprocessors have focused on problems that are uninteresting from the standpoint of synchronization. One of the reasons for this lack of benchmarks is the lack of machines that support fine-grain synchronization. The MICCG3D application meets our criteria because it is an important application with challenging synchronization requirements. Our investigation of fine-grain synchronization has two major aspects. First, we investigate how fine-grain synchronization can be gainfully employed in MICCG3D and determine quantitatively the resulting performance benefits. We analyze the benefits both with a fixed problem size and when problem size is scaled with machine size. Our study uses a simulator of Alewife, a distributed memory multiprocessor that provides hardware support for the sharedmemory abstraction [1] . Our first result is that applications for which synchronization is challenging do exist. Furthermore, implementations on MIMD machines can achieve good performance by employing fine-grain synchronization. Second, through a sequence of experiments, we try to understand exactly where the "muscle" of fine-grain synchronization ties. A common conception of fine-grain synchronization -one which has contributed to the preference for coarse-grain approaches -has been that its success relies on efficient, but expensive, hardware-supported synchronization primitives. We demonstrate that the most significant contributions of fine-grain synchronization for MICCG3D do not rely on hardware acceleration; rather, they arise from the expressiveness and flexibility of language-level support.
Yeung and Agarwal REF explored fine-grain synchronization and language support for preconditioned conjugate gradient on regular problems on Alewife.
Experience with fine-grain synchronization in MIMD machines for preconditioned conjugate gradient
PPOPP '93
Computer Science