Integrated Range Comparison for Data-Parallel Compilation Systems.
AbstractA major difficulty in restructuring compilation, and in parallel programming in general, is how to compare parallel performance over a range of system and problem sizes. Execution time varies with system and problem size and an initially fast implementation may become slow when system and problem size scale up. This paper introduces the concept of range comparison. Unlike conventional execution time comparison in which performance is compared for a particular system and problem size, range comparison compares the performance of programs over a range of ensemble and problem sizes via scalability and performance crossing point analysis. A novel algorithm is developed to predict the crossing point automatically. The correctness of the algorithm is proven and a methodology is developed to integrate range comparison into restructuring compilations for data-parallel programming. A preliminary prototype of the methodology is implemented and tested under Vienna Fortran Compilation System. Experimental results demonstrate that range comparison is feasible and effective. It is an important asset for program evaluation, restructuring compilation, and parallel programming.
Introduction
The most significant question with parallel machines is the same today as it has been for many
decades: How can software applications take advantage of hardware parallelism [1]. Traditionally,
distributed memory architectures have been programmed using message passing where the user
is responsible for explicitly inserting communication statements into a sequential program. The
development of parallel languages such as Vienna Fortran [2], Fortran D [3] and High Performance
Fortran (HPF) [4] improved the situation by providing high-level features for the specification of
data distributions. Among others the Vienna Fortran Compilation System (VFCS) [5] and Fortran
D compilation system [3], have been developed to support such languages and to automatically
generate a message passing program. However, current technology of code restructuring systems
inherently lacks the power to fully exploit the performance offered by distributed memory archi-
tectures. The primary motivation of parallel processing is high performance. Effectiveness and
efficiency of restructuring compilation are the current barriers for the success of a simple, high-level
programming model approach.
Restructuring a program can be seen as an iterative process in which a parallel program is
transformed at each iteration. The performance of the current parallel program is analyzed and
predicted at each iteration. Then, based on the performance result, the next restructuring transformation
is selected for improving the performance of the current parallel program. This iterative
process terminates when certain predefined performance criteria are met or as a result of explicit
user intervention. Integrating performance analysis with a restructuring system is critical to support
automatic performance tuning in the iterative restructuring process. The development of a
fully compiler integrated performance system for scalable parallel machines is especially challeng-
ing. In a scalable environment, the performance of a program vary with data distribution, system
size (number of processors), and problem size. A superior program implementation is only superior
over a range of system and problem size. Predicting the performance of parallel programs and
integrating performance indices automatically into a restructuring compiler are two major challenges
facing researchers in the field [6]. Moreover, current performance analysis and visualization
tools are targeted at message-passing programming models where parallelism and interprocessor
communication are explicit. They fall short in supporting high-level languages and are not readily
integrated into restructuring compilers.
Two major functionalities of data-parallel restructuring compilers are the distribution of data
arrays over processors and the choice of appropriate restructuring transformations. A key question
of realizing these two functionalities is how to predict the scaled performances of a small number
of data distributions and transformations automatically, so that appropriate optimization decisions
can be made. In order to compare relative performance over a range of problem and system sizes,
scalability prediction is proposed as a solution in this study. Scalability is the ability to maintain
parallel processing gain when system and problem size increase. It characterizes the scaling property
of a code on a given machine. A slow code with a good scalability may become superior when system
and problem size scale up. The system sizes for which the performance ranking of different code
changes are called crossing points. In this paper we introduce the concept of range comparison,
which is concerned with the determination of crossing points. Based on analytical results given
in Section 3.2, automatic crossing point prediction and automatic range comparison are studied
in this research. An iterative algorithm is first derived to predict the scalability and crossing
point on a given parallel platform. Then, the connection between the iterative algorithm and an
existing static performance estimator, P 3 T [7], is discussed. A preliminary prototype of automatic
range comparison is implemented under the Vienna Fortran Compilation System (VFCS). Finally,
two applications are tested with two different data distributions to verify the correctness and
feasibility of the range comparison approach. While current experimental results are preliminary,
they clearly demonstrate the feasibility and effectiveness of the range comparison approach for
program restructuring.
This paper is organized as follows. VFCS and its performance estimation tool are introduced
in Section 2. The concept of scalability, performance crossing point and range comparison are
presented in Section 3. An iterative algorithm for automatic performance prediction is described in
detail. Experimental results are given in Section 4 to illustrate how the newly proposed algorithm
can be integrated within VFCS in order to predict the crossing point automatically. Finally, Section
5 concludes with a summary
Compilation System
VFCS is a parallelizing compiler for Vienna Fortran and High Performance Fortran. VFCS is integrated
with several tools for program analysis and transformation, and among others provides
a parallelization technique which is based upon domain decomposition in conjunction with the
Single-Program-Multiple-Data (SPMD) programming model. This model implies that each processor
is executing the same program based on a different data domain. The work distribution
of a parallel program is determined - based on the underlying data distribution - according to
the owner-computes rule which means that the processor that owns a datum will perform the
computations that make an assignment to this datum. Non-local data referenced by a processor
imply communication which is optimized by several strategies [5] such as extracting single element
messages from a loop and combine them into vectors (communication vectorization), removing
redundant communication (communication fusion), and aggregating different communication
statements (communication aggregation). The analysis described in this paper is targeted towards
regular computations, such as stencil computations, and relies heavily on compile-time analysis and
optimization as provided by VFCS.
2.1 performance estimator
is an integrated tool of VFCS which assists users in performance tuning of regular
programs at compile time. P 3 T is based on a single profile run to obtain characteristic data for
branching probabilities, statement and loop execution counts. It is well known [9, 10, 11, 12] that
the overhead to access non-local data from remote processors on distributed memory architectures
is commonly orders of magnitude higher than the cost of accessing local data. Communication overhead
is, therefore, one of the most important metrics in choosing an appropriate data distribution.
communication overhead by two separate performance parameters: number of data
transfers and amount of data transferred. For the sake of brevity, only issues of static estimation
of communication overhead are discussed in this section. Interested readers may refer to [7, 8, 13]
for more information regarding the other performance parameters of P 3 T .
Note that in Section 4 we define communication time that combines the P 3 T parameters
mentioned above and various machine specific metrics.
Number of Data Transfers
The number of data transfers is a critical parameter which reflects the high message startup
costs on most distributed memory architectures. Commonly the overhead for communication is
decreasing if it can be hoisted outside of a nested loop. Moreover, communication inside of a
specific loop body in many cases implies that the loop is sequentialized due to synchronization
between the processors involved in the communication. P 3 T carefully models the loop nesting level
at which a communication is placed, array access patterns, data dependences and distribution,
control flow, and compiler communication optimizations (e.g., communication vectorization and
fusion) in order to determine the number of data transfers with high accuracy.
For communication that can be hoisted outside a loop nest we assume the loosely synchronous
communication model [14] which implies that all involved processors communicate simultaneously.
For such a communication statement the number of data transfers is determined by the maximum
number of data transfers across all involved processors. For communication that cannot be hoisted
outside a loop nest due to a data dependence we assume that it sequentializes the loop at which
the communication is placed as well as all data transfers implied by the communication. The
number of data transfers for such a communication is given by the sum of data transfers across all
processors involved in the communication.
Amount of Data Transferred
The current generation of distributed memory architectures reduces the impact of the message
length on the communication overhead. For applications that transmit small data volumes, the
startup cost is the predominate communication cost factor. However, for increasing data volumes
transmitted, the message transfer time per byte and in turn the amount of data transferred becomes
the first order performance effect. In order to provide a highly accurate estimate for the
amount of data transferred (given in bytes) as induced by a parallel program, P 3 T estimates the
number of non-local data elements accessed and incorporates machine specific data type sizes.
For this purpose, P 3 T examines the loop nesting level at which a communication is placed, array
access patterns, data dependences and distributions, control flow, and compiler communication
optimizations.
As the compiler specifies the communication pattern at the source code level, the target architecture
can be for the most part - except for data type sizes - ignored. Consequently, this
parameter ports easily to a large class of distributed memory architectures.
Performance Range Comparison
While execution time is an important performance metric for optimizing parallel programs, its
comparison bonds to a specific pair of system and problem size. Execution time alone is not
sufficient for performance comparison over a range of system and problem sizes. Scalability has
been recognized as an important property of parallel algorithms and machines in recent years
[15]. Several scalability metrics have been proposed [16, 17, 18]. However, scalability has been
traditionally studied separately as an independent property. Only very recently has the relation of
scalability and execution time been studied and the concept of range comparison been introduced
[19, 20]. Unlike conventional execution time comparison in which performance is compared at a
particular system and problem size, range comparison compares the performance of programs over
a range of system and problem size via scalability and performance crossing point analysis. To
fully understand the concept of range comparison, some background of scalability and crossing
point analysis needs to be introduced.
3.1 Isospeed Scalability
A major driving force behind parallel computing is to solve large problems fast. Traditionally,
execution time is the measure of choice for fixed-size problems. Execution time by itself, however,
is not adequate for scalable computing where problem size scales up with system size. Speed,
defined as work divided by time, has been proposed as an alternative primary metric for scalable
computing 1 . Average speed is the achieved speed divided by the number of processors used. Average
speed is a quantity that ideally would be unchanged with scaled system size. The following definition
was first given in [16].
(Isospeed Scalability of Algorithm-Machine Combination) An Algorithm-Machine Combination
is scalable if the achieved average speed of the algorithm on the given machine can remain
constant with the increasing number of processors, provided the problem size can be increased with
the system size.
For a large class of Algorithm-Machine Combinations (AMCs), the average speed can be maintained
by increasing the problem size. The necessary problem size increase varies with algorithm-
machine combinations. This variation provides a quantitative measurement for scalability. Let W
be the amount of work of an algorithm when p processors are employed in a machine, and let W 0
be the amount of work of the algorithm when processors are employed to maintain the
average speed, then the scalability from system size p to system size p 0 of the algorithm-machine
combination is:
Where the work W 0 is determined by the isospeed constraint. Finally, let T p (W ) be the time for
computing W work on a p processors system, equation (2) shows how scaled execution time can be
computed from scalability,
Three approaches have been proposed to determine scalabilities [16]. They are: computing
the relation between problem size and speed, directly measuring the scalability, and predicting
scalability with certain predetermined parameters. While all of the three approaches are practically
important, scalability prediction seems to be less expensive and benefits most from compiler
support.
The parallel execution time T p (W ) can be divided into two parts: the ideal parallel processing
time and parallel processing overhead, T
1 How to define work, in general, is debatable. For scientific applications, it is commonly agreed that the floating
point (flop) operation count is a good estimate of work.
where T s is the sequential execution time, \Delta is the computing capacity, defined as time per unit
of work, of a single processor. The parallel processing overhead T contains the load imbalance
overhead, communication overhead, and other possible parallelism degradations. By the definition
of scalability (see (1)), scalability can be predicted if and only if the scaled work size, W 0 , can be
predicted. A prediction formula has been given in [21] to compute
where a is the achieved average speed and T 0
is the parallel processing overhead on p 0 proces-
sors. When parallel degradation does exist (i.e. T 0
is traceable. T 0
necessary and sufficient condition of equation 4. When T 0
is achieved with
processing overhead T 0
general is a function
of problem size. With unknowns on both sides of the equation, using formula (4) for scalability
prediction is not a straightforward task.
3.2 Performance Crossing Point and Range Comparison
Theorem 1 gives a relation between scalability and execution time of two different algorithm-
machine combinations. It has been analytically proven and experimentally confirmed in [19].
Theorem 1 If algorithm-machine combinations 1 and 2 have execution time ff \Delta T and T , respec-
tively, at the same initial state (the same initial system and problem size), then combination 1 has
a higher scalability than combination 2 at a scaled system size if and only if the execution time of
combination 1 is smaller than the ff multiple of the execution time of combination 2 for solving W 0
at the scaled system size, where W 0 is the scaled problem size of combination 1.
Theorem 1 shows that if an AMC is faster at the initial state and has a better scalability than
that of others then it will remain faster over the scalable range. Range comparison becomes more
difficult when the initially faster AMC has a smaller scalability. When the system size scales up,
an originally faster code with lower scalability can become slower than another code with a better
scalability. Finding the fast/slow crossing point is critical for optimizing performance and choosing
efficient data distributions and program transformations in a data-parallel environment. Finding
the superiority/inferiority crossing point, however, is very difficult. The definition of crossing point
is problem size and system size dependent. Definition 2 gives a formal definition of crossing point
based on the isospeed scalability [20].
(scaled crossing point) For any ff ? 1, if algorithm-machine combinations 1 and 2
have execution time ff -
T and T respectively at the same initial state, then we say a scaled system size
0 is a crossing point of combinations 1 and 2 if the ratio of the isospeed scalability of combination
1 and combination 2 is greater than ff at p 0 .
Let AMC 1 have execution time t, scalability \Phi(p; p 0 ), and scaled problem size W 0 . Let AMC 2
have execution time T , scalability \Psi(p; p 0 ), and scaled problem size W   . By Definition 2, p 0 is the
crossing point of AMC 1 and 2 if and only if
In fact, by equation (2), when \Phi(p; Notice that since
combination 2 has a smaller execution time at the initial state, t p (W
superiority/inferiority changing in execution time gives the meaning of performance crossing point.
The correctness of Theorems 2 and 3 is proved in [20].
Theorem 2 If algorithm-machine combination 1 has a larger execution time than algorithm-
machine combination 2 at the same initial state, then, for any scaled system size p 0 , p 0 is a scaled
crossing point if and only if combination 1 has a smaller scaled execution time than that of combination
2.
Since two different algorithm-machine combinations may have different scalabilities, their performances
may cross at crossing point p 0 with different scaled problem sizes, W 0 6= W   . Scaled
crossing point is different from the equal-size crossing point where performance crosses with the
same problem size. Theorem 3 gives a relation between the scaled crossing point and equal-size
crossing point.
Theorem 3 If algorithm-machine combination 1 has a larger execution time than algorithm-
machine combination 2 at the same initial state and p 0 is not a scaled crossing point, then combination
1 has a larger execution time than that of combination 2 for solving W 0 at the system size
is the scaled problem size of combination 1.
Theorem 3 gives the necessary condition for equal-size performance crossing with an initial
system size of p: if p 0 is an equal-size crossing point of p it must be a scaled crossing point of p.
On the other hand, if p 0 is not a scaled crossing point of p, it is not an equal-size crossing point of
p. No performance crossing will occur before the scaled crossing point even in terms of equal-size
performance. Theorem 3 provides the mean of range comparison. Based on the above theoretical
findings Figure 1 gives the procedure of range comparison in terms of scalability.
3.3 Automatic Crossing-Point Prediction
The procedure of range comparison listed in Figure 1 is in terms of scalability. Scalabilities of
different code implementations, or different algorithm-machine combinations in general, still need
to be determined for range comparison. Scalabilities of different algorithmic implementations can be
pre-stored for performance comparison. In many situations, however, premeasured results of scaled
systems are not available and predictions are necessary. We propose an iterative method listed in

Figure

2 to compute W 0 and to predict the scalability automatically. We assume that the underlying
application is scalable and its work W is a monotonically increasing function of a scaling parameter
(input data size). We also assume that parallel overhead T o is either independent of parameter n
(ideally scalable) or is monotonically increasing with n (parallel degradation exists). The iterative
algorithm consists of three parts: the main program and two subroutines for computing the function
of OE(W ) and the inverse of OE(W ). Function OE(W ) is implied by equation (4). Mathematically, the
iterative algorithm is to find a fixed point of OE(W ) such that proof of correctness of
the algorithm is provided in the Appendix.
Our correctness proof does not give the convergence rate of the iteration algorithm. Like most
iterative methods, the convergence rate of the algorithm is application dependent. It depends on
the properties of function f(n). For most scientific computations, f(n) is a low degree polynomial
function and the algorithm converges very fast. Our experimental results show that the algorithm
only requires three to five iterations to converge to a solution with an error bound of
Assumption of the Algorithm: Assume algorithm-machine combinations
1 and 2 have execution time ffT and T respectively at the
same initial state, where ff ? 1.
Objective of the Algorithm: Predict if combination 2 is superior
over the range of system sizes from p to p 0 , where
Range Comparison
Begin
Determine the Scalability of combination 1
Determine the Scalability of combination 2
If
Combination 2 is superior over the range !
Else
0 is a scaled crossing point
EndfIfg
EndfRange Comparison g

Figure

1. Range Comparison Via Performance Crossing point
4 Automatic Performance Comparison Under VFCS
We have implemented a prototype version of the iterative algorithm within VFCS for predicting the
scalability and execution time of a parallelized code. The functionalities of P 3 T and VFCS have
been fully implemented as described in Section 2. Figure 3 shows the structure of the scalability
prediction within VFCS. The input program is parallelized, instrumented by VFCS, and a message
passing code is generated. This code is then compiled and executed on the target parallel machine.
A performance analysis tool analyzes the tracefile obtained and computes (initial) performance
indices which are then used by scalability prediction. Finally, scalability prediction implements the
iterative algorithm as described in Section 3. At each iteration of the algorithm the problem size is
specified, the source code is automatically parallelized, performance indices ( number of transfers
Z and the amount of data transferred D) are estimated by P 3 T , and scalability prediction is
performed. This process iterates until the algorithm converges.
Experimental results show that our approach provides an effective solution for capturing the
scaling properties of a parallel code and supports optimizing data-parallel programs. Two cases
are presented in detail in this section to illustrate how the iterative algorithm is used within the
VFCS environment and how the prediction is carried out automatically.
The experiments have been carried out on an iPSC/860 hypercube with processors. The
parallel processing overhead T used in the scalability iteration algorithm, as described in Section 3,
contains communication overhead and load imbalance. We choose two codes, Jacobi and Redblack,
both of which contain several 2 dimensional arrays and imply good load balance. T
contains only the communication time that can be obtained by the formula
Assumption of the Algorithm: Assume work W and overhead T
are increasing functions of the scaling parameter n,
is a constant, and assume the parallel code
under study has been executed on the target machine with W work
and p processors.
Objective of the Algorithm: Compute the scalability from system
size p to p 0 , where with an error of ffl ? 0.
Iterative Method
Begin
Initial Value: W
Compute
Begin Iteration (k=0; k++)
until
Else do
Begin Iteration (k=0; k++)
until
EndfIfg
EndfIterative Methodg
Begin
Solve
Compute
Compute
EndfSubroutine OE(W )g
Begin
Compute
Solve

Figure

2. An Iterative Method for Predicting Scalability
TTracefile
Compute
T'o
Compute
ComputeW' k
NO
YES
Compute
VFCS
Parallelize
Z, D,
MP code
Instrum.
Execution
W,T ,T ,Z,D,T K=1
Compute performance indices
Scalability Prediction
Source code

Figure

3. Scalability prediction within VFCS
where Z and D are predicted at compile time for any problem size W using P 3 T . The machine specific
parameters, ae and fi, are the startup time and the transfer time per message byte, respectively.
represents the additional overhead for each network hop and h is the number of hops.
Jacobi and Redblack, have been parallelized by VFCS and their performance measured on 4
processors of an iPSC/860 hypercube. The performance indices obtained and needed for computing
the initial state of the scalability prediction are given by the work W , the total execution time on p
processors T p , the computation time T c and the communication overhead T . The execution models
of Jacobi and Redblack based on equation (3) are as follows:
and
We assume that the computations of Jacobi and Redblack are uniformly distributed across all
processors.
The computing rate
W and the average speed a
can be determined by the
measured computation time and total execution time. The initial value of the prediction algorithm,
p , is computed based on the work W and Starting with iteration new input
data size n obtained for k - 0. The communication overhead T 0
and the scaled
are predicted using (6) and (4), respectively. Scalability from processors p to processors
determined when the terminating condition is satisfied for a fixed ffl ? 0
used in our experiments). Otherwise the method iterates with the new parameter

Tables

show the measured and predicted scalability of Jacobi algorithm with two different
data distribution strategies: two-dimensional block distribution and column-wise distribution
of all program arrays to a two-dimensional and one-dimensional processors array, respectively. The
difference in percentage between the predicted and measured values is given in the third column of
the tables.
Meas. Pred. Meas. diff. Pred. Meas. diff
p=8 1.000 1.000 0% 0.842 0.819 2.7%

Table

1. Jacobi: two-dimensional distribution, predicted and measured scalability
Meas. Pred. Meas. diff. Pred. Meas. diff
p=8 1.000 1.000 0% 0.796 0.808 1.5%

Table

2. Jacobi: column distribution, predicted and measured scalability
The experimental results confirm that our predicted scalabilities are very accurate and the
variations of scaled performance for various data distributions are also captured.

Table

3 shows the predicted and measured scalability values of the Redblack algorithm with
two-dimensional distribution. Tables 4, 5 and 6 present the predicted execution times versus the
Meas. Pred. Meas. diff. Pred. Meas. diff

Table

3. Redblack: two-dimensional distribution, predicted and measured scalability
measured ones for Jacobi with two-dimensional block distribution, one dimensional distribution
and Redblack with two-dimensional block distribution, respectively.
The initial problem size used in Tables 1 to 6 is determined by the asymptotic speed [22] for best
performance, where chosen. We have measured the average execution time required for
a single iteration (covering parallelization, P 3 T and scalability prediction) of Fig. 3. For Redblack
the parallelization time accounts for 0:7 secs, P 3 T for 0:3 secs and scalability prediction for 0:1 secs.
Overall, every iteration took approximately 1:1 secs which remains constant for changing problem
Meas. diff.

Table

4. Jacobi 2D: Predicted and Measured Execution times (in -s)
Meas. diff.

Table

5. Jacobi C: Predicted and Measured Execution times (in -s)
size. The execution time of Redblack can be written as ffT 4
2:975. According to Tables 1, 2, and 3, the scalability of Jacobi is
higher than that of Redblack. Therefore, by Theorem 1, the smaller initial execution time and
larger scalability shows that Jacobi scales better than Redblack which is confirmed by measured
results as given in Tables 4, 5, 6.
A more interesting result is given by the two different Jacobi versions. From Tables 1 and 2,
we can see that the 2D distribution implementation has a larger initial execution time and a better
scalability, on than that of column-wise distribution. According to Theorem 2, there will
be a crossing point at some scaled system size p 0 . However, in this case the crossing point is greater
than 16 and cannot be confirmed by our prototype implementation. Figure 4 shows that there is
no crossing point for range of 4 to 16 processors.
As pointed out in [21], scaled performance is more sensitive for small applications, where increasing
system size will cause more noticeable change of communication/computation ratio. For
Jacobi, the communication/computation ratio increases with the decrease of problem size. At the
initial state where 20, the execution time for Jacobi with column-wise distribution
strategy is given by T 4 -s and for Jacobi with 2D distribution it is ffT 4
Redblack 2D
Meas. diff.

Table

6. Redblack 2D: Predicted and Measured Execution times (in -s)
Execution
Time
2D distribution
Column distribution

Figure

4. No equal-size crossing point for Jacobi with starting point
1:267. Considering the scalability results of Tables 7 and 8, we see that for
the 2D distribution scales better than that of column-wise distribution. The ratio between the two
predicted scalabilities, 0:652
0:373
1:747, is greater than ff. Therefore, by Definition 2,
crossing point where the execution time of 2D distribution becomes less than that of column-wise
distribution. This crossing point is due to the communication behavior involved on iPSC/860 for
confirmed by the measured execution times as shown in Figure 5.a.
p=4 1.000 0.652 0.548

Table

7. Predicted scalability for Jacobi with 2D distribution
p=4 1.000 0.373 0.333
p=8 1.000 0.893

Table

8. Predicted scalability for Jacobi column-wise distribution
In order to verify whether the crossing point for is an equal-size crossing point, we
measured both codes with In accordance with Theorem 3,
corresponds to an equal-size crossing point. The results are shown in Figure 5.b.
Execution
Time
2D distribution
Column distribution
Processors600.01000.01400.0
Execution
time
2D distribution
Column distribution
(a) (b)

Figure

5. Scaled crossing point (a) and equal-size crossing point (b) for the Jacobi with n=20
5 Conclusion
There are many ways to parallelize a program, and the relative performance gain of different
parallelizations strategies varies with problem size and system size. Comparing the performance
of different implementations of an algorithm over a range of system and problem sizes is crucial
in developing effective parallelizing compilers and ultimately in reducing the burden of parallel
programming. In this study a practical methodology is developed for automatic range comparison
and it is tested in a data-parallel compilation system. The proposed methodology is built on
rigorous analytical models which are both correct and efficient. Experimental results confirm its
effectiveness as part of a parallelizing compiler.
This paper offers several contribution. First we identify the importance and feasibility of range
comparison in data-parallel compilation systems; next an iterative algorithm is developed to experimentally
predict the scalability of algorithm-machine combinations and to enable automatic range
comparison. an existing static estimator, is modified to integrate automatic range comparison
into a data-parallel compilation systems. Finally, the range comparison approach is tested as part
of Vienna Fortran Compilation System. Our experimental results demonstrate the feasibility and
high potential of range comparison in a parallelizing compiler.
The concept and analytical results given in Section 3.1 and 3.2 are very general. They are
applicable to any algorithm-machine combinations. The scalability prediction algorithm given in
Section 3.3 assumes that the workload is a deterministic function of a scaling factor n. While
this assumption is quite reasonable, the algorithm requires an estimation of the parallel processing
overhead. The algorithm has been tested with P 3 T static performance estimator under Vienna
Fortran Compilation System. Due to the availability of VFCS and P 3 T , the experimental results
presented in this paper are limited on the 16 node iPSC/860 available at University of Vienna. The
integrated range comparison methodology introduced in this research, however, is general. It can
be adopted for large parallel systems as well as for other advance compilation systems [23].


Appendix

Proof of Correctness
This appendix gives a formal proof of the correctness of the iterative algorithm listed in Figure
2.
Proof:
If T o is independent of n, then . The scalability is 1. By the If instruction in the
main program we are done. Otherwise by assumption both the computation work W and the parallel
processing overhead T are monotonically increasing functions of the scaling parameter n and
, and therefore, OE
According to equation (4), a problem size W 0 is the scaled problem size for maintaining the isospeed
if and only if
a
Since both f and g are increasing functions of n, so are f \Gamma1 and g \Gamma1 . Also, since a; 4; and p
are constants during the scalability prediction process, relation (7) implies that W increases if and
only if T increases. Therefore, we can conclude that OE and OE \Gamma1 are also increasing functions of
W . By the definition of scalability (1), if the initial value W
satisfies equation (7) then the
ideal scalability, scalability equals one, is reached. Since the parallel processing overhead T does
not decrease with n, we should have the inequality W 0 - W 0 . If W
are done with the If instruction in the main program. Otherwise, the iterative method needs to be
used to find W 0 such that W
Case 1 in the main program), use the iterative method
is an increasing function, inductively we have W
Also, since W 0 is less than W 0 and OE(W ) is an
increasing Inductively we have
Therefore we have shown that That is inequalities
are preserved for all non-negative integers k if and only if it holds
just for the initial value W 0 . Passing limits to both sides of (8) yields that
which implies that iteration (8) converges to the true solution W 0 .
Case the Else instruction in the main program),
As shown in Figure 2, this time the iteration formula
is used. Following a similar argument as given in Case 1, we can conclude iteration
converge to the solution.
The stabaility of the iterative algorithm is analyzed as below. All the b below denote the
purturbed values.
b a \Delta b p
Since both g and f are functions of polynomial, the purturbed function b
OE will be very close to OE
as long as
are small enough, and
Now for the iteration W its purturbation is
Then
, the magnitude of the derivative of OE will be small if the derivative
of f is away from 0, i.e. k df(x)
Therefore, we can conclude that the iteration W
are small enough.
And for the definition of f , k df(x)
easily satisfied.
By similar arguments, the iteration W
are small enough.
The requirement k dg(x)
c is not always satisfied. But when it is not satisfied, by the definition
of the function g, the parallel overhead T will not increase much from the original overhead T
will be close to W And in this case the inverse iteration W
used by the algorithm.
Acknowledgment

The authors are grateful to Mr. Yu Zhuang for his help in strengthening the proof of correctness
of the iterative algorithm and to the anonymous referees for their constructive comments on the
revision of the paper.



--R

"The next 10; 000 2 years,"
"Programming in Vienna Fortran,"
"Fortran D language specification."
"High performance Fortran language specification version 1.0."
Vienna Fortran Compilation System - Version 2.0 - User's Guide
"An integrated compilation performance analysis environment for data parallel programs,"
Automatic Performance Prediction of Parallel Programs
"Estimating and optimizing performance for parallel programs,"
"Buffer-safe communication optimization based on data flow analysis and performance prediction,"
"A unified framework for optimizing communication in data-parallel programs,"
"A communication placement framework with unified dependence and data-flow analysis,"
"TAU,"
"A static parameter based performance prediction tool for parallel programs,"
Solving Problems on Concurrent Processors
"Development of parallel methods for a 1024- processor hypercube,"
"Scalability of parallel algorithm-machine combinations,"
Introduction to Parallel Computing
"Performance metrics: Keeping the focus on runtime,"
"The relation of scalability and execution time,"
"Performance range comparison via crossing point analysis,"
"Performance prediction: A case study using a scalable shared-virtual- memory machine,"
"Performance considerations of shared virtual memory machines,"
"Communication overhead: Prediction and its influence on scalability,"
--TR

--CTR
Xian-He Sun, Scalability versus execution time in scalable systems, Journal of Parallel and Distributed Computing, v.62 n.2, p.173-192, February 2002
Thomas Fahringer , Bernhard Scholz , Xian-He Sun, Execution-driven performance analysis for distributed and parallel systems, Proceedings of the 2nd international workshop on Software and performance, p.204-215, September 2000, Ottawa, Ontario, Canada
scalable computing;performance evaluation;parallel compiler;software systems