An Economy-driven Mapping Heuristic for Hierarchical Master-Slave Applications in Grid Systems

An Economy-driven Mapping Heuristic for
Hierarchical Master-Slave Applications in Grid Systems
Nadia Ranaldo1, Eugenio Zimeo2
1University of Sannio
2University of Sannio
Department of Engineering
Research Centre on Software Technology
Benevento, 82100, Italy
Benevento, 82100, Italy
ranaldo@unisannio.it
zimeo@unisannio.it
Abstract
through an Information System, the broker schedules for
the execution the application tasks distributed on the
In heterogeneous distributed systems, such as Grids, a
selected resources, which are continuously monitored and
resource broker is responsible of automatically selecting
managed.
resources, and mapping application tasks to them. A
Mapping, scheduling, and execution are performed so
crucial aspect of resource broker design, especially in a
that some QoS requirements provided by the requester are
next commercial exploitation of grid systems, in which
satisfied. In particular, the resource broker assigns tasks to
economy theories for resource management will be
resources on the basis of specified policies, called
applied, is the support to task mapping based on the
mapping policies, used to determine the best schedule for
fulfilment of Quality of Service (QoS) constraints. The
the application on the set of available resources. The
paper presents an economy-driven mapping heuristic,
mapping task phase, moreover, is one of the most
called time minimization, for mapping and scheduling the
important functions for a resource broker, since it has a
tasks assigned to the slaves of a master-slave application
direct impact on service response times and, as a
in a hierarchical and heterogeneous distributed system.
consequence, on user satisfaction.
The validity and accuracy of such heuristic are tested by
The deployment of grid systems in the next years will
implementing it in a resource broker of a hierarchical
foster the adoption of new business models for computing
grid middleware used for running a real world
services. Big companies and organizations will prefer to
application.
rent computing resources instead of buying them. In such
a scenario, the efficiency improvement of resource
allocation and scheduling will be possible through the
adoption of economic models to apply among resource
1. Introduction
suppliers and requesters. In recent years, in this
perspective, some economics theories have been studied
A main challenge to efficiently execute parallel and
for the implementation of resource management in a grid
distributed applications in a grid system is the effective
environment [2]. A market, in fact, similarly to a grid
management of the large amount of available
system, is decentralized, dynamic and deals with
computational, storage and communication resources in
competitive resources. The basic components in a market
order to optimize the mapping on them of application
are producer, consumer and commodities, corresponding
tasks. To this end, a central subsystem of a middleware
respectively to resource owner, resource requester (user)
for grid computing is the Resource Management System
and distributed resources in a grid environment.
(RMS). The main goal of the RMS is to enable a
An economy-driven resource management system
transparent access to the pool of resources available in the
provides a mechanism for regulating the supply-and-
Grid.
demand for resources and allocating them to applications
A fundamental component of an RMS is the resource
based on user preferences, such as cost and time
broker, which is mainly responsible of accepting
constraints. It also gives an incentive to resource owners
execution requests from the user and assigning them to
for making resources available for computation and a
specific resources selected from the pool of available ones
basis to users for appropriately trading the quality of
[1]. In addition to this task, which is accomplished
service guarantees they receive against cost.
1-4244-0054-6/06/$20.00 ©2006 IEEE

---

In grid resource management systems a fine accuracy
an actual test-bed executing applications written for the
of mapping decisions requires, in addition to detailed
TMS (Transparent Master Slave) Framework [6], a
information of the underlying distributed system, the
reflection-based framework for master-slave applications,
knowledge and model of application features, in terms of
able to re-use existing code for non-distributed solutions
computational requirements of each task, data and
and to automatically parallelize and schedule the tasks
execution dependencies and communication patterns.
among multiple resources, by satisfying user QoS
This paper presents the definition of an application-
constraints.
oriented and economy-driven mapping heuristic, called
The rest of the paper is organized as follows. Section 2
time minimization, for mapping distributed tasks on a set
presents related work, Section 3 describes the application
of heterogeneous and distributed resources. The proposed
and grid model, Section 4 describes the proposed
heuristic is applied to a specific class of applications
mapping heuristic, Section 5 presents an evaluation of the
which presents the same task dependencies, that is the
proposed heuristic performed adopting some experimental
class of applications based on the master-slave model.
results conducted on a real distributed environment.
The main reasons of such choice are: (1) the master-
Finally Section 6 summarizes the paper and presents
slave model is very spread in scientific community and
future work.
can be adopted to achieve a good performance
improvement of a wide class of applications in many
2. Related
Work
fields of science and engineering, such as weather
prediction, astrophysics, bioinformatics, earth quake
Task mapping policies can be distinguished in system-
research, ground water pollution, multi particle physics,
oriented policies, which try to optimise the overall
etc.; (2) applications programmed according to the
resource utilization, and application-oriented policies,
master-slave model well fit grid systems because of well-
which try to optimise application execution.
defined and limited communication patterns among the
Application-oriented policies are often QoS-based,
distributed computing entities.
since they permit to satisfy QoS requirements specified by
In fact, communication takes place only between the
the user. The optimal solution for such kind of policies in
master and the slaves and in well-defined times of
a heterogeneous and distributed environment leads to NP-
execution. For these reasons, this model is well suited to
complete problems and different heuristics have been
be used in Grids where high-latency and shared wide-area
proposed in the literature to reach a near-optimal solution.
networks are a strong limitation for the execution of
Most of the grid systems use application-oriented
applications based on tightly-coupled parallelism.
mapping heuristics which try to optimise only the
The simplest approach for performing repeatable tests
execution performance, by adopting a mapping that
on task mapping, overcoming resource availability
minimizes the overall execution time with respect to the
problems, is to resort to simulation. Well known projects
available resources. A simple example is the greedy
in the context of grid simulation are GridSim [3] and
approach [7], which iteratively allocates each task to the
Simgrid [4]. On the other hand, the simulation approach
resource that is likely to produce the best performance,
can be hardly used for studying, in a repeatable and non-
without considering the rest of pending tasks. This
intrusive way, the subtle interactions between large-scale
approach leads usually to sub-optimal solutions, since the
shared distributed hardware, application software, and
mapping decisions are based only on local task
complex resource management policies, which are typical
information.
of grid environments. As a consequence, evaluation
More complex mapping algorithms, which try to
results produced by simulation tools to study the
overcome local optimal solutions, are based on genetic
effectiveness of task mapping algorithms may be
algorithms [8], simulated annealing [9] or branch and
inaccurate.
bound methods [10]. Other proposals of mapping
For this reason the accuracy of the proposed heuristic
algorithms are Workerqueue (WQ), Workerqueue with
and its usefulness in mapping and scheduling tasks of real
Replication (WQR) and dynamic FPLTF (Fastest
world applications with time and cost constrains is
Processor to Largest Task First) [11, 12].
studied using such heuristic for implementing the
Some mapping algorithms specific for master-slave
mapping phase of a resource broker of HiMM
applications have been presented in [13]. These
(Hierarchical Metacomputer Middleware) [5], a grid
algorithms adopt an accurate grid model as regards
middleware which delivers basic services of computation,
computation and communication performance, but do not
information, communication and resource management
take into account economic aspects of resources.
for parallel and distributed object-oriented applications.
On the other hand, in a future commercialisation of the
Nevertheless, the solution proposed can be easily applied
Grid, a resource characterization based only on
to other grid middlewares.
performance features is not sufficient to properly model
The time minimization heuristic is, moreover, tested on

---

resources. In economy theories, in particular, the price of
DAG express the dependencies between the tasks, that
resource utilization is the only additional parameter
can be of execution, data, or both.
necessary to operate, providing so a simplified way to
Defining mapping algorithms, able to manage the task
model the resource owner satisfaction and the competition
dependencies of an application described by a generic
among them. In [2] some economic models, that can be
DAG, is difficult. In this work we focus on a class of
applied for managing grid resources and determining the
applications described by the same DAG structure, and in
price of resource utilization, have been studied, for
particular those which adhere to the master-slave pattern
example the commodity market model, the posted price
[17]. In this pattern there are two kinds of entities: master
model, the bargaining model, the auction model, the
and slave. Generally a master decomposes the problem
trading model and the monopoly/oligopoly model.
into smaller tasks, distributes these tasks among a farm of
Paper [14] represents one of the first effort to introduce
slaves and waits for partial results. Each slave performs
economy-driven mapping algorithms based on deadline
its processing on the received task, then returns the result
and budget constraints. Such algorithms were tested in
of the processing back to the master, which gathers and
Nimrod-G [15], a grid resource management system for
assembles the partial results in order to produce the final
scheduling parametric applications. The proposed
solution of the computation.
approach, however, does not model task dependencies
We consider, in particular, the master-slave pattern for
and do not ensure the assignment and execution of all the
coarse-grained parallel applications, which embody a
tasks, since it considers a shared and dynamic
wide spectrum of application domains, from
environment in which only a task at a time is assigned
combinatorial optimization problems, to data mining, to
until the budget is consumed.
processing of large measurement data sets, etc. For such
Our idea, instead, is to grant the execution of all the
applications the partition of input data is used to induce a
tasks of the application respecting the established terms
partition of the overall workload among slaves (data
during the initial negotiation phase between the resource
partitioning), and, in particular, the following
broker and the user. Our approach, in particular, requires
parallelization technique is adopted: the same sequential
to exploit selected resources in an exclusive way, so to
algorithm is executed simultaneously by the slaves,
maintain the predicted performance by the heuristic in the
processing different input data.
time necessary to complete the application execution.
For the master-slave pattern we propose an application
A possible approach to grant the complete availability
model in which the master performs a preliminary task of
of selected resources to scheduled applications is the use
partitioning of input data, and a task of processing of
of advance reservation mechanisms, both for
partial results. The latter is performed when all the partial
communication and computational resources, delivered by
results are returned by the slaves.
the grid middleware [16].
The slaves, moreover, perform the overall workload,
which is decomposed into a high number of sub-tasks,
3. Application and Grid Models and
called atomic sub-tasks, which are parts of the original
workload that can not be further decomposed. By
Notations
definition, the atomic sub-tasks are independent, do not
communicate with each other and are considered the
In this section the class of applications and grid
smallest tasks which can be mapped onto resources. The
systems for which our approach can be applied are
application is characterized by the computation size (or
described and modelled.
complexity), called N, that corresponds to the total
number of atomic sub-tasks, each of which is
3.1 Application
Model
characterized by the same complexity in terms of
computation, data storage and data transfer aspects (see
A very simple model of application is the unstructured
figure 1).
application, that is a distributed application composed of
However, for a large number of distributed resources
a set of independent and self-contained tasks. This model
the centralized control of master can become a bottleneck
is considered as reference model in various resource
for applications and a single point of failure.
broker systems for the activities of task mapping and
To overcome such limitations, a hierarchical version of
scheduling, but can not be considered a realistic model,
the master-slave pattern is taken into account, by
since distributed applications are typically composed of
extending the single master to a hierarchy of masters,
tasks characterized by data and control dependencies. In
each of which controls a different group of slaves at
particular the computation in a distributed application can
different hierarchical levels.
be viewed as a precedence graph, that is, a directed
In the hierarchical master-slave pattern [18], the
acyclic graph (DAG). Each node in the DAG corresponds
master at the top of the hierarchy partitions input data to
to a computation or communication task. The edges of the
the underlying masters, a nd so on, until to reach the

---

Partitioning of
performance improvement of the overall application.
master
input data
Such simplification will be removed in a future work
distribute tasks
in which a mapping policy for all the tasks of a
hierarchical master-slave computation will be taken into
account.
Atomic
Atomic
Atomic
Atomic
Sub-task
Sub-task
Sub-task
. . .
Sub-task
3.2 Grid
Model
1
2
N
slaves
return results
A grid system is generically composed of a pool of
Processing of
distributed and heterogeneous computational resources,
master
partial results
characterized by different computation performance,
inter-connected through communication resources and
accessible via the Internet. In such distributed systems,
Figure 1. The Master-slave pattern.
some computational resources (especially nodes of
clusters and networks of workstations) are often not
slaves, that directly process the received input data (see
directly accessible via the Internet and use dedicated,
figure 2).
high-performance networks whose protocols may not be
Hierarchical master-slave applications, executed in a
IP-compliant. As a consequence, a hierarchical
distributed environment, require to host masters and
organization is a natural topology to represent grid
slaves on different computational resources. In this
systems and offers many advantages: (1) it can be adopted
context the DAG structure requires to model, in addition
to recursively divide an application workload into
to computation tasks performed by masters and slaves,
multiple distributed and concurrent tasks running
communication tasks, due to the realistic limited
simultaneously on grid resources; (2) each administrative
performance of inter-networking resources. Such tasks are
domain can be controlled separately from the others and
related in particular to input data transfers performed by
so remote resource owners can easily enforce their own
the master towards the sub-master, until to the slaves, and
policies on external users; (3) grid applications can
to output data transfers performed by the slaves towards
exploit dedicated and high-performance resources
the master hierarchy.
(supercomputers, dedicated high-speed networks of
The paper focuses on applications for which
workstations, etc.) non-directly accessible through the
partitioning of input data task, processing of partial
Internet; (4) it removes the single centralization point for
results task and communication tasks can be disregarded
grid management, and so improves scalability.
with respect to computation tasks performed by the
In a hierarchical topology, the resources are virtually
slaves, whose optimised distribution on distributed
organized into different levels, and only resources
heterogeneous resource determines the significant
belonging to the same level can directly communicate
among them. A designed machine of a level is used by the
master
resources to communicate with the level above them or
Partitioning of
at the top
input data
of hierarchy
below them. In this organization, grid users access only to
distribute tasks
resources at the highest level, while the complexity of the
masters
Partitioning of
Partitioning of
Partitioning of
underlying hardware and software infrastructure is
input data
input data
input data
hidden.
distribute tasks
Our grid model considers the grid system as a
hierarchy of computational resources distributed on
multiple levels. Due to the simplification of the
Atomic
Atomic
Atomic
Atomic
. . .
. . .
Atomic
. . .
Atomic
Sub-task
Sub-task
Sub-task
Sub-task
Sub-task
Sub-task
application model, communication resources and their
1
N
related performance are not modelled: this corresponds to
slaves
return results
consider a distributed environment characterized by high
Processing of
communication performance.
masters
Proce ssing of
Proce ssing of
partial re sults
partial re sults
partial re sults
Each level of the grid system is modelled as a set R of
return results
resources, each of which is characterized by computation
performance and cost attributes. We indicate a resource
master
Proce ssing of
at the top
partial re sults
with R
of hierarchy
i,, with, i:1..M, where M is the number of available
resources (see figure 3). A resource can be simple, if it
represents a single computer, or aggregate, if it represents
Figure 2. The hierarchical master-slave
a pool of computers of a lower level in the hierarchy
pattern.
(such as a cluster or a network of workstations).

---

The performance of a simple resource Ri is modeled as
The goal of the proposed heuristic is to minimize the
the total time required for the processing of an atomic
total execution time, so the distribution has to be chosen
sub-task and is indicated with ti. The cost of a simple
in order to utilize the best performance resources to
resource Ri, called ci, is modeled as the cost of resource
minimize execution time on each resource. Since we
usage for the processing of an atomic sub-task. Called Ni
consider economic aspects of resource usage, the
the number of resources of the lower level of Ri, and Rij
distribution is also performed so as to not exceed the
with J:1,..Ni, the lower level resources, the performance
budget.
of an aggregate resource Ri can be modelled as the sum of
With respect to the application and grid models
the times tij, which are the times that each resource Rij
described in the previous section, the mapping problem
requires for processing an atomic sub-task, divided by Ni,
can be formalized as follows. The objective function is:
while the cost can be modelled as the sum of the costs cij
per atomic sub-task of each Rij. A more accurate model of
1
( )
t
min( n )
i : 1 M
..
i
i
aggregate resources, which takes into account the
heterogeneity of resources of the lower level, will be
where n
considered in a future work.
i denotes the number of atomic sub-tasks assigned
to resource Ri and represents the unknown quantity of the
algorithm.
4.
The Time Minimization Heuristic
Objective function (1) must be reached respecting the
following constraints:
The time minimization heuristic is based on the
economy model proposed in [2] in which the execution of
( )
2
t n
D
i :
M
..
1
i
i
an application is subject to both time and cost constraints.
M
It regards the problem of finding the “best” resources on
)
3
(
n
N
i
i
1
which to run the slaves of a master-slave application and
M
the best assignment of distributed tasks to them. It can be
( )
4
c n
B
i
i
i
1
adopted into a hierarchical environment, applying
periodically the same procedure to each level of the
where ni has to be not negative, (2) ensures that the
hierarchy and considering both simple and aggregate
deadline is not exceeded, (3) is the constraint on the
resources related to that level.
actual execution of N tasks, and (4) ensures that the
The parameters specified by the user, that determine
budget is not exceeded. Since an atomic sub-task can not
the objective function, are: (1) the total execution time,
be further divided, an additional constraint is that ni must
which represents the deadline, called D, and (2) the total
be integer, since it represents the number of atomic sub-
price for resource usage, which represents the available
tasks assigned to resource Ri.
budget, called B.
To minimize the execution time, we assign a non
The proposed heuristic selects a sub-set of resources
uniform number of atomic sub-tasks to the available
from the pool of available ones, so that the aggregate cost
slaves such that they will finish at roughly the same time.
for their usage is lower than budget B (but not necessarily
So (1) is equivalent to the following objective function:
the minimum) and that are able to complete the
application execution as quickly as possible (time
5
( )
t n
t n
i, j : 1 M
..
minimization) and within deadline D.
i
i
j
j
The approximation in (5) is caused by the
heterogeneity of resources, which are characterized by
level 1
R
. . .
1
R2
R3
RM
different performance, and by the constraint on n
c
c
i to be
2=c21+c22+..+c2N2
c
cM=...
3
1=c11+c12+..+c1N1
t =(t
t2=(t21+t22+..+t2N2)/N2
t
tM=...
adjusted to integers.
1 R
3
11+t12+..+t1N1)/N1
1
R2
Indicated with t the execution time of an atomic sub-
task for the resource with the highest performance, (5)
implies:
c
c
11
c12
1N1
c
. . .
21
c22
c2N2
c
c
M 1
cM2
. . .
t
. . . MNM
t11
t12
1N1
t21
t22
t2N2
t
t
M 1
tM2
M NM
6
( )
t n
t n
i : 1 M
..
i
i
R11
R12
R1N1
R21
R22
R2N2
RM1
RM2
RMNM
level 2
level 2
level 2
where n is the number of atomic sub-tasks assigned to
the quickest resource. The calculation of n permits to
Figure 3. The grid model.
evaluate ni as:

---

t
In this order the most expensive resource is R
7
( )
n
n
i : 1 M
..
M.
i
ti
(f) Because of the required exceeding budget, it is
that, applied to (3) and (4), leads to:
necessary to decrease the number of atomic sub-tasks
assigned to the most expensive resource. As a
M
M t
consequence, a part of atomic sub-tasks assigned to R
)
8
(
n
n
N
M,
i
i
1
i 1 t
called , is distributed among the (M-1) resources in a
i
proportional manner to their performance. To this aim, the
M
M t
)
9
(
n c
nc
B
following system has to be solved:
i
i i
1
i 1 t
i
i
M 1 t
t
Generally constraints (2), (8) and (9) are not satisfied
(n
)c
(n
)c
B
i 1
t
i
t
M
simultaneously. As a consequence, we propose an
i
M
)
10
(
iterative algorithm whose steps are described in the
M 1 t
t
(n
)
(n
)
N
i
following:
i 1
t
t
i
M
(a) Consider set R of all available resources and indicate
with Rp the quickest resource. Solve (9) in order to find
i. If there is a solution with (n
)
0 that verifies
real value n considering to consume the budget, that
constraint (2) on deadline, then the solution of the time
means to equalize the total cost to B. Then approximate
minimization heuristic is given by ni calculated as:
n to the nearest smaller integer, so to not exceed B.
t
n
(n
)
i
..
1 M
1
(b) Use n to calculate n
i
i of all the other resources,
ti
solving (7) for all i:1,..M except p.
)
11
(
t
n
(n
)
M
t
(c) Use constraint (8), considering the equality to N, in
M
order to find the factor x to normalize the calculated ni
values so that their sum is N:
rounding the obtained values to the nearest integers.
ii. If there is not a solution with (n
)
0 that
M (n x) N
i 1
i
satisfies the constraint on deadline, then the procedure
is iterated from step (a), eliminating the resource RM
i. If x>1, that means that (8) can not be satisfied
from the set of available resources. If steps from (a) to
using the current makespan, continue to step (e);
(e) are iterated for M times terminating without a
solution, it is possible to conclude that there is not a
ii. If x<=1, that means that (8) can be satisfied
sub-set of the available resources which permits to
using the current makespan, recalculate ni multiplying
satisfy simultaneously the constraints on deadline and
them by the factor x.
budget.
(d) Verify constraint (2).
Starting from objective function (5) and constraints (2),
i. If (2) is violated the algorithm ends without a
(3) and (4), an optimal solution could be reached with real
solution;
values of ni. On the other hand, a good rounding to the
nearest integers permits to remain very close to the
ii. If (2) is not violated then the algorithm ends with
optimal solution.
a solution given by ni calculated at step (c).ii.
In order to obtain the solution that as best as possible
approximates the optimal one, we propose a generic
(e) Sort list Ro of resources by increasing order of cost
procedure for the rounding of ni values to integers,
per atomic sub-task. If two or more resources have the
respecting the established deadline and budget constraints
same cost, order them for decreasing performance, so to
and maintaining N as total summation of all ni. In this
prefer, among resources with the same cost, the quickest
procedure an ni value is considered integer when the
ones:
absolute value of the difference between it and the nearest
integer is less than a specified little value >0.
R
(R ,.., R ,.., R )
Consider list R
o
1
j
M
o of resources ordered as indicated at
step (e) of the procedure.
with
c
c
or c
c
and t
t
j
1 M
..
j
j 1
j
j 1
j
j 1
- If n1 is not an integer, if deadline is not exceeded for
resource R1, n1 is approximated to the nearest greater

---

integer, indicated with g1, else it is approximated to the
for distributed programming [19]. By using MOP, the
smaller one, indicated with s1.
TMS Framework permits to use every existing class to
In the case of approximation to the nearest greater
transparently instantiate the set of active objects that
integer, the difference between g1 and n1 is subtracted to ni
correspond to masters and slaves instances in the
of the necessary resources in the list, starting from R2,
hierarchical topology, maintaining the application similar
until such values become the respective nearest smaller
to that used for a sequential computation. Therefore, the
integers (eventually except for the last one).
hierarchical master-slave pattern is dynamically
In the case of approximation to the nearest smaller
implemented and every active object can be turned in a
integer:
master able to transparently split the service task into sub-
- the difference between n
tasks and in a slave able to perform the assigned part of
1 and s1 is added to the
resources in list R
the overall task.
o, starting from resource R2, until
their values become the respective nearest greater
The programming model of the TMS Framework
integers (eventually except for the last one, called R
requires to provide the name of the configuration file used
L).
- (9) constraint is checked. If (9) is violated, repeat
to dynamically configure the deployment of active
the previous step without considering R
objects. It is an XML-based file, called Job Description
L and the
following ones, and so on. If no adjustment permits to
Format (JDF), which follows a well-defined format. In
satisfy (9), the procedure ends without a solution.
particular, a part depends on the underlying middleware
- (2) constraint, for resources whose n
adopted for active object management and
i was changed,
is checked. If (2) is violated for one or more resources,
communication, while the other one is common and is
the total quantity of n
used for the reflection mechanisms. The common part, in
i values which cause the
violation is distributed among the previous resources
particular, contains the following information: the method
and the previous step is repeated.
whose invocations have to be distributed over master and
- Repeat starting from the following resource in list R
slaves objects; the input parameters that have to be
o,
(R
partitioned and the policy to partition each of them; the
2, R3, until to RM) and until all ni are rounded to integer.
assembly policy of the output parameter.
Such rounding procedure determines the relative error
Thanks to the ProActive-HiMM middleware
of the heuristic result from the optimal one, that can be
developed by the authors in a previous research work
considered very trivial in the following case:
[20], the TMS Framework can be easily adopted to
leverage HiMM, a hierarchical component and Java-based
t n
t
i, j : 1 M
..
middleware for grid computing, which delivers grid
i
i
j
services of information, communication and resource
management. HiMM, in particular, provides a resource
which is verified in the case of high values of ni.
broker which allows users to submit applications
specifying application code, input data, features and QoS
5. Experimental
Results
requirements described using XML-based descriptor files
[21].
The time minimization heuristic was tested on
The time minimization heuristic, implemented for the
applications written for the TMS Framework, an object-
task mapping phase of the HiMM resource broker, adopts
oriented framework for transparent and hierarchical
information on the application structure and economic-
master-slave applications, which is able to re-use existing
based requirements contained in the XML-based files
code for non-distributed solutions and to automatically
specified by the user and the performance and cost
parallelize and distribute the tasks generated by the
information about the available resources delivered by the
execution among multiple distributed resources.
Resource Managers, HiMM components whose task is to
publish information about available resources in the grid
5.1
The TMS Framework
system. The performance information is necessary in
order to predict the execution time of the assigned number
of atomic sub-tasks to each resource.
Thee TMS Framework manages the functionalities of
In a heterogeneous environment, accurate performance
resource management, scheduling and communication
prediction of resources is a fundamental aspect in order to
required to deploy the application and is able to leverage
obtain an efficient mapping and so the real fulfillment of
already existing services delivered by the middleware
user QoS requirements.
used as underlying layer.
The prediction performance represents an important
Such framework was implemented through reflection
research area in which many efforts have been made.
mechanisms provided by the run-time proxy-based Meta-
Several solutions have been proposed and adopted to
Object Protocol (MOP) provided by the ProActive library
evaluate the resource performance. These can be based on

---

benchmarking, analytical modelling, and monitoring.
The OPSSA application deals with the on-line
In benchmarking methodologies well-defined
assessment of the electrical system’s capacity to maintain
applications are executed on systems to measure the
the flow of electricity from generators to customers, under
performance in term of CPU utilization, RAM
unforeseen phenomena, called contingencies, that could
occupation, etc., which can be also used as a basis for
compromise the correct system behaviour. A contingency
comparisons with other systems. Analytical modelling
can be, for example, an unexpected modification in the
methodologies require the construction of a mathematical
power system structure or a sudden change of the
or logical model that represents the behaviour of the
operational conditions.
system and that has to be analytically evaluated (an
The OPSSA works on real-time distributed data
example is the LogP model [22]). Monitoring approach is
measurements, used to get the most recent estimation of
used to continuously measure and analyse the
the system state variables. Moreover, since such
performance of systems (such as NWS [23]).
application requires stringent time constraints, in order to
In the current approach, because of the assumption of
output data to be usefully leveraged by the system
using resources in a exclusive way by adopting
operators, it is particularly apt for testing the behavior of
reservation mechanisms, a simple benchmarking-based
the proposed mapping heuristic.
performance estimation is adopted to predict resource
The OPSSA consists of three main steps:
performance in terms of execution times. Since the
1. the screening phase: screening of the most “credible”
adoption of a generic benchmark can not be used to
contingencies, that are the most probable and the most
accurately evaluate the execution time of a specific
dangerous ones;
application, our solution is to evaluate resource
2. the predicting phase: the prediction of the impact of
performance with respect to the specific atomic sub-task
each credible contingency on the entire system operation
of an application. As a consequence we suppose to use a
through the system behavior simulation, called Power
Resource Manager which publishes information related to
Flow problem, in both static and dynamic regime (it is the
the time required to execute an atomic sub-task of an
most compute-intensive task of the OPSSA);
application and the cost per task expressed in dollars.
3. the controlling phase: the identification of preventive
Atomic sub-tasks are identified by symbolic names,
and corrective proper control actions able to reduce the
execution times are expressed in seconds, and have to
risk of system malfunctioning.
refer to the computational size of the application, if they
The master-slave solution is based on the distribution
depend on it.
to the slaves of the set of contingencies, each of which
can be analysed independently from each other (see figure
5.2
A Case-study
4).
In particular the master has the following main tasks:
- to collect static and dynamic data of the electric
The time minimization heuristic was tested on various
network necessary to perform the Power Flow problem;
applications written for the TMS Framework, among
-
to opportunely partition the set of credible
which matrix multiplication, finite integral calculation,
contingencies;
Mandelbrot set computation, image rendering, etc. For
- to distribute the set of contingencies among the slaves;
each of these applications, application complexity, atomic
- to collect the partial results replied by the slaves;
sub-task, partition and assembly policies were
- for each contingency, to perform the check of
individuated. For example for the multiplication of two
constraints and to generate an alarm in the case of
square matrices of n2 dimension, the application
constraint violation.
complexity corresponds to the number of rows, that is n,
The slaves, instead, have the following main tasks:
an atomic sub-task is the computation of a row of the
- to receive from the master the most recent state
result matrix, which can be calculated using as input data
estimation of the electrical grid and the sub-set of
the right matrix and the corresponding row of the left
contingencies to analyze;
matrix. The partition policy requires to distribute to all the
slaves the right matrix and to the j-th slave n
- to perform the system simulation, through the Power
j rows of the
left matrix whose indices correspond to those of the result
Flow problem solution, considering each assigned
matrix rows which the slave has to compute.
contingency;
An intense experimentation on a real test-bed,
- to reply to the master the system behavior evaluation
moreover, was conducted on the scientific application
for each assigned contingency.
called On-line Power System Security analysis (OPSSA)
Experiments on the OPSSA application execution were
which regards the security analysis of electrical networks
performed on the IEEE 118-nodes test network. Such
useful to control system operation when power system
network is composed of 118 nodes and the
operators increase the infrastructure exploitation to
experiments refer to potential 186 contingencies related to
maximize their profits [24].
the breaking of one of the 186 transmission lines.

---

contingency, which strongly depends on the
characteristics of the electrical network. For this reason
Acquire field
some preliminary experiments were conducted to evaluate
data
the mean execution time for the analysis of a contingency
Compute state
estimation
for the 118-nodes test network. The mean execution time
was evaluated for each machine, but, because the
Subdivide the
set of contingencies
measured values were very similar for resources with the
same configuration, we associated them to the resource
configuration.
Select the
. . . . . .
Select the
contingency 1
contingency N
The estimated execution times of a contingency
Compute the
Compute the
power flow
power flow
solution
solution
Client
Check the
Check the
constraints
constraints
[for each contingency]
*
Internet
YES
level 1
Any
Generate an
constraint
alarm
violated ?
R1
NO
COW front-end
R2
R3
R4
R1
R1
R1
Figure 4. Activity diagram of the OPSSA
R1
COW
level 2
application.
R1
R1
The execution time of the OPSSA would not exceed
R1
few minutes in order to predict in a useful time the impact
R1
of each credible contingency on the correct system
operation. For this reason in the experimentation we
chose as deadlines 15 minutes (900 seconds) and 20
Figure 5. The test-bed.
minutes (1200 seconds).
Resource
Clock
RAM
CPU
OS
5.3
The test-bed
Configuration
(M Hz)
(MB)
Intel Pentium II
350
128
Windows 2000
R1
(dual processor)
The OPSSA application was implemented for the TMS
R2
Intel Pentium III
350
256
Windows 98
Framework and was deployed on a real test-bed with a
R3
Intel Pentium III
350
256
Windows 2000
two-level topology composed of eight homogeneous
R4
Intel Pentium III
500
64
Windows 98
resources of a cluster, accessed through a front-end, and
three directly accessible heterogeneous computers (see
Table 1. Resource configuration.
figure 5). The configuration of the cluster resources and
of the front-end is indicated with R1 and those of the
three single computers are indicated with R2, R3 and R4
OPSSA Atomic
Re source
OPSSA Atomic
(see table 1). The client was executed on a notebook with
Sub-task
Configuration
Sub-task Cost
Exe cution Time
Intel Pentium III 650 MHz, 256 MB of RAM and running
R1
76.5 s
1.25 $
Windows 2000 operating system.
R2
75.0 s
4 $
The software platform to manage the distributed
R3
77.0 s
5 $
architecture was implemented by using Java provided by
R4
70.0 s
5 $
the JDK 1.4.1, HiMM version 1.1 and ProActive version
2.2.
For the OPSSA application, an atomic sub-task
Table 2. OPSSA atomic sub-task evaluation.
(further called task for brevity) is the analysis of a

---

analysis and related costs, (chosen with a nearly-random
to permit the assignment of all the tasks minimizing the
criterion) are summarized in table 2.
execution time of all the resources, without requiring
Because the proposed heuristic requires to characterize
adjustments. Even if the proposed algorithm requires an
a resource only with a mean execution time of the task
approximation of the calculated optimal real numbers of
and the related cost (which are data collected by the
tasks, in order to assign a whole number of tasks to each
resource broker from the Resource Managers), the cluster
resource, this figure shows as the algorithm is able to
has to be considered as an aggregate resource, with a
obtain quite similar execution times for each resource.
performance given by the mean execution time of the
The shift around the mean execution time is due to the
nodes divided by the number of nodes. As a consequence
rounding applied by the heuristic. As much different as
the cluster will be characterized by the following mean
the performance of resources are, as more its value is
execution time:
greater. In particular, in this case, the shift is about a
t
minute, which is the difference of execution times among
t
R1
.
9 56 s
COW
8
the resource COW and the other resources.
Figure 8 shows the distribution of the contingencies
Moreover the cost per task of the cluster is modelled as
among the resources, under maximum exploitation of
the cost of a cluster node multiplied by the number of
deadline and budget, considering 900 seconds as deadline
nodes, that is 10 $.
and different budget values.
5.4 Experimental
Results
100
90
Table 3 reports the execution times and expended
80
budgets predicted by the time minimization heuristic in
70
relation to a deadline of 900 seconds and a budget of
esource 60
1200 $.
The estimated execution time for the overall
50
R1
R2
computation is evaluated as the maximum value among
40
R3
COW
the execution times of each resource. As it is possible to
30
.
of tasks for R
observe, using this test-bed and budged, it is not possible
N 20
to execute 130 tasks within the deadline (the estimated
10
execution time is 910 seconds), that means that it is
possible to complete the analysis of only a part of all the
30
40
50
60
70
80
90
100
110
120
Total n. of tasks
possible contingencies.
Figure 6 shows the number of tasks assigned to each
Figure 6. Tasks assigned to each resource
resource varying the total amount of tasks to perform.
varying the total amount of tasks (D=900s,
Because of similar capabilities of resources R2, R3 and
B=1200$).
R4, the number of assigned tasks to each of them is very
similar. On the contrary, because the cluster (indicated
900
with COW) has the best performance with respect to the
others, it receives a greater amount of tasks, which in
800
particular increases with the total number of tasks to
700
perform.
e (s)
Figure 7 is related to the same conditions of the
600
previous figure and shows the estimated execution time
500
for each resource. In this scenario the budget is sufficient
R2
400
R3
Execution tim
R4
COW
300
Num ber of tasks
30
40
50
60
70
80
90
100
110
120
130
200
Execution
231
277
375
450
525
564
631
698
770
841
910
time (s)
30
40
50
60
70
80
90
100
110
120
Expended
249
337
420
503
586
675
758
841
935
1014
1096
N. of tasks
budget ($)
Figure 7. Estimated execution times for
Table 3. Estimated execution times and
each resource varying the total amount of
expended budgets (D=900s, B=1200$).
tasks (D=900s, B=1200$).

---