Eddy Caron

Benjamin Depardon

Frédéric Desprez

Modelization for the Deployment of a Hierarchical Middleware on a Homogeneous Platform

Keywords: Hierarchical middleware, Deployment, Modelization, Grid Intergiciel hiérarchique, Déploiement, Modélisation, Grille

Accessing the power of distributed resources can nowadays easily be done using a middleware based on a client/server approach. Several architectures exist for those middlewares. The most scalable ones rely on a hierarchical design. Determining the best shape for the hierarchy, the one giving the best throughput of services, is not an easy task. We first propose a computation and communication model for such hierarchical middleware. Our model takes into account the deployment of several services in the hierarchy. Then, based on this model, we propose an algorithm for automatically constructing a hierarchy. This algorithm aims at offering the users the best obtained to requested throughput ratio, while providing fairness on this ratio for the different kind of services, and using as few resources as possible. Finally, we compare our model with experimental results on a real middleware called 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 meta-scheduler (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 | Ninf-g: 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 roundrobin. 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 homogeneous platform. As we will see this model can easily be applied to a computation heterogeneous platform. Secondly, we present an algorithm 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 in Section 4. We then compare the behavior of the Diet middleware with the model in Section 5. Then, we present, in Sections 6 and 7 the platform and Diet elements benchmarks necessary for the experiments. Finally, we compare the theoretical results with experimental results in Section 8, before concluding.

Model assumptions

Request definition. Clients use a 2-phases process to interact with a deployed hierarchy: they submit a scheduling request to the agents to find a suitable server in the hierarchy (the scheduling phase), and then submit a service request (job) directly to the server (the 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. 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 seconds.

Resource architecture. In this paper we will focus on the simple case of deploying the middleware on a fully homogeneous, fully connected platform G = (V, E, w, B), i.e., all nodes' processing power are the same: w in M f lops/s, and all links have the same bandwidth: B in M b/s (see Figure 1. We do not take into account contentions in the network. 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 . 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. Objective. 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 power for scheduling and solving, 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 , while having as few agents in the hierarchy as possible, so as not to use more resources than necessary.

3 Hierarchy model

Overall 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.

Hierarchy elements model

We now precise 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 j = i. Agents will not 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 j = i as it will never receive such requests. 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 b 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.

Server computation model. Let's consider that we have n i servers of type i, and that n i requests of type i are sent. On the whole, the n i servers of type i require ni.wpre i +wapp i w time unit to serve the n i requests: each server has to compute the performance prediction n i times, and serve one request. Hence, on average, the time to compute one request of type i is given by Equation 1.

T server compi = w prei + wapp i ni w (1)
Thus, the service throughput for requests of type i is given by the following formula, note that ρ comp servi is the service throughput without taking into account communications:

ρ comp servi = w w prei + wapp i ni (2)
Lemma 3.3 ρ comp servi tends to w wpre i as n i grows larger.

Server communication model. A server of type i needs, for each request, to receive the request, and then to reply. Hence Equations 3 and 4 represent respectively the time to receive one request of type i, and the time to send the reply to its parent.

T server recvi = m reqi B (3) T server sendi = m respi B ( 4
)
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 T server recvi + T server sendi + T server compi (5)
• Send or receive, and compute, single port: a node can simultaneously send or receive a message, and compute.

ρ servi = min 1 T server recvi + T server sendi , 1 T server compi (6)
• Send, receive, and compute, single port: a node can simultaneously send and receive a message, and compute.

ρ servi = min 1 T server recvi , 1 T server sendi , 1 T server compi (7)

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. 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 children having 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. This amount grows linearly with the number of children. 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 a request it receives and forwards is given by Equation 8.

T agentj comp = i∈R ρ servi .δ j i .w reqi + i∈R ρ servi .w respi Chld j i w (8)
Agent communication model. Agent A j needs, for each request of type i, to receive the request and forwards it to the relevant children, then to receive the replies and forward the aggregated result back up to its parent. Hence Equations 9 and 10 present the time to receive and send all messages when the servers provide a throughput ρ servi for each i ∈ R.

T agentj recv = i∈R ρ servi .δ j i .m reqi + i∈R ρ servi . Chld j i .m respi B (9)
T agentj send

= i∈R ρ servi .δ j i .m respi + i∈R ρ servi . Chld j i .m reqi B ( 10
)
We combine ( 8), [START_REF] Caron | DIET: A scalable toolbox to build network enabled servers on the grid[END_REF], and (10) according to the chosen communication / computation model (Equations ( 5), [START_REF] Caniou | Recent Developments in Grid Technology and Applications, chapter High performance GridRPC middleware[END_REF], and ( 7)).

Lemma 3.4 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 [START_REF] Caron | GoDiet : A deployment tool for distributed middleware on grid'5000[END_REF], [START_REF] Caron | DIET: A scalable toolbox to build network enabled servers on the grid[END_REF] and [START_REF] Casanova | Netsolve: a network server for solving computational science problems[END_REF]), having only one child of each type of service is the configuration that induces the lowest load on an agent.

Automatic planning

Given the models presented in the previous section, we propose a heuristic for automatic deployment planning. 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 the |V | -N remaining nodes, which is able to support the throughput generated by the servers. In 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 finally in Section4.3 we present the whole algorithm.

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.

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 i ← first service in S 5:

Assign one more node to i, and compute the new ρ servi 6:

n ← n + 1 7: if ρ servi ≥ ρ * i then 8: ρ servi ← ρ * i 9:
S ← S -{i} 10:

S ← Sort services by increasing

ρserv i ρ * i 11: until n = N or S = ∅ 12:
return n 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): (L 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 - k-1 l=1 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 (L 1 ), we can recursively define the hierarchy of agents, starting from the bottom of the hierarchy.

Let's have a closer look at (L 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 | DIET: A scalable toolbox to build network enabled servers on the grid[END_REF] states that at least one agent has to be present in the hierarchy. Line [START_REF] Casanova | Netsolve: a network server for solving computational science problems[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 (L 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.

Remark 4.1 In order to improve the converge time to an optimal solution for linear program (L 1 ), we can add the following constraint:

a 1 (k) ≥ a 2 (k) • • • ≥ a M k (k) (11) 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 i (k).m reqi + Chld j i (k) .m respi B + δ j i (k).m respi + Chld j i (k) .m reqi B   ≤ 1 (L 1 )
This states that only the first nodes can be agents. This prevents the solver from trying all swapping possibilities when searching a solution. We can safely add this constraint, as we suppose that we have a homogeneous platform.

Building the whole hierarchy

So far, we did not talk about the repartition of the available nodes between agents and servers. We will now present the whole algorithm for building the hierarchy.

Maximum attainable throughput per service. Whatever the expected throughput for each service is, there is a limit on the maximum attainable throughput. Given Equations ( 8), ( 9) and [START_REF] Casanova | Netsolve: a network server for solving computational science problems[END_REF], and the fact that a hierarchy must end at the very top by only one agent, the maximum throughput attainable by an agent serving all kinds of services (which is the case of the root of the hierarchy), is attained when the agent has only one child of each service (see Lemma 3.4). Hence, the maximum attainable throughput for each service, when all service receive the same served to required throughput ratio, from the agents' point of view is given by linear program (L 2 ) which computes ρ max servi for i ∈ R, the maximum attainable throughput for each service i that an agent can offer under the assumption that all services receive an equal share.

Maximize µ Subject to                    (1) ∀i ∈ R µ ≤ ρ max servi ρ * i and µ ∈ [0, 1], ρ max servi ∈ [0, ρ * i ] (2) ∀i, i ′ ∈ R ρ max servi ρ * i = ρ max serv i ′ ρ * i ′ (3) 1 ≤ j ≤ M k i∈R ρ max servi × w reqi + w respi w + 2.m reqi + 2.m respi B ≤ 1 (L 2 )
When building the hierarchy, there is no point in allocating nodes to a service i if ρ servi gets higher than ρ max servi . Hence, whenever a service has a throughput higher than ρ max servi , then we consider that its value is ρ max servi when building the hierarchy. Thus, lines 7 and 8 in Algorithm 1 become:

7: if ρ comp servi ≥ min ρ * i , ρ max servi then 8: ρ servi ← min ρ * i , ρ max servi
Building the hierarchy. Algorithm 2 presents how to build a hierarchy, it proceeds as follows.

We first try to give as many nodes as possible to the servers (line 4 to 7), and we try to build a hierarchy on top of those servers with the remaining nodes (line 8 to 24). Whenever building a hierarchy fails, we reduce the number of nodes available for the servers (line 24, note that we can use a binary search to reduce the complexity, instead of decreasing by one the number of available nodes). Hierarchy construction may fail for several reasons: no more nodes are available for the agents (line 10), (L 1 ) has no solution (line 12), or only chains of agents have been built, i.e., each new agent has only one child (line 20). If a level contains agents with only one child, those nodes are set as available for the next level, as having chains of agents in a hierarchy is useless (line 23).

Finally, either we return a hierarchy if we found one, or we return a hierarchy with only one child of each type i ∈ R, as this means that the limiting factor is the hierarchy of agents. Thus, only one server of each type of service is enough, and we cannot do better than having only one agent.

Correcting the throughput. Once the hierarchy has been computed, we need to correct the throughput for services that were limited by the agents. Indeed, the throughput computed using (L 2 ) may be too restrictive for some services. The values obtained implied that we had effectively an equal ratio between obtained throughput over requested throughput for all services, which may not be the case if a service requiring lots of computation is deployed alongside a service requiring very few computation. Hence, once the hierarchy is created, we need to compute what is really the throughput that can be obtained for each service on the hierarchy. To do so, we simply use our agent model, with fixed values for ρ servi for all i ∈ R such that the throughput of i is not limited by the agents, and we try to maximize the values of ρ servi for all services that are limited by the agents. We use linear program L 3 and Algorithm 3 for this purpose. Use Algorithm 1 to find the server repartition with N nodes 5:

nbU sed ← number of nodes used by Algorithm 1

6: M 0 ← nbU sed 7:
Set all variables: n i (0), a j (0), δ j i (0), Chld j i (0) and c j l (0)

8: k ← 1 9: M k ← |V | -nbU sed 10:
while M k > 0 and not Done do

11:
Compute level k using linear program (L 1 )

12:

if level k could not be built (i.e., (L 1 ) failed) then availN odes ← M k 16:

M k ← M k j=1 a j (k) // Get
if nbChains == M k-1 then 21:
break// This means we added 1 agent over each element at level k -1

22: k ← k + 1 23: M k ← availN odes -M k-1 + nbChains 24: N ← nbU sed -1 25: if Done then 26:
return the hierarchy built with (L 1 ) without chains of agents 27: else 28: return a star graph with one agent and one server of each type i ∈ R

Algorithm 3 Correct Throughput 1: R agLim ← i ∈ R such that service i is "agent limited" 2: Ag ← set of agents per level 3: while R agLim = ∅ do 4: µ, {ρ max i } ← Solve linear program (L 3 ) 5: Find i ∈ R agLim such that µ = ρ max i ρ * i 6: ρ servi ← ρ max i 7: R agLim ← R agLim -{i} Maximize µ Subject to                                                                        (1) ∀i ∈ R agLim µ ∈ [0, 1], µ ≤ ρ max i ρ * i and 0 ≤ ρ max i ≤ ρ servi (2) ∀k, ∀j ∈ Ag[k] i∈R-RagLim ρ servi . δ j i (k).w reqi + w respi Chld j i (k) w + i∈RagLim ρ max i . δ j i (k).w reqi + w respi Chld j i (k) w + i∈R-RagLim ρ servi . δ j i (k).m reqi + Chld j i (k) .m respi B + i∈RagLim ρ max i . δ j i (k).m reqi + Chld j i (k) .m respi B + i∈R-RagLim ρ servi . δ j i (k).m respi + Chld j i (k) .m reqi B + i∈RagLim ρ max i . δ j i (k).m respi + Chld j i (k) .m reqi B ≤ 1 (L 3 )
In (L 3 ), Equation ( 1) states that µ is the minimum of all ratios, (2) states that value of ρ max i cannot be greater than the throughput that is offered at the server level. The following equations ensure that bandwidth and computing power aren't violated.

A few discussion about this model

Reducing complexity The problem of using an MILP representation for our problem, is that the time required to compute the solution may grow exponentially with the number of nodes. Hence, if dealing with large number of nodes, we can reduce the time spent in searching the hierarchy of agents by first constructing a few homogeneous sub-hierarchies, i.e., hierarchies within which only one service is present, using d-ary trees (maybe not complete d-ary trees, but only some of the lower levels, and keeping only nodes that are fully loaded, i.e., where the degree d is attained). Doing so will reduce the number of levels we will need to build using MILP, and should give a good solution.

Messages without a fixed size In this model, we supposed that the size of the reply messages was fixed, i.e., that whatever the number of servers, the hierarchy always returns only one choice to the client. We could also modify our model in the case where the size of return messages in the hierarchy grows linearly with the number of servers found so far. The middleware could also return to the client the full list of servers. Hence, at each level of the hierarchy the reply message would grow. This can easily be taken into account in our model. Let Cpt j i (k) be the number of servers of type i in the hierarchy under element j at level k. For level k = 0 we set Cpt j i (0) = 1 if node j is a server of type i, otherwise we set Cpt j i (0

) = 0. For k > 0, i ∈ R, 1 ≤ j ≤ M k we have Cpt j i (k) = M k-1 l=1 Cpt l i (k -1) × c j l (k)
. Then, we would need to change the equations for the sending and receiving time at the agent level with the following ones:

i∈R ρ servi .δ j i (k).m reqi + i∈R ρ servi .m respi . M k-1 l=1 c j l (k).Cpt l i (k -1) B ( 12
) i∈R ρ servi .m respi . M k-1 l=1 c j l (k).Cpt l i (k -1) + i∈R ρ servi . Chld j i (k) .m reqi B ( 13
)
Extending the model to heterogeneous machines. The model and the algorithms can easily be extended to support the case where each machine has a different computing power w j , but are still connected with the same bandwidth B. Indeed, we only need to replace w by w j in all the previous agents equations, replace equation ( 1) by wapp i +|Si|.wpre i P j∈S i wj (with S i the set of servers of type i), and modify Algorithm 1 so as to take into account the power of the nodes (for example by sorting the nodes by increasing power) to be able to deal with heterogeneous machines interconnected with a homogeneous network. Note that in this model Remark 4.1 is no longer relevant.

Comparing the model with the behavior of Diet

Diet follows the model presented in Section 3: whenever a requests arrives at an agent, it is forwarded only to its underlying children that declared having this service in their underlying hierarchy. We ran some experiments to assess the fact that an agent forwards only to the rightful children a request.

We deployed two kinds of hierarchies, and used TAU [?] to retreive the number of instructions executed per request per LA. The first one has 1 MA, 2 LA and under each LA n SeD, but only 1 service is present under each LA, see Figure 2. The second hierachy has 1 MA, 1 LA and n SeD per service (we used 2 services), note that in this case, the LA's degree is twice as large as the degree of each LA in the first case, see Figure 3. We then made 10 requests per service. with one request is almost the same for each LA, whatever the platform used. If Diet was not following the model depicted in Section 3.2, but instead would forward the requests to all children, the work required for the LA of the second hierarchy should have been twice as much as for the LA of the first hierarchy (as the degree is twice as large).

In platform 1, each LA received only 10 requests, whereas in platform 2, the LA received 20 requests.

6 Benchmarking the platform

Platform

We used a 79-nodes cluster present in the Grid'5000 experimental platform [START_REF] Bolze | Grid'5000: a large scale and highly reconfigurable experimental grid testbed[END_REF]: the cluster Sagittaire from the Lyon site. Each node has an AMD Opteron 250 CPU at 2.4GHz, with 1MB of cache and 2GB of memory. All those nodes are connected on a Gigabit Ethernet network supported by an Extreme Networks Blackdiamond 8810. Hence, for this platform our fully homogeneous, fully connected platform assumption holds (we ran bandwidth tests using iPerf1 to confirm that there really was a Gigabit network between any two machines).

We measured the computing capacity of the nodes with HPL2 (along with the Altas3 version of BLAS) we found a mean value of 3.249 Gflops.

Impact of the bandwidth on the model

The bandwidth the message receive is not necessarily the maximum bandwidth attainable on the cluster. Indeed, in order to have the full links capacity, one has to transmit large messages. In our case messages in the hierarchy are quite small (a few kilobits), hence we need to determine the bandwidth received by the messages. We used NWS4 to determine the bandwidth when sending messages of different size. Figures 6, 7 and 8 show the impact of the bandwidth on the model: the red and green line present respectively the theoretical dgemm and Fibonacci throughput, and the red and green points represent respectively the experimental throughput for dgemm and Fibonacci during the experiment. Figure 6 presents the results obtained when using a bandwidth of 1033M b.s -1 in the model: maximum bandwidth measured on the cluster. Figure 7 presents the results for a bandwidth of 53M b.s -1 bandwidth measured with NWS for 1kb messages. And finally, Figure 8 presents the results for a bandwidth of 186.7M b.s -1 : bandwidth measured with NWS for 8kb messages, i.e., the buffer size just above the messages size (around 5kb), the minimum buffer size of the system is 4kb, hence when using messages of about 5kb, the system buffer increases up to 8kb. As can be seen, the results with 186.7M b.s -1 are the most accurate.

Benchmarking the Diet elements

Throughout the rest of the paper, we will denote by dgemm x the fact of calling the dgemm service on a x × x matrix, and Fibonacci x the fact of calling the Fibonacci service for computing the Fibonacci number for n = x.

Computation/communication models versus experiments

Messages

We used tcpdump and wireshark to analyze the messages sent between the agent and the SeD.

SeD

In order to benchmark the SeDs, we used a two steps approach. The first step consisted in finding what was the required number of clients to load a SeD (i.e., obtaining the maximum throughput, without having too much variations on the throughput value). Then, we deploy a new platform, and launch the number of clients found in the previous step, and determine using Diet statistics, the model parameters model. We deploy a platform composed of 1 MA, 1 LA and 1 SeD. Then, we run threaded clients to load the platform. A threaded client launches a new thread every second until attaining its total number of allowed thread. We launch a client, then wait for it to run all its thread, and wait 20 seconds more for the throughput to stabilize, then we run a new client on another node. We run enough clients to fully load the platform. Once all the clients are run, we let the system work for 60 seconds before cleaning the platform. The number of threads per client depends on the type of service (for a dgemm on a large matrix, a client cannot have too many threads, otherwise it will start to swap).

7.3.1

Determining the necessary number of clients for dgemm dgemm 10 we ran 5 clients, each having 40 threads. Figure 13 presents the throughput. The maximum throughput is attained at about 90s. Hence, the maximum number of threads we need is 70 spread on two nodes. dgemm 100 we ran 10 clients, each having 20 threads. Figure 14 presents the throughput. The maximum throughput is attained at about 80s. Hence, the maximum number of threads we need is 40 spread on two nodes. dgemm 500 we ran 40 clients, each having 5 threads. Figure 15 presents the throughput. The maximum throughput is attained at about 70s. Hence, the maximum number of threads we need is 15 spread on 3 nodes. FIBO 30 we ran 4 clients, each having 50 threads. Figure 17 presents the throughput. The maximum throughput is attained at about 50s. Hence, the maximum number of threads we need is 50 on 2 nodes.

FIBO 40 we ran 4 clients, each having 50 threads. Figure 18 presents the throughput. The maximum throughput is attained at about 10s. Hence, the maximum number of threads we need is 10 on 1 nodes.

Benchmarking

We then ran the previously found number of clients for each kind of service, and let them send requests for 60 seconds. During this time, we collected statistics on the time required by the SeD to process a request, and to solve a request.

Agent

We deploy a platform composed of 1 MA, 1 LA and n SeD. Then we run threaded clients to load the platform. We launch all clients, then wait 10s for the clients to finish to run their threads, then we conduct the measurements for 60s. As we aim at loading the agent, we need lots of requests. Hence, we run only small services at the SeD level: the client call a dgemm on a 10 × 10 matrix, or request to solve the Fibonacci number for x = 20. The number of threads per client depends on the type of service, and is set to 170 threads on 5 nodes for FIBO 20,and

Experimental Results

In order to validate our model, we conducted experiments with Diet on the French experimental testbed Grid'5000 [START_REF] Bolze | Grid'5000: a large scale and highly reconfigurable experimental grid testbed[END_REF]. After a phase of benchmarking for the Diet elements, the services (dgemm [START_REF] Dongarra | Basic linear algebra subprograms technical forum standard[END_REF] and computation of the Fibonacci number using a naive algorithm), and the platform; we generated hierarchies for a number of nodes ranging from 3 to 50 (even though the algorithm is based on an MILP, it took only a few seconds to generate all the hierarchies).

Our goal here is to stress Diet, so we use relatively small services. We compared the throughput measured and predicted for various services combinations:

• dgemm 100 × 100 and Fibonacci 30 (medium size services)

• dgemm 10 × 10 and Fibonacci 20 (small size services)

• dgemm 10 × 10 and Fibonacci 40 (small size dgemm, large size Fibonacci)

• dgemm 500 × 500 and Fibonacci 20 (large size dgemm, small size Fibonacci)

• dgemm 500 × 500 and Fibonacci 40 (large size dgemm, large size Fibonacci) 8 sums up the results. The results are quite close to the expected throughput, even when the hierarchy as two levels of agents: for 20 nodes, the agent hierarchy contained 1 MA and 3 LA. Over 20 nodes, the algorithm returned the same hierarchy as with 20 nodes. Figure 25 presents graphically the results of Table 8. No No .

Figure 26 presents the results when requesting concurrently services dgemm 10 and Fibonacci 20. Table 8 sums up the results. For really small services such as presented here, the error increases greatly. Clearly here the problem lies in a bad estimation of the costs incurred by this kind of requests, i.e., really small requests in terms of required computation at the server level are harder to benchmark correctly. The limiting factor is the agent, hence, over 3 nodes the hierarchy always contained only 3 nodes: 1 MA and 1 SeD for each service. No .

Figures 27 to 33 present the results when requesting concurrently services dgemm 10 and Fibonacci 40. Table 10 sums up the results. The Fibonacci service closely follows the model, whereas the DGEMM service parts from it due to benchmarking problems. Figure 34 presents graphically the results of Table 10. problems. dgemm results diverges a bit from the theoretical predictions. This is certainly due to the fact that our model does not explicitly take into account the client/server communications (they are implicitly taken into account in the "time" required by the server to serve a request).

Figure 42 presents graphically the results of Table 11. follows the model, with sometimes less than 0.5% of relative error. Figure 50 presents graphically the results of Table 12.

Relevancy of the servers repartition

We also compared the throughputs obtained by our algorithm, and the ones by a balanced star graph (i.e., a star graph where all services received the same number of servers). A balanced star graph is the naive approach that is generally used when the same throughput is requested for all services, which is what we aimed at in our experiments. Figures 51 to 55 present the comparison between the throughput obtained with both methods. As can be seen our algorithm gives better results: the throughput is better on all but one experiment (dgemm 500 in the dgemm 500 Fibonacci 40 experiment), no more resources than necessary are used (in Figure 51, no more than 20 nodes are required to obtain the best throughput, and in Figure 52

Elements influencing the throughput

It isn't straightforward to obtain the best throughput out of a given hierarchy. Several parameters have to be taken into account in order to obtain the best throughput. We give here a list of some of the problems we encountered while trying to obtain the best throughput.

Bad scheduling

The basic scheduling implemented within Diet relies on the time of the last request a SeD has solved: when a request is sent down the hierarchy, each SeD replies the time since last solve, i.e., the time elapsed since the SeD has solved a request. Hence, when multiple requests are sent in the hierarchy, the SeD can reply the same value of time since last solve for multiple requests, and thus the same SeD is likely to be chosen for a lot of requests. This of course, may overload some SeD and do not give any load to the other SeD. Hence, in order to cope with this, we need to activate an option of Diet which allows a client to make its own scheduling: the client keeps a local list of available SeD for the service, and choose the server in a round robin fashion (which is what is implied by our model, as all servers are meant to have the same amount of load). Figures 56 and57 presents the throughput obtained on a mixed hierarchy containing both Fibonacci and dgemm services, when using or not the scheduling at the client level. Exactly the same number of clients have been used for both experiments, and the same hierarchy has been used as well. We can see that the throughput is better when using the scheduling at the client level in two ways: first it is higher, and secondly it is less perturbed. Logging Turning on or off the logging in Diet greatly influences the obtained throughput. Figure 58 presents the throughput obtained when turning on the logging on a platform on 30 nodes. Figure 59 presents the throughput obtained on the same platform, with the same number of clients, but when turning off the logging. As can be seen the throughput is greatly influenced by the logging facility. Indeed, several log messages are sent by each element of the hierarchy whenever a request is sent and solved. We observe a peak between 40 and 50 seconds on Figure 58, this behavior is typical from configurations with logging on, on some other experiments we obtained such peaks several times.

Number of clients

The number of clients involved in the system also influences the throughput. The first point is of course the fact that too few clients won't send enough requests in the system to fully load it. Conversely, too many clients will overload the system as no queuing is done at the SeD level. Hence, in order to find the best throughput we need to find the correct number of clients. One more point has to be taken into account, is that having lots of clients with each sending a request at a time is more expensive than having less clients, but threaded clients that are able to send several requests in parallel. Figure 60 presents the throughput obtained for services dgemm 100 and Fibonacci 30 with 150 clients per service, all clients being deployed on 40 nodes. Figure 61 presents the throughput obtained on the same platform, but with threaded clients: 10 dgemm clients with 15 threads each, and 2 Fibonacci clients with 75 threads each, a node is used for each client. Each thread can send a single request in the system at a given time (i.e., a new request can only be sent when the previous one has been solved). Hence, the two configurations are equivalent in terms of number of "clients", i.e., the number of requests that can be sent to the hierarchy at a given time. What can be seen is that with threaded clients, the throughput is higher, and more stable.

omniORB configuration omniORB has by default some limits on the number of threads CORBA clients and servers can use at the same time. This can limit the throughput of the platform, especially if "large" data transfers have to take place (this is the case for example with dgemm 500). Thus, in order to improve the throughput, we need to increase the number of threads clients and servers can use. This is done respectively with maxGIOPConnectionPerServer (default value: 5), and maxServerThreadPoolSize (default value: 100). We set those values respectively to 100 and 1000. With these values, we gained around 17% -18% on the number of requests per seconds.

Conclusion

In this paper we presented a computation and communication model for hierarchical middleware, when several services are available in the middleware. We proposed an algorithm to find a hierarchy that gives the best obtained throughput to requested throughput ratio for all services.

The algorithm uses a bottom-up approach, and is based on an MILP to successively determine levels of the hierarchy. Our experiments on a real middleware, Diet, show that the obtained throughput closely follows what our model predicts and that our bottom-up algorithm provides excellent performances. We clearly showed that it adds new levels of agents whenever required, and that it outperforms the classical approach of deploying the middleware as a balanced star graph. Finally, the experiments allowed us to determine several elements that have a great impact on the throughput.

As future works, we intend to run experiments on larger platforms, with "bigger" services. Deployment on homogeneous machines is only the first step that allowed us to validate our model, we intend to extend our model and algorithms to fully heterogeneous platforms.

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, RE-NATER and several Universities as well as other funding bodies (see https://www.grid5000.fr).

Figure 1 :

 1 Figure 1: Homogeneous platform

Algorithm 2

 2 Build hierarchy 1: N ← |V | -1 // One node for an agent, |V | -1 for the servers 2: Done ← false 3: while N ≥ |R| and not Done do

13 : break 14 :

 1314 nbChains ← count number of agents having only 1 child 15:

Figure 2 :Figure 3 :Figure 4 :

 234 Figure 2: Platform 1: 1 MA, 2 LA, n SeD, 2 services

Figure 5 :

 5 Figure 5: Total number of cycles per request for each LA

Figure 8 :

 8 Figure 8: Throughputs obtained when modeling with 186.7M b.s -1

Figures 9 and 10 Figure 9 :

 109 Figures 9 and 10 present the comparison between the theoretical model of communication/computation and the experimental results. As can be seen, the serial model, i.e., send or receive or compute, single port is the one that best matches the experimental results.

Figures 11 and 12

 12 present the messages exchanged when requesting a service (respectively for DGEMM and Fibonacci).

Figure 10 :

 10 Figure 10: Fibonacci experimental, and theoretical throughput with the different models.

Figure 12 :

 12 Figure 12: Messages exchanged during a request for service Fibonacci on a hierarchy composed of 1 MA, 1 LA and 1 SeD. Numbers in brackets represent the size of the message in bytes.

Figure 13 : dgemm 10 throughput 7 . 3 . 2

 13732 Figure 13: dgemm 10 throughput

Figure 20 :

 20 Figure 20: Agent's time to process a FIBO request.

8. 1

 1 Results dgemm 100 Fibonacci 30

Figure 21 :

 21 Figure 21: Throughputs for services dgemm 100 and Fibonacci 30, on 3 nodes. Figures 21 to 24 present the results when requesting concurrently services dgemm 100 and Fibonacci 30. Table8sums up the results. The results are quite close to the expected throughput, even when the hierarchy as two levels of agents: for 20 nodes, the agent hierarchy contained 1 MA and 3 LA. Over 20 nodes, the algorithm returned the same hierarchy as with 20 nodes. Figure25presents graphically the results of Table8.

Figure 22 :

 22 Figure 22: Throughputs for services dgemm 100 and Fibonacci 30, on 5 nodes.

Figure 23 :Figure 24 :

 2324 Figure 23: Throughputs for services dgemm 100 and Fibonacci 30, on 10 nodes.

Figure 25 :Figure 26 :

 2526 Figure 25: Comparison theoretical/experimental results, for dgemm 100 Fibonacci 30.

Figure 27 :

 27 Figure 27: Throughputs for services dgemm 10 and Fibonacci 40, on 3 nodes.

Figure 28 :

 28 Figure 28: Throughputs for services dgemm 10 and Fibonacci 40, on 5 nodes.

Figure 29 :Figure 30 :Figure 31 :Figure 32 :Figure 33 :Figure 34 :Figure 35 :

 29303132333435 Figure 29: Throughputs for services dgemm 10 and Fibonacci 40, on 10 nodes.

Figure 36 :

 36 Figure 36: Throughputs for services dgemm 500 and Fibonacci 20, on 5 nodes.

Figure 37 :

 37 Figure 37: Throughputs for services dgemm 500 and Fibonacci 20, on 10 nodes.

Figure 38 :

 38 Figure 38: Throughputs for services dgemm 500 and Fibonacci 20, on 20 nodes.

Figure 39 :

 39 Figure 39: Throughputs for services dgemm 500 and Fibonacci 20, on 30 nodes.

Figure 40 :

 40 Figure 40: Throughputs for services dgemm 500 and Fibonacci 20, on 40 nodes.

Figure 41 :Figure 42 :Figure 43 :

 414243 Figure 41: Throughputs for services dgemm 500 and Fibonacci 20, on 50 nodes.

Figure 44 :

 44 Figure 44: Throughputs for services dgemm 500 and Fibonacci 40, on 5 nodes.

Figure 45 :Figure 46 :Figure 47 :Figure 48 :Figure 49 :

 4546474849 Figure 45: Throughputs for services dgemm 500 and Fibonacci 40, on 10 nodes.

Figure 50 :

 50 Figure 50: Comparison theoretical/experimental results, for dgemm 500 Fibonacci 40.

  only 3 nodes). Our algorithm also tries to balance the ρi ρ * i ratio without degrading the performances, whereas with the balanced star graph adding more nodes can degrade the performances of both services.

Figure 51 :

 51 Figure 51: Comparison: our algorithm and balanced star for dgemm 100, Fibonacci 30.

Figure 52 :

 52 Figure 52: Comparison: our algorithm and balanced star for dgemm 10, Fibonacci 20.

Figure 53 :

 53 Figure 53: Comparison: our algorithm and balanced star for dgemm 10, Fibonacci 40.

Figure 54 :

 54 Figure 54: Comparison: our algorithm and balanced star for dgemm 500, Fibonacci 20.

Figure 55 :

 55 Figure 55: Comparison: our algorithm and balanced star for dgemm 500, Fibonacci 40.

  with and without client scheduling DGEMM with client scheduling DGEMM without client scheduling

Figure 56 :

 56 Figure 56: Throughput for dgemm 100 with and without client scheduling.

  with and without client scheduling FIBO with client scheduling FIBO without client scheduling

Figure 57 :

 57 Figure 57: Throughput for Fibonacci 30 with and without client scheduling.

Figure 58 :

 58 Figure 58: Throughput for dgemm 100, Fibonacci 30. With logging on.

Figure 59 :Figure 60 :Figure 61 :

 596061 Figure 59: Throughput for dgemm 100, Fibonacci 30. With logging off.

Table 1 :

 1 Table 1 presents the messages size for both dgemm and Fibonacci services. Fibonacci 4.176 × 10 -3 5.456 × 10 -3 Messages size in Mb for dgemm and Fibonacci services.

	Service	m reqi	m respi
	dgemm	5.136 × 10 -3 5.456 × 10 -3

Table 2

 2

						DGEMM 100 throughput
		400
		350
		300
	Throughput (nb request/s)	200 250
		150
		100
		50
		0	50	100	150	200	250	300	350	400	450	500
							Time (s)
					Figure 14: dgemm 100 throughput
				Nb requests	getRequest		solve
			dgemm 10		286050	0.000415694734846 0.00319375696017
			dgemm 100		16633	0.000314177963958 0.0585402570871
			dgemm 500		536	0.000297451642022	0.656850664473

and 3 present the mean time for getRequest (the time to process a request) and solve (the time to solve a request), respectively for dgemm and Fibonacci services.

Hence, the values in MFlops presented in tables 4 and 5.

Table 2 :

 2 dgemm mean getRequest and solve times (in s).

		Nb requests	getRequest	solve
	FIBO 20	305711	0.000401932459236 0.00507951654684
	FIBO 30	14477	0.000253283154893	0.165682609844
	FIBO 40	115	2.28923300038e -5	4.77842594437

Table 3 :

 3 FIBO mean getRequest and solve times (in s).

		getRequest	solve
	dgemm 10	0.0784808320277 0.602963382785
	dgemm 100 0.0625602101851 11.6567398347
	dgemm 500 0.164611652527	363.505383958

Table 4 :

 4 dgemm mean getRequest and solve required computing power (in MFlops).

						DGEMM 500 throughput
		30
		25
	Throughput (nb request/s)	15 20
		10
		5
		0	20	40	60	80	100	120	140	160	180
						Time (s)
					Figure 15: dgemm 500 throughput
					getRequest	solve
				FIBO 20 0.0467540134516 0.590864906532
				FIBO 30 0.0205522633808	13.4440548822
				FIBO 40 0.00812040104002 1695.01029392

Table 5 :

 5 FIBO mean getRequest and solve required computing power (in MFlops).

Table 6 :

 6 70 threads on 2 nodes for dgemm 10. Agents parameters

	Service	w reqi	w respi
	dgemm	0.398057810949015	0.2370227507159
	FIBO	0.376124815390629 0.235280539487372

Table 7 :

 7 Agents parameters when removing the communication time

				FIBO 30 throughput
	Throughput (nb request/s)
	0	50	100	150	200	250	300	350
				Time (s)
			Figure 17: FIBO 30 throughput

Table 8 :

 8 Comparison between theoretical and experimental throughputs, for dgemm 100 Fibonacci 30. Relative error: |T heoretical-M ean|

	. nodes Client	Theoretical Mean Median Std Dev Relative Error
	3	dgemm Fibonacci	272.924 238.317	278.0 242.5	278 242	4.4 11.2	1.87% 1.76%
	5	dgemm Fibonacci	534.758 470.144	543.2 476.1	544 477	6.1 10.7	1.58% 1.26%
	10	dgemm Fibonacci	1027.75 915.364	984.9 912.9	995 922	49.5 52.1	4.17% 0.26%
	20	dgemm Fibonacci	1699.05 1738.56	1624.4 1699.0	1666 1735	114.7 114.0	4.39% 2.28%
		T heoretical	.

Table 9 :

 9 Comparison between theoretical and experimental throughputs, for dgemm 10 Fibonacci 20. Relative error: |T heoretical-M ean| T heoretical

	. nodes Client	Theoretical Mean Median Std Dev Relative Error
	3	dgemm Fibonacci	2486.33 2486.33	3166.5 3164.2	3157 3191	319.7 231.3	27.4% 27.3%

Table 10 :

 10 Comparison between theoretical and experimental throughputs, for dgemm 10 Fibonacci 40. Relative error: |T heoretical-M ean| T heoretical

	. nodes Client	Theoretical Mean Median Std Dev Relative Error
	3	dgemm Fibonacci	3752.54 1.92	4773.5 2.2	5853 2	325.5 2.33	27.2% 14.6%
	5	dgemm Fibonacci	3752.54 5.75	4842.7 6.35	4856 6	212.2 2.4	29.1% 10.4%
	10	dgemm Fibonacci	3752.54 15.32	4805.9 16.8	4854 18	292.5 7.3	28.1% 9.7%
	20	dgemm Fibonacci	3752.54 34.44	4828.9 37.2	4859 37	279.4 3.0	28.7% 8.0%
	30	dgemm Fibonacci	3752.54 53.51	4811.2 57.1	4882 58	358.2 2.9	28.2% 6.7%
	40	dgemm Fibonacci	3752.54 72.55	4613.4 71.5	4739 72	386.2 4.9	22.9% 1.4%
	50	dgemm Fibonacci	3258.15 91.54	4037.0 93.6	4072 95	433.9 8.8	23.9% 2.3%

Table 11 :

 11 Comparison between theoretical and experimental throughputs, for dgemm 500 Fibonacci 20. Relative error: |T heoretical-M ean| T heoretical . Figures 35 to 41 present the results when requesting concurrently services dgemm 500 and Fibonacci 20. Table11sums up the results. Here the small service also suffers from the benchmarking

	No. nodes Client	Theoretical Mean Median Std Dev Relative Error
	3	dgemm Fibonacci	8.9 4034.6	8.8 5318.1	9 5366	3.3 372.4	1.1% 31.8%
	5	dgemm Fibonacci	26.7 4034.6	26.5 5351.8	27 5328	3.6 206.9	0.7% 32.6%
	10	dgemm Fibonacci	70.95 4034.6	68.8 5221.0	69 5258	4.8 264.4	3.0% 26.4%
	20	dgemm Fibonacci	158.1 3856.3	153.3 4851.8	153 4865	10.9 339.1	3.0% 25.8%
	30	dgemm Fibonacci	235.2 4034.6	224.0 4845.85	228 4946	23.8 289.3	4.7% 20.1%
	40	dgemm Fibonacci	311.0 2539.3	281.35 2391.6	291 2466	55.6 473.8	9.5% 5.8%
	50	dgemm Fibonacci	385.5 2694.3	311.7 2973.3	328 2960	63.2 352.1	19.1% 10.4%

Table 12 :

 12 Comparison between theoretical and experimental throughputs, for dgemm 500 Fibonacci 40. Relative error: |T heoretical-M ean| T heoretical . Figures 43 to 49 present the results when requesting concurrently services dgemm 500 and Fibonacci 40.Table 12 sums up the results. In these experiments, the experimental results closely

	No. nodes Client	Theoretical Mean Median Std Dev Relative Error
	3	dgemm Fibonacci	8.9 1.9	8.7 2.1	8 1	3.3 2.7	2.2% 10.5%
	5	dgemm Fibonacci	8.9 5.7	8.2 6.3	8 7	3.8 3.2	7.9% 10.5%
	10	dgemm Fibonacci	17.8 13.4	17.1 14.5	17 15	4.6 4.2	3.9% 8.2%
	20	dgemm Fibonacci	35.6 28.7	34.6 31.2	36 31	6.0 4.4	2.8% 8.7%
	30	dgemm Fibonacci	44.5 45.9	44.5 48.5	45 48	4.7 3.4	0.0% 5.7%
	40	dgemm Fibonacci	62.1 61.1	61.8 63.9	62 64	6.3 3.6	0.5% 4.6%
	50	dgemm Fibonacci	79.7 76.4	79.5 76.6	80 77	5.1 3.9	0.3% 0.3%

http://sourceforge.net/projects/iperf/

http://www.netlib.org/benchmark/hpl/

http://math-atlas.sourceforge.net/

http://nws.cs.ucsb.edu/ewiki/

E. Caron, B. Depardon and F. Desprez

Clients parameters used for the experiments

In this section, we list the parameters used for the clients for each of the previously presented experiments. Table 13 presents the number of multithreaded clients used for each experiment: one client was launched on a physical node, and each client had a certain number of threads. Each thread continuously sent requests to the Diet hierarchy.

Experiment

Relevancy of creating new agent levels

In order to validate the relevancy of our algorithm to create the hierarchies, we compared the throughput obtained with our hierarchies, and the ones obtained with a star graph having exactly the same repartition of servers obtained with our algorithm. Thus, we aim at validating the fact that our algorithm sometimes creates several levels of agents whenever required. In fact in the previous experiments, this happens only for the following deployments:

• dgemm 100 Fibonacci 30 on 20 nodes: 1 MA and 3 LA

• dgemm 500 Fibonacci 20 on 30, 40 and 50 nodes: 1 MA and 2 LA It is clear that with more nodes, the number of levels would increase.

Here are the results we obtained with such star graphs. We present the gains/losses obtained by the star graph deployments compared to the results obtained with the hierarchies our algorithm computed:

• dgemm 100 Fibonacci 30 on 20 nodes: we obtained a throughput of 911.95 for dgemm and 779.07 for Fibonacci. Hence a loss respectively of 43.8% and 54.1%.

• dgemm 500 Fibonacci 20 on 30 nodes: we obtained a throughput of 211.65 for dgemm and 3490.58 for Fibonacci. Hence a loss respectively of 5.5%, and 28%.

• dgemm 500 Fibonacci 20 on 40 nodes: we obtained a throughput of 238.1 for dgemm and 2476.9 for Fibonacci. Hence a loss of 15.4% for dgemm, and a gain of 3.6% for Fibonacci.

• dgemm 500 Fibonacci 20 on 50 nodes: we obtained a throughput of 184.68 for dgemm and 2494.0 for Fibonacci. Hence a loss respectively of 40.7% and 16.1%.

We can see from the above results that our algorithm creates new levels of agents whenever required: without the new agent levels the obtained throughput can be much lower. This is due to the fact that the MA becomes overloaded, and thus do not have enough time to schedule all requests.