%VAL - you might check out the case study on fusion. It mentions performance models there and which can be used
%
%    %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%               General-Purpose Preamble
%    %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
%
%
%
\documentstyle[11pt]{article}
\pagestyle{plain}
\setlength{\textheight}{8.0in}
\setlength{\textwidth}{6.0in}
\setlength{\evensidemargin}{0.3in}
\setlength{\oddsidemargin}{0.3in}
\setlength{\topmargin}{0.0in}
\setlength{\parskip}{2ex}
%
%
\begin{document}

\begin{center}
{\Large \bf Performance Modeling}
\end{center}
	
	

Application performance was mentioned in most of the 
presentations given at the Petaflops summer workshop.  Performance 
issues also were discussed in detail during a lengthy session on performance
modeling.  This section summarizes the various discussions.
 
\section{Performance Models: Benefits and Challenges}
Performance models are analytical equations that predict and evaluate the 
performance (usually in terms of execution time) of an application executing on a given machine or type of machine.
Performance models can provide 
vital information about performance bottlenecks.
The programmer may use this information to
rewrite or transform an algorithm;
the vendor may gain insight into ways 
of redesigning the hardware for future products.

The major 
challenge in developing effective performance models is
the derivation and validation of the 
analytical equations.
The {\it derivation} of the analytical equations requires an in-depth 
understanding of the application, the processors used in the machine, the 
interconnection of the processors, and the granularity of parallelism extracted 
from the applications (e.g., data versus task). 
The problem here is that the person who is most knowledgeable about the application
(the computational scientist)
typically is {\it not} 
the same person who is most knowledgeable about the way the computer system
operates (the computer scientist). 
Moreover, whereas
the computational scientist focuses on the results of the application,  
the computer scientist focuses on core algorithms.
{\it
These two groups must work more closely:}
the computer scientist must 
gain a better understanding of 
the complete application, not just the core algorithms; and
the computational scientist
(particularly one working with the so-called killer applications)
must exploit the
significant work that has been done in the area of core 
numerical algorithms.

The {\it validation} of the analytical equations requires significant amounts of 
empirical data from experiments.  This data is used to refine the 
coefficients in the equations.  The empirical data 
is affected by various factors.
For uniprocessors, these factors include
the operating system,
the organization of the memory hierarchy, and
the branch prediction and penalty scheme.  For multiprocessors,
the factors include the communication pattern on link contention 
and congestion, load imbalance, and 
synchronization effects due to the diameter of the machine.

For 
Petaflops computers, 
performance modeling is made more difficult because of the
use of more components, the complexity of the 
applications, and the varied programming 
models.  Some of the industrial attendees emphasized that 
current performance models already are breaking down for parallel systems and that 
it is increasing difficult and costly to provide performance information for 
customer applications.  Hence, significant research is needed in the area 
of performance models.


\section{Performance Modeling Session}

The session dedicated to performance modeling consisted of two talks, one 
from academia and one from industry. Applications 
and computer scientists held discussion for approximately three hours.  
The academic talk focused on the use of various metrics to compare the 
performance of different parallel algorithms. 
The industry talk focused on the synergism of core algorithms.
 
\subsection{Performance Metrics}

The most important metric for performance modeling is
the {\it isoefficiency function,} which provides insight into the 
scalability of a parallel application.  The isoefficiency function 
%VAL - Do you have the equation?
@VAL- other metrics mentioned and their limitations?
relates the scaling the problem to the saling of the number of processors 
necessary to maintain a fixed efficiency value.  Depending on the 
complexity of this relationship, one can determine whether the parallel 
application is good for execution on a large number of processors.

The isoefficiency 
function assumes the existence of the speedup equation to derive the 
isoefficiency function.  This speedup equation can be only a gross 
approximation to performance.
For reliable performance evaluation, however, the coefficients are critical. 
Currently, most parallel performance models comprise only first-order 
parameters such as computation, communication, and idle times.  The 
computation time generally reflects the number of operations necessary, 
with some compensation for memory latency. 
Further research is needed to develop
performance models that include second- and third-order machines 
parameters.
In particular,
with the use of 
large number of processors, the network congestion may have a significant 
effect on the communication time; 
hence it is desirable for performance 
models to include such analysis.  The machine diameter may affect the 
synchronization time, and hence the idle time; hence, this 
parameter also should be included in accurate performance models.

Finally, research is needed
to develop
tools for validating and refining the performance models. 
Such tools include hardware performance monitors, memory monitors, and 
simulators for the entire memory hierarchy.

\subsection{The Breakdown of Performance Modeling}

The industrial speakers
emphasized
the increasing difficulty
of conducting adequate performance modeling.
Indeed, they characterized the situation as being on the
point of breakdown.

The difficulty stems from the following situation.
Industry is asked to 
measure (or predict) the performance
for benchmark applications
provided by the customer. 
The performance of the supplied 
customer benchmark is projected by industry based upon the performance of 
well-defined, standard, but isolated core algorithms. 
Such projections are subject to erroneous 
performance estimates, unaccounted large system effects, and undetected 
systems errors and bugs.

The discussions following this talk focused on the need to develop a type 
of ``performance calculus" that can accurately predict the performance of full 
applications 
from the {\it synergism} of core algorithms. 
Specifically, research is needed to 
identify the interrelationship of various core algorithms used in the 
same application.  The applications requiring high-performance parallel 
systems are often very complex, entailing core algorithms from various 
engineering disciplines. 



\section{Application Performance}

An almost universal theme in the
applications presentations was the 
poor performance
(relative to so-called peak performance)
currently attainable on parallel machines.
The discussions 
brought out various issues regarding 
methods for improving the performance.

For example,
in research on controlled magnetic fusion,
an I/O traffic of 2.7 petabytes to disk in 8.1 hours of execution time is antici
pated for magnetofluid calculations,
with 1,200 grid points and 36,000 modes on a Petaflops machine.
File sizes of 1.6 gigabytes will be written to disk every time step, for
an aggregate I/O throughput of 93 gigabytes/sec.
This {\it I/O capacity} needs to be accommodated in the design of a Petaflops machine.

As another example,
in research on
automatic test pattern generation
(the process of generating a set of input patterns for a digital device
that are sufficient to detect all physical defects in the device that may
be present in it after it is manufactured),
most algorithms are latency limited.
Scientists would like access to
a machine that is able to pass medium-sized packets
of data (approximately 1--10 kilobytes) with {\it very low latencies}
regardless of the number of processors.
 
With specific regard
to {\it uniprocessor performance,}
questions were raised concerning 
the application and the processor architecture.  In terms of the 
application, the following
factors were identified as important:
\begin{itemize}
\item
total memory requirements
\item
working set size
\item
 data structures used
\item
 operand size 
(32-bits, 64-bits)
\item
description of core algorithms.
\end{itemize}
 In terms of 
processor architecture, the following factors were identified:
\begin{itemize}
\item
amount of functional parallelism available in the processor
\item
 memory bandwidth
\item
description of memory hierarchy
\end{itemize}

With specific regard to {\it parallel performance,} questions related to the application 
and machine were also discussed.  In terms of the parallel application, the 
following factors were identified:
\begin{itemize}
\item
level of parallelism exploited
\item
 data layout 
\item
possibility of using prefetching schemes
\item
 programming model
\item
decomposition methods
\item
 application scalability
\item
communication pattern (use of broadcasts, multicasts, or local 
communication)
\item
 amount of data sharing
\item
 application scalability
\item
dynamic behavior
\end{itemize}
In terms of the parallel machine, the 
following factors were identified:
\begin{itemize}
\item
bisection bandwidth
\item
communication to 
computation ratio
\item
 topology
\end{itemize}

It was agreed that
a 
team of computer scientists and application scientists
should conduct in-depth case studies to determine
the relative effect of these factors---independent of the parallel  machine and the programming model.

\section{Findings}

Performance models can play a useful role in assessing and predicting the performance of an application.
For effective use for Petaflops applications,
however,
researchers must carry out the following tasks:
\begin{enumerate}
\item
Develop performance models that incorporate
second- and third-order machines
parameters,
in particular,
analysis of 
network congestion
and synchronization time resulting from machine diameter.
\item
Design 
tools for validating and refining the performance models;
these tools include hardware performance monitors and memory monitors for
the entire memory hierarchy.
\item
Analyze the
interrelationship of core algorithms
taken from various disciplines and 
used in the
same application.
\item
Devise
a methodology or technique for using the detailed model of a core algorithm
to predict the performance of a full application.
\end{enumerate}







\end{document}
