Thesis on automatic parallelization available

I am pleased to announce the availability of my thesis on the web, at URL:


http://www.cri.ensmp.fr/~creusil/REPORTS/A-295.ps.gz (~900 MB)


Title:
ARRAY REGION ANALYSES AND APPLICATIONS


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.




_ Beatrice CREUSILLET ______ creusil@cri.ensmp.fr __________
____________________________ http://www.cri.ensmp.fr/~creusil


Centre de Recherche en Informatique, Ecole des Mines de Paris
35, rue Saint-Honore, F-77305 FONTAINEBLEAU cedex FRANCE
Tel: +33 (0)1 64 69 48 38 Fax: +33 (0)1 64 69 47 09
--

Return to the comp.compilers page.
Search the comp.compilers archives again.