Full text of DOI:10.1155/2002/354024

Scientific Programming 10 (2002) 3–17
IOS Press
3
Performance engineering, PSEs and the GRID
Tony Heya and Juri Papayb
aDirector UK e-Science Programme EPSRC, Polaris House, North Star Avenue Swindon SN2 1ET, UK
E-mail: Tony.Hey@epsrc.ac.uk
bDepartment of Electronics and Computer Science, University of Southampton, Southampton SO17 1BJ, UK
E-mail: jp@ecs.soton.ac.uk
Abstract: Performance Engineering is concerned with the reliable prediction and estimation of the performance of scientific
and engineering applications on a variety of parallel and distributed hardware. This paper reviews the present state of the art in
’Performance Engineering’ for both parallel computing and meta-computing environments and attempts to look forward to the
application of these techniques in the wider context of Problem Solving Environments and the Grid. The paper compares various
techniques such as benchmarking, performance measurements, analytical modelling and simulation, and highlights the lessons
learned in the related projects. The paper concludes with a discussion of the challenges of extending such methodologies to
computational Grid environments.
1. Introduction
One possible reason why performance issues do not
feature explicitly in current software methodologies is
Moore’s Law. Up to now, the exponential growth in
microprocessor performance has usually enabled users
to avoid hitting any serious ‘performance-wall’. How-
ever, in the relatively near future, it is likely that growth
in processor performance will slow down and begin to
deviate from Moore’s Law. Software developers will
then be forced to pay more attention to the efficient
use of the available silicon real-estate. Furthermore,
if the Grid becomes a reality and computer resource
‘marketplaces’ begin to emerge, software performance
on different hardware platforms will be directly related
to real costs. In such a ‘computational economy’, it is
clear that performance engineering and reliable perfor-
mance estimation will play a pivotal role in the estab-
lishment of realistic ‘performancecontracts’. A perfor-
mance contract is the productof the negotiating process
between the suppliers and customers of computing re-
sources. It contains information about the resource de-
mand of applications and available computingcapacity.
At present this feature is not available, this is mainly
due to the lack of reliable performance estimation tech-
niques. The Grid is assumed to be ‘an infrastructure
that enables flexible, secure, coordinated resource shar-
ing among dynamic collections of individuals, insti-
tutions and resources’ [13]. The resources accessible
Performance has been a central issue in computing
since the earliest days [3]:
‘As soon as the Analytical Engine exists, it will nec-
essarily guide the future course of science. When-
ever any result is sought by its aid, the question
will then arise – by what course of calculation can
these results be arrived at by machine in the shortest
time?’
Performance engineering may be defined as a sys-
tematic approach in which components of both the ap-
plication and computer system are modelled and val-
idated. Although performance is probably one of the
most frequently used words in the vocabulary of com-
puting, paradoxically it is evident that there is a sub-
stantial “knowledge gap” between the software devel-
opment process and actual performance estimation and
optimisation. It is still often the case that programmers
and software system designers have insufficient knowl-
edge of the performance implications of their design
choices. Indeed, it is clear that systematic performance
engineering is not yet an integral part of the software
development process and that performance issues often
arise very late in the process. As a result it is not sur-
prising that performance problems are a frequent cause
of failure of large software development projects.
ISSN 1058-9244/02/$8.00 2002 – IOS Press. All rights reserved

4
T. Hey and J. Papay / Performance engineering, PSEs and the GRID
via the Grid include computational systems, data stor-
age and specialized facilities and are thus a richer set
of ‘informational utilities’ than the Web. In this con-
text it is helpful to consider the Grid as providing the
global middleware infrastructure that will enable the
establishment of transient “virtual organizations” on a
transparent and routine basis.
summarize the objectives and achievements of Park-
bench.
The main objectives of the ParkBench initiative
were:
1) To establish a comprehensive set of parallel
benchmarks that is generally accepted by both
users and vendors of parallel systems.
There will be many different types of applications
for the Grid and in many cases it is likely that Problem
Solving Environments (PSEs) generalized to the Grid
will play an important role. A PSE is an application-
specific environment that provides the user with sup-
port for all stages of the problem solving process –
from program design and development to compilation
and performance optimisation. Such an environment
also provides access to libraries and integrated toolsets,
as well as support for visualization and collaboration.
It may also implement some form of automated work-
flow management. Performance engineering – includ-
ing estimation, monitoring and measurement – will be
an integral component of any Grid PSE since reliable
models of performance prediction will be required for
any realistic Grid scheduling and accounting packages.
The paper is organized as follows. Section 2 re-
views several different approaches that have been at-
tempted for performance engineering and gives a short
account of some performance benchmarking, monitor-
ing and simulation techniques. Section 3 takes a brief
look at Problem Solving Environments in the context
of performance and presents a short account of two re-
cent UK-based PSE projects. The next section outlines
some of the challenges represented by the Grid for the
performance evaluation community and reviews some
EU experiments on Europe-wide meta-computing. Fi-
nally we offer some conclusions and challenges for the
performance engineering community.
2) To provide a focus for parallel benchmark activ-
ities and avoid unnecessary duplication of effort
and proliferation of benchmarks.
3) To set standards for benchmarking methodology
and result-reporting with establish a database/
repository for both benchmarks and the results.
4) To make parallel and sequential versions of the
benchmarks and results freely available in the
public domain.
As a result of this effort a benchmarksuite was devel-
oped which contains sequential and message passing
versions of the following codes:
– 5 Low Level Communication codes
– 5 Low Level Sequential codes
– 5 Parallel Linear Algebra Kernels
– 2 NAS Parallel Benchmark Kernels
– 3 NAS Compact Application codes
– ORNL Shallow Water Model Application code
Open-MP versions of some of these codes are now
available [18]. By providing three tiers of benchmark
complexity – low-level, kernel and compact applica-
tion – it was hoped that the performanceof real applica-
tions could be understood. The low-level codes provide
basic machine parameters, the kernels provideinforma-
tion about compute intensive algorithms and the com-
pact applications add the complexities of start-up, I/O
and so on. In the event, Parkbench was only partially
successful: lack of dedicated funding for such a bench-
mark evaluation programme prevented its full explo-
ration and realization. Nonetheless, there were signif-
icant achievements – a serious programming method-
ology was defined, parallel versions of the NAS Paral-
lel Benchmarks were made available in the public do-
main and a repository for results with a graphical in-
terface established. In addition, an electronic journal
for the rapid publication of performance results was
established [19] and this is now established as a special
section of the journal Concurrency and Computation:
Practice and Experience.
2. Performance engineering approaches
2.1. Benchmarks
The goal of benchmarking is to understand and pre-
dict the key parameters that determine the performance
of computing platforms and full scale applications.
There have been numerous benchmarking efforts un-
dertaken in the past but no general agreement on how
to conduct the measurements and how to interpret the
results. Examples of benchmarking efforts include the
Livermore Loops [38], the NAS Kernels [4] and the
Parkbench initiative [16]. It is worthwhile for us to
Two examples will illustrate the type of data that was
made available by these benchmarks. Figure 1 shows
the performance of the parallel LU kernel benchmark

T. Hey and J. Papay / Performance engineering, PSEs and the GRID
5
C-90 Aug.92
T3D Oct.94
10000
SP-1 Feb.94
SP-2 Aug.94
Paragon-OSF1.2 Jul.94
1000
100
1
10
100
1000
10000
Number of processors
Fig. 1. Performance of vector vs. distributed memory machines on LU kernel.
on distributed memory (DM) machines. The data is
ous functions and can use this information to identify
potential problem areas.
from 1994 and shows for perhaps the first time the
performance of a parallel DM system outperforming
the largest vector supercomputer of the time. Fig-
ure 2 shows results of the low-level communication
benchmark COMMS1 for the Intel Delta and the Intel
iPSC/860 systems.
The main concern of performance engineering is to
develop techniques which enable to predict the perfor-
mance and resource requirements of applications, in
this sense benchmarking has little to offer. The re-
sults of benchmarks are usually expressed by a single
number which is sufficient for comparing and rating
various computers, however this number provides lit-
tle information about the key parameters governing the
resource requirements of real applications.
Trace tools on the other hand, provide the user with
much more detailed information on the sequence of
events as they happen during program execution. Trace
files record time ordered events and can constitute a
large volume of data. The information recorded in a
trace can represent various levels of abstraction. In the
case of parallel platforms, the recorded traces for the
different nodes need to be collected, sorted according
to time stamps and merged into a global event trace.
Although trace tools provide more detailed information
about the parallel program execution than the profiling
tools, there can be a significant overhead for trace gen-
eration. Furthermore, the large volumes of trace data
generated can be overwhelming.
There are numerous commercial and academic trac-
ing and profiling tools available. Examples include
Apprentice [8], gprof, Vampir [41] and Paradyne [5].
Apprentice is a product of Cray Research which uses
source code instrumentationthroughcompiler switches
to provide statistics on the level of functions and basic
blocks. The advantage of source code instrumentation
is that the results of monitoring can be easily interpreted
in terms of programming language statements and give
very direct feedback to the programmer. A problem
with this approach is that the libraries cannot gener-
ally be monitored at the same level of detail since they
are usually only available in binary format. Unlike the
2.2. Performance measurements
Performance measurements are based on event pro-
filing and tracing. These techniques assume an event
model of program execution. During program execu-
tion, profiling tools accumulate summary data for sig-
nificant events such as function calls, cache misses,
communicationsetc. Typically, this approachhas a low
overhead since such profiling is usually implemented
by simple event counters. Using this method users can
obtain statistical information on the percentage of time
spent by their application program in performing vari-

6
T. Hey and J. Papay / Performance engineering, PSEs and the GRID
100
Delta
iPSC/860
10
1
0.1
0.01
1
10
100
1000
10000
100000
Message length, Byte
Fig. 2. Benchmarking of communication latency.
Cray product, Vampir is a commercial graphical event
trace browser from Pallas that is available on many dif-
ferent platforms. Vampir also provides visualization
and statistical analysis of trace files.
been extended to characterize communication perfor-
mance in parallel DM message-passing systems. In
this case the pipeline parameters captured the commu-
nication latency and asymptotic communication band-
width. Typically, the nodes of such systems are scalar
processors but it is also possible to use Hockney-style
pipeline parameters to provide a simple characteriza-
tion of the memory hierarchy of the node. These are
basic hardware parameters. It is also possible to char-
acterize the ‘computational intensity’ of an application
in terms of the ratio of the number of arithmetic opera-
tions performed per off-chip memory access. The par-
allel program is represented as an alternation of non-
overlapping computation and communication stages.
The application program is described in terms of the
number of scalar floating point operations, the amount
of data transferred and the number of messages. The
output of the model is assumed to be the sum of pro-
cessing and communication times. The model assumes
perfect load balance and the timing formula derived for
a single processor is used for the performance charac-
terisation of the whole parallel program. A weakness
of this model is that it is only valid for the performance
analysis of parallel algorithms with regular structures
and good load balancing.
Measurement and profiling tools have achieved a
high level of maturity, however the usage of these tools
for reliable performance estimation is still an open is-
sue. These tools can generate a large volume of de-
tailed data, but in order to gain some understanding
of the application’s runtime behaviour this data needs
to processed and interpreted. The interpretation is not
a simple and straightforward process, it requires user
intervention and considerable knowledge of the prob-
lem domain. An important aspect of these tools is the
level of intrusion which affects the accuracy of mea-
surements and can even alter the behaviour of the sys-
tem, this is often not mentioned or not quantified. The
amount of data that is collected during the measure-
ment is related to the level of intrusion, therefore it is
vital to find the right balance between the volume of
data and the acceptable level of intrusion.
2.3. Analytical models
Historically, Hockney’s n1/2 and r ‘pipeline’
∞
model provided a useful abstraction of Vector Super-
computer architecture [15]. This pipeline model has
In recent years, several other cost models have been
developed. These include the BSP (Bulk Synchronous

T. Hey and J. Papay / Performance engineering, PSEs and the GRID
7
Parallel) model [46,36,37] and the LogP model [9].
Analytical modeling is in fact complexity analysis,
Both these approaches attempt to get beyond the usual
(unrealistic) assumptions made in ‘classical’ PRAM
complexityanalysis. In particular an attempt is made to
take into account the limitations of real systems such as
the network bandwidth, and communication and syn-
chronisation overheads. These models aim to provide a
machine independent framework for parallel algorithm
design and performance prediction. The LogP model
characterises the parallel system by the following pa-
rameters:
which involves an abstract model of program execution
and cost models of computation and communication
operations. This technique attempts to combine the pa-
rameters of the application and the computer in order
to produce a mathematical expression for performance
estimation. This approach involves numerous assump-
tions which approximate the system and application’s
behaviour. Although these approximations make the
performance evaluation analytically tractable, they sig-
nificantly reduce the accuracy of predictions and limit
the applicability of analytical models to certain class of
applications or computer architectures.
– the upper bound on communication latency from
source to target (L),
– the overhead of send and receive (o),
– the minimum time interval between consecutive
transmissions or receptions (g),
2.4. Simulation
Simulation can provide very detailed information
about both the computer system and application pro-
gram. This information can be at various levels, in
terms of hardwarearchitecture rangingfrom simulation
of only the main components of the architecture right
down to simulations at the gate level, and on the ap-
plication side, from programming language statements
down to machine code. The simulation model charac-
terizes the system by a numberof state variables that are
updated as the simulation progresses. Simulation tech-
niques can be classified according to four basic types:
instruction driven, trace driven, execution driven and
event driven. Instruction driven simulation is based on
interpreting instructions of the target machine. This
technique gives high accuracy, achieved by step-by-
step simulation of each instruction, but requires long
simulation times. Full instruction level simulation is
too time consuming for practical use on real applica-
tions and complex machine architectures.
Trace driven simulation uses records of measure-
ments obtained from the real system or synthetic traces
generated by the trace generator. The trace is a se-
quence of user defined events generated by an instru-
mented program. This technique can require large
amounts of memory and processing time to produce re-
liable results. The DIMEMAS tool is an example of a
trace-driven performance prediction tool for message-
passing parallel programs [34]. This tool uses the Vam-
pir Trace File and scales the CPU time spent in each
block of code and the parameters of communication
events according to the target machine parameters.
Event driven simulation maintains a global queue of
events. The operation cycle consists of event fetch-
ing, the simulation step and update of the data structure
representing the simulated system [42]. The inputs of
– the number of processor/memory modules (P).
The model assumes asynchronous execution mech-
anism, finite network capacity and specifies the work
(W) between communications.
The BSP model, on the hand, has an equally sim-
plistic and unrealistic cost model. In fact, the Oxford
‘BSP model’ bears almost no resemblance to Valiant’s
actual BSP complexity analysis. In order to prove any
useful results, in his original BSP model Valiant re-
quires parallel slackness at the nodes to hide communi-
cation delays, two-phase random routing of messages
to avoid possible network congestion, and data hashed
randomly across the processors with a sufficiently ran-
dom class of hash functions to avoid memory ‘hot
spots’. All that is left of Valiant’s BSP analysis in the
Oxford BSP model is the programming methodology
of the bulk synchronous programming style! Both the
BSP and LogP models are similar in a sense that they
attempt to provide an abstraction of the performance
of the communication network and processing nodes
using a minimal number of ‘average’ performance pa-
rameters. Details of the network topology and memory
hierarchy are ignored. Such models represent, at best,
a “back-of-theenvelope” approach to performancepre-
diction. Nevertheless, it must be said that in some
cases, as the experiments on CM-5 showed, the LogP
model was able to provide a close match to actual per-
formance measurements [11]. As we will see below, a
similar ‘average’ speed analysis of the Livermore loops
ignoring any effects of the memory hierarchy gives
performance results that can be over 100% under- or
over-estimated. Other interesting approaches to per-
formance modelling include Carter’s Parallel Memory
Hierarchy Model [2] and the Manchester group’s Over-
head Analysis approach [40,44].

8
T. Hey and J. Papay / Performance engineering, PSEs and the GRID
The PERFORM system developed by Dunlop at
Southampton is an execution-driven simulation tool
that uses a novel ‘Fast Simulation Method’ that at-
tempted to improve the accuracy of prediction and over-
come some of the problems with a full simulation of the
memory hierarchy [10,14]. The model uses the “pro-
gram slicing” technique to isolate the control variables
and array indices of the source code, retaining suffi-
cient information to simulate data movement within the
memory hierarchy. The sliced program is then aug-
mented with calls to the PERFORM simulator which
models the effects of memory hierarchy cache mem-
ory, computation and message passing. Fast simulation
is achieved by providing feedback between the sim-
ulator and source and curtailing loop execution when
the cache behaviour of iterations are reliably estimated.
The main stages of the Fast Simulation Method used in
PERFORM tool are illustrated in Fig. 4.
An example of the accuracy of predictions that can
be achieved by the PERFORM tool is shown in Fig. 5
that compares actual and predicted performance on a
SPARC system. As can be seen, the predicted lower
bound provided by PERFORM captures the detailed
cache effects very accurately.
Simulation is a useful technique for the performance
evaluation of systems at the design stage of devel-
opment. Concerns with such simulation-based ap-
proaches are the level of detail of the simulation model,
accuracy and the simulation time. Simulation models
are usually large size programs, their development is
expensive and in the case of simulations of the archi-
tecture at the instruction level for example, require a
long run-time in order to provide meaningful results.
Fig. 3. Prediction error of static statement analysis.
event driven simulation models are probability distri-
butions of response times, request arrivals and delays.
The main disadvantages of probabilistic workloadmod-
els are that they do not directly represent the parame-
ters of specific application programs and the results of
the simulation require in-depth statistical processing in
order to determine the accuracy of the model.
Finally, execution-driven simulation models inter-
leave the execution of an application with the simu-
lation of the target system. The main advantages of
execution driven simulation are the speed and the use
of actual programs for the simulation of parallel archi-
tectures rather than using distribution or trace driven
workloads. That such an execution drivenapproach is a
feasible solution for the simulation of parallel systems
has been demonstratedby systems such as the Rice Par-
allel Processing Testbed (RPPT) [7] and the Wiscon-
sin Wind Tunnel [43]. The disadvantage of this tech-
nique is that it is more difficult to implement than the
trace driven approach due to the complex interactions
between the application program and the simulator.
A key lesson learned from the previous work is that
any simulation method must take account of memory
hierarchy for realistic performance estimation. Sim-
ple static statement analysis of the source code is well
known to be unpredictably unreliable as it is presented
by Fig. 3, which shows the difference between pre-
dicted and actual execution times of Livermore Fortran
kernels on SPARC 1 and SPARC 5 workstations.
3. Problem Solving Environments
A Problem Solving Environment (PSE) is an inte-
grated computing environment which incorporates all
stages of the problem solving process, such as problem
specification, computation, analysis and optimization.
The key issues associated with the architecture design
of PSEs are interoperability, modularity and reusabil-
ity of components. The problem of interoperability of
the different software packages stems from the differ-
ent (and often proprietary) file formats produced by the
variouscomponents. This is oftenthe case, for example
in mechanical engineeringwhere we frequently need to
implement data exchange between various CAD pack-
ages and CAE tools. Several recent papers [20,21]
highlight the need to adopt a universal file format based

T. Hey and J. Papay / Performance engineering, PSEs and the GRID
9
Input program
Architecture
parameters
Simulation Engine
“Sliced” Program
Augmented program
Program with
feedback
Executable
Fig. 4. Key stages of fast simulation method.
20
on XML that will simplify data exchange and structure
specification. Many of these pleas are from users with
real industrial applications but vendors of component
software packages see little commercial incentive to
make their software easily interoperable with packages
from other vendors. At present there is no generally ac-
cepted methodology for the specification, analysis and
design of modular reusable systems.
18
16
14
12
10
8
In recent years there has been a significant progress
in the development of middleware technologies that
provide support for system integration based on ob-
jects. Examplesof these technologiesinclude CORBA,
DCOM and, in the context of Web Services,the recently
proposed SOAP protocol. Although these technolo-
gies share many common features there is no univer-
sally accepted definition of objects and consequently
their claims to provide full interoperability within the
same system are somewhat questionable. At present,
CORBA is the dominant middleware technology in the
PSE world. Key advantages of CORBA are the exis-
tence of a single specification document and the par-
ticipation of more than 800 companies in the consor-
tium. Nevertheless, despite the existence of the IIOP
inter-ORB protocol, there is still a problem for applica-
tions that attempt to mix two or more of the large num-
ber of vendor specific implementations of CORBA. An
unwelcome result of this diversity is the problem of
interoperability between competing middleware prod-
6
Optimised benchmark results
Predicted lower bound execution time
4
2
0
0
1
2
3
4
Data size, MByte
Fig. 5. Predictive power of PERFORM tool.
ucts. It should also be emphasised that programming
using any of the CORBA implementations is not trivial
and the C++ syntax is rather complex. By contrast,
DCOM is Microsoft’s answer to CORBA and this has
the definite advantage that there is one specification,
implementation and one vendor. A limitation is that
DCOM runs only on Windows.

10
T. Hey and J. Papay / Performance engineering, PSEs and the GRID
Monitor
Reporter Task launcher
DB
Scheduler
Browser
Despatcher
Objects
WEB
server
Services
Machine boundary
ORBACUS
Web-pages
Fig. 6. A PSE architecture built from Cardiff/Southampton PSE components.
Arguably, two of the most successful PSEs are the
execution on remote/parallel platforms, help facilities
and application integration. The system is based on
CORBA and uses a parallel architecture(VIPar) for im-
age processing. This PSE has been further developed
in the CAESAR and JULIUS EU projects. A key prob-
lem for implementation of their ’Computational Sci-
ence Pipeline’ is the data transfer between the different
components.
The aim of Cardiff/Southampton PSE Project is
to leverage modern software technologies such as
CORBA, Java and XML and to develop the key mod-
ules which can be used for the rapid prototyping of
application specific PSE environments [47]. The main
components developed in this project are: a Visual
Component Composition Environment, an Intelligent
Resource Manager, based on the Southampton Intrepid
Scheduler [1] and a Software Component Repository.
The two applications targetedby this projectare Molec-
ular Dynamics and Photonic Crystal Structures simula-
tions. A PSE architecture incorporating the developed
components is presented in Fig. 6.
The system is based on the object-web concept where
the services are represented as network objects. The
problem is formulated as an XML request by the user
and the response, also in XML, is produced by the Web
server. The user interface is embedded in the browser
environment and enables visual programming by al-
lowing “drag-and-drop” of objects in a task-graph de-
sign area. The interaction with the user is implemented
as a sequence of Web pages. As a commercial middle-
ware ORB, the ORBACUS implementation of CORBA
commercial products Matlab and Mathematica. Both
these mature software environments have successfully
combined good usability with functionality. Perhaps,
strictly speaking, these products do not qualify as gen-
uine PSEs since they both provide rather generic envi-
ronments for a broad range of application areas rather
than an environment targeted at a single application.
Nevertheless, these products have a wide user base and
demonstrate what is possible in principle though nei-
ther have seen the development of a version for paral-
lel systems as a high commercial priority. Apart from
these examples, there are many ‘research’ PSEs either
in existence or under development in many universities
and research institutes around the world. Examples in-
clude GasTurbnLab from Purdue [22], BIOPSE from
Utah [23] and Autobench from Stuttgart [24]. Unfortu-
nately, it is not clear whether any of these PSE systems
are much used by real users.
As two examples of PSE projects, we shall
briefly describe two ongoing UK projects: one a
project with considerable direct industrial involve-
ment and the other a purely ‘academic’ project.
These are the Swansea/BAE Systems Project [49]
and the Cardiff/Southampton PSE project [47]. The
Swansea/BAE Systems project represents a complete
industrial environment for multi-disciplinary compu-
tational fluid dynamics, electro-magnetics and struc-
tural mechanics simulations. This PSE includes geom-
etry builder, mesh repair, unstructured grid generation,
grid quality analysis, post-processingand data analysis,

T. Hey and J. Papay / Performance engineering, PSEs and the GRID
11
was selected which is a mature product and provides
numerous services for naming, trading and interface
repository.
and simulation part of the engineering process. There
is a real need to incorporate the experimental validation
and testing part of the process. Thus a complete PSE
would offer support for the recording and analysis of
experimental as well as simulation data. Incorporation
of databases of experimental measurements and simu-
lation results will allow the development of data min-
ing and knowledge discovery components of the PSE.
PSEs have a long way to go to prove their worth in real
engineering environments!
PSEs often represent large scale meta-applications
which require massive computing resources. In this
case the role of performance engineering is to predict
the resource requirements of the application, to ensure
that there is sufficient computing capacity available and
the individualtasks are assigned to the most appropriate
computer.
The main task of the Monitor is to collect and store
information about machines and tasks running in the
system. The information about machines includes data
about the available resources such as memory, proces-
sors, disk and load. The task information is a represen-
tation of the resources used by the given task such as
size of occupied memory, communication and I/O traf-
fic, and disk volume used. The information collected
by the Monitor is stored in a database and used by the
Scheduler for task allocation and load balancing. The
interactions of Monitor with the other components of
the system are represented in Fig. 7. On each computer
there is an Object Server deployed which instantiates
the Reporter object. The Reporter registers with the
Name Server, which maintains a list of remote object
addresses. The Monitor at regular intervals queries the
Reporter objects and updates the Machine and Task
tables in the database.
4. Grids
The Scheduler provides task allocation to resources,
run-time forecast and dynamic load-balancing. The
scheduling is based on machine independent applica-
tion load models for CPU, memory size, I/O traffic
and disk volume. These algebraic expressions are in-
cluded in the description of each task and represent
the task resource requirements. The scheduling algo-
rithm performs the following steps for each task in the
task-graph:
4.1. The Grid as a new paradigm
The significant investments currently being made in
Grid research shows that the governments around the
world are taking the development of such infrastructure
middleware very seriously. With the recent announce-
ment of IBM’s support for the Grid, it is not unreason-
able to expect that the Grid will eventually become the
key middleware not only for science and engineering
but also for industry and commerce.
– check the availability of licenses, memory, disk
– generate list of candidate machines
– compute time components
In the US several agencies are funding major Grid
initiatives. Examples include:
– select minimum execution time
– include task-machine binding in the schedule
– NASA Information Power Grid [25]
– NSF Science Grid [26]
– NSF GriPhyN Project [27]
– DOE PPGrid [28]
– NSF NVO [29]
– NSF NEESGrid [30]
The three year project is nearing completion and a
full evaluation with performance measurements will be
available soon. Preliminary indications are that such a
component based approach can bring real advantages
in terms of software development and deployment. In
the final analysis, however, it will be the reaction of
users to such an environment that will provide the real
measures of success or failure!
On the whole, the lessons learnt from many of these
PSE experiments are not very encouraging. There are
major problems in automating the data flow between
CAD and CAE tools. Furthermore, there is little incen-
tive for vendors of legacy codes to make their product
interoperable with tools from other vendors. In addi-
tion, present PSEs focus almost entirely on the design
Most of these Grid Infrastructure and Application
Projects make use of the Globus Toolkit [12] as the
basic platform on which to provide Grid services. In
addition, the NSF funded GrADS project [6] identifies
many important research issues for Grid computing.
Europe has been also active in Grid R&D. In addition
to two initial EU Grid projects, DataGrid [17] and Eu-
roGrid [31], several new EU Grid-centred projects are
currently under negotiation. National governments in
the EU have also recognised the potential strategic im-
portance of the Grid. For example, under its new ‘e-

12
T. Hey and J. Papay / Performance engineering, PSEs and the GRID
Machine Table
Machine ID
Memory
Processor
Disk
Load
Object
Server
Performance Index
1
Name
Server
5
3
2
Reporter
Monitor
5
Task Table
4
Machine boundary
1. Object creation
Ta sk ID
2. Register with Name Server
3. Obtain object address
4. Query Reporter Objects
5. Update DB tables
Exe Time
Resources Used
Fig. 7. Monitor interactions.
Computing resources
Instruments
Complex problem
GRID
Data
People
Knowledge
Solution
Fig. 8. Grid vision.
Science Programme’, the Office of Science and Tech-
nology (OST) in the UK have allocated £120M for the
deployment of e-Science Grids spanning a wide range
of application areas and the development,with industry,
of the associated Grid middleware.
The Computation Grid is perhaps best envisaged as
an infrastructure that integrates computing resources,
data, knowledge, instruments and people. The con-
struction of such an environment will enable sharing
of computational resources, data repositories and fa-
cilities in a routine way as the Web now allows us to
share information. In cartoon form, this Grid vision is
depicted in Fig. 8.
There are many genuine Computer Science research
challenges to be overcome before we can realize this
vision. In the context of this paper, an obvious issue is
the need for realistic performanceestimation. Together
with mechanisms for monitoring and accounting, reli-
able performance estimation will allow the creation of
global marketplaces for Grid resources. As a starting
point for a discussion of Grid performance estimation,
it is worthwhile to review results from some recent

T. Hey and J. Papay / Performance engineering, PSEs and the GRID
13
Table 1
WAN experiment statistics
Partner
CPUs
Nproc
Availability
Access
Shot statistics
Successful
In PVC
Used
Failed
Total
Southampton (PAC)
Southampton University
Barcelona (UPC)
Stuttgart (RUS)
Madrid (CASA)
Bilbao (CEIT)
Torino (ItalDesign)
Torino (Blue Enginnering)
Grand Totals
15
10
16
12
15
12
11
11
102
15
10
16
12
15
12
11
11
102
15
9
14
6
16
9
14
8
5
1
0
1
0
15
0
2
6
25
150
40
275
104
184
98
63
61
975
151
40
276
104
199
98
65
67
1000
16
11
15
12
6
11
95
7
79
Total cpus installed
Total cpus defined in PVC
Total cpus available
102
102
95
Elapsed Execution Time: 4:39:16
Approx Single CPU Time: 250 hrs
Total cpus used in WAN
79
meta-computing projects.
4.2. Meta-computing experiments
Initially all machines listed above were specified as
comprising the Parallel Virtual Computer (PVC). Dur-
ing the actual run, however, some of them were either
not available or not used due to the pre-existing high
load on them. As can be seen, the experiment was very
successful and utilized nearly 100 processors and re-
sulted in a very significant improvement in exploration
of the design space.
The key module of a distributed computing environ-
ment is the scheduler. This must perform task allo-
cation to resources, run-time prediction and dynamic
load-balancing. Resource management decisions must
be made using platform independent application load
or resource demand models for CPU, memory size, I/O
traffic and disk volume. In the above mentioned meta-
computing projects, such models were developed by
benchmarking large industrial size codes such as NAS-
TRAN and Sysnoise. The process of obtaining load
models and using them by the scheduler is presented in
Fig. 9.
The accuracy of performance predictions obtained
by this technique is illustrated on the case study of a
static analysis with NASTRAN [39]. It is important
to stress that, as is commonly the case for commercial
codes, the source code was not available for instru-
mentation. A series of 2D and 3D test problems were
used for benchmarking on two different architectures –
a Distributed Memory IBM SP2 and a Shared Memory
SGI Power Challenge. During benchmarking, the run-
time, memory, disk traffic, disk space parameters were
measured. These measurements were then used for the
development of analytical performance models. At the
first stage a machine independent model of the appli-
cation is derived. Figure 10 illustrates that the derived
CPU-load model (number of floating point operations)
for SP2 and Power Challenge show a close match so
There have been numerous meta-computing projects
involving performance engineering. Here we shall
restrict our discussion to several EU-funded meta-
computing projects – Promenvir [35], Toolshed [32]
and HPC-VAO [33]. The main application focus of
these projects is engineering design optimisation by
simulations. In these simulations, the parameter space
of key design parameters is explored to find a set of
optimal values: simulations must be performed for ev-
ery new set of parameter values. The applications were
drawn from a variety of engineering domains including
satellite alignment analysis, surface accuracy analysis,
reflector deployment,crash analysis, vibro-acoustic op-
timization and CFD computation.
Optimisation by simulation is computationally ex-
pensive and the user needs these simulations to exe-
cute in the shortest possible time or within a set pe-
riod or resource cost. There is a clear economic incen-
tive to achieve efficient utilisation of the available re-
sources with as little intervention as possible. Several
of these meta-computing experiments utilized Europe-
wide computing resources. An illustration of the results
of the PROMENVIR project performed by connecting
up the resources of project partners across Europe is
given in Table 1. Table 1 contains statistics of the re-
source usage obtained by running a large scale Monte
Carlo simulation of satellite deployment. The program
and associated data were small enough that each simu-
lation could run on a single workstation or node: non-
trivial parallelism of the application code was not re-
quired. In this simulation a thousand ‘shot’ (parame-
ter set) computational experiment has been performed.

14
T. Hey and J. Papay / Performance engineering, PSEs and the GRID
Input files
Extraction
Applic. dep,
Machine indep
Task sizes
Application model
Scheduler
Loads:
Applic. and
Machine indep.
Flops, Disk and
Memory space,
I/O traffic
Task Selection
Machine
allocations
Ta sk
Execution
Machine model
Runtime, Utilisation
(CPU, Memory,
Disk, I/O b/w)
Capacity
Planning Display
Task Assignment
Fig. 9. Development and utilisation of platform independent load models.
10000.0
1000.0
100.0
10.0
100000.0
3D Chall
3D SP2
2D Chall
2D SP2
10000.0
1000.0
100.0
10.0
1.0
1.0
100
1000
10000
100000
100
1000
10000
100000
N
N
Fig. 10. Derived CPU-loads of static analysis in NASTRAN for 2D-3D problems for PowerChallenge and SP2.
that, as might be expected, the number of FPU oper-
ations in both cases is approximately the same. The
derived load models are used for the development of an
analytic expression that incorporates the key applica-
tion parameters such as degrees of freedom, front size,
number of extracted eigenvalues, etc. The accuracy of
the analytical model of CPU-load for the NASTRAN
static analysis code is illustrated in Fig. 11.
Similar models to the one presented in Fig. 11 have
been developed for I/O load, disk volume and memory
size. The advantage of this approach is that it provides
simple mathematical expressions that include the key
parameters governing the performance of the applica-
tion. The main drawback is that the development of
these models requires substantial benchmarking effort
and also some knowledge of the algorithm and applica-

T. Hey and J. Papay / Performance engineering, PSEs and the GRID
15
100000.0
10000.0
1000.0
100.0
(1) The national and international levels of invest-
ment in Grid computing make it clear that per-
formance estimation, modelling and measure-
ment on the Grid will assume an increasingly
important role in any future computational Grid
economy. Over the last decade, we have seen a
shift in the software industrie towards an object-
oriented, component-based software methodol-
ogy. At present, although the programming in-
terfaces and functionality of these components
are exposed, there is no methodology for ex-
pressing performance trade-offs in the software
developmentprocess. We thereforesuggest that,
in addition to specifying interfaces and func-
tions, software methodologies need to incor-
porate some form of “performance metadata”.
Such metadata would contain information about
the performance and resource requirements of
software constructs and components. Only with
the availability of such performance metadata
will the construction of truly intelligent sched-
ulers become possible. An internationally co-
ordinated effort to define a common format for
performance metadata seems long overdue.
(2) As we have seen, performance models range
from simple algebraic models that attempt to
identify a few key parameters, to complex sim-
ulation models with many parameters and in-
volving powerful mathematical techniques such
as queuing theory. However, the key to realis-
tic performance prediction lies in understanding
the interaction between the application and the
computer architecture. It is also important to
note that in a typical industrial application users
will not have access to the source code of a soft-
ware package or library routine. These require-
ments highlight the need for performance model
abstractions that are relatively simple and easy
to use yet are sufficiently accurate in their pre-
dictions to be useful as input to a scheduler or
intelligent agent. Reliable performance estima-
tion becomes even more relevant when we con-
sider payment for services in a computational
Grid economy. Users will require answers to
questions such as best value for money as well
as guarantees for specified turn-around times.
2D Chall
2D Model
3D Chall
3D Model
10.0
100
1000
10000
100000
N
Fig. 11. CPU-load model for static analysis in NASTRAN.
tion. Nevertheless, these experiments demonstrate the
level of accuracy that can be obtained in the industrially
relevant environment in which the source code of the
application package is unavailable.
4.3. Performance and the Grid
Performance estimation and forecasting will be vital
ingredients of the future Grid environment as has been
emphasised in several US projects such as GrADS [6],
AppLeS [45] and the Network Weather Service [48].
The GrADS Project envisages a “performance contrac-
t” framework as the basis for a dynamic negotiationpro-
cess between resource providers and consumers. The
Network Weather Service monitors the available per-
formance capacity of distributed resources, forecasts
future performance levels using statistical forecasting
models, reports monitoring data to client schedulers,
applications and visual interfaces. Such a service is
important for the Grid environment but needs to be
scalable, portable, and secure. There are many open
issues that need further investigation such as the bal-
ance between intrusiveness of sensors and accuracy of
measurements, fault diagnosis and adaptive sensors.
Finally, we have seen that there are many existing
tools for performance monitoring, some of which have
a non-negligible user community. When it comes to
performance estimation, there are few tools and few
users. Although the computer science community has
5. Concluding remarks
In this paper, various techniques used for perfor-
mance engineering on parallel and distributed systems
have been reviewed. We conclude with two remarks:

16
T. Hey and J. Papay / Performance engineering, PSEs and the GRID
been researching performance for a long time, we be-
lieve that such research needs to become more system-
atic and scientific. A common approach to performance
metadata together with a methodology that allows in-
dependent verification and validation of performance
results would be a good start.
[17] W. Hoschek, J. Jaen-Martinez, A. Samar, H. Stockinger and K.
Stockinger, Data Management in an International Data Grid
Project, in: Proc. 1st IEEE/ACM International Workshop on
Grid Computing, Springer Verlag Press, 2000.
[18] http://www.netlib.org/parkbench/.
[19] http://hpc-journals.ecs.soton.ac.uk/PEMCS/.
[20] http://www-106.ibm.com/developerworks/xml/.
[21] http://www.xml.com/.
[22] http://www.cs.purdue.edu/research/cse/gasturbn/.
[23] http://ampano.cs.utah.edu/software/.
References
[24] http://wwwvis.informatik.uni-
stuttgart.de/eng/research/proj/autobench/.
[25] http://www.ipg.nasa.gov/.
[26] http://www.ncsa.uiuc.edu/About/PACI/.
[27] http://www.griphyn.org/.
[28] http://www.ppdg.net/.
[1] N.K. Allsopp, T.P. Cooper and P. Ftakas, Porting Legacy Engi-
neering Applications onto Distributed NT Systems. Proceed-
ings of the 3rd USENIX Windows NT Symposium, Seattle,
Washington, USA, July 12–15, 1999.
[29] http://www.hoise.com/primeur/01/articles/monthly/AE-PR-
04-01-15.html.
[30] http://www.neesgrid.org/.
[2] B. Alpern, L. Carter, E. Feig and T. Selker, The Uniform Mem-
ory Hierarchy Model of Computation, Algorithmica 12(2/3)
(1994), 72–109.
[3] Babbage, Charles, Passages of the Life of a Philosopher, Long-
man, et alia, London, 1864.
[4] D. Bailey, J. Barton, T. Lasinski and H. Simon, (eds), The NAS
parallelbenchmarks. Technical Report RNR-91-02, NASA
Ames Research Center, Moffett Field, CA 94035, January
1991.
[31] http://www.eurogrid.org/.
[32] http://www.cse.clrc.ac.uk/ActivityResources/16.
[33] http://www.beasy.com/projects/hipsid/pac.html.
[34] J. Labarta, S. Girona and T. Cortes, Analyzing scheduling
policies using Dimemas, Parallel Computing 23(1–2) (1997),
23–34.
[35] J. Marczyk, Principles of Simulation-Based Computer-Aided
Engineering FIM Publications, Barcelona, 1999, pp. 174.
[36] W.F. McColl, BPS Programming, in Proc. DIMACS Work-
shop on Specification of Parallel Algorithms, Princeton, 9–11
May 1994.
[5] B.P. Miller, M.D. Callaghan, J.M. Cargille, J.K.
Hollingsworth, R. Bruce Irvin, K.L. Karavanic, K. Kun-
chithapadam and T. Newhall, The Paradyn Parallel Perfor-
mance Measurement Tools, IEEE Computer 28(11) (Novem-
ber 1995), 37–46.
[37] W.F. McColl, Truly, madly, deeply parallel, New Scientist,
February 1996, pp. 36–40.
[38] F.H. McMahon, The Livermore Fortran kernels test of the nu-
merical performance range, Performance Evaluation of Su-
percomputers (1988), 143–186.
[6] F. Berman, A. Chien, K. Cooper, J. Dongarra, I. Foster,
D. Gannon, L. Johnsson, K. Kennedy, C. Kesselman, D.
Reed, L. Torczon and R. Wolski, The GrADS Project: Soft-
ware Support for High-Level Grid Application Development,
http://www.hipersoft.rice.edu/grads/publications/tr/grads
project.pdf, February 15, 2000.
[7] R.G. Covington, S. Dwarkadas, J.R. Jump, J.B. Sinclair and S.
Madala, Efficient Simulation of Parallel Computer Systems,
International Journal in Computer Simulation 1 (1991), 31–
58.
[39] MSC/NASTRAN Quick Reference Guide, Version 70, The
MacNeal-Schwendler Corporation, 1997.
[40] N. Mukherjee, G. Riley and J. Gurd, FINESSE: A Prototype
Feedba-guided Performance Enhancement System, Proceed-
ings of 8th Euromicro Workshop on Parallel and Distributed
Processing, Rhodes, Greece, IEEE Computer Society Press,
January 19–21, 2000, pp. 101–109.
[8] CRAY Research, Introducing the MPP Apprentice Tool,
CRAY Manual IN-2511, 1994.
[41] W.E. Nagel, A. Arnold, M. Weber, H.-C. Hoppe and K.
Solchenbach, VAMPIR: Visualization and Analysis of MPI
Resources, Supercomputer 63 12(1) (1996), 69–80.
[42] D. Pease et al., PAWS: A Performance Evaluation Tool for
Parallel Computing Systems, IEEE Computer (January 1991),
18–29.
[43] S.K. Reinhardt, M.D. Hill, J.R. Larus, A.R. Lebeck, J.C. Lewis
and D.A. Wood, The Wisconsin Wind Tunnel: Virtual Proto-
typing of Parallel Computers, in Proceedings of the 1993 ACM
SIGMETRICS Conference on Measurements & Modeling of
Computer Systems, May 1993, pp. 48–60.
[9] D. Culler, R. Karp and D. Patterson, LogP: Towards a realis-
tic Model for Parallel Computation, ACM SIGPLAN Notices
28(7) (1993), 1–12.
[10] A. Dunlop, Southampton Ph.D. thesis, 1997.
[11] A.C. Dusseau, D.E. Culler, K.E. Schauser and R. Martin,
Fast Parallel Sorting under LogP: Experience with the CM-
5, IEEE Transactions on Parallel and Distributed Systems
(August 1996).
[12] I. Foster and C. Kesselman, Globus: A Metacomputing In-
frastructure Toolkit, International Journal of Supercomputer
Applications 11(2) (1997), 115–128.
[44] G. Riley, M. Bull and J. Gurd, Performance Improvement
through Overhead Analysis: A Case Study in Molecular Dy-
namics, Proceedings of the 1997 International Conference on
Supercomputing, ACM Press, 1997.
[45] N. Spring and R. Wolski, Application Level Scheduling of
Gene Sequence Comparison on Metacomputers, Proceedings
of the 12th ACM International Conference on Supercomput-
ing, Melbourne, Australia, July 1998.
[13] I. Foster and C. Kesselman, (eds), The Grid: Blueprint for a
New Computing Infrastructure, Morgan Kaufmann, 1999.
[14] T. Hey, A. Dunlop and E. Hernaˆndez, Realistic Parallel Per-
formance Estimation, Parallel Computing 23 (1997), 5–21.
[15] R.W. Hockney, Performance parameters and benchmarking of
supercomputers, in: Computer Benchmarks, J.J. Dongarra and
W. Gentzsch, eds, Elsevier Science Publishers, Holland, 1993,
pp. 41–63.
[46] L.G. Valiant, A bridging model for parallel computation, Com-
munications of the ACM 33(8) (1990), 103–111.
[16] R.W. Hockney and M. Berry, PARKBENCH Report: Public
international benchmarks for parallel computing, Scientific
Programming 3(2) (1994), 101–146.

T. Hey and J. Papay / Performance engineering, PSEs and the GRID
17
[47] D.W. Walker, M. Li, O.F. Rana, M.S. Shields and Y. Huang,
The Software Architecture of a Distributed Problem-Solving
Environment Concurrency: Practice and Experience 12(15)
(2001), 1455–1480.
[48] R. Wolski, Forecasting Network Performance to Support Dy-
namic Scheduling Using the Network Weather Service. In
Proc. 6th IEEE Symp. on High Performance Distributed Com-
puting, Portland, Oregon, 1997.
[49] Y. Zheng, N.P. Weatherill, E.A. Turner-Smith, M.I. Sotirakos,
M.J. Marchant and O. Hassan, Visual Steering of Grid Gener-
ation in a Parallel Simulation User Environment, Chapter 27
in Enabling Technologies for Computational Science: Frame-
works, Middleware and Environments, The Kluwer Interna-
tional Series in Engineering and Computer Science, (vol. 548),
Kluwer Academic Publishers, Boston, 2000, pp. 339–349.

Journal of
Industrial Engineering
Advances in
Multimedia
Applied
Computational
Intelligence and Soft
Computing
International Journal of
Distributed
The Scientific
World Journal
Sensor Networks
Hindawi Publishing Corporation
Hindawi Publishing Corporation
Hindawi Publishing Corporation
Hindawi Publishing Corporation
http://www.hindawi.com
Hindawi Publishing Corporation
http://www.hindawi.com
http://www.hindawi.com
Volume 2014
http://www.hindawi.com
Volume 2014
Volume 2014
Volume 2014
http://www.hindawi.com
Volume 2014
AFduvanzcezs iyn
Systems
Modelling &
Simulation
in Engineering
Hindawi Publishing Corporation
http://www.hindawi.com
Hindawi Publishing Corporation
http://www.hindawi.com
Volume 2014
Volume 2014
Submit your manuscripts at
http://www.hindawi.com
Journal of
Computer Networks
and Communications
ꢀAdvancesꢀinꢀ
Artificial
Intelligence
Hindawi Publishing Corporation
http://www.hindawi.com
HindawiꢀPublishingꢀCorporation
http://www.hindawi.com
Volume 2014
Volumeꢀ2014
International Journal of
Advances in
Biomedical Imaging
Artificial
Neural Systems
International Journal of
Computer Games
Technology
Advances in
Advances in
Computer Engineering
Software Engineering
Hindawi Publishing Corporation
http://www.hindawi.com
Hindawi Publishing Corporation
http://www.hindawi.com
Hindawi Publishing Corporation
http://www.hindawi.com
Hindawi Publishing Corporation
Hindawi Publishing Corporation
Volume 2014
Volume 2014
Volume 2014
http://www.hindawi.com
Volume 2014
http://www.hindawi.com
Volume 2014
International Journal of
Reconfigurable
Computing
Computational
Intelligence and
Neuroscience
Advances in
Journal of
Journal of
Human-Computer
Electrical and Computer
Robotics
Interaction
Engineering
Hindawi Publishing Corporation
http://www.hindawi.com
Hindawi Publishing Corporation
http://www.hindawi.com
Hindawi Publishing Corporation
http://www.hindawi.com
Hindawi Publishing Corporation
http://www.hindawi.com
Hindawi Publishing Corporation
Volume 2014
Volume 2014
Volume 2014
Volume 2014
http://www.hindawi.com
Volume 2014