The theory of specifunctions is applied to a new weakest-design calculus in the context of BSP. The calculus is based on the par-seq specifunction which involves two required components: it places one established component in parallel with one required component and the result in sequence with another required component to meet a given specification. A calculus is provided for the par-seq specifunction and it is applied to the derivation of a distributed BSP algorithm for greatest common divisor.
Each component is augmented with "component dependence metadata", which characterizes the constraints on its execution order, data distribution and memory access order. We show how this supports dynamic adaptation of each component to exploit the available resources, the context in which its operands are generated, and results are used, and the evolution of the problem instance.
Using a computational fluid dynamics visualization example as motivation, we show how component dependence metadata provides a framework in which a number of interesting optimizations become possible. Examples include data placement optimization, loop fusion, tiling, memoization, checkpointing and incrementalization.
The GpH parallel functional language automatically manages most coordination aspects, but also allows some high-level control of coordination using evaluation strategies. We study the coordination behaviour of three typical data parallel programs, and find that while some can be improved by introducing clustering evaluation strategies, others require that the program is restructured. Thus, we introduce a new generic Cluster class that allows clustering to be systematically introduced, and improved by program transformation. In contrast to many other parallel program transformation approaches, we transform large executable programs and report performance results on a 32-processor Beowulf cluster.