ANALYSES DE REGIONS DE TABLEAUX ET APPLICATIONS

Béatrice CREUSILLET

Résumé :
 
  La complexité et la diversité des machines parallèles à mémoire distribuée
  ou à hiérarchie de mémoires rend leur programmation particulièrement
  délicate. La parallélisation automatique, qui consiste à transformer un
  programme séquentiel exprimé dans un langage de haut niveau en un
  programme parallèle, apparaît alors comme une solution d'avenir. Ce
  processus nécessite d'une part une analyse des dépendances pour exposer le
  parallélisme potentiel, et d'autre part des transformations de programme
  comme la privatisation de tableaux pour accroître la localité des références.
  Nous montrons dans cette thèse comment ceci peut être effectué de manière
  automatique à partir d'analyses de régions de tableaux.
  
  
  Quatre types de régions de tableaux sont décrits. Les régions READ et
  WRITE résument les effets des instructions et des procédures, et sont
  utilisées dans le cadre de l'analyse des dépendances interprocédurales.
  Les régions IN contiennent les éléments de tableaux importés
  par l'instruction courante~; et les régions OUT les éléments
  vers une utilisation ultérieure. Ces deux dernières analyses
  permettent de détecter la localité des calculs. Un nouvel algorithme de
  privatisation de tableaux permettant d'exploiter cette localité est
  présenté. 
  
  
  Ces analyses ne peuvent pas être effectuées de manière exacte à la
  compilation, et il est nécessaire de recourir à des approximations. Les
  analyses approchées inférieurement posent des problèmes particuliers
  lorsque le domaine choisi pour la représentation des ensembles d'éléments
  de tableaux n'est pas clos pour l'union. Nous proposons alors d'utiliser
  un critère d'exactitude calculable pour définir la sous-approximation à
  partir de la sur-approximation. Cette approche est appliquée à la
  représentation des ensembles d'éléments de tableaux sous forme de
  polyèdres convexes.

  
  Les analyses de régions de tableaux sont bien adaptées aux analyses
  macroscopiques, au niveau des séquences d'instructions ou des procédures.
  Ceci nécessite de pouvoir traduire les régions de l'espace de nommage
  d'une procédure à celui d'une autre, malgré les différences entre les
  déclarations des variables (array reshaping). Nous présentons donc
  un nouvel algorithme de traduction permettant de traiter les différents
  problèmes dans un cadre linéaire unifié.  Il apparaît comme une synthèse
  et une extension des techniques existantes.
  
  Cette approche est implantée dans PIPS, le paralléliseur développé à
  l'Ecole des mines de Paris.  Des expériences qualitatives sur des
  applications réelles ont permis de montrer la robustesse de cette
  implantation, ainsi que sa capacité à paralléliser des boucles contenant
  des appels de procédures et nécessitant une privatisation des tableaux à
  l'intérieur des boucles ou des procédures appelées.

 

ARRAY REGION ANALYSES AND APPLICATIONS

Béatrice CREUSILLET

Abstract:


Programming parallel computers with distributed or hierarchical memories is
particularly difficult, because of their complexity and diversity. Automatic
parallelization, which converts high level sequential applications into
parallel programs appears as a promising solution. This technique requires
an analysis of dependences to expose potential parallelism, and program
transformations such array privatization to enhance the locality of
references. We show in this thesis how this can be achieved using array
region analyses.


Four types of array regions are described: READ and WRITE regions summarize
the effects of instructions and procedures, and are used for the analysis of
interprocedural dependences. IN regions contain the array elements imported
by the current statement; whereas OUT regions contain the array elements
exported towards the program continuation. These two analyses characterize
the computation locality, and are the basis of a new privatization algorithm
which exploits this locality.


Exact array regions cannot be computed at compile time, and approximations
must be used instead. However, when the domain chosen for the representation
of array element sets is not closed under set union, the definition of
under-approximations is problematic. We therefore propose to use an
exactness criterion to compute the under-approximation from the
over-approximation. This technique is applied to the representation of array
regions as convex polyhedra.

Array region analyses are well adapted to coarse grain analyses, at the
level of instruction sequences or procedures. Array regions must then be
translated from the name space of a procedure into another, which is
particularly difficult in case of array reshaping. A new algorithm
exclusively based on linear algebra is therefore presented; it appears as a
synthesis and extension of existing techniques.

The whole framework is implemented in PIPS, the parallelizer developed et
Ecole des mines de Paris. Qualitative experiments have shown its robustness,
as well as its ability to parallelize loops containing procedure calls, and
requiring array privatization inside loops or called procedures.