On the loss of parallelism by imposing synchronization structure
Arturo González Escribano, Valentín Cardeñoso-Payo, Arjan J. van Gemund · Research Repository (Delft University of Technology) · 1997
Recently a new parallel programming model has been presented that imposes synchronization restrictions in order to allow for fully automatic, retargetable program optimization. The motivation for the model is the conjecture that in practice the loss of parallelism due to the inherent synchronization restrictions is less than a factor of 2. In this paper we provide compelling evidence in favor of this conjecture, based on the results of a largely empirical investigation into the ratio between the critical paths of unstructured task graphs and their approximations under the restricted synchronization model. 1 INTRODUCTION A long-term goal in program compilation for parallel and distributed systems is the development of compile-time techniques that perform optimizations automatically, without requiring costly user interaction, thus providing portability as well as performance. For example, in the case of a distributed-memory target machine the compiler should be able to automatically de...