Report

This report documents research aimed at predicting the performance of
scientific applications on high-end computing systems.

Performance modeling techniques use either an analytical approach or a
simulation approach. Snavely's framework for performance modeling is
simulation-based. The POEMS project incorporates both simulation and
analytical models. The CEPBA-IBM Research Institute is attempting to
derive a linear model of execution time of MPI applications as a
function of parameters such as processor speed, network latency, network
bandwidth and number of processors. The CARNIVAL project employs a Lost
Cycles Analysis approach, which involves measurement and modeling of all
sources of overhead in a parallel program. Clement's work applies
multivariate data analysis techniques to performance prediction of
Dataparallel C codes. Zhang's work applies a semi-empirical methodology,
combining analytical modeling and measurements, in predicting
performance. Mendes' work transforms trace obtained from an instrumented
run of an application on a base machine to predict performance on a
target real or hypothetical machine. Each of these research efforts is
now described in greater detail.

# [Snavely's framework]{.underline}

Allan Snavely, Laura Carrington, Nicole Wolter, Jesus Labarta, Rosa
Badia, Avi Purkayastha , SC2002, Baltimore

[A Framework for Application Performance Modeling and
Prediction](http://www.sdsc.edu/pmac/Papers/SC-final.doc)

Laura Carrington, Nicole Wolter, Allan Snavely, and Cynthia Bailey Lee\
UGC 2004, Williamsburgh, June 2004.

[Applying an Automated Framework to Produce Accurate Blind Performance
Predictions of Full-Scale HPC
Applications](http://www.sdsc.edu/~allans/UGC2004_final.pdf)

Xiaofeng Gao and Allan Snavely, ICCS Workshop on Performance Modeling
and Analysis (PMA03), June 2003, Melbourne

[Exploiting Stability to Reduce Time-Space Cost for Memory
Tracing](http://www.sdsc.edu/pmac/Papers/ICCS_June2003_Xiaofeng.pdf)

The framework is instantiated with

-   MAPS and PMB benchmark data for machine profiles

-   MetaSim tracer and MPIDtrace for application signatures

-   Dimemas and MetaSim convolver to provide the automated convolving
    step

![](media/image1.png){width="5.9944444444444445in"
height="3.7743055555555554in"}

![](media/image2.png){width="5.998611111111111in"
height="6.478472222222222in"}

![](media/image3.png){width="5.990972222222222in"
height="2.1284722222222223in"}

![](media/image4.png){width="5.995833333333334in"
height="4.511805555555555in"}

Some additional details on Snavely's work is contained in

<http://www.cse.ohio-state.edu/~shet/Snavely_summary.doc>

## POEMS

"V. S. Adve, R. Bagrodia, J. C. Browne, Deelman, E., A. Dube, E.
Houstis, J. Rice, R. Sakellariou, D. Sundaram-Stukel, P. J. Teller, and
M. K. Vernon, \"POEMS: End-to-end Performance Design of Large Parallel
Adaptive Computational Systems\", *IEEE Transactions on Software
Engineering*, Special Section of invited papers from the WOSP \'98
Workshop, Vol. 26, No. 11, Nov. 2000, pp. 1027-1048"

<http://www.cs.wisc.edu/~vernon/papers/poems.00tse.pdf>

Sundaram-Stukel, D. and M. K. Vernon, \"Predictive Analysis of a
Wavefront Application Using LogGP\", *Proc. 7th ACM SIGPLAN Symp. on
Principles and Practices of Parallel Programming (PPoPP \'99)*, Atlanta,
GA, May 1999, pp. 141-150

<http://www.cs.wisc.edu/~vernon/papers/poems.99ppopp.pdf>

\"Performance Prediction of Large Parallel Applications Using Parallel
Simulations,\" Rajive Bagrodia, Ewa Deelman, Steven Docy, Thomas Phan;
*ACM SIGPLAN 1999 Symposium on Principles and Practice of Parallel
Programming,* Atlanta, Georgia, May 4-6, 1999

<http://www.cs.utexas.edu/users/poems/Papers/Bagrodia_ppopp.ps>

The POEMS framework integrates multiple modeling paradigms

-   Component models:

```{=html}
<!-- -->
```
-   *Analytical models*: deterministic task graph analysis, LogP, LogGP,
    LoPC and customized Approximate Mean Value Analysis (AMVA)

-   *Simulation models*: SimpleScalar simulator (for processor and
    memory hierarchy simulation), MPI-Sim and COMPASS (for MPI program
    simulation), parallel I/O system simulators, interconnection network
    models using the PARSEC parallel simulation language

-   *Direct measurements*

```{=html}
<!-- -->
```
-   Application models: Static and dynamic task graph representation of
    Sweep3D

**[Analytical modeling in POEMS:-]{.underline}**

For predicting the execution time of Sweep3D on an IBM SP-2 system, a
LogGP model of Sweep3D is developed. The parameters L, o, G are derived
using simple two-node micro-benchmarks. Other model parameters are
obtained by measuring small application problem sizes on four SP nodes.
The LogGP model is then used to predict execution time for large
problems running on 128 nodes. Projections are also provided for very
large future processor configurations.

The LogGP model of Sweep3D is shown below.

![](media/image5.png){width="5.9944444444444445in"
height="2.886111111111111in"}

The following document summarizes machine models proposed in literature:
<http://www.cse.ohio-state.edu/~shet/Parallel_Machine_Models.doc>

## 

## CEPBA-IBM Research

\"Deriving Analytical Models from a Limited Number of Runs\", Rosa M.
Badia,\
G. Rodriguez, Jess Labarta, Minisymposium on Performance Analysis,
ParCo\
2003

<http://www.cepba.upc.edu/dimemas/docs/models_parco.pdf>\
\
\"Generation of Simple Analytical Models for Message Passing
Applications\",\
G. Rodriguez, R.M. Badia, and J. Labarta, Euro-Par 2004 Parallel\
Processing, 10th International Euro-Par Conference, Pisa, Italy, August
31 - September 3, 2004\
<http://www.cepba.upc.edu/dimemas/docs/europar04.pdf>

The DIMEMAS tool used in Snavely's communication performance model is
developed by CEPBA. DIMEMAS is a network simulator that simulates a
network of SMPs by accepting user definitions of initial and target
machines.

For each application that is to be analyzed, a real execution is
performed to extract the tracefile that feeds DIMEMAS. The tracefile
characterizes an instantiation of problem size and number of processors.
The tracefile obtained contains information of communication requests by
each process as well as the CPU demands between those requests.
Additionally, by accepting user input for processor ratio (the speed of
the target machine relative to the machine where the trace was obtained)
and network bandwidth/latency characteristics of the target machine,
DIMEMAS predicts execution time on the target machine. The processor
ratio is used to approximate the computation time. The communication
time is modeled with the simple linear model T = L + S/BW where L =
network latency, S = message size and BW = network bandwidth. The
summation of computation and communication times gives the execution
time.

To fit a linear model to architectural parameters like processor speed,
network latency and network bandwidth, a bunch of simulations of the
same tracefile is launched randomly, varying for each simulation the
values of these parameters. From the results of the simulations a linear
regression is performed to extract a linear model for the elapsed time
of the application against the architectural parameters. The
coefficients in the model become the summarized characterization of the
application.

To fit a linear model to processor count, several traces are obtained
with different numbers of processors and linear regression is done.

**[Results:]{.underline}**

![](media/image6.png){width="5.416666666666667in"
height="0.6145833333333334in"}

![](media/image7.png){width="5.993055555555555in" height="2.1375in"}

![](media/image8.png){width="5.997916666666667in"
height="1.6236111111111111in"}

## Parallel Performance Prediction Using Lost Cycles Analysis

Mark E. Crovella, Thomas J. LeBlanc (1994)\
[Parallel Performance Prediction Using Lost Cycles
Analysis.](http://www.cs.bu.edu/faculty/crovella/paper-archive/lca-sc94/paper.pdf)\
In: *Proceedings of Supercomputing \'94*. pp. 600\--609.

Crovella, M. [Performance Prediction and Tuning of Parallel
Programs.](ftp://ftp.cs.rochester.edu/pub/papers/systems/95.tr573.Performance_prediction_and_tuning_of_parallel_programs.ps.gz)
Ph.D. Dissertation, TR 573, Computer Science Department, University of
Rochester, August 1994.

Wagner Meira Jr., [Modeling Performance of Parallel
Programs](ftp://ftp.cs.rochester.edu/pub/papers/systems/95.tr589.Modeling_performance_of_parallel_programs.ps.gz),
TR 589, Computer Science Department, University of Rochester, June 1995.

Lost cycles analysis is based on the observation that the distinction
between productive computation and parallel overhead is useful both for
performance diagnosis and for performance prediction. To predict
performance, total parallel overhead To, and pure computation Tc, are
modeled as functions of environment variables like the size of the input
dataset, the structure of the input dataset, the specific problem
definition, the number of processors used, and the particular machine
used. Given To and Tc, running time is predicted as Tp = (To + Tc) / p.

The parallel overhead is broken down into categories that can be
separately modeled. The categories are

-   Load Imbalance (LI): processor cycles spent idling, while unfinished
    parallel work exists.

-   Insufficient Parallelism (IP): processor cycles spent idling, while
    no unfinished parallel work exists.

-   Synchronization Loss (SL): processor cycles spent acquiring a lock,
    or waiting in a barrier.

-   Communication Loss (CL): processor cycles spent waiting while data
    moves through the system.

-   Resource Contention (RC): processor cycles spent waiting for access
    to a shared hardware resource.

Each category is modeled as a separate function of each environment
variable. A small number of measurements for each environment variable
suffice to parameterize the models, leading to an aggregate model of
performance prediction spanning the entire environment space.

Lost cycles analysis is supported by two tools, pp and lca. The role of
pp is to accurately measure parallel overheads and attribute them to
defined categories. While the output of pp can provide insight to
parallel programmers in its own right, the main use of pp\'s output is
as input to the tool lca. The role of lca is to guide the user in
fitting performance models to the data output from pp. The output from
lca forms the basis for the performance model of the application.

![](media/image9.png){width="4.59375in" height="3.9270833333333335in"}

![](media/image10.png){width="4.989583333333333in" height="4.46875in"}

#### Using Lost Cycles Analysis to model the performance of 2D FFT:-

![](media/image11.png){width="4.552083333333333in"
height="4.052083333333333in"}

![](media/image12.png){width="4.708333333333333in" height="3.0625in"}

![](media/image13.png){width="4.75in" height="4.4375in"}

![](media/image14.png){width="5.998611111111111in" height="2.45in"}

**[Multivariate Statistical Techniques for Parallel Performance
Prediction]{.underline}**

[TR BYU-NCL-95-100](http://star.cs.byu.edu/papers/ps/stat.ps)
**\"Multivariate Statistical Techniques for Parallel Performance
Prediction\"**, Mark J. Clement and Michael J. Quinn. Also appeared in
*Proceedings of the 28th Hawaii International Conference on System
Sciences, HICSS-28* January 3-6, 1995.

[TR BYU-NCL-95-101](http://star.cs.byu.edu/papers/ps/scale.ps)
**\"Symbolic Performance Prediction of Scalable Parallel Programs\"**,
Mark J. Clement and Michael J. Quinn. Also appeared in *Proceedings of
the 9th International Parallel Processing Symposium*, April 1995.

[TR BYU-NCL-94-102](http://star.cs.byu.edu/papers/ps/thesis.ps)
**\"Analytical Performance Prediction of Data-Parallel Programs\"**,
Mark J. Clement. Dissertation, August, 1994.

This work uses counts of critical operations like counts of arithmetic
operations, virtual processor emulation loops, level one cache misses,
messages sent and the number of bytes transmitted as predictor variables
for multivariate analysis. Given Dataparallel C source code,
instrumentation code is inserted to determine execution characteristics
which will be used to build a call graph for the application.
Architecture specifications for the target machine are then passed to a
linearization phase which outputs operation counts for significant
system parameters. Given a statistically significant number of
experimental runs with different problem sizes and numbers of
processors, Linear least-squares models is used to obtain the cost in
seconds for each operation type. The counts, combined with costs in time
for each operation type, results in a symbolic equation for execution
time. Since the result of this model is an equation rather than a time
estimate for a given problem size, the execution time can be
differentiated with respect to a given system parameter. The resulting
equation can be used to determine the sensitivity of the application to
changes in that parameter as the problem is scaled up.

![](media/image15.png){width="4.25in" height="3.2604166666666665in"}

The execution time is modeled as

![](media/image16.png){width="2.1979166666666665in" height="0.40625in"}

where **χ~i~** denotes an operation count and **β~i~** denotes the
corresponding operation cost. The **β~i~** values are determined using
the S-PLUS statistical software package.

![](media/image17.png){width="4.166666666666667in"
height="1.9895833333333333in"}

where **β~Ops~** denotes the time for an arithmetic operation, **β~VP~**
denotes the time to set up a virtual processor emulation loop, **β~St~**
denotes message startup time, **β~Bw~** denotes the time to transfer one
byte.

**[Semi-empirical Multiprocessor Performance Predictions]{.underline}**

[TR-96-05-01.pdf](http://www.cs.wm.edu/hpcs/WWW/HTML/publications/papers/TR-96-05-01.pdf)
Z. Xu, X. Zhang and L. Sun, \`\`Semi-empirical multiprocessor
performance predictions", Journal of Parallel and Distributed Computing,
Vol. 39, No. 1, 1996, pp. 14-28.

[TR-95-03-01.pdf](http://www.cs.wm.edu/hpcs/WWW/HTML/publications/papers/TR-95-03-01.pdf)
X. Zhang and Z. Xu \`\`Multiprocessor Scalability Predictions Through
Detailed Program Execution Analysis\", In Proceedings of the 9th ACM
International Conference on Supercomputing, (ICS\'95), July 1995.

[TR-94-02-01.pdf](http://www.cs.wm.edu/hpcs/WWW/HTML/publications/papers/TR-94-02-01.pdf)
X. Zhang, Y. Yan, and K. He, \`\`Latency metric: an experimental method
for measuring and evaluating parallel program and architecture
scalability\". The revised version was published in Journal of Parallel
and Distributed Computing, Vol. 22, No. 3, 1994.

This work uses a combination of analytical and empirical results to
predict performance. The proposed methodology is based on a two-level
hierarchical model. In the higher level, a graphical model called the
thread graph is used to characterize parallel applications, and a
graphical algorithm is used to estimate the parallel execution time of a
parallel application, assuming the elapsed times of all individual
segments and events in the thread graph are known. On the lower level,
the elapsed times of individual segments and events in the thread graph
are determined with both analytic and experimental methods. Implicit and
non-deterministic system effects are obtained through experimental

measurements.

This work also proposes a latency metric as a practical method to
effectively predict and evaluate scalability based on measured latencies
inherent in the program and the architecture.

## Performance Scalability Predictions on Multicomputers

Celso L. Mendes, \"[Performance Prediction by Trace
Transformation](http://www.renci.unc.edu/Publications/Papers/PerformancePredictionbyTraceTransformation.ps.gz),\"
Fifth Brazilian Symposium on Computer Architecture, Florianopolis,
Brazil, September 1993.

Celso L. Mendes and Daniel A. Reed, \"[Performance Stability and
Prediction](http://www.renci.unc.edu/Publications/Papers/PerformanceStabilityandPrediction.ps.gz),\"
*IEEE International Workshop on High Performance Computing (WHPC\'94)*,
Sao Paulo, Brazil, March 28-30, 1994.

Celso L. Mendes, \"[Performance Scalability Prediction on
Multicomputers](http://www.renci.unc.edu/Publications/Theses/MendesPhD.ps.gz),
1997

This work explores stability of parallel programs and cross­machine
performance prediction on multicomputers. Program behavior is
characterized by an execution graph, obtained from running an
instrumented version of the program. Program stability is assessed using
time perturbations, and the resulting execution graphs are analyzed with
an approximation of a graph comparison metric based on subgraph
isomorphism. On programs with stable behavior, performance is predicted
across different systems by transforming the observed execution trace;
this trace transformation adjusts timestamps of events according to the
architectural parameters of the systems under study, assuming the same
partial event order on both systems. This technique allows performance
to be predicted for future, hypothetical systems.