Full text of DOI:10.1155/2000/481921

127
The MicroGrid: A scientific tool for
modeling Computational Grids
H.J. Song, X. Liu, D. Jakobsen, R. Bhagwan,
X. Zhang∗, K. Taura∗∗ and A. Chien
Department of Computer Science and Engineering,
University of California, San Diego, La Jolla, CA
92093, USA
erogeneous environments, significant challenges in the
design of middleware software, application software,
and even Grid hardware configuration remain. For in-
stance, Internet/Gridenvironmentsexhibitextreme het-
erogeneity of configuration, performance, and reliabil-
ity. Consequently, software must be flexible and adap-
tive to achieve either robustness or even occasionally
good performance. To put it directly, we have no sys-
tematic way to study the dynamics of such software
to evaluate its effectiveness, robustness, or impact on
Grid system stability. We believe that one critical chal-
lenge facing the computer systems community is to un-
derstand the decidedly non-linear dynamics of Inter-
net/Grid scale systems. The current practice is to per-
form actual test-bed experiments (at moderate scale) or
simplistic simulations that are not validated.
At UCSD, we are pursuing a research agenda
which explores how to simulate and model large-scale
Grid structures1 – applications, services, and resource
infrastructure2. Our objective is to develop a set of
simulation tools called the MicroGrid that enable sys-
tematic design and evaluation of middleware, applica-
tions, and networkservices for the ComputationalGrid.
These tools will provide an environment for scientific
and repeatable experimentation. It is our hope that the
MicroGrid will catalyze the development of experimen-
tal methodologies to robustly extrapolate grid simula-
tion results and rational grid design and management.
To achieve these goals, at a minimum, Grid simulation
tools must supportrealistic grid software environments,
modeling of a wide variety of resources, and scalable
performance.
E-mail: mgrid@csag.ucsd.edu
The complexity and dynamic nature of the Internet (and the
emerging Computational Grid) demand that middleware and
applications adapt to the changes in configuration and avail-
ability of resources. However, to the best of our knowledge
there are no simulation tools which support systematic explo-
ration of dynamic Grid software (or Grid resource) behavior.
We describe our vision and initial efforts to build tools
to meet these needs. Our MicroGrid simulation tools en-
able Globus applications to be run in arbitrary virtual grid
resource environments, enabling broad experimentation. We
describe the design of these tools, and their validation on
micro-benchmarks, the NAS parallel benchmarks, and an en-
tire Grid application. These validation experiments show that
the MicroGrid can match actual experiments within a few
percent (2% to 4%).
1. Introduction
The explosive growth of the Internet and its use in
computing, communication, and commerce have made
it an integral and critical infrastructure of our soci-
ety. The Internet’s increasing capability has created
excitement about a vision for the next-generation In-
ternet which enables seamless integration of comput-
ing, storage, and communication into the Computa-
tional Grid. While demonstrations on large scale test-
beds using software infrastructures such as Globus [6]
and Legion [7] highlight the potential of computational
grids to enable large-scale resource poolingand sharing
(compute, communicate, storage, information) in het-
We have designed an initial set of MicroGrid tools
which allow researchers to run Grid applications on
virtual Grid resources, allowing the study of complex
dynamic behavior. In this paper, we describe our initial
1The ultimate simulation goals are networks of 10 to 100 million
entities.
2The development of these tools is part of the NSF funded Grid
Application Development Software (GrADS) project, led by Ken
Kennedy at Rice University (http://hipersoft.cs.rice.edu/grads/).
∗Corresponding author. E-mail: xzhang@cs.ucsd.edu.
∗∗Also affiliated to University of Tokyo, Japan.
Scientific Programming 8 (2000) 127–141
ISSN 1058-9244 / $8.00
Dallas, Texas, USA.
2000, IEEE. Reprinted with permission from Proceedings of IEEE Supercomputing 2000, 4–10 November 2000,

128
H.J. Song / The MicroGrid: A scientific tool for modeling Computational Grids
design, implementation, and validation of the Micro-
Grid tools. First, these tools enable the use of Globus
applications without change by virtualizing the execu-
tion environment, providing the illusion of a virtual
Grid. Thus, experimentation with a wide variety of
existing Grid applications is feasible. Second, these
tools manage heterogeneous models in the virtual grid,
using a global virtual time model to preserve simu-
lation accuracy. Third, the MicroGrid provides basic
resource simulation models for computing, memory,
and networking. We describe the implementation of
these elements, and validate them at the following three
levels.
2. MicroGrid architecture
2.1. Overview
The basic functionality of the MicroGrid is to allow
Grid experimenters to simulate their applications on a
virtual Grid environment. The simulation tool should
be made flexible to allow accurate experimentation on
heterogeneous physical resources, as shown in Fig. 1.
Our MicroGrid implementation supports Grid applica-
tions which use the Globus Grid middleware infrastruc-
ture.
The basic architecture of the MicroGrid is shown in
Fig. 2, and each element in the figure corresponds to one
of the major challenges in constructing a high-fidelity
virtual Grid. These challenges are as follows:
– Micro-benchmarksIndividualresourcemodeltests
which show these models to be accurate.
– Parallel benchmarks Use of the NAS Parallel
Benchmark suite which shows the combined ac-
curacy of the MicroGrid for modeling system and
application performance.
– An Application A complex application program
(CACTUS PDE solver) which further validates the
utility and fidelity of the MicroGrid models.
Virtualization The application must perceive only the
virtual Grid resources (host names, networks), in-
dependentof the physicalresources being utilized.
Global Coordination To provide a coherent global
simulation of potentially different numbers of
varying virtual resources on heterogeneous phys-
ical resources, global coordination of simulation
progress is required.
Resource Simulation Eachvirtualresource(host,cpu,
network, disk, etc.) must be modeled accurately
as an element of the overall simulation.
Experiments with MicroGrids on the NPB Class A
data sets ultimately match within 2 to 4% while main-
taining high execution efficiency. In addition, we per-
form an internal validation showing that the execution
at each time step within a MicroGrid simulation closely
follows that in an actual execution, varying only from
3 to 8%. This internal validation is achieved using
the Autopilot [17] tools, and running them within the
MicroGrid environment. Finally, experiments with an
entire application (CACTUS), match closely as well,
within 5 to 7%.
These validations form an important first step in
building a set of tools which can support large scale
experimentation with software for the Computational
Grid. However, while we are pleased with our initial
progress, significant challenges remain. To achieve the
larger vision of Grid simulation, significant advances
in scalability, precision of modeling and network traffic
modeling must be achieved.
Our approach towards overcoming these challenges
is discussed in the following subsections.
2.2. Virtualization
To providethe illusion of a virtual Grid environment,
the MicroGrid intercepts all direct uses of resources
or information services made by the application. In
particular, it is necessary to mediate over all opera-
tions which identify resources by name either to use or
retrieve information about them.
2.2.1. Virtualizing resources
In general, the MicroGrid needs to virtualize pro-
cessing, memory, networks, disks, and any other re-
sources being used in the system. However, since the
operating system in modern computer systems effec-
tively virtualizes each of these resources – providing
unique namespaces and seamless sharing – the major
challenge is to virtualize host identity. In the Micro-
Grid, each virtual host is mapped to a physical machine
using a mapping table from virtual IP address to physi-
cal IP address. All relevant library calls are intercepted
and mapped from virtual to physical space using this
table. These library calls include:
The remainder of this paper is organized as follows.
Section 2 describes the elements of the MicroGrid and
their implementation in our prototype. Experiments
and validation of our basic system can be found in Sec-
tion 3. Section 4 discusses related work, and Section 5
summarizes our results and points out new directions.

H.J. Song / The MicroGrid: A scientific tool for modeling Computational Grids
129
Grid Software: Applications and Services
Researcher’s
Displays
Virtual Grid
Researcher’s
Controls
MicroGrid
Software
Simulation
Computational Power
LAN Workgroup
Scalable Cluster
Fig. 1. Illustration of a user experimenting with a MicroGrid system to explore a range of virtual resources and executing on a range of physical
resources.
Virtual Grid Interface
Virtual Grid Interface
Local Resources
Virtual Grid Interface
Virtual Grid Interface
Local Resource
Networks
Virtual Grid Resources
Virtual Grid Interface
Local Resource Simulation
Fig. 2. MicroGrid simulator diagram: the local resource simulations provide a virtual Grid resource environment and the network simulator
captures the interaction between local virtualized resources.
– gethostname()
through the virtual Grid resource’s gatekeeper. We can
run any socket-based application on the virtual Grid as
the MicroGrid completely virtualizes the socket inter-
face.
– bind, send, receive (e.g. socket libraries)
– process creation3
By intercepting these calls, a program can run trans-
parently on a virtual host whose hostname and IP ad-
dress are virtual. The program can only communi-
cate with processes running on other virtual Grid hosts.
Many other program actions which utilize resources
(such as memory allocation) only name hosts implic-
itly, and thus do not need to be changed. A user of
the MicroGrid will typically be logged in directly on a
physical host and submit jobs to a virtual Grid. Thus,
the job submission must cross from the physical re-
sources domain into the virtual resources domain. For
the Globus middleware, our current solution is to run
all gatekeeper, jobmanager and client processes on vir-
tual hosts. Thus jobs are submitted to virtual servers
2.2.2. Virtualizing information services
Information services are critical for resource discov-
ery and intelligent use of resources in Computational
Grids. Since the MicroGrid currently supports Globus,
this problem amounts to virtualization of the Globus
Grid Information Service (GIS).
Desirable attributes of a virtualized GIS include:
– Compatibility: virtualized information should be
used as before by all programs
– Identification and Grouping: easy identification
and organization of virtual Grid entries should be
provided
– Use of identical information servers: there should
be no incompatible change in the entries
3We currently capture processes created through the Globus re-
source management mechanisms, but not those created via other
mechanisms.
Our approach achieves all of these attributes by ex-
tending the standard GIS LDAP records with fields

130
H.J. Song / The MicroGrid: A scientific tool for modeling Computational Grids
containing virtualization-specific information. Specif-
ically, we extend records for compute and network re-
sources. Extension by addition ensures subtype com-
patibility of the extended records (a la Pascal, Modula-
3, or C++). The added fields are designed to support
easy identification and grouping of the virtual Grid en-
tries (there may be information on many virtual Grids
in a single GIS server). Finally, all of these records
are placed in the existing GIS servers — no additional
servers or daemons are needed. Figure 3 shows an ex-
ample of the extensions to the basic host and network
GIS records:
rate of simulation over all available resources ensures
accurate performance analysis of the processes run on
the MicroGrid.
Virtualizing Time Many Grid programs monitor their
progress by calling system routines for time (e.g. get-
timeofday()), and if their correct behavior is to be main-
tained, the illusion of virtual time must be provided.
Using the chosen simulation rate,we have implemented
a virtualization library which returns appropriately ad-
justed times to the system routines to provide the illu-
sion of a virtual machine at full speed.
2.3. Global coordination
2.4. Resource simulation
Achieving a balanced simulation across distributed
resources requires global coordination. Based on the
desired virtual resources and physical resources em-
ployed (CPU capacity and networkbandwidth/latency),
the virtual time module can determine the maximum
feasible simulation rate.
The method for calculating the maximum feasible
simulation rate is explained here, starting with a few
definitions. The simulation rate (SR) is defined for
each resource type r as the value
Within the MicroGrid simulation, each of the Grid
resources must also be simulated accurately, provide
real-time performance feedback to the simulation, and
be simulated at the rate at which virtual time is allowed
to progress. While ultimately many resources may be
critical, we initially focus on two resource types —
computing and communication.
SRr = (specification of physical resource r)/
(Σ specification of the virtual resources
of type r mapped to this physical
resource)
2.4.1. Computing resource simulation
For Grid applications, many of which are compute
intensive, accurate modeling of CPU speed is critical.
Therefore, our first simulation module focuses on sim-
ulating the execution speed of various processors. For
each virtual host, the speed of its processoris stored as a
GIS attribute on the host record (see Fig. 3). Given the
virtual host CPU speed, the physical processor speed
can be used to calculate the simulation rate, which in
this case yields an actual CPU fraction which should be
allocated for this Grid simulation. This CPU fraction
is then divided across each process on a virtual host.
The resulting fractions are then enforced by the local
MicroGrid CPU scheduler.
The local MicroGrid CPU scheduler is a scheduler
daemon which uses signals [8] to allocate the local
physical CPU capacity to local MicroGrid tasks. The
current scheduler uses a round-robin algorithm (see
Fig. 4), and a quantum of 10 milliseconds as supported
by the Linux timesharing scheduler.
The specifications are parameters such as CPU
speed, network bandwidth, reciprocal of propagation
delay, etc.4 The significance of the SR can be explained
in the following way. Suppose a process running on the
physical resource takes x time to complete. Then, sim-
plistically, it can be said that the same process would
take x ∗ SR time to complete on the virtual resource.
The maximum value of SR over all the resources
represents the fastest rate at which the simulation can
be run in a functionally correct manner, and is there-
fore termed the maximum feasible simulation rate. No
resource should be allowed to work “faster” than this
rate though it can since this would lead to incorrect
results. This global coordination mechanism for the
A challenge for this scheduler is to achieve exactly
the desired simulation rate, as against many multimedia
systems, where the objective is to achieve a minimum
CPU fraction for interactive response.
4The parameters need to be expressed such that a higher value
signifiesfasterexecution. For example, if the CPUspeedof a physical
resource is 100 MIPS and the CPU speed of the virtual resource is
200 MIPS, the SR is 0.5.

H.J. Song / The MicroGrid: A scientific tool for modeling Computational Grids
131
Fig. 3. Example virtual GIS host and GIS network records.
Fig. 4. The local CPU scheduler algorithm.
2.4.2. Network simulation
it into the MicroGrid. Due to its better scalability, we
are currently exploring the use of DaSSF for our next
MicroGrid.
In Grid applications, network behavioris often a crit-
ical element of performance [13,22]. As such, the ba-
sic requirements for network simulation include pre-
cise modeling of arbitrary network structure and online
simulation (conveyanceof the communicationtraffic to
the right destination with the right delay). Ultimately,
scalability to the extreme (tens of millions of network
elements) is an important requirement. These require-
ments for network simulation provide one of the key
challenges for the ultimate viability of the MicroGrid
for large-scale modeling.
We have explored VINT/NSE, PDNS, and DaSSF
and no existingnetwork simulatorfully satisfies the Mi-
croGrid’s requirements. For our initial MicroGrid pro-
totype, we have chosen to modify the real-time version
VINT/NSE (an online simulator), and have integrated
The VINT/NSE simulation system allows definition
of an arbitrary network configuration. Our MicroGrid
system reads desired network configuration files and
inputs a network configuration for NSE according to
the virtual network information in the GIS. The net-
work simulator (NSE) is then connected to our virtual
communicationinfrastructure, and thereby mediates all
communication. Of course, NSE delivers the commu-
nications to each destination according to the network
topology at the expected time.
While this system works well, as shown in Section 3,
VINT/NSE still presents several significant challenges
for use in a MicroGrid system:

132
H.J. Song / The MicroGrid: A scientific tool for modeling Computational Grids
– NSE is a best-effort simulator, delivering the mes-
3.2.1. Memory capacity modeling
The following test is performed with the goal of
verifying the scheduler’s ability to enforce the memory
limitation as specified when assigning a process to a
virtual machine.
sages in close to real-time. If it cannot achieve
real-time, it simply gives a warning and continues
at the best it can.
– NSE requires an unpredictable amount of com-
putational effort to simulate a network and traf-
fic pattern. As a result, determining a safe global
simulation rate is difficult.
– NSE performs detailed simulation, with high over-
head.
– NSE is a sequential simulator, and therefore does
not scale up to large simulations well.
A MicroGrid process is initialized on the scheduler
and a process, and that process which constantly allo-
cates memory until it generates an out of memory er-
ror. The test is repeated with various memory limits for
the process and the maximum amount of memory suc-
cessfully allocated is logged for each repeat of the test.
Figure 5 shows the result of the tests where memory
limitations from 1 KB to 1 MB are specified.
As shown in Fig. 5, there is a clear linear correlation
between the memory limit and the amount of memory
accessible by the process. In each case, the process
could allocate about 1KB less then the specified mem-
ory limitation. This is due to memory overhead for the
process.
3. Experiments and validation
We are executing a series of experiments designed
primarily to validate the MicroGrid simulation tools.
These experiments can be categorized as follows:
3.2.2. Processor speed modeling
1. Micro-benchmarksofMicroGridsimulationmod-
This test focuses on how precisely the MicroGrid
processor scheduler maintains the processing model in
the presence of CPU competition on the physical ma-
chine. This test is done in several steps: For each step
a virtual machine of a given speed is created on the
scheduler, a process performing a fixed computation is
scheduled on that virtual machine, and after the process
completes, the virtual machine is deleted. This test is
repeated with various speeds for the virtual machines
and with competition in form of CPU intensive and
IO intensive processes running in parallel with the Mi-
croGrid scheduler. The process scheduled on the vir-
tual machine is a reference process performing a fixed
CPU-intensive computation (i.e. the process is never
blocked) work and its execution speed running as the
only process on the physical CPU.
els
2. Benchmark MPI Programs (NAS Parallel Bench-
marks)
3. Application programs (CACTUS)
These experiments test successively large parts of
the MicroGrid simulation, and with successively more
complex application behavior. With a solid validation
of the tools, the range of interesting experiments is
virtually unbounded.
3.1. Experimental environment and methodology
All of the experiments were run on a cluster of
533 MHz 21164 Compaq Alpha machines with 1 GB
main memory each, and connected by a 100 Mbit Eth-
ernet. The software used is Globus 1.1 run on top of
the MicroGrid layer. For each type of benchmark and
experiment, we report different metrics.
The three versions of the processor microbenchmark
are:
– No Competition: This is used as a reference. Dur-
ing this test the scheduler is running as the only
process on the CPU.
– CPU Competition: In parallel with the scheduler
daemon, a computationally intense process is ex-
ecuting. The computationally-intensive process
does floating-point divisions continuously.
– IO Competition: In parallel with the scheduler
daemon, an IO intensive process is executing. The
IO intensive process used during this test continu-
ously flushes a 1MB buffer to disk.
3.2. Micro-benchmarks
We have performed extensive compute node simu-
lation and network simulation experiments. We use
some micro-benchmarksto validate the accuracy of the
models.

H.J. Song / The MicroGrid: A scientific tool for modeling Computational Grids
1000
133
Ma
xi
mu
m
All
oc
ate
d
me
mo
ry
900
800
700
600
500
400
300
200
100
0
0
200
400
600
800
1000
Specified memory limit [kb]
Fig. 5. Memory microbenchmark.
100
90
80
70
60
50
40
30
20
10
10
20
30
40
50
60
70
80
90
100
Specified CPU fraction [%]
No Competition
IO Competition
CPU Competition
Fig. 6. Processor microbenchmark.
From Fig. 6 it is seen that the MicroGrid scheduler
is able to schedule the reference process according to
the specified speed for the virtual machine across a
wide range of speeds up to 95% of the total CPU ca-
pacity. Both the operating system and the scheduler’s
CPU usage form this upper boundary. For the IO com-
petition and CPU competition tests, the results show
that above a specified CPU speed of 40%, the virtual
machine does not deliver the specified CPU fraction.
This inadequacy is caused by the characteristics of the
time-sharing scheduling policy in Linux.
Figure 7 shows that with no competition, when the
MicroGrid scheduler is running as the only process on
the CPU, the CPU time allocated to a process is almost
the same as the virtual time specified by the user. This
test also shows that computational intensive processes
running in parallel withtheMicroGridschedulerdid not
have any influence on the performanceof the scheduler.
Extreme IO competition did affect resulting quantum
size, but not severely.
The followingtest is performedwith the goal of char-
acterizing the stability of the scheduled quantum size.
We modified the MicroGrid scheduler daemon to col-
lect performance data, logging the time slice size as-
signed to each process. The test consists of three ses-
sions, producing about 9000 samples, correspondingto
about 90 seconds of test. The process that actually runs
on the MicroGrid during this test is an inactive process
that constantly sleeps.
3.2.3. NSE network modeling
In this experiment we use MPI bandwidth and la-
tency benchmarks to test the accuracy of the simulated
network performance. These benchmarks run on two
virtual nodes connected by virtual networks (a 100 Mb
Ethernet). The results are compared with outputs from
the real system. We can see that the simulated network
has the similar characteristics with the real system.

134
H.J. Song / The MicroGrid: A scientific tool for modeling Computational Grids
Normalized Time Slice Distributing
0.7
0.6
0.5
0.4
0.3
0.2
0.1
0
:
5
9
0
4
9
6
8
15
94
0.
65
99
0.
0
0
15
8
9
9
015
065
1.
1
0.
1.
0.
0.
0.
1.
1.
1.
time slice
NO-Competition: Mean=1.000, Dev=0.002
CPU-Competition: Mean=1.01, Dev=0.015
IO_Competition:Mean=0.978,Dev=0.027
Fig. 7. Distribution of quanta sizes, normalized to a mean of unity.
Bandwidth
Late ncy
80
35000
30000
25000
20000
15000
10000
5000
70
60
50
40
30
20
10
0
Ethernet
Mgrid
Ethernet
Mgr i d
0
4
6
16
64
56
24
4
6
4
6
53
2
0
09
4
384 536
44
21
16
64
56
2
1
5
6
024
2144
26
09
4
16
1
1638
65
26
message size (byte)
m essage siz e (byte)
Fig. 8. NSE network modeling.
3.3. Benchmarks
A bar graph comparing the actual run times with
those simulated on the MicroGrid is shown in Fig. 10.
As shown in the figure, the MicroGrid matches IS, LU,
and MG within 2%. For EP and BT, the match is
slightly worse, but still quite good, within 4%. Be-
cause the simulationtracks the performancedifferences
across configurations fairly well, we consider the Mi-
croGrid validated for these applications.
In searching to explain the slight mismatches in per-
formance, microscopic analysis of these programs be-
havior revealed that the MicroGrid’s current 10 mil-
lisecond scheduling quantum was introducing model-
ing error, when processes are synchronized at shorter
intervals.
We used the NPB (NAS Parallel Benchmarks) 2.3
applications [19] to perform a more extensive valida-
tion of the MicroGrid tools, encompassing not only
the compute node and network models, but also their
integration into a unified simulation.
3.4. Total run time
3.4.1. Machine configurations
Our first goal was to validate the MicroGrid sim-
ulator for the NAS Parallel Benchmarks across a
range of machine configurations. To do so, we ran
all of the benchmarks across a range of processor
and network configurations matching those for which
performance data is available on the NPB web site
(http://www.nas.nasa.gov/Software/NPB/). We stud-
ied the virtual Grid configurations shown in Fig. 9.
To test this hypothesis, we explored a range of quan-
tum sizes for each of the benchmark applications, and
used the Class S (small) data sets, which would exacer-
bate the inaccuracies introducedbythequantasize. The

H.J. Song / The MicroGrid: A scientific tool for modeling Computational Grids
135
Fig. 9. Virtual grid configurations studied.
NPB for HPVM
450
NPB for Alpha Cluster
400
350
300
250
200
150
100
50
400
350
300
250
200
150
100
50
pgrid
mgrid (vc)
Pgrid
Mgrid (vc)
0
EP
BT
LU
MG
IS
0
EP
BT
LU
MG
IS
Fig. 10. NPB benchmark performance (Class A), comparing physical machine runs with equivalent MicroGrid simulations.
results from these experiments are shown in Fig. 11,
and demonstrate that varying the time quanta can sig-
nificantly improve the modeling precision.
The MicroGrid can also be used to study systems
with complex network topologies and structures (as
will be common in many Grid systems). For example,
a MicroGrid simulation can model the effect of spread-
ing an application over a wide-area network testbed
such as the United States National Science Founda-
tion’s vBNS testbed [21] (see Fig. 13). We study the
possibility of executing the NAS parallel benchmarks
over a fictional vBNS distributed cluster testbed, vary-
ing the speed of the WAN network links. Our exper-
iment uses 4-process NPB jobs with two processes at
UCSD (in CSE department LAN) and two processes
at UIUC (on the CS department LAN). Thus, the path
from one cluster to another traverses LAN, OC3, and
OC12 links as well as several routers (finer detail such
as switches and hubs are not modelled). In the experi-
ment, we vary a bottleneck link from 10 Mb/s to OC12,
producing the NPB benchmark performance shown in
Fig. 14.
The results (see Fig. 14) show that theperformance of
the NAS parallel benchmarks distributed over a wide-
area coupled cluster is only mildly sensitive to network
bandwidth. With the exception of EP, the latency ef-
fects dominate, producing poor performance for nearly
all network bandwidths. This confirms the commonly
held perspective that Grid applications need be latency
tolerant to achieve good performance.
For the MG, BT, LU, and EP benchmarks on the
Class S benchmarks, the best quantum sizes for match-
ing are 2.5 ms, 5 ms, 2.5 ms, and 10 ms respectively.
Without exception, the benchmarks that synchronize
frequently match better with shorter time quanta. The
matches with the best time quanta in each case are quite
close, with differences of 12%, 0.6%, 0.4%, and 1.3%
respectively. Clearly, for codes that communicate and
synchronize frequently, scheduling with smaller time
quanta is an important feature of future MicroGrids.
3.4.2. Additional experiments
The MicroGrid can also be used to extrapolate likely
performance on systems not directly available, or those
of the future. For example, a MicroGrid simulation can
be used to explore the futureimplications of technology
scaling at different rates – network, memory, and pro-
cessor speed – for application or system software. For
example, Fig. 12 explores the impact of faster proces-
sors, holding network performance constant (1 Mbps
and 50 millisecond latency). For these benchmarks,
significant speedups can be achieved solely based on
increases in processor speed.

136
H.J. Song / The MicroGrid: A scientific tool for modeling Computational Grids
20
15
10
5
Physical grid
Mgrid (slice=2.5ms)
Mgrid (slice=5ms)
Mgird (slice=10ms)
Mgrid (slice=30ms)
0
MG (class S) BT (class S) LU (class S) EP (class S)
Fig. 11. The effect of varying the scheduling quanta length on MicroGrid modeling accuracy (NPB Class S benchmarks).
1.2
1
0.8
1x CPU
2x CPU
0.6
4x CPU
8x CPU
0.4
0.2
0
MG
BT
LU
EP
Fig. 12. Total run times varying only the virtual cpu.
The MicroGrid can be run at a variety of actual
speeds, yet yield identical results in virtual Grid time.
This capability is useful in sharing simulation re-
sources, or in interfacing the MicroGrid simulations
with external resources for which we may not be able
to control rates precisely. For example, slowing the
processor and network simulations can be used to make
a slow disk seem much faster, or an external sensor
data rate much higher (to model a future higher speed
sensor). The results in Fig. 15 show how the fidelity of
simulation varies as the speed of simulation varies over
an order of magnitude.
international collaboration of physicists and computa-
tional scientists.
To validate the MicroGrid, we again use a model
of DEC Alpha machines in a cluster. We present run
times for CACTUS running WaveToy on this testbed
and compare to runs on the MicroGrid with appropri-
ate processor and network speed settings. These re-
sults (see Fig. 16), show excellent match, within 5 to
7%. Thus, a micro-benchmark, full blown benchmark
suite, and entire application program validation has
been done for the MicroGrid tools, demonstrating its
accurate modeling capabilities for full program runs.
3.5. Applications
3.6. Internal performance
The largest validation tests must include full-blown
application programs. We have studied and validated
the MicroGrid simulation on the CACTUS code –
http://www.cactuscode.org/ – a flexible parallel PDE
solver.
Cactus [1] is an open source problem solving envi-
ronment designed for scientists and engineers. It orig-
inated in the academic research community, where it
was developed and used over many years by a large
A more demanding validation of the MicroGrid
matches the internal application behavior and timing of
each run with that on an actual machine. To make this
comparison, we used identical performance tools (the
Autopilot system [17]) and monitored the NAS Paral-
lel Benchmarks. Autopilot enables the tracking of the
values of certain types of program variables over the
execution of the program. The resulting data, normal-

H.J. Song / The MicroGrid: A scientific tool for modeling Computational Grids
137
Fig. 13. Our fictional distributed cluster testbed uses the vBNS and models the network using the MicroGrid simulator.
ized over execution time of the programs are shown in
Fig. 17.
4. Related work
While there are many related efforts, we know of no
other Grid, distributed system, or parallel system mod-
eling efforts that seek this level of modeling of Compu-
tational Grids – validated, general purpose direct sim-
ulation.
Early papers on the Globus MDS described a fea-
ture called “resource images” which are similar to our
virtual Grid entries. However, to our knowledge, these
images were never used. The most closely related
project is the Ninf/Bricks project [20] which has fo-
cused on evaluating scheduling strategies based on syn-
thetic models of applications and innovative network
traffic models. However, to date Bricks has not used
Grid applications as a direct driver.
The graph shows the the changingvalue of a periodic
function of counter variables in EP, BT and MG with
time for class A data sizes for the Alpha cluster (using
100% CPU time) and the MicroGrid (using 4% CPU
time). The simulation rate is therefore 0.04. The x-
axis shows the time, with one sample of the variables
being made every 1 second for the Alpha cluster, and
every 25 seconds for the MicroGrid to take into account
the simulation rate. We see that the traces for both
the physical system and the simulation follow the same
structure, and match fairly well in time. We calculated
the “skew” in the graphs for each benchmark as the root
mean square percentage difference recorded at each
sample time. This value was found to be 3.08% for
EP, 2.02% for BT and 8.33% for MG. The closeness of
the internal matching provides stronger evidence that
the MicroGrid is precisely matched the modeled Grid
system’s behavior.
There are a wide variety of simulation tools for par-
allel systems; however, they focus primarily on archi-
tectural simulations [4,14,16,18] and program debug-
ging [5,12]. These tools typically do not model system
heterogeneity, irregular network structure, a complex

138
H.J. Song / The MicroGrid: A scientific tool for modeling Computational Grids
NPB under network degrade
30
25
20
15
10
5
622Mb/s
155Mb/s
10Mb/s
0
LU
BT
MG
EP
bandwidth of one link of vBNS drops from 622Mb/s to
10 Mb/s
Fig. 14. Performance of NPB over the vBNS distributed cluster testbed, varying the network speed of the major WAN links.
1.05
1
1x system
0.95
0.9
0.85
2x system
4x system
8x system
0.8
MG
BT
LU
EP
Fig. 15. Total run times varying emulation rates.
Grid software environment, and the traffic modeling
required by the network environments.
high intensity workloads and large dynamic range (six
orders of magnitude) in single user network demand.
There a wide variety of network simulation tools, in-
cluding those for parallel systems [10,11,15] and those
for Internet style networks [2,3,9]. The parallel system
tools typically do not model the detailed structure in
complex heterogeneous network environments. Those
for Internet systems typically do not support live traffic
simulation. Also, since Internet workloads are typi-
cally large numbers of WWW users on low-bandwidth
links, these simulators do not focus on scaling with
5. Summary and future work
We are pursuing a research agenda which explores
how to simulate and model large-scale Grid structures.
To this end, we have developed a set of simulation
tools called the MicroGrid that enable experimenters
to run arbitrary Grid applications on arbitrary virtual

H.J. Song / The MicroGrid: A scientific tool for modeling Computational Grids
139
120
100
80
60
40
20
0
2
1.5
Physical Grid
MicroGrid
1
Physical Grid
MicroGrid
0.5
0
50
250
50
250
Grid Size (one edge)
Fig. 16. CACTUS runs on a physical cluster and on the MicroGrid tools modeling that same cluster performance.
Performance of EP
Performance of BT
45
40
35
30
25
20
15
10
5
9
8
7
6
5
4
3
2
1
0
Physical grid
Physical grid
MicroGrid
MicroGrid
0
Sample number
Sample number
Performance of MG
2.5
2
1.5
1
Physical grid
MicroGrid
0.5
0
Sample number
Fig. 17. Comparing autopilot data from a physical system and a MicroGrid simulation.
Grid resources, allowing the study of complex dynamic
behavior. We describe our initial design, implementa-
tion, and validation of the MicroGrid tools on micro-
benchmarks, a well-known parallel benchmark suites,
the NAS parallel benchmarks, anda full-blownapplica-
tion program, the CACTUS system for parallel partial
differential equation solvers. These studies show that
the MicroGrid approach is feasible and the basic im-
plementation is validated. In addition, we perform an
internal validation showing that the execution at each

140
H.J. Song / The MicroGrid: A scientific tool for modeling Computational Grids
time step within a MicroGrid simulation closely fol-
lows that in an actual execution. This internal valida-
tion is achieved using the Autopilot tools, and running
them within the MicroGrid environment.
[4] G.T.E. Tam, J. Rivers and E.S. Davidson, mlcache: A Flex-
ible Multi-Lateral Cache Simulator, University of Michigan
Department of Electrical Engineering and Computer Science,
CSE-TR-363-98, 1998.
[5] M. Feng and C.E. Leiserson, Efficient Detection of Determi-
nacy Races in Cilk Programs, in: Proceedings of the Ninth
Annual ACM Symposium on Parallel Algorithms and Archi-
tectures (SPAA), 1997, pp. 1–11.
[6] I. Foster and C. Kesselman, Globus: A metacomputing in-
frastructure toolkit, International Journal of Supercomputing
Applications, (1997), http://www.globus.org.
[7] A.S. Grimshaw, W.A. Wulf and the Legion team, The Legion
vision of a worldwide virtual computer, Communications of
the ACM (1997), http://legion.virginia.edu.
[8] C. Lin, H. Chu and K. Nahrstedt, A Soft Real-time Scheduling
Server on the Windows NT, in: Proceedings of the Second
USENIX Windows NT Symposium, 1998.
[9] D.M. Nicol, J. Cowie and A.T. Ogielski, Modeling the Global
Internet,
Computing in Science & Engineering 1(1) (1999), pp. 42–50,
http://www.cs.dartmouth.edu/˜jasonliu/projects/ssf/.
[10] L. Snyder, K. Bolding and M. Fulgham, The Case for Chaotic
Adaptive Routing, University of Washington, UW-CSE-94-
02-04, 1994.
[11] J.H. Kim and A. Chien, Network Performance Under Bimodal
Traffic Loads, Journal of Parallel and Distributed Computing
28(1) (1995).
[12] LAM/MPI Parallel Computing, Home Page, at http://mpi.nd.
edu/lam/.
[13] N. Miller and P. Steenkiste, Collecting Network Status In-
formation for Network-Aware Applications, in: Infocom’00,
2000, http://www.cs.cmu.edu/afs/cs.cmu.edu/project/cmcl/
www/remulac/index.html.
[14] V.S. Pai, P. Ranganathan and S.V. Adve, RSIM: An Execution-
Driven Simulator for ILP-Based Shared-Memory Multipro-
cessors and Uniprocessors, in: Proceedings of the Third Work-
shop on Computer Architecture Education, February 1997,
http://www.ece.rice.edu/˜rsim/.
[15] S. Prakash, Performance Prediction of Parallel Programs,
University of California Los Angels, 1996, http://pcl.cs.ucla.
edu/projects/sesame/.
[16] S.K. Reinhardt, M.D. Hill, J.R. Larus, A.R. Lebeck, J.C.
Lewis and D.A. Wood, The Wisconsin Wind Tunnel: Virtual
Prototyping of Parallel Computers, in: Proceedings of the
1993 ACM Sigmetrics Conference on Measurement and Mod-
eling of Computer Systems, 1993, pp. 48–60, http://www.cs.
wisc.edu/˜wwt/.
While we have made tangible progress, signifi-
cant challenges remain. For some applications, us-
ing smaller scheduling quanta, enabled by a real-time
scheduling subsystem can improve the fidelity of our
simulations. We are pursuing the development of a
new scheduler based on real-time priorities. In the near
term, we plan to support scaling to dozens of machines,
dynamic mapping of virtual resources, and dynamic
virtual time. In the longer term, we plan to solve ques-
tions of extreme scalability – how to get to 100 mil-
lion simulated nodes, exploring a range of simulation
speed and fidelity, understanding how to extrapolate
from a small set of Grid simulations to a much broader
space of network environment and application behav-
ior. We will also pursue the use of the MicroGrid tools
with a much larger range of applications, exploiting the
growing range of Globus applications that are becom-
ing available. We also invite the participation of other
research groups to extend and enhance the MicroGrid
simulation infrastructure.
Acknowledgements
The research described is supported in part by
DARPA thru the US Air Force Research Laboratory
Contract F30602-99-1-0534. It is also supported by
NSF EIA-99-75020 andsupportedinpart by funds from
the NSF Partnerships for Advanced Computational In-
frastructure – the Alliance (NCSA) and NPACI. Sup-
port from Microsoft, Hewlett-Packard, Myricom Cor-
poration, Intel Corporation, and Packet Engines is also
gratefully acknowledged.
[17] R.L. Ribler, J.S. Vetter, H. Simitci and D.A. Reed, Au-
topilot: Adaptive Control of Distributed Applications, Pro-
ceedings of the 7th IEEE Symposium on High-Performance
Distributed Computing, 1998, http://www-pablo.cs.uiuc.edu/
Project/Autopilot/AutopilotOverview.htm.
[18] M. Rosenblum, S.A. Herrod, E. Witchel and A. Gupta, Com-
plete Computer Simulation: The SimOS Approach, IEEE Par-
allel and Distributed Technology (1995), http://simos. stan-
ford.edu/.
[19] W. Saphir, R.V. der Wijngaart, A. Woo and M. Yarrow, New
Implementation and Results for the NAS Parallel Benchmarks
2, NASA Ames Research Center, http://www.nas.nasa.gov/
Software/NPB/.
[20] A. Takefusa, S. Matsuoka, H. Nakada, K. Aida and U.
Nagashima, Overview of a Performance Evaluation Sys-
tem for Global Computing Scheduling Algorithms, Proceed-
ings of 8th IEEE International Symposium on High Perfor-
References
[1] G. Allen, T. Goodale, G. Lanfermann, T. Radke and E. Seidel,
The cactus code, a problem solving environment for the grid,
2000.
[2] S. Bajaj, L. Breslau, D. Estrin, K. Fall, S. Floyd, P. Haldar,
M. Handley, A. Helmy, J. Heidemann, P. Huang, S. Kumar, S.
McCanne, R. Rejaie, P. Sharma, K. Varadhan, Y. Xu, H. Yu
and D. Zappala, Improving simulation for network research,
Technical Report 99-702, University of Southern California,
1999, pp. 99–702, http://netweb.usc.edu/vint/.
[3] J. Cowie, H. Liu, J. Liu, D. Nicol and A. Ogielski, Towards Re-
alistic Million-Node Internet Simulations, in: Proceedings of
the 1999 International Conference on Parallel and Distributed
Processing Techniques and Applications (PDPTA’99), 1999,
http://www.cs.dartmouth.edu/˜jasonliu/projects/ssf/.

H.J. Song / The MicroGrid: A scientific tool for modeling Computational Grids
141
mance Distributed Computing (HPDC8), 1999, pp. 97–104,
http://ninf.etl.go.jp/.
[21] The United States National Science Foundations vBNS. Very
high performance backbone network service. MCI WorldCom,
Inc. http://www.vnbs.net/.
[22] R. Wolski, Dynamically forecasting network performance us-
ing the network weather service, Journal of Cluster Comput-
ing (1998), http://nws.npaci.edu/NWS/.

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