Exécution de notre outil de synthèse sur un nouvel article

Résumé : Sequential programs parallelization is an adequate approach to exploit architectural features proposed on parallel computers. This paradigm has been successfully (i.e., industrially) applied on current supercomputers such as the Cray family or Japanese machines ; there, programs generally, but not only, written in sequential Fortran77 are analyzed by smart vectorizers which can detect parallel constructs (loops) and map them on adequate hardware (pipeline processors).We propose to enhance this technique, pioneered by Kuck, with the notion of semantic parallelization ; the principle is to consider the program transformations induced by parallelization as a non-standard denotational semantics of the programming language. Put in an other way, we propose to define a new (i.e., non standard) semantics of the programming language which maps sequential programs into their parallel equivalent ; moreover, this semantic definition is integrated within the denotational framework [Gordo79]. We show how to apply this concept to a toy language ALL, presented in [Jouve86a].First, we propose to parallelize complex commands such as loops with non-index variables in subscripts. We use for that goal semantic informations automatically extracted from the program source. These informations are implemented as systems of linear inequalities on the program variables ; we use them in order to have a better understanding of the memory locations concerned by every statement in the program. This semantic knowledge is important to decide whether two commands are in mutual conflict (because they have a non empty intersection of set of addresses) or not ; this notion is fundamental to parallelize these statements. Second, we detect reductions (in the APL sense) such as the sum of a vector, which can be efficiently implemented on “tree processors”. We designed a symbolic evaluator of the ALL language to detect these constructs [Jouve86b]. We evaluate loop bodies and then try to know (using a pattern-matching technique) whether the corresponding function is associative (i.e., is a reduction operator). Lastly, we try to deal with some type of programs using indirections (implemented by “Scatter/Gather” operations). We propose here a new notion, namely array predicates. These predicates are formulas in the full Presburger arithmetics ; they are automatically built from the program source and give an approximation of the values stored in an array. These informations are subsequently used to decide whether a loop which uses this array as an indirection vector has any conflict. Thanks to results in domain theory and abstract interpretation [Jouve87a], we give correctness proofs for these transformations with respect to ALL standard semantic.A practical byproduct of our approach follows from the fact that a denotational specification is also an executable prototype if all functions have finite domains (i.e., may be implemented as pair lists). We implemented a semantic parallelizer in the ML higher-order functional language (with some critical routines coded in FranzLisp). We have been able to automatically parallelize some toy examples which could not be tackled with previous techniques.