Keywords: Intergiciel hiérarchique, Déploiement, Modélisation, Grille

Modélisation pour le Déploiement d'un Intergiciel Hiérarchique sur une Plate-Forme Hétérogène Résumé : De nos jours, l'accès à des ressources distribuées peut être réalisé aisément en utilisant un intergiciel se basant sur une approche client/serveur. Différentes architectures existent pour de tels intergiciels. Ceux passant le mieux à l'échelle utilisent une hiérarchie d'agents. Déterminer quelle est la meilleure hiérarchie, c'est à dire celle qui fournira le meilleur débit au niveau des services, n'est pas une tâche aisée.

Nous proposons tout d'abord un modèle de calcul et de communication pour de tels intergiciels hiérarchiques. Notre modèle prend en compte le déploiement de plusieurs services au sein de la hiérarchie. Puis, en nous basant sur le modèle, nous proposons des algorithmes pour construire automatiquement la hiérarchie sur différents types de plates-formes: des plates-formes avec des communications homogènes et des puissances de calcul hétérogènes, ou des plates-formes complètement hétérogènes. Les algorithmes visent à offrir aux utilisateurs le meilleur ratio entre le débit demandé, et le débit fourni, tout en utilisant le moins de ressources possible. Pour chaque type de plate-forme, nous comparons notre modèle à des résultats expérimentaux obtenus avec l'intergiciel de grille Diet.

Introduction

Using distributed resources to solve large problems ranging from numerical simulations to life science is nowadays a common practice [START_REF] Berman | Grid Computing: Making the Global Infrastructure a Reality[END_REF][START_REF] Foster | The Grid 2: Blueprint for a New Computing Infrastructure[END_REF]. Several approaches exist for porting these applications to a distributed environment; examples include classic message-passing, batch processing, web portals and GridRPC systems [START_REF] Seymour | The end-user and middleware apis for GridRPC[END_REF]. In this last approach, clients submit computation requests to a metascheduler (also called agent) that is in charge of finding suitable servers for executing the requests within the distributed resources. Scheduling is applied to balance the work among the servers. A list of available servers is sent back to the client; which is then able to send the data and the request to one of the suggested servers to solve its problem.

There exists several grid middlewares [START_REF] Caniou | Recent Developments in Grid Technology and Applications, chapter High performance GridRPC middleware[END_REF] to tackle the problem of finding services available on distributed resources, choosing a suitable server, then executing the requests, and managing the data. Several environments, called Network Enabled Servers (NES) environments, have been proposed. Most of them share a common characteristic which is that they are built with broadly three main components: clients which are applications that use the NES infrastructure, agents which are in charge of handling the clients' requests (scheduling them) and of finding suitable servers, and finally computational servers which provide computational power to solve the requests. Some of the middlewares only rely on basic hierarchies of elements, a star graph, such as Ninf-G [START_REF] Tanaka | Ninfg: A reference implementation of RPC-based programming middleware for grid computing[END_REF] and NetSolve [START_REF] Arnold | Users' Guide to NetSolve V1.4.1[END_REF][START_REF] Casanova | Netsolve: a network server for solving computational science problems[END_REF][START_REF] Yarkhan | Gridsolve: The evolution of a network enabled solver[END_REF]. Others, in order to divide the load at the agents level, can have a more complicated hierarchy shape: WebCom-G [START_REF] Morrison | Webcom-G: grid enabled metacomputing[END_REF] and Diet [START_REF] Amar | Tunable scheduling in a GridRPC framework[END_REF][START_REF] Caron | DIET: A scalable toolbox to build network enabled servers on the grid[END_REF]. In this latter case, a problem arises: what is the best shape for the hierarchy?

Modelization of middlewares behavior, and more specifically their needs in terms of computations and communications at the agents and servers levels can be of a great help when deploying the middleware on a computing platform. Indeed, the administrator needs to choose how many nodes must be allocated to the servers, and how many agents have to be present to support the load required by the clients. Using as many nodes as possible, may not be the best solution: firstly it may lead to using more resources than necessary; and secondly this can degrade the overall performances. The literature do not provide much papers on the modelization and evaluation of distributed middleware. In [START_REF] Tanaka | Design, implementation and performance evaluation of gridrpc programming middleware for a large-scale computational grid[END_REF], Tanaka et al. present a performance evaluation of Ninf-G, however, no theoretical model is given. In [START_REF] Caron | Automatic deployment for hierarchical network enabled servers[END_REF][START_REF] Pushpinder Kaur Chouhan | Automatic middleware deployment planning on clusters[END_REF][START_REF] Chouhan | Automatic Deployment for Application Service Provider Environments[END_REF] the authors present a model for hierarchical middlewares, and algorithms to deploy a hierarchy of schedulers on clusters and grid environments. They also compare the model with the Diet middleware. However, a severe limitation in these latter works is that only one kind of service could be deployed in the hierarchy. Such a constraint is of course not desirable, as nowadays many applications rely on workflows of services. Hence, the need to extend the previous models and algorithms to cope with hierarchies supporting several services.

In this paper, we will mainly focus on one particular hierarchical NES: Diet (Distributed Interactive Engineering Toolbox). The Diet component architecture is structured hierarchically as a tree to obtain an improved scalability. Such an architecture is flexible and can be adapted to diverse environments, including arbitrary heterogeneous computing platforms. Diet comprises several components. Clients that use Diet infrastructure to solve problems using a remote procedure call (RPC) approach. SeDs, or server daemons, act as service providers, exporting functionalities via a standardized computational service interface; a single SeD can offer any number of computational services. Finally, agents facilitate the service location and invocation interactions of clients and SeDs. Collectively, a hierarchy of agents provides higher-level services such as scheduling and data management. These services are made scalable by distributing them across a hierarchy of agents composed of a single Master Agent (MA) (the root of the hierarchy) and several Local Agents (LA) (internal nodes).

Deploying applications on a distributed environment is a problem that has already been addressed. We can find in the literature a few deployment software: DeployWare [START_REF] Flissi | A generic deployment framework for grid computing and distributed applications[END_REF], ADAGE [START_REF] Lacour | Generic application description model: Toward automatic deployment of applications on computational grids[END_REF], TUNe [START_REF] Broto | Autonomic management policy specification in tune[END_REF], and GoDiet [START_REF] Caron | GoDiet: A deployment tool for distributed middleware on grid'5000[END_REF]. Their field of action ranges from single deployment to autonomic management of applications. However, none include intelligent deployment mapping algorithms. Either the mapping has to be done by the user, or the proposed algorithm is random or round-robin. Some algorithms have been proposed in [START_REF] Caron | Automatic deployment for hierarchical network enabled servers[END_REF][START_REF] Pushpinder Kaur Chouhan | Automatic middleware deployment planning on clusters[END_REF] to deploy a hierarchy of schedulers on clusters and grid environments. However, a severe limitation in these works is that only one kind of service could be deployed in the hierarchy. Such a constraint is of course not desirable, as nowadays many applications rely on workflows of services. Hence, the need to extend the previous models and algorithms to cope with hierarchies supporting several services.

The contribution of this paper is twofold. We first present a model for predicting the performance of a hierarchical NES on a heterogeneous platforms. Secondly, we present algorithms for automatically determining the best shape for the hierarchy, i.e., the number of servers for each services, and the shape of the hierarchy supporting these servers.

We first present in Section 2 the hypotheses for our model, then the model itself in Section 3 for both agents and servers. Then, we explain our approach to automatically build a suitable hierarchy on communication homogeneous/computation heterogeneous platforms in Section 4, and present experimental results. We then present, in Section 5 a genetic algorithm for automatically building a hierarchy on totally heterogeneous platforms, and also give some experimental results. Finally, we conclude this paper in Section 6.

Model Assumptions

Request Definition

Clients use a 2-phases process to interact with a deployed hierarchy. They submit a scheduling request to a Master Agent to find a suitable server in the hierarchy (scheduling phase), and then submit a service request (job) directly to the server (service phase). A completed request is one that has completed both the scheduling and service request phases and for which a response has been returned to the client. The throughput of a service is the number of completed requests per time unit the system can offer. We consider that a set R of services have to be available in the hierarchy. And that for each service i ∈ R, the clients aim at attaining a throughput ρ * i of completed requests per second. Figure 1 presents the scheduling and service phases. The example shows the following steps:

1. the client sends a request of type i (i = 2 in Figure 1); !"#$"#%&'(#&%"#$)*"&+ !"#$"#%&'(#&%"#$)*"&, -+.

-,.

-/.

-0.

-,. -,.

-/.

-1. 2. the request is forwarded down the hierarchy, but only to the sub-hierarchy that knows service i;

3. the SeDs perform performance predictions, and generate their response;

4. responses are forwarded up the hierarchy, and "sorted", i.e., the best choice is selected at each agent level;

5. the scheduling response is sent back to the client (the response contains a reference to the selected server);

6. the client sends a service request directly to the selected server;

7. the server runs the application and generates the results;

8. the results are directly sent back to the client.

Resource Architecture

We consider the problem of deploying a middleware on a fully connected platform G = (V, E, W, B): V is the set of nodes, E is the set of edges, w j ∈ W is the processing power in M f lops/s of node j, and the link between nodes j and j ′ has a bandwidth B j,j ′ ∈ B in M bit/s. We do not take into account contentions in the network. We also denote by N = |V | the number of nodes.

Remark 2.1 We consider that whatever the node they are running on, services and agents require a constant amount of computation, i.e., we consider the case of uniform machines where the execution time of an application on a processor is equal to a constant only depending on the machine, multiplied by a constant only depending on the application.

Deployment Assumptions

We consider that at the time of deployment we do not know the clients' locations or the characteristics of the clients' resources. Thus, clients are not considered in the deployment process and, in particular, we assume that the set of computational resources used by clients is disjoint from V , and that we will not consider client/servers direct communications in our model (phases 6 and 8 in Figure 1). This corresponds to the case where data required for the services is already present in the platform, and does not need to be sent by the clients. A valid deployment will always include at least the root-level agent and one server per service i ∈ R. Each node v ∈ V can be assigned either as a server for any kind of service i ∈ R, or as an agent, or left idle. Thus with |A| agents, |S| servers, and |V | total resources, |A| + |S| ≤ N .

Objective

We consider that we work in steady-state. The platform is loaded to its maximum. Thus, we do not take into account the phases when only a few clients are submitting requests to the system, but only the phase where the clients submit as many requests as the middleware is able to cope with. As we have multiple services in the hierarchy, our goal cannot be to maximize the global throughput of completed requests regardless of the kind of services, this would lead to favor services requiring only small amount of computing power to schedule and to solve them, and with few communications. Hence, our goal is to obtain, for each service i ∈ R, a throughput ρ i such that all services receive almost the same obtained throughput to requested throughput ratio:

ρi ρ * i
, of course we try to maximize this ratio, while having as few agents in the hierarchy as possible, so as not to use more resources than necessary.

3 Servers and Agents Models

"Global" Throughput

For each service i ∈ R, we define ρ schedi to be the scheduling throughput for requests of type i offered by the platform, i.e., the rate at which requests of type i are processed by the scheduling phase. We define as well ρ servi to be the service throughput. Lemma 3.1 The completed request throughput ρ i of type i of a deployment is given by the minimum of the scheduling and the service request throughput ρ schedi and ρ servi .

ρ i = min {ρ schedi , ρ servi } Proof: A completed request has, by definition, completed both the scheduling and the service request phases, whatever the kind of request i ∈ R. Case 1: ρ schedi ≥ ρ servi . In this case, requests are sent to the servers at least as fast as they can be processed by the servers, so the overall rate is limited by ρ servi .

Case 2: ρ schedi < ρ servi . In this case, the servers process the requests faster than they arrive. The overall throughput is thus limited by ρ schedi . Lemma 3.2 The service request throughput ρ servi for service i increases as the number of servers included in a deployment and allocated to service i increases.

INRIA

Hierarchy Elements Model

We now describe the model of each element of the hierarchy. We consider that a request of type i is sent down a branch of the hierarchy, if and only if service i is present in this branch, i.e., if at least a server of type i is present in this branch of the hierarchy. Thus a server of type i will never receive a request of type i ′ = i. Agents won't receive a request i if no server of type i is present in its underlying hierarchy, nor will it receive any reply for such a type of request. This is the model used by Diet.

Server model

We define the following variables for the servers. w prei is the amount of computation in M F lops needed by a server of type i to predict its own performance when it receives a request of type i from its parent. Note that a server of type i will never have to predict its performance for a request of type i ′ = i as it will never receive such a request. w appi is the amount of computation in M F lops needed by a server to execute a service. m reqi is the size in M bit of the messages forwarded down the agent hierarchy for a scheduling request, and m respi the size of the messages replied by the servers and sent back up the hierarchy. Since we assume that only the best server is selected at each level of the hierarchy, the size of the reply messages does not change as they move up the tree. Figure 2 presents the server model.

Server computation model

We suppose that a deployment with a set of servers S i completes N i requests of type i in a given time frame. Then, each server S j ∈ S i will complete N j i such that:

j∈Si

N j i = N i (1)
On average, each server S j has to do a prediction for N i requests, and complete N j i service requests during the time frame. Let T serverj compi be the time taken by the server S j ∈ S i to compute N j i requests and predict N i requests. We have the following equation:

T serverj compi = w prei .N i + w appi .N j i w j (2)
Now let's consider a time step T during which N i requests are completed. On this time step, we have:

∀i ∈ R, ∀j ∈ S i , T = w prei .N i + w appi .N j i w j (3)
From ( 3), we can deduce the number of requests computed by each server S j ∈ S i for all type of requests i ∈ R:

N j i = T.w j -w prei .N i w appi (4)
From equations ( 1) and ( 4), we can rewrite the time taken by the S i servers to process N i requests of type i:

j∈Si N j i = j∈Si T.w j -w prei .N i w appi N i = T × j∈Si w j w appi 1 + j∈Si wpre i wapp i N i = T × j∈Si w j w appi + |S i | .w prei T = N i × w appi + |S i | .w prei j∈Si w j (5)
Hence the average computation time for one request of type i:

T server compi = w appi + |S i | .w prei j∈Si w j (6)
and the service throughput for service i:

ρ comp servi = j∈Si w j w appi + |S i | .w prei (7)
Server communication model A server of type i needs, for each request, to receive the request, and then to reply. Hence Equations ( 8) and ( 9) represent respectively the time to receive one request of type i, and the time to send the reply to its parent. Communications time depends on the shape of the hierarchy, as the bandwidth is not the same over the platform. Thus, we denote by f j i the father of server S j ∈ S i . Server S j ∈ S i receive time for one request of type i:

T serverj recvi = m reqi B j,f j i (8)
Server S j ∈ S i reply time for one request of type i:

T serverj sendi = m respi B j,f j i (9)

INRIA

Service throughput Concerning the machines model, and their ability to compute and communicate, we consider the following models:

❼ Send or receive or compute, single port: a node cannot do anything simultaneously.

ρ servi = 1 max j∈Si T serverj recvi + T serverj sendi + T server compi , (10)
❼ Send or receive, and compute, single port: a node can simultaneously send or receive a message, and compute.

ρ servi = min 1 max j∈Si T serverj recvi + T serverj sendi , 1 T server compi (11)
❼ Send, receive, and compute, single port: a node can simultaneously send and receive a message, and compute.

ρ servi = min 1 max j∈Si max T serverj recvi , T serverj sendi , 1 T server compi (12)

Agent model

We define the following variables for the agents. w reqi is the amount of computation in M F lops needed by an agent to process an incoming request of type i. Let A be the set of agents. For a given agent A j ∈ A, let Chld j i be the set of children of A j having service i in their underlying hierarchy. Also, let δ j i be a Boolean variable equal to 1 if and only if A j has at least one child which knows service i in its underlying hierarchy. w respi Chld j i is the amount of computation in M F lops needed to merge the replies of type i from its Chld j i children. We suppose that this amount grows linearly with the number of children. Figure 3 presents the server model. Our agent model relies on the underlying servers throughput. Hence, in order to compute the computation and communication times taken by an agent A j , we need to know both the servers throughput ρ servi for each i ∈ R, and the children of A j . Agent computation model. The time for an agent A j to schedule all requests it receives and forwards,when the servers provide a throughput ρ servi for each i ∈ R, is given by Equation [START_REF] Pushpinder Kaur Chouhan | Automatic middleware deployment planning on clusters[END_REF].

T agentj comp = i∈R ρ servi .δ j i .w reqi + i∈R ρ servi .w respi Chld j i w j (13)
Agent communication model. Agent A j needs, for each request of type i, to receive the request and forward it to the relevant children, then to receive the replies and forward the aggregated result back up to its parent. We also need to take into account the variation in the bandwidth between the agent and its children. Let f j be the father of agent A j in the hierarchy. Equations ( 14) and ( 15) present the time to receive and send all messages when the servers provide a throughput ρ servi for each i ∈ R. Agent A j ∈ A receive time:

T agentj recv = i∈R ρ servi .δ j i .m reqi B j,f j + i∈R k∈Chld j i ρ servi .m respi B j,k (14)
Agent A j ∈ A send time:

T agentj send = i∈R ρ servi .δ j i .m respi B j,f j + i∈R k∈Chld j i ρ servi .m reqi B j,k (15)
We combine ( 13), [START_REF] Flissi | A generic deployment framework for grid computing and distributed applications[END_REF], and (15) according to the chosen communication / computation model (similarly to Equations ( 10), [START_REF] Casanova | Netsolve: a network server for solving computational science problems[END_REF], and ( 12)).

Lemma 3.3 The highest throughput a hierarchy of agents is able to serve is limited by the throughput an agent having only one child of each kind of service can support.

Proof: The bottleneck of such a hierarchy is clearly its root. Whatever the shape of the hierarchy, at its top, the root will have to support at least one child of each type of service (all messages have to go through the root). As the time required for an agent grows linearly with the number of children (see ( 13), ( 14) and ( 15)), having only one child of each type of service is the configuration that induces the lowest load on an agent.

Planning on Communication Homogeneous / Computation Heterogeneous Platforms

Given the models presented in the previous section, we propose a heuristic for automatic deployment planning on communication homogeneous/computation heterogeneous platforms. As we consider that we have homogeneous communications, we have ∀j, j ′ ∈ V, B j,j ′ = B. The heuristic comprises two phases. The first step consists in dividing N nodes between the services, so as to support the servers. The second step consists in trying to build a hierarchy, with remaining nodes, which is able to support the throughput generated by the servers. In

INRIA

this section, we present our automatic planning algorithm in three parts. In Section 4.1 we present how the servers are allocated nodes, then in Section 4.2 we present a bottom-up approach to build a hierarchy of agents, and present in Section 4.3 the whole algorithm. Finally, we give experimental results in Section 4.4.

Servers repartition

Our goal is to obtain for all services i ∈ R the same ratio

ρserv i ρ * i
. Algorithm 1 presents a simple way of dividing the available nodes to the different services. We iteratively increase the number of assigned nodes per services, starting by giving nodes to the service with the lowest

ρserv i ρ * i ratio.
We need to take into account the nodes' heterogeneity. Hence, we propose two heuristics: min-first which first give the less powerful nodes to the servers, and max-first which first give the more powerful nodes to the servers. Assign one more node to i: n, following the order of L, and compute the new ρ servi 8:

L a ← L + {n} 9:
if ρ servi ≥ ρ * i then 10:

ρ servi ← ρ * i 11:
S ← S -{i} 12:

S ← Sort services by increasing

ρserv i ρ * i 13: until |L a | = N or S = ∅ 14: return L a

Agents hierarchy

Given the servers repartition, and thus, the services throughput ρ servi , for all i ∈ R, we need to build a hierarchy of agents that is able to support the throughput offered by the servers. Our approach is based on a bottom-up construction: we first distribute some nodes to the servers, then with the remaining nodes we iteratively build levels of agents. Each level of agents has to be able to support the load incurred by the underlying level. The construction stops when only one agent is enough to support all the children of the previous level. In order to build each level, we make use of a mixed integer linear program (MILP): (LP 1 ). We first need to define a few more variables. Let k be the current level: k = 0 corresponds to the server level. For i ∈ R let n i (k) be the number of elements (servers or agents) obtained at step k, which know service i. For k ≥ 1, we recursively define new sets of agents. We define by M k the number of available resources at step k:

M k = M 1 -i∈R k-1
l=2 n i (l). For 1 ≤ j ≤ M k we define a j (k) ∈ {0, 1} to be a boolean variable stating whether or not node j is an agent in step k. a j (k) = 1 if and only if node j is an agent in step k. For 1 ≤ j ≤ M k , ∀i ∈ R, δ j i (k) ∈ {0, 1} defines whether of not node j has service i in its underlying hierarchy in step k. For the servers, k = 0, 1 ≤ j ≤ M 0 , ∀i ∈ R, δ j i (0) = 1 if and only if server j is of type i, otherwise δ j i (0) = 0. Hence, we have the following relation:

∀i ∈ R, n i (k) = M k j=1 δ j i (k). For 1 ≤ j ≤ M k , ∀i ∈ R, Chld j i (k) ∈ N is as previously the number of children of node j that know service i. Finally, for 1 ≤ j ≤ M k , 1 ≤ l ≤ M k-1 let c j l (k) ∈ {0, 1} be a boolean variable stating that node l in step k -1 is a child of node j in step k. c j l (k) = 1 if and only if node l in step k -1 is a child of node j in step k.
Using linear program (LP 1 ), we can recursively define the hierarchy of agents, starting from the bottom of the hierarchy.

Let's have a closer look at (LP 1 ). Lines (1), ( 2) and (3) only define the variables. Line (4) states that any element in level k -1 has to have exactly 1 parent in level k. Line (5) counts, for each element at level k, its number of children that know service i. Line [START_REF] Caniou | Recent Developments in Grid Technology and Applications, chapter High performance GridRPC middleware[END_REF] states that the number of children of j of type i cannot be greater than the number of elements in level k -1 that know service i, and has to be 0 if δ j i (k) = 0. The following two lines, ( 7) and ( 8), enforce the state of node j: if a node has at least a child, then it has to be an agent (line (7) enforces a j (k) = 1 in this case), and conversely, if it has no children, then it has to be unused (line (8) enforces a j (k) = 0 in this case). Line [START_REF] Caron | Modelization for the Deployment of a Hierarchical Middleware on a Homogeneous Platform[END_REF] states that at least one agent has to be present in the hierarchy. Line [START_REF] Caron | DIET: A scalable toolbox to build network enabled servers on the grid[END_REF] is the transposition of the agent model in the send or receive or compute, single port model. Note that the other models can easily replace this model in MILP (LP 1 ). This line states that the time required to deal with all requests going through an agent has to be lower than or equal to one second.

Finally, our objective function is the minimization of the number of agents: the equal share of obtained throughput to requested throughput ratio has already been cared of when allocating the nodes to the servers, hence our second objective that is the minimization of the number of agents in the hierarchy has to be taken into account.

Building the whole hierarchy

We do not detail the whole algorithm for building the hierarchy, as it is the same as the one presented in [START_REF] Caron | Modelization for the Deployment of a Hierarchical Middleware on a Homogeneous Platform[END_REF] for homogeneous platforms. So, we refer the reader to this research report.

INRIA Minimize M k j=1 a j (k) Subject to                                                                                                    (1) 1 ≤ j ≤ M k a j (k) ∈ {0, 1} (2) 1 ≤ j ≤ M k , ∀i ∈ R δ j i (k) ∈ {0, 1} and Chld j i (k) ∈ N (3) 1 ≤ j ≤ M k , 1 ≤ l ≤ M k-1 c j l (k) ∈ {0, 1} (4) 1
≤ l ≤ M k-1 M k j=1 c j l (k) = 1 (5) 1 ≤ j ≤ M k , ∀i ∈ R Chld j i (k) = M k-1 l=1 c j l (k).δ l i (k -1) (6) 1 ≤ j ≤ M k , ∀i ∈ R Chld j i (k) ≤ δ j i (k).n i (k -1) (7) 1 ≤ j ≤ M k , i ∈ R δ j i (k) ≤ a j (k) (8) 1 ≤ j ≤ M k a j (k) ≤ i∈R δ j i (k) (9)
M k j=1 a j (k) ≥ 1 (10) 1 ≤ j ≤ M k i∈R ρ servi ×   δ j i (k).w reqi + w respi Chld j i (k) w j + δ j i (k).m reqi + Chld j i (k) .m respi B + δ j i (k).m respi + Chld j i (k) .m reqi B   ≤ 1 (LP 1 )
RR n➦ 7309

Experiments

We ran experiments on Diet hierarchies containing two services: dgemm 100 and Fibonacci 30. We used two clusters on the Lyon site of Grid'5000: Sagittaire and Capricorne. Their respective computing power is w sagittaire = 3249M F lops and w capricorne = 2922M F lops. We used two strategies to sort the nodes that are divided between the services: either we sorted them by increasing w j (heuristic min-first) or by decreasing w j (heuristic max-first).

Theoretical model / experimental results comparison

We validate our model against real executions with the Diet middleware. Figures 4 and 5 present the comparison between theoretical and experimental throughput for respectively experiments with min-first and max-first heuristics. Table 1 presents the relative error for those experiments. As can be seen, the min-first heuristic is the most interesting one when dealing with large platforms. This can easily be explained: using less powerful nodes for servers leaves more powerful nodes for the agents, hence the maximum attainable throughput due to agents limitation is higher. Whatever the heuristic, we remain within 18.3% of the theoretical model.

Comparison with star graphs

On the tested platforms, our heuristics create hierarchies having up to three levels of agents. Is this really necessary, or would have a star graph, having the same SeD mapping, given the same or better results? Figure 6 presents the comparison between min-first and a star graphs having the same SeD distribution, and figure 7 present the comparison between max-first and star graphs having the same SeD distribution. As can be seen our approach clearly surpasses the simple star graph approach.

The fact that on Figure 7 the star graph throughput increases with 25-25 nodes, is easily explained by the number of SeDs this star graph has. As can be seen on Figure 11 (25-25 nodes) less SeDs are present than in Figure 10 (20-20 nodes). Thus, the MA is less loaded on the star graph obtained on 25-25 nodes, than on the star graph obtained on 20-20 nodes.

Hierarchy shape

INRIA !" !" !" !" !" ¡ ¡ ¡ ¡ ¡ ¡ ¡ !" !" !" !" ¡ ¡ ¡ ¡ %" ¡ ¡

Fully Heterogeneous Platforms

In this section we finally deal with a fully heterogeneous platform: each node j has a computing power of its own w j , and the communication links between any two nodes j, j ′ are possibly all different: B j,j ′ . Hence, the agents and servers models follow the general model presented in Section 3.

The problem when dealing with totally heterogeneous platforms is that we need information about both the location of the parent, and location of the children. Hence, the bottom-up approach we used so far won't be applicable, nor would be a top-down approach: we won't be able to build a level if we do not know the position of the parent in a bottom-up approach, and conversely we cannot build a level without knowing the position of the children in a top-down approach.

A Genetic Algorithm Approach

As we cannot use an iterative approach to build a hierarchy without risking to have to test all possible solutions, we took a totally different approach: we rely on a genetic algorithm to generate a set of hierarchies, then evolve them, and finally select the best one among them.

In order to define our genetic algorithm, we need to describe a few notions: the objective function, crossover and mutations, and finally the evaluation strategy.

Objective function

The objective function has to encode all the goals we aim at optimizing in a hierarchy. It also needs to be subject to an order relation. Many genetic algorithm frameworks require that the objective function is encoded on an integer or floating point variable.

Our goal is the same as previously: we aim at maximizing the minimum ρ i /ρ * , while minimizing the number of agents constituting the hierarchy. Hence our goal can be summarized with the following point of decreasing importance: (i) maximize min i∈R {ρ i /ρ * }, (ii) then maximize the second ratio, the third. . . , (iii) minimize the number of agents to support the maximum throughput (i.e., maximize N minus the number of agents). In order to encode all these points into a single value, we use the following encoding (presented Figure 12): if we are given a precision ǫ on each ρ i /ρ * i ratio, then we can encode them on 1/ǫ digits; moreover, as the maximum number of agents is N -1, we only need ⌈log 10 (N )⌉ digits to encode the number of agents. Hence, on the whole we need

R × 1/ǫ + ⌈log 10 (N )⌉ digits. X X X X X X X X X X X X X X X X X X ρ i /ρ i * x 1/ε sorted by increasing values N -NbAgents ...

Objective value to maximize

INRIA

Actually, in order to guide a bit more the genetic algorithm towards convergence, we added two more metrics that we wish to minimize at the end of the fitness value: the number of agents that do not have any children (in order to remove really useless elements) and the depth of the hierarchy (this shouldn't affect the throughput, but this impacts the response time of the hierarchy, and limits the formation of chains of agents).

Genotype

The genotype needs to encode the whole hierarchy: the parent/children relationship, and the type of each node (agent, server or unused). It can easily be encoded on two arrays of size N : one for encoding the type of the nodes, and one for encoding the parent/children relationship. The alleles, i.e., each value in the arrays, can have the following values. The type of a node can either be 0 if the node is unused, 1 if it is an agent, or i ∈ {2 . . . 2 + R} if the node is a server of type i -2. The parent of a node i can either be itself if the node is unused (i.e., type[i] = 0) or the MA, or the node number corresponding to the parent of i in the hierarchy. Genotypes are randomly generated when creating the first generation of individuals: nodes' types and relationship are randomly chosen in such a way that a valid hierarchy is created.

Crossover

We define a crossover between two hierarchies as follows. Crossovers are only made on the parent array. We randomly select two nodes (one on each hierarchy) and exchange the parent of both selected nodes. Figure 13 presents an example of crossover. Why not define a crossover which replaces a whole part of a hierarchy into another one? This approach works well for a small number of nodes, but has a far too big impact on the hierarchy shape on a large number of nodes. As an example, consider hierarchies H 1 and H 2 in Figure 13, suppose a crossover between node 6 in H 1 and node 1 in H 2 . Transferring node 6 into H 2 in place of node 1 would remove seven nodes, as node 6 is a server. Conversely, we cannot transfer node 1 in place of node 6 into H 1 , as node 1 is the root of the hierarchy, and thus a transfer would lead to a loop in the hierarchy.

Mutation

Mutations on a hierarchy can occur at different levels in the hierarchy. We define the following mutations, also presented in Figure 14:

❼ Hierarchy modification:

1. we randomly select a node to change its type. If the mutation changes the type from agent to unused or SeD, or from SeD to unused, then we remove the underlying hierarchy and modify the type of the node.

If the type changes from unused to agent or SeD, we randomly choose a parent among the available agents.

2. we randomly select a node that will choose a new parent among the available agents. We can end up with two hierarchies (if the new parent is the node itself), in this case we randomly select one of the two hierarchies, and delete the other.

❼ Pruning: a node is randomly selected, then its whole underlying hierarchy is deleted.

Hierarchy evaluation

In order to evaluate a hierarchy generated by our genetic algorithm, we first compute for all i ∈ R the throughput supported by the servers, we denote by ρ max i this throughput. Then, for each agent in the hierarchy, we compute the maximum throughput ρ i for each service supported by the agent, we use (LP 2 ) to compute ρ i .

Maximize

ρ 1 ρ max 1 Subject to                                (1) ∀i ∈ R 0 ≤ ρ i ≤ ρ max i (2) ∀i ∈ R, i = 1 ρ 1 ρ max 1 = ρ i ρ max i (3) i∈R ρ i .δ j i . w reqi w j + i∈R ρ i . Chld j i . w respi w j + i∈R ρ i .δ j i .m reqi B j,f j + i∈R k∈Chld j i ρ i .m respi B j,k + i∈R ρ i .δ j i .m respi B j,f j + i∈R k∈Chld j i ρ i .m reqi B j,k ≤ 1 (LP 2 ) INRIA 5.1.

Implementation and parameters

Genetic algorithms rely on quite a lot of different parameters. Each one of them can influence the quality of the result. Among them are the following:

❼ Selection method : when comparing x individuals, we need to choose which one should "survive." Different approaches exist: deterministic tournament, stochastic tournament, roulette or ranking. Our tests showed that the deterministic tournament was the one giving on average better results. Hence, we use this selection method in our experiments. When we force that the best parent replaces the weakest child if the child has a lower fitness, we talk about weak elitism. Weak elitism can possibly provide better solutions as it forces the algorithm to converge towards a locally good solution. However, it also reduces the population diversity, and thus, can lead to a local optimum. Our simulations tended to provide worst solutions when weak elitism was used, thus, in the following studies, we do not use it.

❼ Size of the population: with n machines, we varied the size of the population between n/4 and 2 × n. The worst results were always obtained for a size of n/4. The best results were obtained for populations having 5/4 × n and 2 × n. On average, better results were obtained for populations of sizes between 5/4 × n and 2 × n.

❼ Probability of crossover and mutation: crossover rate should generally be high, around 80%-90%, and mutation rate quite low, around 0.5%-1%. A very small mutation rate may lead to genetic drift, whereas a high one may lead to loss of good solutions. We chose set the mutation and crossover rates respectively to 1% and 80%.

We used the ParadisEO [START_REF] Cahon | Paradiseo: A framework for the reusable design of parallel and distributed metaheuristics[END_REF] framework to implement our genetic algorithm.

Quality of the Approach

Genetic algorithms mainly depend on stochastic processes, thus we need to assess the quality of the results. As we do not have any other algorithm for fully heterogeneous platforms, we compare our genetic algorithm with the heuristics proposed in Section 4 for computation heterogeneous platforms.

Comparison with computation heterogeneous, communication homogeneous algorithm

We compare our genetic algorithm (GA) with min-first and max-first. GA was run on 1000 generations, on a population having at least 50 individuals (or 2 × |V | if this is higher than 50). We used the deterministic tournament method of selection, and we ran 100 executions (100 seeds). Figure 15a and 15b respectively present the results for dgemm and Fibonacci services. As can be seen, even if on the mean GA do not obtain results as good as min-first or max-first, the best GA results closely follows the min-first heuristic. Table 2 presents the relative gain/loss obtained with the best solution of the genetic algorithm, compared to the min-first and max-first heuristics. As one can see, the loss is no bigger than 15%, and it gives better results than max-first for the larger platform. This confirms that our approach can be effective: even if one run of GA is not sufficient to obtain the best result, taking the best hierarchy over a few runs of GA can give us good results. Note that this is often the case with genetic algorithms, as it is an exploratory method. We are quite confident that the performance loss obtained with the GA solutions can be reduced by fine tuning the GA parameters.

Initialization difference

We also compared the results of the genetic algorithm for different initialization strategies. We compared four different strategies:

❼ Random: we first randomly choose the number of nodes for each service, they are mapped on random nodes. Then, we create a random number of agents, and finally we just connect everything randomly, but in a way that creates a valid hierarchy. This is the initialization method used in the previous section.

❼ min-first or max-first: we use the random initialization for all but one hierarchy. We initialize this latter with the hierarchy found by min-first or max-first (this of course is only possible for a communication homogeneous platform).

❼ star-graph: we randomly choose the type of each nodes, and ensure that only one can be an agent. Then elements are connected as a star graph under the agent.

Figures 16a and 16b present the results. The star-graph gives the worst results, as new levels of hierarchy can be created only through mutations, and they do not occur often. Without much surprise, the min-first and max-first initialization give the best results as they are guided by the result of the bottomup algorithm. Finally, the random initialization give results that are in between min-first and max-first on the mean, but which best result is almost as good as min-first method. These results also assess the effectiveness of our approach, as starting from totally random hierarchies, we obtain results as good as with the min-first heuristic. RR n➦ 7309

Experiments

We ran experiments on Diet hierarchies, with the same services as before: dgemm 100 and Fibonacci 30. We used three clusters present on three different sites of Grid'5000: Sagittaire in Lyon, Chti in Lille and Paradent in Rennes. Their respective computing power is w sagittaire = 3249M F lops, w Chti = 3784M F lops and w P aradent = 4378M F lops. Figure 17 present the comparison between theoretical and experimental throughput, and Table 3 presents the relative error. As can be seen, the experiments follow the model. Even though the error can be quite big for small platforms (less than 10 nodes), the performance prediction becomes more accurate for larger platforms, as the relative error remains lower than 16%. The higher errors obtained for small platforms can be explained by the fact that the platform benchmarks have been done by stressing the network and machines. This stress is more easily attained when many nodes are involved in the experiments. Figure 18 presents the shape of the hierarchy obtained for a 17-17-16 platform. As can be seen, not all the available nodes are used: as previously, adding more nodes does not necessarily provide better performances as it tends to overload the agents. Blue nodes are on the Chti cluster, red ones on Paradent, and the white ones on Sagittaire.

Conclusion

In this paper we presented a computation and communication model for hierarchical middleware, when several services are available in the middleware. We proposed algorithms to find a hierarchy that gives the best obtained throughput to requested throughput ratio for all services on two different kinds of platforms: communication homogeneous/computation heterogeneous platforms, and fully heterogeneous platforms. The algorithm for communication homogeneous platforms uses a bottom-up approach, and is based on a linear program to successively determine levels of the hierarchy. The algorithm for totally heterogeneous platforms relies on a genetic algorithm. Our experiments on a real middleware, Diet, show that the obtained throughput closely follows what our model predicts and that both approaches (bottom-up algorithm, and genetic algorithm) provide excellent performances. We clearly showed that they add new levels of agents whenever required, and that it outperforms the classical approach of deploying the middleware as a balanced star graph.

Acknowledgment

Experiments presented in this paper were carried out using the Grid'5000 experimental testbed, being developed under the INRIA ALADDIN development action with support from CNRS, RENATER and several Universities as well as other funding bodies (see https://www.grid5000.fr).

  $"#%&'(#&%"#$)*"&+ !"#$"#%&'(#&%"#$)*"&,

Figure 1 :

 1 Figure 1: Scheduling and service phases.

Figure 2 :

 2 Figure 2: Server model parameters.

Figure 3 :

 3 Figure 3: Agent model parameters.

Algorithm 1

 1 Servers repartition Require: L: list of available nodes Ensure: L a : list of nodes allocated to the servers 1: S ← list of services in R 2: L a ← ∅ 3: N ← |L| 4: L ← L sorted according to min-first or max-first heuristic 5: repeat 6:i ← first service in S 7:

Figure 4 :

 4 Figure 4: dgemm 100, Fibonacci 30 theoretical and experimental throughput, with min-first heuristic.

Figure 5 :

 5 Figure 5: dgemm 100, Fibonacci 30 theoretical and experimental throughput, with max-first heuristic.

Figures 8 , 9 ,

 89 Figures 8, 9, 10 and 11 give an example of the shape of the hierarchy generated by respectively min-first on a 20-20 and 25-25 platform, and max-first on a 20-20 and 25-25 nodes platform. Red nodes are on the Sagittaire cluster, white nodes on the Capricorne cluster. "D" stands for dgemm, and "F" stands for Fibonacci.

Figure 6 :

 6 Figure 6: Comparison min-first with a star graph with the same SeD distribution.

Figure 7 :Figure 8 :

 78 Figure 7: Comparison max-first with a star graph with the same SeD distribution.

Figure 9 :Figure 10 :Figure 11 :

 91011 Figure 9: min-first: 25-25.

Figure 12 :

 12 Figure 12: Objective value encoding.

Figure 13 :

 13 Figure 13: Crossover. Colored nodes are the one selected for crossover, within hierarchy elements represent the nodes' number.

Figure 14 :

 14 Figure 14: Mutations. Colored node has been selected for mutation. Hexagons are agents, and circles are servers.

Figure 15 :

 15 Figure 15: Comparison genetic algorithm results with min-first and max-first results.

Figure 16 :

 16 Figure 16: Different methods of initialization.

Figure 17 :

 17 Figure 17: dgemm 100, Fibonacci 30 theoretical and experimental throughput, with genetic algorithm approach.

Figure 18 :

 18 Figure 18: Hierarchy shape for a 17-17-16 platform.

Table 1 :

 1

	Experiment		Number of nodes
		1-2	2-3	5-5 10-10 15-15 20-20 25-25
	min-first	dgemm Fibonacci 4.1% 0.3%	5.2% 5.1% 10.2% 6.1%	3.2% 9.7%	3.9% 10.0%	2.9% 10.6%	4.20% 11.0%
	max-first	dgemm Fibonacci 4.6% 10.8% 12.7% 2.1% 0.1% 7.0%	7.7% 12.8%	8.9% 18.3%	2.3% 4.5%	3.8% 3.0%

Relative error, using min-first and max-first heuristics.

Table 2 :

 2 Genetic algorithm gains/loss compared to the min-first and max-first heuristics. A positive number denotes a gain, whereas a negative one denotes a loss.

  13-14-13 17-17-16

	dgemm	5.42%	2.29% 14.26% 0.33%	4.44%	11.73%	3.12%
	Fibonacci 98.63% 35.70%	8.16% 4.96%	4.91%	10.53%	15.95%

Table 3 :

 3 Relative Error, using genetic algorithm.

RR n➦ 7309