## Tesi etd-05222010-171909 |

Thesis type

Tesi di dottorato di ricerca

Author

MENEGHIN, MASSIMILIANO

email address

themaxmail@gmail.com

URN

etd-05222010-171909

Title

An Optimization Theory for Structured Stencil-based Parallel Applications

Settore scientifico disciplinare

INF/01

Corso di studi

INFORMATICA

Supervisors

**tutor**Prof. Vanneschi, Marco

Parole chiave

- Stencil Transformations
- Stencil Theory
- Stencil Models
- Data Parallelism
- Stencil Optimizations
- Stencil Based Applications

Data inizio appello

24/06/2010;

Consultabilità

Completa

Riassunto analitico

In this thesis, we introduce a new optimization theory for stencil-based applications which is centered both on a modiﬁcation of the well known owner-computes rule and on base but powerful properties oftoroidal spaces. The proposed optimization techniques provide notable results in diﬀerent 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 deﬁning 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 modiﬁcations to the owner-computes rule, we exploit stencil application feature of being characterized by a set of consecutive steps. For such conﬁgurations, it is possible to deﬁne speciﬁc two phase optimizations.

The ﬁrst phase is characterized by the application of program

transformations which result in an eﬃcient computation of an

output that be easily converted into the original one. In other words the transformed program deﬁned by the ﬁrst 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 deﬁne 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 speciﬁc patterns of functional dependencies, we discover a set of novel transformations which result in signiﬁcant 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 diﬀerent types of multi-cores.

All classical optimization theory is based on deﬁning 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 modiﬁcations to the owner-computes rule, we exploit stencil application feature of being characterized by a set of consecutive steps. For such conﬁgurations, it is possible to deﬁne speciﬁc two phase optimizations.

The ﬁrst phase is characterized by the application of program

transformations which result in an eﬃcient computation of an

output that be easily converted into the original one. In other words the transformed program deﬁned by the ﬁrst 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 deﬁne 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 speciﬁc patterns of functional dependencies, we discover a set of novel transformations which result in signiﬁcant 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 diﬀerent types of multi-cores.

File

Nome file | Dimensione |
---|---|

Massimil...eghin.pdf | 34.29 Mb |

Contatta l'autore |