Optimizations for Automatic Extraction of Parallelism
Antonio Magnaghi and Hidehiko Tanaka
The University of Tokyo

1 Introduction
In scienti c research world, massively parallel computers are considered to be one of the most promising answers to the remarkable demand increase in computational power. The continuos improvements in hardware
technologies had made possible to produce computers
based on articulated and complex architecture, indeed
capable of a high system performance on a potentiallevel. However, a frontier challenge is to e ectivelyexploit available resources in order to bridge the gap
between actual and achievable performance. The process of ecient parallel software development becomesa critical factor, being extremely error-prone becauseof the inherent complexity of the programming environment. Parallelizing compilers [2, 3] for imperative
languages aim at automatically discovering as muchparallelism as possible from sequential source code, andat mapping the original program to a modi ed parallel one with improved execution performance. Reconstruction techniques have been extensively developed
for vector computers, but in the eld of massively parallel machines relevant questions still need analysis.

6RXUFHWR6RXUFH &RPSLOHU0LWWZRFK§
1¢-XOL¦ ~
'LDJUDPP& 6RXUFH&RGH)URQW(QG
0DFKLQH ,QGHS
2SW
0LWWZRFK§ 'LDJUDPP
1¢-XOL¦ ~

,QWHUPHGLDWH
5HSUHVHQWDWLRQ%DFN(QG+LWDFKL65
0DFKLQH 'HS
2SW%DFN(QG)XMLWVX$3
0DFKLQH 'HS2SW3DUDOOHO&RGH&$3 /LE

Figure 1: Compiler functional structure
exploited in successive transformations. An intermediate code representation is produced and optimizations are carried out including constant propagation,
loop normalization [3] and induction variables identi cation [2]. In some cases a variety of transformations
might be applicable, but some of them can later inhibit
successive reconstruction phases. Thus, additional information needs to be produced, because it is necessary
to address the issue of \mappings invertibility", in order to undo code transformations, if convenient.
On the other hand, the machine dependent group ofrestructuring tools, to be included as part of the backend, addresses more speci c transformations. Concurrency is to be extracted mainly from loops contained in
the program, basing on data dependency and control
ow analysis. In this context, program transformations
are more strictly linked to architectural characteristicsof the target computer. For instance, improving memory locality through loops reordering and strip-mining
requires additional information about the cache lines
size, data partitioning in shared memory space will result in execution speed-up only if synchronization andcommunication overhead costs are conveniently evaluated.
The adopted strategy is to design a parametric backend for distributed memory computers, basing on peculiar architectural parameters. Therefore it is possible to build a compiler for di erent computers byre-using the portable front-end and by modifying theset of parameters the back-end employs. In particular, our interest is in the massively parallel computer HitachiSR2201 and in FujitsuAP1000. Bothhave distributed-memory and are based on a messagepassing paradigm. Target code performs message passage through MPI (Message Passage Interface) libraryon HitachiSP2201, and through CAP library on FujitsuAP1000.

2 Compiler implementation design
The implementation part of our project is concernedwith the design of a source-to-source compiler ( g.1).
It will perform the fundamental optimizing mappingson input code, producing as output a program to be
executed on a massively parallel computer. In addition to this, our goal is to study reconstruction criteriathat might allow the extraction of more concurrency
on a parallel computer. Our research activity aims at
designing a parallelizing compiler that uses imperative
C-like source code as input to produce optimized parallel code as output. The compiler implementation design considers that the abstraction level of the analyzed
source code has a strong impact on the kind of optimizations to perform. Therefore, a clear distinction isintroduced between high level and low level mappings.
This approach well matches the typical modular organization of commercial compilers into a front-end anda back-end.
The rst group of reconstruction techniques, to beincluded in the front-end of the compiler, relays on
machine independent properties of the input code inorder to increase its portability on di erent systems.
As a rst step, standard optimizing transformations
presented in the literature are being implemented. Thecompiler front-end gathers information about control
ow and dependency analysis to be conveniently1

As concerns the compiler life cycle, an incremental
approach seems to be the most valuable, in order to develop successive extended versions with enlarged setsof optimizing instruments. Hence, new optimizing algorithms can be e ectively integrated with the core of
the compiler itself, enabling a comparative evaluationof performance improvement and a more complete understanding of key factors in parallel computation.
3 Preliminary considerations for parallelism
extraction
Parallel execution requires data distribution and duplication on computer nodes, because of dependencies among di erent program statements. As a consequence, consistency issues arise. It is critical to decide how to map data, because on one hand generally many di erent alternatives are available, and on
the other hand the adopted choice will have a remarkable impact on the global amount of communication.
Therefore some implemented systems require a directinteraction with the programmer.
A possible direction we are interested in investigating is to perform a data partition based on dependency constraints in order to identify distinct code
points from which parallel execution could independently start. Considerations about usage of data in theprogram computations could pinpoint those portions
more weakly or not even interfering with each other insharing information. Thus, improvements can derivefrom limiting locally duplicated data to strictly necessary parts and minimizing communication costs among
computer nodes. In this context, it is worthwhile how
to properly represent data dependency. FUD (FactoredUse De nition [2]) chains are a powerful and compact
manner to link a variable use to its reaching de nitions, taking into account at the same time also control
ow structure of the analyzed program. The analysis
of FUD chains for some code fragments seems to help
understand better the characteristics of the algorithm
to compile. Basing on the following simple example,
we are aiming at intuitively showing the reason whya proper data partition on FUD chain can produce a
positive impact on execution time.
for(I=0;I<N;I++){S1 : b=a[I]+1;
S2 : c = a[I]-b;
S3 : d = c+200;
S4 : f = a[I]/2;S5 : a[I] = f+2;
S6 : a[I+1] = f+250+a[I];}Figure 2 presents the FUD chain for the loopbody. We can distinguish two graph components,QD>L@&&
6
E6
I6
F6
D^L`

6
G6
D^L@

6
H

6RQQWDJ§'LDJUDPP1¢-XOL¦ ~

Figure 2: FUD chain representation
C1=fIn,S1,S2,S3,S4g and C2=fIn,S5,S6,S7g employing as input a[I]. The element a[I] is the unique common node for C1 and C2. Eliminating it produces adisconnected graph.
Each loop iteration could be executed faster by theemployment of two processors P1 and P2, one for component C1 and one for C2, requiring duplication of onlya[I] on P1 and P2. Moreover, we can get an additional
improvement through parallel execution compared tosequential one, because such a decomposition allows tohasten next iteration. The i-th loop iteration can bestarted as soon as the value of a[I] is available. Therefore, through the considered partition it is also possible
to execute in advance the (i+1)-th iteration, successive
to i-th one. In the sequential case, the computation ofa[I+1], input element to (i+1)-th iteration, requires thevalue of a[I] in S6. However S6 can be executed only
after S4 because of an anti-dependence constraint fromS4 to S6. As a consequence a[I+1] is to be produced at
the end of each iteration, therefore the execution of thesuccessive iteration is to be delayed until the previous
one is over. In the parallel case, the value of a[I+1]
is determined earlier, on processor P2, independently
from processor P1, hence the next (i+1)-th loop iteration can begin before the i-th one is terminated.
4 Future work
Design activity is driving the programming phase inorder to implement and test the optimizing compiler.
Then, a comparative analysis will be carried out oncommercial benchmarks.
References[1] T. Fahringer
Automatic performance prediction of parallel pro-. Kluer Academic Publ., 1996

grams

[2] M. WolfeHigh performance compilers for parallel computing. Addison-WesLey, 1996

[3] H. Zima, B. Chapman
Supercompilers for parallel and vector computers

ACM Press, Addison-Wesley, 1991.