The synergetic effect of compiler, architecture, and manual optimizations on the performance of CFD on multiprocessors.
This paper discusses the comprehensive performance profiling, improvement and benchmarking of a Computational Fluid Dynamics code, one of the Grand Challenge applications, on three popular multiprocessors. In the process of analyzing performance we considered language, compiler, architecture, and algorithmic changes and quantified each of them and their incremental contribution to bottom-line performance. We demonstrate that parallelization alone cannot result in significant gains if the granularity of parallel threads and the effect of parallelization on data locality are not taken into account. Unlike benchmarking studies that often focus on the performance or effectiveness of parallelizing compilers on specific loop kernels, we used the entire CFD code to measure the global effectiveness of compilers and parallel architectures. We probed the performance bottlenecks in each case and derived solutions which eliminate or neutralize the performance inhibiting factors. The major conclusion of our work is that overall performance is extremely sensitive to the synergetic effects of compiler optimizations, algorithmic and code tuning, and architectural idiosyncrasies.
Introduction
Despite the continuing quest to achieve high performance, complete scientific applications obtain only a
fraction of the expected speedup on modern multiprocessors. On the other hand, the proliferation of parallel
architectures throughout the spectrum of computer systems is indisputable. Few would argue against the
significance of parallelism, but even fewer would suggest that parallel machines deliver the performance that
users have come to expect.
In this paper, by means of a "Grand Challenge" application, we show that compiler, architectural limi-
tations, and algorithmic characteristics can restrict performance more severely than Amdahl's law suggests,
even in cases where parallelism may be abundant. As some of our results indicate, a synergetic approach in
simultaneously addressing all these limitations can result in significant performance payback.
Our work focused on the comprehensive and multi-level analysis of a complete commercial scientific
application, a Computational Fluid Dynamics (CFD) code based on SIMPLE (Semi-Implicit Method for
Pressure-Linked Equation) [8]. This paper reports on the performance bottlenecks of hardware, architectures,
compilers and operating systems, and on the importance of manual optimizations and code tuning. The hand
optimizations, used in this work to improve performance, as well as, the isolation of hardware bottlenecks,
point to possible architectural and software improvements that can alleviate the performance limitations of
multiprocessor machines.
For our experiments, we used three commercial multiprocessors: the SGI Challenge, the Alliant FX/2800,
and the Alliant FX/80. We used two commercial and two experimental parallelizing compilers. Our results
suggest that a user of a CFD application who is not an expert on code optimization and/or computer
architecture, should expect to see little, if any, performance improvement by running such a code on a
multiprocessor. This is true even in the presence of powerful automatic parallelizing compilers. Such tools
can be effective only under expert intervention.
Even though our results from a single commercial application cannot be generalized across the spectrum
of scientific applications, the size and the type of codes that make up CFD programs are representative of
Converge
Time Iteration24Solve Continuous Equation
Solve NS-Eq.(z component)
Solve NS-Eq.(y component)
Solve NS-Eq.(x component)
Boundary Condition
Boundary Condition
Boundary Condition
Boundary Condition
Set Time
Input Data
Output Result
COEFV
COEFV
COEFV
CORECT
COEFP
Solve System
Set Coefficient of System
Set Coefficient of System
Set Coefficient of System
Set Coefficient of System
Solve System
Solve System
Solve System
Add P' to P6

Figure

1: The algorithm of the CFD application (SIMPLE)
linear system solvers and PDE solvers which are the core of the majority of numerical applications. Many
performance evaluation and benchmarking studies employ selected kernels of complete applications, which
may be more amenable to automatic parallelization or parallel execution. We resisted this approach in
our work and considered the performance of the entire application by profiling the performance of all the
components of our CFD code, and weighted their contribution to overall speedup.
The result of hand optimizations, targeted compilation, and code tuning to avoid architectural bottlenecks
was a significant improvement in overall performance. Our findings also underscore the need to predict the
maximum possible theoretical performance gains for a given application. Such upper bounds on performance
could be useful reference points for both automatic and manual parallelization. It comes as no surprise that
runtime overhead plays a more important role on performance than the serial bottlenecks in Amdahl's law.
2 The CFD code and Experimental Environment
Inflow(1m/s)
x
y
z
Density: 0.001kg/m
-5

Figure

2: The model
cube, divided in 40 meshes in each direction.
Our CFD program is based on the SIMPLE method [8], which is outlined in Figure 1. The algorithm
first increments the time step (Step 1 in Figure 1), and then iteratively solves the Navier-Stokes equations
to compute the velocity (Steps 2-4) and the continuity equations (Step 5) until they converge. Each of
Steps 2 through 5 in Figure 1 consists of three modules: (i) Assemble a system of linear equations by
discretization, (ii) modify those equations according to boundary conditions, and (iii) solve the system of
linear equations. We employ MICCG (Modified Incomplete Cholesky Conjugate Gradient) [5] to solve the
continuity equation (Module SOLVEP), and ILUCR (Incomplete LU Conjugate Residual) [6] to solve the
Navier-Stokes Equations (Module SOLVEV).
The performance is evaluated using the 3-dimensional space as shown in Figure 2. In our experiments
we measured the entire CFD code, except the input and the output of data, identified as Steps 0 and 6 in

Figure

1.
The performance of the resulting codes was measured and compared on three multiprocessor systems:
the Alliant FX/2800, the Alliant FX/80, and the SGI Challenge. The Alliant FX/80 is an 8-processor
MIMD system where each processor has a vector unit and all processors share a 4-quadrant cache [2]. The
Alliant FX/2800 was the next generation of MIMD machines from Alliant and is a 20-processor machine
using the Intel i860 processor. Finally, the SGI system used for our experiments was an SGI Challenge;
configurations of 12 and 8 processors of the machine were used for our measurements and specified explicitly
in the experimental sections.
All the execution times in this paper were measured in dedicated mode on all three machines. Each
measurement was repeated several times and the average was taken. In cases where the standard deviation
was above the equivalent of 1% the experiments were repeated; thus all measurements reported have a
standard deviation of almost zero.
The serial and parallel versions of our CFD code were used for the measurements in each machine. We
use the terms "serial" and "parallel" to refer to the serial and parallel execution times respectively. The
serial and parallel versions of the CFD were compiled using two experimental parallelizing compilers and the
manufacturer-supplied parallelizers on each machine, as explained below.
Serial: The serial version of the CFD code (used to measure serial execution time) was compiled using the
native (non-parallelizing) compiler with the optimizations option turned on.
Parallel: In each case, parallel execution time was computed by running the parallel version of the CFD
obtained as follows. The original code was compiled by each system's native parallelizing compiler. For the
Alliant, we used the Alliant compiler with the automatic parallelization/vectorization options [1]. For the
SGI Challenge, we used the SGI Parallel Fortran Accelerator (PFA) [10].
Parafrase-2 and Polaris: The original code was compiled by each experimental source-to-source parallelizing
compiler, Parafrase-2 [7] and Polaris [9]. The parallelized source output from the two parallelizers was
compiled again by the back-end Fortran compiler of each machine. Both the SGI and the Alliant back-end
compilers parallelize loops only when explicitly indicated.
In the following sections, the incremental effects of compilers, system architecture, manual optimizations,
and their limitations on overall performance are discussed.
3 Effect of Compiler Parallelization and Optimization
In this section, we discuss the effectiveness of automatic parallelization on our CFD code. Moreover, we
consider specific limitations of the compilers tested and identify several areas of potential improvement in
ALLT
COEFV
COEFP
CORECT
|||||||Normalized
Execution
Serial Parallel PPolaris
Alliant FX/280016161616135789 90Serial Parallel PPolaris
Alliant FX/8016161616
Serial Parallel PPolaris

Figure

3: Performance by automatic parallelizing
Executed with 8 processors. Parallel indicates execution time by running our application using
each computer's native compilers.
terms of both functionality and performance. All four compilers were tested on our CFD code and on each
machine.

Figure

3 shows the normalized execution time of the CFD code on each machine using each of the
four compilers. We took the serial execution time (as defined above) as the normalized time. The native
parallelizer of each system was used to compute the time labeled "Parallel" in Figure 3. The different shades
in each bar correspond to the execution time of each of the modules of the CFD code as illustrated in Figure
1.
The first clear observation is that none of the four compilers improved performance significantly. In the
best case, the speedup of the automatically parallelized CFD was 1.19, a dismal performance under any
circumstances. Of course, this could be due to the serial nature of the underlying algorithm; however, as
shown later, this was not the case. Our CFD code exposes a significant amount of parallelism which none
of the parallelizing compilers was able to exploit due to a number of reasons.
From

Figure

3, it is evident that all four compilers performed uniformly poorly with hardly any significant
difference observed. A closer observation of the output codes revealed that Parafrase-2 and Polaris did in
do
(a) Local Variables
do
else
endif
(b) IF statements
do
do
do
(f) Reduction

Figure

4: Code samples illustrating compiler bottlenecks
fact parallelize a significant number of loops; however, much of the exposed parallelism was too expensive to
exploit on each of the three machines. Although both experimental compilers are more powerful than PFA or
the Alliant compilers, they tend to extract the maximal parallelism, regardless of its impact on performance.
As a result the parallel execution of small loops resulted in an execution time worse than the serial time.
This clearly points to the need of compile-time determination of exploitable and non-exploitable paral-
lelism; very few of the existing compilers provide even rudimentary support for determining the quality of
exposed parallelism. From our group of four compilers only the PFA provides the capability of computing
the trade-off between run-time overhead and amount of parallelism.
Although the same CFD loops were parallelized by the experimental compilers, performance on the SGI
Challenge was noticeably worse than on the two Alliants. This is due mostly to the architectural bottlenecks
on the SGI Challenge whose effect was more profound than on the Alliants. We further examine architectural
bottlenecks in later sections.
In order to better understand and characterize the poor performance of the compilers used for our CFD
code, we isolated the largest loops and characterized them as serial, parallel and undetermined. For the serial
and undetermined versions, we further examined the loops by hand to determine the cause of serialization
or partial parallelization. In the following we discuss the limitations of each compiler and identify high-yield
optimizations which can significantly improve performance.

Table

characterizes Parafrase-2 and Polaris in terms of the most important optimizations and gives the
percentage improvement over serial execution time, T 1
of the CFD on an 8-processor SGI Challenge (time
is normalized to the serial execution time which is taken to be 100). We observe that the most significant
payoff was due to local variable recognition and allocation in DO loops.
In the following comparison, we limited our analysis on the SGI by considering the two experimental
compilers and the SGI's PFA.
(a) Local Variables in DO Loops: At present Parafrase-2 cannot parallelize DO loops with localizable
variables such as the one shown in Figure 4(a) unless it is invoked with the scalar expansion pass. However,
the scalar expansion pass is not powerful enough to handle many of the loops in our code. Polaris was more
effective in identifying local variables and resulted in the parallelization of simple loops by privatarizing
localizable variables.
(b) IF Statements in DO Loops: Parafrase-2 is much more effective in the parallelization of DO loops
whose body contains IF statements, such as the loop of Figure 4(b). Polaris, however, cannot parallelize
such loops. Since most large DO loops have both local variables and IF branches, neither Parafrase-2 nor
Polaris could parallelize loops with branches and local variables.
Although each of the experimental compilers can deal effectively with either local variable recognition or
branches inside loops, neither could handle the combination of local variables and control flow statements
inside the loop body. As a result, we applied both optimizations manually to the original code.
code involved index expressions of order two and were missed by both compilers. Both the PFA and the
Alliant compilers are even weaker with respect to dependence analysis. More powerful dependence analysis
schemes are necessary in order to improve the effectiveness of automatic parallelization. As previously, false

Table

1: Characteristics of Parafrase-2 and Polaris
Bottleneck Parafrase-2 Polaris Impact
a Local variable in DO loop Weak Yes
b IF statement in DO loop Yes No
c Index Expression in higher order No
e Distributing strongly connected components No
Reduction No
All Optimization - 52
dependences due to higher order index expressions were manually removed.
(d) Loop Distribution: Although Parafrase-2 is very effective with distributing loops, it applies loop distribution
in all possible cases resulting in a large number of relatively small loops. Even though this may be
desirable for generating vector code, it may be counter productive in the case of parallel loops. Ideally, we
should distribute a loop only when this enables the parallelization of that loop. Figure 4(d) is the typical
case. For this reason, the distribute pass was not used in our experiments. In the hand-optimized version,
we distributed loops manually only when it was helpful.
Distributing Strongly Connected Components: The DO loop shown in Figure 4(e) cannot be parallelized
by Polaris or Parafrase-2. However, if the two statements in the body of the loop are distributed, we find
those distributed loops parallelizable. Currently, there is no way to determine the legality of this distribution
automatically. The compiler would have to be able to execute the loop symbolically in order to determine
the legality of the distribution, and thus automatically parallelize the loop.
typical reduction is shown in Figure 4(f). Loops with reductions cannot be parallelized by
Parafrase-2. Polaris parallelized them only if the back end compiler can handle the reduction. A reduction
operation can be parallelized by breaking down a loop into several parts, summing each part and, finally,
calculating a total sum 1 .
1 Because the parallel version of the code adds the elements together in a different order than the sequential version, the
round-off errors accumulate differently for the two versions of the code. Thus, the answer may differ slightly.
The impact of each optimization shown in Table 1 (expressed as % improvement on T 1
by related optimizations. Thus the aggregate improvement by applying all optimizations is not necessarily
equal to the sum of the individual improvements. For example, the first row of the table shows a 30%
improvement in execution time by specifying local variables in parallel loops; these include loops with
branches which contribute in the improvement shown on the second row of the table.
After incorporating the optimizations discussed in this section, the performance of our CFD code improved
by 52%, achieving a speedup of 2.1. Automatic parallelization proved ineffective in the case of our
CFD code, especially on the SGI Challenge. Incorporating or improving particular transformations may
not result in significant pay-off; implementation/improvement of all transformations would be necessary to
achieve the improvement suggested in Table 1.
Perhaps one of the least looked at issue in parallelizing compilers is that of "useful" versus "useless"
parallelism, or equivalently, coarse and fine grain parallelism. Compilers need the ability to quantitatively
analyze sections of code and determine the trade-off between the pay-off and the cost of a particular trans-
formation. Symbolic program analysis [3] provides a powerful means for computing the symbolic size of code
sections; however, with the exception of Parafrase-2 no other compiler provides this capability.
4 Architectural Bottlenecks
After all compiler transformations were manually incorporated in our code, the performance of the parallelized
version was compared on the SGI Challenge and the Alliant machines. The impact of architectural
bottlenecks was more profound on the SGI multiprocessor (as shown in Section 6) than on the Alliants,
mostly due to the cost of enforcing cache coherence (a non-existing problem for the Alliants which use
shared cache), and the limited bus bandwidth. Therefore, our experiments and solutions to the architectural
bottlenecks focused on the SGI Challenge.
4.1 Runtime Overhead

Table

2: Cost of Scheduling and Synchronization Operations on SGI
Operation Initialization Subsequent use
Create/use thread 446741 20
Barrier Entry 103 63
Barrier Exit 17 7
(-sec)
In order to put the following experimental results in perspective, we first measured the overhead associated
with primitive operations and bookkeeping functions on the SGI Challenge, such as the cost of issuing a
parallel loop iteration, barrier synchronization, and setting up the threads used in parallel loop execution.
We used SGI-supplied timers to make detailed performance measurements.

Table

2 shows the cost of creating a thread and the cost of re-using existing threads. Each loop iteration
is assigned to an empty thread at a cost of about 20 -secs. The cost of creating threads is extremely high
as indicated in Table 2, and it approaches 0.5sec; however this cost is paid once per thread and threads are
re-cycled on subsequent parallel loops. Nevertheless, the accumulated run-time overhead of thread creation
and thread assignment to loop iterations is high and can be detrimental to performance for applications with
a small number of loops and/or loops with small loop bodies.
Barrier synchronization overhead was measured as a pair of numbers: the barrier entry and the exit.
The former was computed as the time difference between the completion of the last and the first processor,
and it includes skew due to load balancing; the latter was measured as the difference between the time the
last iteration completed execution and the time the loop exited. Figure 5 shows the space-time diagram
of the execution of a parallel loop with 8 iterations and a large loop body. The figure shows the start-up
phase (with existing threads) and the completion phase; each processor was assigned one iteration of the
parallel loop. The top horizontal bar indicates the time just before execution entered the loop to the time the
loop completed execution. Although the right part of Figure 5 shows a noticeable unbalance, all processors
completed within an interval of 5-7% of the total execution time of the loop.
Although SGI supports gang scheduling for parallel loops (all processors start on a loop simultaneously),
we observe a noticeable difference among processors in starting up execution. This difference is due to the
l
Iteration
number
time in -sec
|
1000 1010
|
|
|
Iteration
number
time in -sec

Figure

5: Diagram of 8 processors
C$DOACROSS LOCAL(J)
do i=1,8
do j=1,2000000
(a) Program to emulate false sharing
C$DOACROSS LOCAL(j, r)
do i=1,8
do j=1,2000000
a(i)=r
(b) Eliminate by a local variable
dimension a(D,8)
do
do j=1,2000000
(c) Eliminate by keeping arrays
separate

Figure

sharing
synchronization overhead associated with exclusive access of the loop index. In the case of 8 processors, a
total of approximately 10-secs was spent on locking and updating the loop index - or about 1-sec for each
lock operation.
In very approximate terms, the total overhead associated with each processor participating in the execution
of a parallel loop has a lower bound of 60-secs, or equivalently, approximately 10,000 clock cycles.
Therefore, parallel execution starts paying off for loops whose body contains 10,000 or more instructions.
4.2 False Sharing
False sharing occurs when multiple processors access (and cache) a small section of memory; although
memory accesses may be truly independent, they may be treated as accesses to shared data. Figure 6(a)
shows a loop that gives rise to false sharing, like many more complicated loops in our CFD code. False
l
time(sec)
Iteration
number
(a) Time stamps of Figure 6(a)
# of procs. Local
(time in sec)
(b) Execution time of Figure 6(b) and (c)

Figure

7: Performance of sharing false
sharing is enforced at the cache line level, not at the byte or word level. Thus, when a processor writes a
byte of a cache line, the entire line is invalidated, not just the modified byte. We discuss two techniques to
avoid false sharing and measure their effect on performance on sample codes.
The first solution to false sharing is the use of local variables wherever possible, as shown in Figure 6(b)
- the loop has been manually rewritten in order to make explicit use of local variables. The execution time
of the loop of Figure 6(b) for varying number of processors is shown in the second column of Figure 7(b),
under the header "local".
The second approach is spreading the allocation of shared data in memory, so that they are separated
by addresses which differ more than the cache line size; this improvement is illustrated in the code example
of 6(c). The last three columns of Figure 7(b) show the execution time of the loop of Figure 6(c) for three
different allocations of the shared array: "D" is the distance, or the number of array elements between
variables accessed by successive loop iterations.
Notice that the worst performance is observed for D=1 which corresponds to the maximum amount of
false sharing. Since the cache line size of the SGI Challenge is 128 bytes, we can eliminate false sharing by
keeping elements between the threads. The numbers shown in italics display poor performance because
the shared array is not spread wide enough to avoid false sharing. It is worth noting that the execution times
of the local variable version is better than those of the shared array version. This is due to the effect of local
variables, whose values do not have to be written back to memory; we suspect registers are more effectively
used for them. When local variables are not allowed or supported, we have to write back to memory all
dimension a(nmax,8)
do
do Store data to local cache.
c
C$DOACROSS local(jj,i), share(a)
do 100 j=1,8 -
do 110 i=1,nmax/2 - Execution time of this loop

Figure

8: Program to emulate bus contention
iadd is a switching parameter. If iadd=0, there is no bus contention. If iadd=1, there is bus
contention.
values thus reducing performance. This is implicitly suggested in [10]. Although we can avoid false sharing
by either method, using local variables appears to be more effective, possibly due to the opportunity of
extensive register reuse. None of the compilers tested was able to handle effectively the problem of false
sharing.
4.3 Bus Contention
Clearly, locality of data is important not only for cache performance, but also for minimizing memory
accesses and network traffic. On bus-based multiprocessors such as the SGI Challenge, bus contention can be
a serious performance bottleneck. A few modules in our CFD code performed poorly due to a combination
of false sharing and bus contention. Bus contention was measured by comparing the performance of two
almost identical loop kernels which are in Figure 8. The first version of the loop needs only data in local
cache (iadd=0), while for (iadd=1) the loop accesses data not present in the local caches.
When processors request a significant amount of data from shared memory or from remote caches, we
can anticipate bus contention which varies with the number of processors attempting to do data transfers
# Read from local cache
Read also from the other caches||||||1/(# of proc.)
Time
(msec)
(a) 16KB
# Read from local cache
Read also from the other caches
|||||||1/(# of proc.)
Time
(msec)
(b) 4MB

Figure

9: The influence of bus contention on performance
simultaneously. We measured the performance effects of bus contention by changing the size of the array
and the number of processors used to execute the kernel of Figure 8. The size of array (nmax) was taken
to be 4096 and 1048576 elements, or equivalently, 16KB and 4MB respectively. The execution time of the
parallel loop is shown in Figure 9. When the array size is 16KB, the worst case scenario was a 30% increase
in execution time for 8 processors. Cache misses account for this difference. With an array size of 4MB,
execution time was 900% longer as compared to the case of caching the entire array into local caches. This
performance difference cannot be attributed to cache misses alone. False sharing did not play a role in this
case since the data were skewed appropriately in shared memory in order to avoid false sharing. Thus the
bulk of the slow down was due to bus contention. Although we attempted to separate the performance loss
due to cache misses from that due to bus contention, it was not possible to measure events at the level of
clock period with software timers.
The Alliants avoid network contention due to false sharing and coherence in general since neither is
applicable. The performance on both of the Alliants is limited by raw bus bandwidth which can be saturated
when large arrays are accessed and cached simultaneously by different processors.
x
y
z
(a) (b)
Each line is executed in parallel
Each allow is executed serially
in each parallel loop
All are executed serially
(c)
Each plane is executed
in parallel

Figure

10: Computing order of
(a) the original serial code, (b) the 3-dimensional hyperplane method, (c) the 2-dimensional hyperplane with
projection method
5 Algorithmic Changes
In this section we discuss extensive hand re-coding of our CFD code that bordered on algorithmic changes.
Although current compiler technology is insufficient for performing this type of code restructuring, future
parallelizing compilers could potentially perform restructuring at the computation (not the language) level,
in order to improve the degree or the quality of exploitable parallelism.
In order to further improve the performance of the most time-consuming modules of our CFD code,
we changed the order in which calculations are performed without violating algorithmic dependences. In
addition, we exploited non-loop (or functional) parallelism in the computation of velocities; the latter involved
a change in algorithm SIMPLE.
Among the seven modules shown in Figures 1 and 3, SOLVEP, SOLVEV and COEFV are the most
time-consuming modules. COEFV was extensively parallelized by the compiler optimizations discussed in
Section 3. The structure of the calculations in SOLVEP and SOLVEV are similar, and we thus limit the
discussion to SOLVEP - a similar approach was used for SOLVEV. The details of the hand-restructuring of
the code are given in [4]. In this paper, we outline the changes at the highest possible level.
The computations in SOLVEP sweep a 3-dimensional structure as shown in Figure 10(a). Parallelization
is difficult in this case due to the dependences: each point computed depends on its three immediate neighbors
on the x, y, z dimensions. Figure 10(b) shows how one can alter the order of computations with respect to
Converge
Time Iteration
Set Time
Input Data
Output Result
Solve Continuous Equation
Solve NS-Eq.
Solve NS-Eq.
(z component)
Solve NS-Eq.
(y component)

Figure

Parallelized SIMPLE algorithm by velocity
Certain subcomputations of Step 5 have been distributed to Steps 2-4
the three dimensions without changing the underlying algorithm. The order shown in Figure 10(b) yields
the maximum amount of parallelism since all elements within each cross-diagonal plane can be computed in
parallel; we refer to this as the 3-dimensional hyperplane method. However, the planes close to the beginning
and end of the cube contain few elements; this translates to parallel loops with few iterations which provide
little opportunity of exploiting cache locality, and are more sensitive to run-time overhead.

Figure

10(c) shows an alternative order of calculations for SOLVEP by organizing the computation
across diagonal planes (adopted in our optimized CFD code); we refer to this approach as the 2-dimensional
hyperplane with projection method. Although parallelism is less than in the case of 10(b), it results in
parallel loops with longer bodies that sweep across elements of the plane in the direction of the arrows. Thus
each parallel loop iteration can now perform computations on the elements of a local vector - locality of
data had a profound effect on performance in this case. In addition, the larger granularity of parallel loop
iterations contributed to the amortization of the overhead. As a result, the restructuring based on Figure
10(c) outperformed the one based on 10(b).
The speedup achieved for SOLVEP for the versions of Figure 10(b) and (c) on an 8 processor SGI
Challenge was 1.7 and 7.4 respectively.
The final manual change of our code targeted the exploitation of non-loop parallelism. Figure 11 shows
an alternative order of performing the computations within each iteration of the algorithm. As illustrated in

Figure

11, the code was restructured in order to take advantage of simultaneous computation across the x,

Table

3: Performance improvements from parallelizing the components of velocity
Part Serial Parallel Speedup
ALL 100.0 62.5 1.6
other 2.4 2.3 1.0
ALL
COEFV
COEFP
CORECT
|
|||||||Normalized
Execution
Serial Parallel PPolaris m(com) m(com+alg) m(all)
Alliant FX/2800161616161
Serial Parallel PPolaris m(com) m(com+alg) m(all)
Alliant FX/80161616161
100 969841Serial Parallel PPolaris m(com) m(com+alg) m(all)
SGI Challenge16040471611
Figure

12: Performance
With 8 processors. Parallel refers to parallelized by the native compiler.
y and z components of the model. This can be done by structuring the calculations across each dimension
as shown in Figure 11. In addition to the very high-level parallelism resulting by simultaneous execution of
the three solvers, parallelism at the loop level can still be exploited within each component. This approach
is expected to yield better performance due to significantly higher degree of data locality. Table 3 shows the
speedup of the new CFD code when only non-loop parallelism is exploited. We were unable to exploit both
functional and loop parallelism on the SGI Challenge due to the fact that the system allows only one level
of parallelism, and no nested parallelism is supported by the PFA compiler or the run-time library.
6 Performance Analysis

Figure

12 gives a comprehensive account of the performance of our CFD code on the three multiprocessors
before and after each set of automatic and manual optimizations were incorporated. There are three groups of
execution time bars, one for each of the three multiprocessors used in our experiments: the Alliant FX/2800,
the FX/80, and the SGI Challenge respectively. The shades-key on the right hand-side of Figure 12 shows
the correspondence of the various shades of each bar to the major modules of the CFD code, as defined in

Figure

1. For each case, seven performance bars are shown with the following data from left to right: The
leftmost bar in each group corresponds to the normalized serial execution time of the CFD code on each
machine, with serial optimizations turned on. All other execution times are normalized with respect to the
serial execution time.
The next three bars labeled "Parallel", "P 2", and "Polaris" correspond to the parallel execution time
of the code on each machine when the code was compiled with the manufacturer-supplied parallelizer, with
Parafrase-2, and Polaris respectively. These are identical to the timings shown in Figure 3. As illustrated in

Figure

3, automatic parallelization failed in a major way. It is worth noting that all compilers were effective
in parallelizing specific loops; however, a combination of bias toward specific transformations and the lack
of quantitative analysis resulted in no bottom-end improvement. For example, a loop which is parallelized
but misses on the cache in each iteration can hardly benefit from its parallel execution.
The bars labeled "m(com)" correspond to the parallel execution time of the code, after all manual compiler
optimizations and parallelization techniques described in Section 3 were carried out. These reflect
optimizations and restructuring techniques which are automatable and can be integrated into existing parallelizing
compilers. We notice a significant improvement after manual parallelization on all three machines,
with a resulting speedup between 2 and 3.
The bars with labels "m(com+alg)" show the resulting execution times when both the compiler optimizations
and the algorithmic (code) changes, as discussed in Section 5, were incorporated. In the case of
both of the Alliants the algorithmic changes resulted in yet more significant improvements corresponding
to additional speedups of approximately 3. However, algorithmic changes that increased parallelism (e.g.,
the 3-dimensional hyperplane method of Section 5) resulted in little improvement on the SGI Challenge.
This was the case because in the latter case performance was topped off not due to the lack of additional
Number of Processors
Speed

Figure

13: Scalability of our CFD code
parallelism, but due to cache misses and saturation of the bus bandwidth.
The interference of the coherence overhead and the bus saturation on the Challenge become more evident
on the rightmost bar of Figure 12. The bars labeled "m(all)" show the parallel execution times of the CFD
code when in addition to automatic and manual optimizations and algorithmic changes, the code was altered
to eliminate interference of architectural bottlenecks, such as false sharing and bus bandwidth. In fact, the 2-
dimensional hyperplane with projection method outlined in Section 5 restricted the amount of parallelism but
promoted data locality and eliminated false sharing. The "m(all)" bar on the SGI data of Figure 12 reflects
the improvements achieved due to the elimination of these bottlenecks obtained with the 2-dimensional
hyperplane with projection. The major improvement came about in the case of the SGI with an additional
speedup of almost three, resulting from the elimination of false sharing, increased data locality, and reduction
on bus traffic; these optimizations were discussed in Section 4.
Our CFD code achieved a total speedup of approximately 7 on all three systems. Figure 13 shows the
speedup of the CFD benchmark on the SGI for three different problem sizes. In all cases, in computing
speedup we took as "serial" execution time the execution time of the parallelized code on a single processor,
not the optimized sequential code; thus all speedups reported fall on the conservative side, at least for the
SGI and the FX/2800 2 . Figure 13 attests to the scalability of the CFD code with problem size.
2 The sequential execution times on the Alliant FX/80 were obtained by running the parallel version of the code on a single
processor without vectorization; vectorization was used in all parallel runs.
As discussed above, a laborious and time-consuming analysis and optimization of our CFD code resulted
in a total speedup of approximately 7. However this result does not tell us anything regarding the maximum
potential parallelism and maximum performance attainable by our CFD benchmark on the machines tested.
In order to determine the position of the delivered speedup with respect to the ideal we used two ap-
proaches. In the first we used Amdahl's law to compute maximum speedup, by measuring the serial and
parallel parts of the code through actual execution on the SGI. We measured the execution time of the CFD
several times and on different numbers of processors; using least square approximation we estimated the
parallel and serial fractions of the code. These were used to estimate an upper bound on performance using
Amdahl's law. Table 4 shows the maximum attainable speedup estimated through measurements on the
SGI Challenge, and for the three problem sizes indicated.
The speedup of 15.6 corresponds to the problem size used to obtain the measurements reported on Figure
12. The delivered speedup was approximately half of the Amdahl's upper bound on maximum speedup. We
believe that the factor of two difference is attributed to network bandwidth interference and cache misses.
In addition to the above, we estimated the maximum speedup using properties of the underlying algorithms
and hand-carried analysis of the code. Amdahl's law was again used to obtain the upper bound;
however, the serial and parallel fractions of the code were estimated through inspection of the code and static
analysis. This approach yielded a maximum speedup of 40 and 100 for the 3-dimensional and 2-dimensional
hyperplane with projection methods respectively; the problem size was again fixed at 40x40x40. There is a
factor of about 6 between the ideal maximum and the measured maximum speedup. Most of this discrepancy
is again attributed to architectural bottlenecks.
Thus, a powerful parallelizer/backend combination on an multiprocessor architecture without bottlenecks
would be expected to deliver speedups of about 40-100 for our CFD application. This is a factor of almost
between the highly optimized CFD version and a further optimized version running on a bottleneck-free
architecture with an "infinite" number of processors.

Table

4: Scalability of maximum speedup
Elements Maximum Speedup
7 Conclusion
This paper presented a comprehensive performance profiling, analysis, optimization and tuning of a commercial
computational fluid dynamics code. CFD is one of the most important applications running on
high-performance computers and one of the most demanding in terms of computational resources.
Our findings underscore the severe limitations of commercial and experimental parallelizing compilers
as well as the architectural bottlenecks (and their performance implications) of popular high-performance
multiprocessors such as the SGI Challenge. Most importantly, our findings stress the importance of the
synergetic effect of compiler and algorithmic optimizations on overall performance. The prowess of compilers
on individual transformations and optimizations have little effect on bottom-line performance; however, a
global approach to optimization which considers the interdependencies among various optimizations can
result in significant performance improvements.
All of our experiments were based on the performance of the complete CFD code as opposed to selected
kernels. Although individual compilers performed excellently on specific loops, their performance on the entire
application proved to me dismal. The same was true for the delivered performance. The performance of
our CFD code on the SGI Challenge was a striking case of mismatch between compiler optimizations and architectural
idiosyncrasies. Parallelization by itself may result in far less than expected delivered performance,
if it does not attempt to customize parallelization to the underlying architecture. Alternatively, in order
for parallelism to work effectively architectural bottlenecks should be eliminated or taken into consideration
during compilation. Finally, sophisticated program restructuring which can capture and alter the order and
type of computations can result, in certain cases, in improvements similar to those of parallelization and
code optimization.



--R

Alliant Computer Systems Corporation.
Alliant Computer Systems Corporation.
Symbolic Analysis for Parallelizing Compilers.
On the parallelization of a cfd code.
Guidelines for the usage of incomplete decompositions in solving sets of linear equations as they occur in practical problems.

A new generation parallelizing compiler for mpp's.
Numerical Heat Transfer and Fluid Flow.

Silicon Graphics Inc.
--TR
Symbolic analysis for parallelizing compilers
parallel architectures;performance evaluation;parallelizing compilers;program optimization;parallel processing;parallel algorithms and programs;profiling and program tuning;CFD computational fluid dynamics;cache optimization