An Optimization Theory for Structured Stencil-based Parallel Applications

In this thesis, we introduce a new optimization theory for stencil-based applications which is centered both on a modification of the well known owner-computes rule and on base but powerful properties oftoroidal spaces. The proposed optimization techniques provide notable results in different computational aspects: from the reduction of communication overhead to the reduction of computation time, through the minimization of memory requirement without performance loss. All classical optimization theory is based on defining transformations that can produce optimized programs which are computationally equivalent to the original ones. According to Kennedy, two programs are equivalent if, from the same input data, they produce identical output data. As other proposed modifications to the owner-computes rule, we exploit stencil application feature of being characterized by a set of consecutive steps. For such configurations, it is possible to define specific two phase optimizations. The first phase is characterized by the application of program transformations which result in an efficient computation of an output that be easily converted into the original one. In other words the transformed program defined by the first phase is not computational equivalent with respect to the original one. The second phase converts the output of the previous phase back into the original one exploiting optimized technique in order to introduce the lowest additional overhead. The phase guarantees the computational equivalence of the approach. Obviously, in order to define an interesting new optimization technique, we have to prove that the overall performance of the two phases sequence is greater than the one of the original program. Exploiting a structured approach and studying this optimization theory on stencils featuring specific patterns of functional dependencies, we discover a set of novel transformations which result in significant optimizations. Among the new transformations, the most notable one, which aims to reduce the number of communications necessary to implement a stencil-based application, turns out to be the best optimization technique amongst those cited in the literature. All the improvements provided by transformations presented in this thesis have been both formally proved and experimentally tested on an heterogeneous set of architectures including clusters and different types of multi-cores