The importance of synchronization structure in parallel program optimization
Arjan J. C. van Gemund · 1997
In automatic, retargetable compilation low-cost, analytic cost estimation techniques are crucial in order to efficiently steer the optimization process.Programming models aimed at optimum expressiveness of parallelism, however, are not amenable to static cost estimation.We present a new coordination model, called SPC, that imposes specific restrictions in the synchronization structures that can be programmed.Imposing these restrictions enables the efficient computation of reliable cost estimations paving the way for automatic optimization.Regarding SPC's limited expressiveness we present a conjecture stating that the loss of parallelism when programming in SPC is typically limited to a constant factor of 2 compared to the unrestricted case.This limited loss is outweighed by the unlocked potential of automatic performance optimization as well as the portability that is achieved.We demonstrate how SPC enables automatic program optimizations through a compilation caSe study involving a line relaxation kernel on a distributedmemory machine.