Sylvain Dahan

Alexandru Dobrila

Jean-Marc Nicod

Laurent Philippe

Performances Study of the Distributed Spanning Tree an Overlay Network for server lookup

Random graph and tree are two topologies used to build overlay networks. These overlay networks may be used by large scale discovery mechanisms to run search algorithms. The Distributed Spanning Tree (DST) is another topology that may be used as overlay. In a DST, every computer is a leaf. DST's non-leaf nodes are sets of computers instead of computers. Thus, it allows the use of tree traversal algorithms while avoiding the usual tree's bottlenecks. As a result, the DST allows more efficient executions of search algorithms in term of number of sent messages and in term of load balancing. In this paper, we describe the results of several simulations of flooding algorithm executions. These simulations are run on the three previous topologies and for different numbers of nodes. These simulations indicate that the DST structure is more efficient than graph topology which, in turn, is more efficient than tree topology in term of traversal speed and in term of supported load for every simulated scale. We study as well the behaviour of the DST when nodes are added or deleted to show that the structure is adapted to dynamic environments.

Introduction

Grid middleware allows resources sharing between several entities. These resources consist into a wide variety of hardware, data and software. As the size of Grid deployments increases, finding the resource that is needed by a user becomes an issue. To solve this issue, peer-to-peer systems are an inspiration source for Grid middleware because they propose several scalable search mechanisms [START_REF] Lua | A survey and comparison of peer-to-peer overlay network schemes[END_REF]. These mechanisms could be classified into two categories [START_REF] Mcgrath | Discovery and its discontents: Discovery protocols for ubiquitous computing[END_REF].

The first category is composed by mechanisms based on a directory. Each resource has to register itself by specifying its name and its location to be visible. Then, clients can find this resource by giving the corresponding name to the directory. Distributed Hash Tables are a good example of directories based peer-to-peer search mechanisms.

The second category is composed by mechanisms based on flooding algorithms. Information on resources are stored on each computer participating to the peer-to-peer system. The computers are connected together to form a communication graph, also called overlay network. When a peer, a node of the graph, is looking for some information that it does not already have, it asks its adjacent nodes for the information. If they do not own it, these nodes forward the request to their adjacent nodes, and so on until the information is found or until a specified maximum number of hops is reached (usually called Time To Leave or TTL).

The performances of flooding algorithms depend on many factors. One of them is the topology of the communication graph. The tree is an interesting topology because its complexity in number of exchanged messages is optimum as it directly depends on the number of nodes. But searches on trees generate bottlenecks when the load of the system increases. So flooding algorithms are run most of the time on pseudo-random graphs although their complexity in term of number of messages is higher.

To improve the performances of flooding algorithms, we propose a new way to build a tree which does not have the usual tree's bottlenecks. This original structure, called Distributing Spanning Tree (DST), has already been described from a theoretical point of view in two previous publications [START_REF] Dahan | Distributed Spanning Tree algorithms for large scale traversals[END_REF][START_REF] Dahan | The Distributed Spanning Tree: A scalable interconnection topology for efficient and equitable traversal[END_REF]. But no study about how it behaves in practise has been made public. The purpose of this paper is to share pertinent results and comments about simulations that were made to study the performances of flooding algorithms using a DST structure. These performances are compared with two others topologies: pseudo-random graphs and trees.

Simulations have been used numerous times to study performance of flooding algorithms in various contexts. For example, G. Fletcher and H. Sheth [START_REF] Fletcher | Unstructured peer-to-peer networks: Topological properties and search performance[END_REF] compare search on a CAN distributed hash table, on a random graph and on a Pandurangan Graph to evaluate their efficiency . L. Qin et Al. [START_REF] Qin | Search and replication in unstructured peer-to-peer networks[END_REF] wrote a comparative study about performances and supported load of various random-graph topologies and various resources distribution. Beside simulations, some peo-ple, like R. Gaeta et Al. [START_REF] Gaeta | A simple analytical framezork to analyze search strategies in large-scale peer-to-peer networks[END_REF], also propose analytical model for those search algorithms on random graphs.

The article is organised the following way. The DST is shortly presented in section 2. We study the cost in term of messages when nodes arrive or leave the DST in section 3. The performances comparisons are conducted on a simulator described in 4. The simulations results are discussed in section 5 and exhibit the interest of the DST structure for search algorithms. Then, we conclude on the use of the DST structure in several distributed contexts.

The DST Structure

The DST structure is designed to correct the drawbacks of trees and random graphs in large scale overlay networks.

The DST is a virtual tree which covers the whole set of computersspanning -and where nodes are distributed across several computers to avoid bottlenecks. A DST is similar to a B-Tree [START_REF] Knuth | The Art of Computer Programming[END_REF]: it is composed of several levels. All leaves belong to the same level, each non-leaf node has a limit number of sons and the root, if it is not a leaf, has at least two sons. The level 0 contains the leaves of the tree. The level 1's nodes are complete graphs of leaves, By definition, a DST's node is distributed through its descendants. Thus, a DST's node is distributed through the computers that are leaves of the node's subtree. To implement a node of level n with n>2 we connect each computer of this node to at least one computer of each children of the node as shown in Fig. 3. Thus, any computer of a node can send a message to every children of this node via the computers that are inside these children.

Using this construction, each node generates its own "routing table". The routing table of one node has as many entries as levels in the DST and each entry contains a link to a computer that resides inside each brother nodes. On Fig. 3, if node 2 wants to broadcast a message to its descendant, it will send a message to node 21, node 22 and node 23. If, the process that initiates the broadcast is located in node 213, it will send its message to the process of node 21 located in node 213, to the process of node 22 located in node 221 and to the process of node 23 located in node 232. Then, node 21, node 22 and node 23 forward the message to their children using their complete graph. This quick explanation of the DST's structure provides enough information to understand that a DST is a tree where non-leaf nodes are complete graphs of their children. By recursively creating complete graphs, we are able to distribute non-leaf nodes between their children and create a spanning tree per node. As every computer acts as a node of different levels, it is possible to share the load of these levels between several and thus avoid the usual tree's bottlenecks. For more information about the DST structure and details on construction algorithms, a complete description of the DST structure is available in [START_REF] Dahan | The Distributed Spanning Tree: A scalable interconnection topology for efficient and equitable traversal[END_REF].

The DST management

The DST has an incremental structure : we add and we delete nodes as participants come or leave the DST. To be a DST member, a node must know another node which is already in the DST. We study here the cost of adding and deleting nodes from the DST. We also introduce the notion of limits with an inferior and superior limit which apply to the size of a node. If a node is too small (under the inferior limit) it should be merged, it should be split if it is too big (above the superior limit).

Cost of adding nodes

Figures 4 and5 show the number of messages for a 4 and a 8 levels DST. The abscissa indicates the number of messages necessary to add a node and the ordered indicates the number of nodes that has generated this number of messages (two nodes can generate the same number of messages). In this figure, each peak matches with the split of a higher level node. If the node is high in the hierarchy then more nodes will be affected by the splitting which implies an important number of messages. These figures indicate that the number of messages needed to split a node grows exponentially with the level of the node. Besides, the number of splits for a node decrease logarithmically with its level in the DST. Thus, we have a lot of splits into first levels, those are costless in comparison with higher level splits which are far more seldom. In this simulation we have a relation of ten between both.

Cost of deleting a node

We study here the impact of different factors coming from the departure of a node.

Impact of the area where the node is deleted We test the DST behaviour when nodes leave in a restricted area. For those simulations we use a DST with 50 nodes in which we delete 30 nodes. The inferior and superior limits for the nodes size are respectively 2 and 4. First we delete node randomly from the DST. This result will be the witness. Then, we focus on a restricted area. We ran 20 simulations for both situations and note the total number of messages needed for all deletes. Both curves are shown on figure 6 (a). The average cost of random deleting is 1374 messages for 30 leaving nodes. When deleting in a restricted area the cost is 1555 messages for the same number of leaving nodes. The probability of merging nodes is higher when deleting from the same area. The merging operation has an important cost, that explain this result. Thus a good merging algorithm is paramount. We focus on the reorganisation cost in the next paragraph.

Reorganisation cost

We use a DST with the smallest possible limits (2 and 4). We create a DST with 90 nodes and 5 levels. We delete 88 nodes so that we can study all the We observe peak for series 2 and 3 just before the tenth delete. This peak corresponds to the merging operation that implies the delete of the level 5. All peaks are due to reorganisation. The peaks are very pronounced because after a reorganisation the DST is well balanced.

Average cost of deleting. During our simulation we observe a linear increase of the number of messages in function of the level. Note that, in the studied case we initiate a very fragile DST with limits of 2 and 4. Thus, by studying the worst case we have the worst behaviour.

Description of the Simulations

The simulations presented in section 5 use two algorithms. The first is a TTL-based flooding algorithm that is used with the graph and tree topologies [START_REF] Dahan | Scalability in a GRID server discovery mechanism[END_REF]. The second use the DST structure to run a traversal with similar properties. Fig. 7 illustrates the four steps of the execution of this algorithm on a DST of height 3. The request is initiated by the gray node on step 1. Then it broadcasts the request in the subtrees of level 1 on step 2, level 2 on step 3 and level 3 on step 4. Complete algorithms are given in [START_REF] Dahan | Performances study of management and traversal algorithms on the DST overlay network[END_REF]. Our first idea was to simulate and study the DST behavior on the Internet. However, experiences on Internet cannot be reproduced as the simulation conditions cannot be two times the same. Thus, we restrict to a model where all computers have one link, an access to every other computer through a central router and the bandwidth is limited. This model is not far from a realistic Internet model if we consider different bandwidth for different links and FIFO queues that assure that there is no more than one message in a link at any time. This way, we can mesure the impact of different factors on the execution performances.

Exact details of the simulations can be found by downloading the simulator 1 . We perform simulations for populations of 10, 100, 1 000 and 10 000 peers to study the behaviour of the algorithms when the overlay network scales up.

For all topologies the TTL is set to 10. Hundred different types of resources are available, and each computer has a probability of 10 % to own a resource for each type. Each search request stops either when it finds a node with the requested resource, when the TTL is reached or when the whole structure is traversed. However, we noticed that a maximum depth of four is generaly enough to find a resource whith this probability to find the resource.

About the overlay topologies characteristics, trees are bidirectional and their arity is 5. Graphs are also bidirectional, connected and the degree of each node is 5. Finally the DST is made in a way that each node has 5 children. These degrees were chosen because they show the best performances in our simulations. More precisely, we ran few tests at various scales to find these optimal degrees. Then, we used them for all our simulations by considering that these degrees are always optimal in our experiments. However, these values depend on the links throughput and the probability to find a service. Changing one of these parameters implies that the chosen degrees would not longer be optimal.

Discussion about the simulation results

In this section, we discuss the results obtained by the simulations. For each simulated overlay network, we compare the performances of the three tested topologies. The two performance criteria that we are interested about in this article are the average time taken to process a search and its variation depending on the average load of the system. The system load is defined by the requests arrival rate or frequency: the number of queries that are initiated per second for the whole network. In the last section, we explain how the three topologies scale up.

1 http://lifc.univ-fconte.fr/∼philippe/pub/simulator-12-06.tar.gz

10 peers overlay networks

The simulations results for 10 peers overlay networks are displayed in Fig. 8. The simulations show that the average time needed to process a request depends on the requests arrival rate. This is an ordinary observation. When the number of initiated requests grows, the system becomes more and more loaded and messages spend more time in a waiting queue before being sent. When the number of requests that enter the system becomes higher than the number of requests that leave it, the system becomes saturated. This saturation is easily identifiable for the DST on Fig. 8: the average time needed to process a request grows slowly for frequencies from 1 req.s -1 to a frequency of 150 req.s -1 ; but it grows very quickly for frequencies greater than 200 req.s -1 . On the other hand, the graph and the tree become very quickly saturated.

For a 10 peers overlay network, the simulations tell us that graphs and trees have similar performances. This is interesting because we expected to get better performances with the graph in term of time used to process a request when the system is not loaded (0.1 req.s -1 ) as explained in section 5.2. The more plausible explanation of this result is that some requests completely traverse the graph as no resource is found (we only have 10% of chance to find a resource on each peer and we only have 10 peers). So, these requests need an additional round to check that no other peers can be contacted. This is the final round where lots of messages are sent to traverse both ways the latest links, not marked as flooded, although no untraversed peer remains. Due to this additional round, the traversal depends on the number of links rather than on the number of nodes and affects the global average search time.

Studies of individual load of peers also explain why the tree and the graph become saturated on a similar way: bottlenecks of both topologies have to support similar load. This can be explained by the fact that the tree has few bottlenecks that send an average of, say x messages. With the graph traversal every peer also sends an average of x messages, as the number of messages depends on the number of links. Because every peer has the same bandwidth, and because the topologies performances are limited by their bot-tlenecks, both topologies become overloaded in a similar way at this scale. The DST has the best behaviour for these simulations. Because a DST is based on trees, a search request only needs 2.n messages to query n peers, which is less than the graph. But because it distributes the load of father nodes between its children, it does not suffer from the tree bottlenecks. Thus, the DST can support much more load than the other topologies at a scale of 10 peers. Note that the DST also generates a lower search time than the tree when the system is not loaded.

100 peers overlay networks

Fig. 9 presents the simulations results for 100 peers. Like before, the three topologies saturate when the query arrival rate becomes too high. From the simulations, it is clear that the tree has the worst performances in term of supported load. 100 req.s -1 is enough to overload trees while graphs and DST start to overload for a frequency of 700 req.s -1 . Before reaching this point, the average search time grows slightly with the average load of the system. Graphs performances are roughly similar to the DST ones in term of supported load and average search time. Because each search needs to query a small part of the graph, few links are traversed to access already contacted peers. Thus, few peers are contacted twice by the same request and the number of exchanged messages is, in a wide approximation, roughly similar to the tree's one. It depends on the number of nodes rather than on the number of links. For this reason, as graphs inherently distributes their load between their peers and as a DST is a tree that distributes the father's nodes load between its descendants, the performances of both graphs and DST are approximately similar in term of average query time and supported load.

We observed that tree topologies have a higher average search time than graphs even when the average load is very low. This is counter-intuitive if we think that the average query time only depends on the number of exchanged messages and that the tree based traversal generates an optimal number of messages. In a balanced tree with an arity of 5, there are lot more leaves than non-leaf nodes. Because every peer has the same probability to initiate a search, the majority of searches are initiated by leaf nodes. These searches are not efficient because the first step of a search only queries one peer, its father, when the same step queries 5 peers in a graph or in a DST. At the second step the tree queries 5 peers when the graph or the DST can query 25 peers. Further, the tree behaves as if it always has one round late compared to the two other topologies, because tree leaves have one more hop to cross when they issue a search request. Being one round behind the other topologies is translated by a higher latency which explains why the average search time of the tree is more important than the two others even when the system is under light load.

Same simulation were made for 1 000 and 10 000 peers overlay networks. Results shown the same type of curves. For 1 000 peers, a load of 300 req.s -1 is enough to saturate the tree and it starts to overload around 1 000 req.s -1 for 10 000. Graphs and DST start to overload around 8 000 req.s -1 with 1 000 peers and support at least a load of 40 000 req.s -1 with 10 000. Before overloading, the average search time of DSTs and graphs grows slowly when the load increases and it linearly depends on the load.

Scalability of the three topologies

Until now, we have discussed the performances for each scale separately. Here we present how the number of peers affects the performances of each topologies. For Fig. 8 and Fig. 9, we note that adding new peers always allows to increase the performances in term of supported load. But, depending on the topology, the supported load per node may decrease. For the tree topology, 40 req.s -1 saturate a tree of 10 peers, 100 req.s -1 saturate a tree of 100 peers, 300 req.s -1 saturate a tree of 1 000 peers and 1 000 req.s -1 saturate a tree of 10 000 peers. This is not very efficient because multiplying the number of peers by 100 (from 100 peers to 10 000 peers) only multiplies the supported load by a factor 10 (from 100 req.s -1 to 1 000 req.s -1 ). We can conclude that the tree topology does not scale and the reason is clearly the bottlenecks generated by non-leaf nodes. The DST has a good scalability. The supported load grows linearly with the number of peers: 150 req.s -1 for 10 peers, 700 req.s -1 for 100 peers, 8 000 req.s -1 for 1 000 peers and more than 40 000 req.s -1 for 10 000 peers. When the system is not saturated, the performances, in term of average search time, are stable: it varies from 25 ms to 75 ms whatever the number of peers is. A performance of 150 req.s -1 on 10 peers for a DST seems to be inconsistent with the performance of 700 req.s -1 for 100 peers, but this is normal. There is only 10 peers, so two steps searches only contact 10 peers when the same search contact 25 peers in a 100 peers DST. Less peers contacted means less messages generated and implies that the overlay networks supports mode load. The scalability of the graph is similar to the DST's one except for small scale where it is worst. This similarity comes from the fact that both topologies behave in a similar way when the probability to find a resource on each peer is fixed (10 % in our simulation) and that the number of peers is high enough. If the scale is too small, then queries contact several times the same peers and graphs perform badly. However, if the probability to find a resource is low enough that peers receive a query several time, then graphs' performances cannot cope with the DSTs' ones. Fig. 10 presents the performances of graphs and DSTs of 1 000 computers when the probability to find a resource is 0 %. In this case, the DST's performances are better than the graph's ones because a DST sends fewer messages and distributes fairly its load between computers. Note that a frequency of 1 request every 5 seconds is enough to saturate a DST of 1 000 computers. This is normal as TTLbased flooding algorithms, which generate several waves of search, are not efficient for this kind of applications. A directory, like a DHT, should be used instead.

Other simulations on influence of service population and load balancing were run in [START_REF] Dahan | Performances study of management and traversal algorithms on the DST overlay network[END_REF].

Conclusion

If the performances of search algorithms only depend on the number of messages generated by a search request then, in theory, these algorithms are more efficient on a tree than on a graph. But, taking into account bottlenecks, graphs are more resistant than trees.

The Distributed Spanning Tree (DST) is a tree based structure that connects a set of computers while distributing the load of parent nodes between their children. This structure is in theory better suited to run flooding based search algorithms than trees and graphs topologies. It is designed to send an optimal number of messages like a tree without suffering from topological bottlenecks. The simulations presented in the paper confirm the interest of this approach and the DST always has better performances in term of average search time and supported load. Moreover, we found that, thanks to the DST structure, the implementation of traversal algorithms is simpler for the DST than for graphs.

As these results are encouraging, we are currently working on the dynamics of the structure. We already designed the algorithms to dynamically construct and manage a DST. Simulations are carried out to observe the evolution and robustness of the DST in a context of short lived peers. We will focus on that point for further works.

Figure 1 :Figure 2 :

 12 Figure 1: Level 1's nodes of a DST Fig. 1 presents 3 nodes of level 1 and 8 leaves. Upper levels of a DST are structured the following way: any node of level n+1 is a complete graph of its children which are nodes of level n. The Fig. 2 is an example of a level 2's node.

Figure 3 :

 3 Figure 3: Links that implement a complete graph of graphs.

Figure 4 :Figure 5 :

 45 Figure 4: Number of messages with 4 levels.

Figure 6 :

 6 Figure 6: Cost study of deleting.steps of merges. The results are given on figure6 (b). We observe peak for series 2 and 3 just before the tenth delete. This peak corresponds to the merging operation that implies the delete of the level 5. All peaks are due to reorganisation. The peaks are very pronounced because after a reorganisation the DST is well balanced.

Figure 7 :

 7 Figure 7: Example of a DST's traversal

Figure 8 :

 8 Figure 8: Performances for 10 peers networks

Figure 9 :

 9 Figure 9: Performances for 100 peers networks

Figure 10 :

 10 Figure 10: Performances for 1 000 peers networks when no resources are available


Sékou Diakité
email: [diakite@lifc.univ-fcomte.fr

Jean-Marc Nicod
email: nicod@lifc.univ-fcomte.fr

Laurent Philippe
email: philippe]@lifc.univ-fcomte.fr

Processing Identical Workflows on SOA Grids: Comparison of Three Approaches

Keywords: Batch scheduling, grid computing, heterogeneous platform, on-line scheduling, steady state scheduling, genetic algorithm

In this paper we consider the scheduling of a batch of workflows on a service oriented grid. A job is represented by a directed acyclic graph without forks (intree) but with typed tasks. The processors are distributed and each processor have a set of services that carry out equivalent task types. The objective function is to minimize the makespan of the batch execution. Three algorithms are studied in this context: an online algorithm, a genetic algorithm and a steady-state algorithm. The contribution of this paper is on the experimental analysis of these algorithms and on their adaptation to the context. We show that their performances depend on the size and complexity of the batch and on the characteristics of the execution platform.

I. INTRODUCTION

Processing workflows of images is a very processor consuming activity therefore, when the size of the image set grows up it is mandatory to use a distributed execution platforms such as Grids. In this paper, the targeted application is a workflow that generates datas such as medical images. Each image is computed from a set of existing data on which we applied different operations: extracting data from an image, applying filters to enhance the image quality, calculating correlation between two images, merge of images to highlight some property and so on. After acquiring a set of images or data, we apply on them the same workflow, i.e. the same set of operations, to get the final result. However, the execution of such workflows on grids is not simple as the platform is heterogeneous from the performances viewpoint as well as from the deployed services viewpoint. Misplacement of execution may lead to very poor execution performances while certain medical applications need almost interactive results (not more than a few minutes). Thus, the schedule of the set of workflows must be carefully defined.

Different approaches can be used in this context to minimize the response time of such executions. Traditional scheduling techniques includes on-line approaches and off-line approaches. Our aim is to evaluate the efficiency of these approaches depending on the workflow and grid platform characteristics, then to use these results as input data to implement efficient scheduling policies in grid middlewares as DIET. As grid experiments are very costly to deploy and not repeatable due to the dynamic behavior of other applications, we started our evaluation by simulating the grid and the algorithms. The simulations have generated a first set of results presented here.

In this paper we compare the performances of three approaches. A simple on-line algorithm which schedules tasks depending on the computers and tasks availability and two off-line algorithms which are implemented to maximize the flow and makespan criterion. On one hand, we show that both the workflow's and platform's characteristics have an impact on the performances, this impact may be up to 50%, and, on the other hand, that the criteria to optimize must rather be makespan oriented when the number of workflows to perform is less than 100 and flow oriented when this number is above 250.

In the following section of this paper we define the application model, the platform's characteristics and the related works. In the third section we present the algorithms, their properties and different adaptations we did to well known algorithms to better fit our context. Then, in the forth section, we detail the implementation of these algorithms in a grid simulator. The fifth section is dedicated to the results and their analysis. A conclusion is given in the last section of the paper.

II. CONTEXT

Defining the context and the characteristics of the application execution is a very important step in the scheduling problem resolution. Indeed, scheduling researchers are actives since a long time and have addressed lots of scheduling issues. Therefore, the choice of scheduling algorithms must be done in regard to a particular platform model and a particular application model. In order to clearly define the platform's and application's characteristics, we first give a more formal model of the platform and of the workflows. Then we present the works related to the workflows scheduling on grids.

A. Platform model

Executing an application on the grid usually consist in asking a grid administrator, human or not, for nodes allocation. Then the system respond with a set of nodes that are availiable and the start time of the reservation. However, on Service Oriented Architecture Grids (SOA Grids) this model can vary as the request for nodes depends on the services deployed on the nodes. In some grid middlewares such as Diet or Ninf, the user asks for computing nodes that provides a set of services. In this context, nodes are selected according to the services the workflow needs.

In our model, nodes and processors are equivalent, the execution platform is modeled as a set of processors, interconnected by network links. It is represented as an undirected graph: P F = (P, L), where the vertices are the n nodes p i (p i ∈ P : i ∈ [1..n], n = |P |) and the edges are the network links l i between these nodes.

Each node p i implements a limited set of services or functions to carry out the different parts of the workflows. We define as F i the set of functions that the processor p i is able to perform.

Fig. 1 gives an example of a grid with the communication links. The communication graph is complete as the communications usually use the internet network. On this figure, the letters A, B, C and D represents the services deployed on the nodes of the grid; different services are deployed on the nodes. 1 gives an example of the performances that characterize the platform. The given values correspond to the number of time units necessary to carry out a given service on a given processor, such values can be obtained by extrapolation of unary execution tests. When no value is given, the processor is not able to process the given service. For instance, processor p 4 can process functions A and D but cannot process functions B and C.

B. Application model

The defined platform model executes a batch of workflows. Usually a workflow is defined as a global task composed of sub-tasks. Each of these sub-tasks has to be executed in a constrained order. The workflow is done once all of it's subtask are computed.

Our target application is a set of images and data onto which we apply the same operations, the workflow, composed of filters or analysis operations. The whole set of images to be executed is available at some starting time t and the workflows are identical.

A batch B of length m is defined as a set of m identical instances J j of the job (workflow) J such as B = {J j : j ∈ [1..m]}. The job J is composed of several tasks with dependency constraints and is represented by a directed acyclic graph (DAG): J = (T, D) where the vertices T are the tasks t k and the edges D are the dependency constraints between the tasks. Note that there will be several instances of task t k belonging to different instances J j of job J.

Let F be the set of all the functions used by the job J thus ∪ i F i = F where i ∈ [1..N ]. The time T needed to execute a task T k on different nodes p i is not uniform: T (T k , p i ) = T (T k , p ′ i ). Fig. 2 gives an example of a job we have to schedule M times. The job is composed of five tasks. The arrows indicate the dependency constraints. Note that this job needs several time the same service A.

C. Related works

Scheduling problems have been studied extensively in the literature. In general, DAG scheduling is an NP-Complete problem [START_REF] Kwok | Static Scheduling Algorithms for Allocating Task Graphs to Multiprocessors[END_REF].

[1] is a survey for scheduling DAG in a static context considering homogeneous platforms. Therefore, this problem is also NP-Complete in a Heterogeneous Computing (HC) environment. So, requiring of good heuristics is mandatory in this domain. Classical solutions to optimize the makespan of a set of tasks use heuristics such as Earliest Finish Time [START_REF] Topcuouglu | Performance-effective and lowcomplexity task scheduling for heterogeneous computing[END_REF] or Critical Path [START_REF] Kwok | Dynamic critical-path scheduling: An effective technique for allocating task graphs to multi-processors[END_REF]. A more complete study evaluates eleven heuristics in [START_REF] Braun | A Comparison of Eleven Static Heuristics for Mapping a Class of Independent Tasks onto Heterogeneous Distributed Computing Systems[END_REF] for example: Min-min, Max-min or Sufferage. These 3 heuristics are based on the Minimum Completion Time (MCT). Genetic based scheduling algorithms [START_REF] Braun | A Comparison of Eleven Static Heuristics for Mapping a Class of Independent Tasks onto Heterogeneous Distributed Computing Systems[END_REF], [START_REF] Wang | Task matching and scheduling in heterogeneous computing environments using a genetic-algorithm-based approach[END_REF] gives good results in HC but these approaches are very time consumming compared to classical solutions. In the context of the Grid, [START_REF] Casanova | Heuristics for Scheduling Parameter Sweep Applications in Grid Environments[END_REF] presents a modification of the 3 previous heuristics to take into account input and output data transfert times in the computation of MCT. [START_REF] Maheswaran | Dynamic Mapping of a Class of Independent Tasks onto Heterogeneous Computing Systems[END_REF] studies dynamic mapping heuristics considering a class of independent tasks in HC environment. When the tasks are multiple DAGs, problem of fairness between DAGs are studied in [START_REF] Zhao | Scheduling multiple DAGs onto heterogeneous systems[END_REF]. These approaches compute a off-line scheduling considering the whole set of tasks. If the number of tasks scales up, the computation time becomes too long due to the complexity of the algorithm. The strategies applied to schedule workflows onto the grid are presented in [START_REF] Mandal | Scheduling strategies for mapping application workflows onto the grid[END_REF] with the description of real life medical application. Another example of a scientific application workflow is given in [START_REF] Caniou | Ocean-Atmosphere Modelization over the Grid[END_REF] about Ocean-Atmosphere modeling.

This study deals with static workflows scheduling in HC environment considering a few hundred of identical DAGs and limited resources. Finding an optimal schedule in this case is not possible with direct method. Two solutions are suitable in this context: (1) either use a scalable heuristic to compute a suboptimal schedule or (2) use the results of an optimal solution to a problem close to ours. So, three approaches match this context: makespan optimization heuristic using genetic algorithm, steady state techniques, and on-line techniques.

The suboptimal schedule strategy we evaluate is a static genetic based scheduling algorithm adapted to our context: GATS [START_REF] Daoud | Gats 1.0: A novel ga-based scheduling algorithm for task scheduling on heterogeneous processor nets[END_REF]. The algorithm explained the the next section is able to schedule a large number of DAGs.

The second approach optimize the throughput of the workflow in the HC environment. This Steady-state techniques achieve an optimal makespa n for an infinite number of identical jobs [START_REF] Beaumont | Assessing the impact and limits of steady-state scheduling for mixed task and data parallelism on heterogeneous platforms[END_REF]. The resulting schedule is composed of an sub-optimal initialization stage that allow to enter the optimal steady-state stage and a sub-optimal termination stage that performs the remaining tasks. This schedule will tend towards optimality when the size of the batch increases, as the weight of the initialization and termination stages decreases in the global schedule. When the number of batches is too small, the sub-optimal stages overhead leads however to an inefficient schedule. So, the question is to evaluate for which number of batches the steady-State scheduling becomes interesting.

The third approach is an on-line oriented techniques that schedule tasks on the fly during the jobs execution. They take the state of the system into account to assign new tasks to processors. These techniques are very easy to implement and give rather good results. They give however no guarantee on the quality of the schedule.

In our context, we can note that only the Steady-State techniques benefit from the knowledge that the executed jobs are identical.

III. SELECTED SOLUTIONS

Three algorithms are selected and adapted to our context characteristics to allow us to schedule a workflow of identical jobs. They represent different approaches and all of them give good results in our context. The first chosen algorithm is listbased on-line scheduling algorithm. This algorithm is used to give us a reference makespan to ease the comparison between the three algorithms. The second one is a static scheduling algorithm for graphs of aperiodic tasks on a heterogeneous platform. It is a genetic based approach that improves a list-based scheduling heuristic. It allows us to evaluate the performances of an algorithm designed for a set of tasks to schedule a workflow. The last algorithm we evaluate in this paper is a steady-state oriented scheduling algorithm well adapted to workflow and periodic jobs scheduling. A linear program allows us to optimize the throughput of the workflow regarding the constraints given by the platform and the periodic DAG to schedule. This solution is optimal in the steady-state period of time when the both initialization and termination stages are negligible [START_REF] Beaumont | Assessing the impact and limits of steady-state scheduling for mixed task and data parallelism on heterogeneous platforms[END_REF]. It allows us to evaluate an algorithm initially designed for an unlimited workflow when the number of jobs are limited to a few hundred.

A. On-line Scheduling with knowledge

The workflow that we have to schedule is a set of DAGs but not a unique connected graph of tasks. Therefore, it is not possible to implement the well known EFT scheduling algorithm because it is not possible to identify the tasks with the earliest deadline: several tasks are ready at the same time but do not have any precedence constraint between them. So we implement a list-like scheduling algorithm which principle is to schedule a ready task as soon as possible on the processor that will perform it the first. No heuristic is used to select the task to schedule unlike a classical list based scheduling algorithms [START_REF] Topcuouglu | Performance-effective and lowcomplexity task scheduling for heterogeneous computing[END_REF], [START_REF] Wu | Segmented min-min: A static mapping algorithm for meta-tasks on heterogeneous computing systems[END_REF]. This mechanism shortens the traversal time of a job. The best processor is selected using the Earliest Finish Time (EFT) heuristic [START_REF] Topcuouglu | Performance-effective and lowcomplexity task scheduling for heterogeneous computing[END_REF].

B. GATS

Genetic Algorithm for Task Scheduling (GATS) [START_REF] Daoud | Gats 1.0: A novel ga-based scheduling algorithm for task scheduling on heterogeneous processor nets[END_REF] is a genetic based algorithm that improves about 7% to 10% a classical scheduling algorithm for aperiodic tasks on a heterogeneous platform. The GATS approach enhances the schedule computed first with a list based scheduling heuristic. The initial population is created at the first step: the first individual represents the result of a list-based schedule which favors the tasks on the critical path of J. Then one individual per processor represents a random schedule where all the tasks are affected to the given processor and the remain of the population represents random schedules.

GATS individuals represent tasks-processors allocations. Thus, the scheduling is computed by a decoding step of each individual. This reconstruction phase has to take into account the dependencies between tasks while respecting the allocation. The fitness f of each individual is deduced from the decoded schedule thanks to the formula: f = 1/Makespan(schedule). The classical genetic operations on individuals such as mutations or cross-overs are easy to compute because of the simple chromosome representation without time informations and precedence constraints. Indeed, one task can be moved from one slot to another. Once the initial population is created, GATS performs a limited number of loops that compute the fitness of the individuals, a rankbased selection, mutations and cross-overs. The termination criterion used is this fixed number of loops. In the worst case, the computed schedule is at least equal to the initial list-based solution.

C. Steady-state scheduling

In our context, the optimization of the scheduling is to maximize the throughput of of the workflow we have to compute. But, we also have to respect the constraints due to the platform characteristics. These constraints ensure that jobs are fully computed. So, this optimization problem can be written as a linear program. When the system enters the steady-state stage, the solution is easy to compute because the linear program variables are rational thanks to the periodic scheduling approach. Indeed, the solution of this linear program gives the ratio of time spent by each processor for each task of the jobs and the proportion of time spent by each network link to send task results for each inter-tasks dependencies. This solution is translated into a weighted sum of allocation, where an allocation represents the traversal of a job in the platform (task/processor associations). The steadystate scheduling computes a period in which the allocations are interleaved according to their weight. The steady-state stage is the concatenation of the adequate number of these periods to compute the whole size of the workflow.

Before entering the steady state stage, the platform has to be initialized by computing every tasks needed to enter the steady-state. After the last period, a termination stage is also necessary to finish all the DAGs initiated by previous periods. In the original algorithm, the initialization is not optimized. The master computes itself every tasks without parallelism facility. As the initialization, the termination stage is performed by the master in a sequential way. Its role is to terminate every task staying in the platform after the last steady-state period.

IV. SIMULATION

The targeted applications are very time consuming. For this reason, we make the assumption that the bandwidth of P F allows us to neglect the communication time for all the computation steps of each instance J i of the job J.

Building a mathematical model of the algorithms is not realistic due to the complexity of the problem. Their implementation on a grid cannot give reproducible results. So we use a grid simulator to evaluate the three algorithms.

The simulator is implemented above SimGrid and its MSG API [START_REF] Casanova | Simgrid: A toolkit for the simulation of application scheduling[END_REF], [START_REF] Casanova | Scheduling distributed applications: the simgrid simulation framework[END_REF]. The algorithms are implemented with the master/slave paradigm. A master node runs the scheduling algorithms and dispatch the tasks to process to slaves node according to the scheduler decisions.

Slaves node runs two threads, the first one is in charge of receiving requests from others nodes. When the requests is a tasks computation, the task to perform is put on a FIFO queue. Other requests (for example query about queue length, time when the processor will be idle) are answered in place.

The second threads iteratively removes a task from the queue and execute it. The computing power of an host is not shared, tasks are executed with full computational resources one after another without preemption.

Two of the three algorithms are off-line scheduler, for them the simulator is just a tool to validate the computed schedule. Indeed an off-line scheduler has a full knowledge of the platform before the actual execution and it's computed schedule is just played back on the execution platform.

The third algorithm is an on-line scheduler, thus it is closely tied to the simulator. For each of it's scheduling decisions this scheduler has two query each of the processors for tasks queue length and the time when there will be able to finish a given task.

Two evaluate the simulated algorithms performances we introduce the notion of efficiency as the ratio between the optimal makespan over the simulated makespan. As the scheduling problem is NP-Hard and the size of the problem is important, we are not able to evaluate the optimal makespan. However the number of jobs to process (N ) divided by the steady-state throughput (ρ) is a good optimal lower bound.

1) On-line:

The on-line algorithm is a simple list scheduler. The task selection is performed by selecting the first task that is ready to be scheduled. The processor selection is based on the earliest finish time heuristic.

When scheduling multiple instances of the same job this approach is problematic. In the example of Fig. ?? the on-line algorithm produces the gant in Fig. 4a for 10 instances. All of the tasks A are scheduled first because at time 0 there are ready. Then at time 10 the first task B is ready but all the slot are reserved for A.

This schedule has a makespan of 150 (5×A+10×B on p 1 ) and during the last 100 time units, p 2 is idle. Our solution is to limits the size of the processors input buffer, for example with a limit of 1 the gant diagram is shown in Fig. 4b. Because of this buffer limit some tasks B are available concurrently with tasks A, the makespan is lower (110 time units) and processors p 2 is idle only for 20 time units.

2) GATS: The original GATS algorithm is not designed to schedule multiple instances of the same job. One simple method to make GATS able to solve this problem is to schedule all the job instances as a single job. This method increases however the time and the physical memory necessary for GATS to compute the schedule. So we use a hybrid method that schedules the tasks in successive intervals of x jobs and appends the set schedules.

This method introduces a new problem: the concatenation of two successive intervals leaves some processors idle so, we overlap intervals as shown on Fig. 5. The interval Interval i 3) Steady state: As explained in III-C, the objective of the steady-state algorithm is to maximize the throughput. A side effect is that the makespan-minimization for finite number of instances is not an objective. The original algorithm execute initialization and termination sequentially, in this study, we parallelize these non-optimal stages with the on-line algorithm.

B B B B B B B B B B A A p 2 A A A A A A A A

VI. ALGORITHMS COMPARISON

In this part we compare the performances and the behavior of the chosen algorithms according to different parameters: platform characteristics, number of workflows to compute, etc. We study this behavior for different complexity and size of workflows.

The workflows are given by Fig. 6, Fig. 8 and Fig. 10. The letter inside the vertices of the workflow graph are the task type (i.e. the service) to be executed at this step of the workflow. The platforms are presented in Table 2. For instance, in this table, for the P F 3 platform, the processor p 4 needs 10 time units to perform a task A (p 4 (A) = 10).

A. Small jobs

The first example is a very simple workflow composed of two tasks A and B where B use the result of A, see Fig. 6. We execute several instances of this job. The idea here is to show, using this very simple job, one of the drawbacks we have identified.

A B

Fig. 6: Small job J 1

We execute this workflow on different homogeneous platforms, with equivalent execution time for the same function, or on heterogeneous platforms. The platforms described in Table 2 are the platforms used for Fig. 6 but we did more simulations to identify the possible issues. As a first result, we can note that even on homogeneous platforms the efficiencies of the algorithms may depend on the characteristics and very different results may be obtained as shown on Fig. 7a, Fig. 7b and Fig. 7c. On these figures we can observe three different behaviors for the algorithms. First, on Fig. 7a GATS generates nearly optimal results which tends toward an efficiency of 1 around 250 workflows.

On the opposite, the steady-state gives poor efficiencies, two times less than the GATS when the number of jobs is less than 200. Then the efficiency slowly increases. The reason of these poor efficiencies is that this approach try to use as much as possible the whole platform capabilities to optimize the flow: so it uses p 4 for executing A tasks while it cost almost 100 times more than on other machines. To use p 4 , the algorithm generate a very long period of 110 workflows, 220 tasks. Due to its conception, the algorithm first generates all the tasks needed to enter the steady-state period: 110 A tasks in the case of platform P F 1 and workflow J 1 . This means that before entering the steady-state period the algorithm must perform 110 A tasks and, when the number of jobs is less than 110, the schedule does not start a period. Then, we have to execute 110 workflows more to realize a period. This means than under 220 workflows no complete period is realized. For sets of workflows bigger than 220, the steady-state will progressively makes up the difference with the other algorithms and tends toward optimal. So, a first drawback of this algorithm is that, by using all the resources available on the platform, it may generate poor schedules.

Another important remark on the steady-state schedule for the P F 1 /J 1 case is that it starts by an initialization phase that generates all the needed tasks to enter the period. For these tasks, the aim is not to find the best schedule of the workflows implied in the initialization phase but rather to reach the period. We can illustrate that with the case of platform P F 1 and job J 1 . Each period computed by the steady-state algorithm will generate 110 tasks. So to enter this period, we need to generate 110 A tasks that have precedence constraints with the 110 B tasks that will be executed in the period. Obviously, looking at the P F 1 platform, it does not lead to a good schedule to first executes all these A tasks. This is the reason why the schedule behaves so badly in this case. For the on-line scheduling, the efficiencies are stable around 0.9 which is rather good, but as good as for the GATS. The explanation is the short view of this algorithm: at each step it just schedules the ready tasks without taking the rest of the workflows that has to be done. So it does not benefit form a global view on the schedule. We can consider that this result is rather good compared to the simplicity of the algorithm.

On Fig. 7b, for platform P F 2 and the same job J 1 , all the algorithms gets near optimal results. We can note that, in this case, the solution was obvious: the scheduling algorithms do not have an other choice than executing B tasks on processor p 1 and these tasks are critical as it it possible to execute A tasks more quickly either on processor p 2 or processor p 3 . In this case, the short view of the on-line algorithm, is not a drawback as there is nothing else to do than executing as fast as possible these B tasks.

On Fig. 7c, for P F 3 platform and the same J 1 job, we can note that the GATS algorithm decreases its efficiencies when the number of workflows to execute increases. The on-line algorithm is stable almost the same as on Fig. 7a while steadystate algorithm quickly tends toward an optimal efficiency. The reason of these behavior is the choice that has to be done on processor p 1 . To get good efficiencies, the three processors must be used to execute A tasks and sometimes processor p 1 must be used to execute B tasks. The steady-state algorithm find the optimal flow, with a period of 200 where p 1 start by executing 5 B tasks, for 100 and then execute one A while the other processors execute 2 A tasks each. In this case, GATS cannot find an optimal schedule when the size of the worksflows set is greater than 200. This results is closely linked to the size of the GATS period which is set to 400 tasks in this case, so 200 workflows. For the on-line algorithm, the results are explained as for Fig. 7a: the short view cannot anticipate to optimize.

In general, for small jobs, the scheduling decision is often simple and all the algorithms get good efficiencies, very close to the optimal. When the number of workflows is less that hundred, the GATS often gets the best efficiencies. However, the results are not reliable in the sense that on some particular values it may perform very badly. The standard list algorithm performs rather well but does not always reach the optimality: it may stay around 0.9 even when the number of workflows increase. The steady-state scheduling has to make up its initialization and termination stages.

From the three figures, Fig. 7a, Fig. 7b and Fig. 7c, we can also conclude that the architecture/characteristics of the platform impact on the algorithm behavior as, for the same simple job, the efficiencies may vary according to the following observations:

• the heterogeneity of the platform will extend the period and leads to longer initialization/termination phases and thus to an higher cost. So this algorithm will have no interest until a high number of workflows. • the complexity of the platform may generate poor results

for the GATS algorithm. This is probably linked to its division into intervals.

• the short view of the on-line algorithm may lower its efficiencies in some cases, in particular when the critical task must be executed on one processor and that other, earlier tasks, may be also affected to this processor.

In the following we study the behavior of the algorithms with much complex workflows.

B. Medium jobs

In this part we study the execution of jobs J 2 and J 3 (see Fig. 8 on the same platform P F 4 (see Table 3). The aim here is, on the one hand, to see if the behaviors differ when the complexity and size of the workflow is higher and, on the other hand, to analyze these behaviors regarding to the heterogeneity of the platform. 3 and compared to the platforms of Table 2 the heterogeneity is lower for both the execution times and the application available one the platforms. The results shown on Fig. 9a can be compared to Fig. 7a, where the steady-state slowly improve its efficiencies, and the results shown on Fig. 9b can be compared to Fig. 7c.

C. Big/complex jobs

This last part presents results with bigger jobs. To evaluate the impact of the dependency on the efficiencies, we use the same set of tasks but with different dependencies. Note that, as explained before, we have no communication cost in the experiments so that the deviations between the algorithms efficiencies is just linked to the dependencies characteristics. We execute these jobs on two different platforms P F 5 and P F 6 given in Table 4. Platform P F 5 is very simple and have homogeneous execution time. We added two more processors on platform P F 6 . These processors have heterogeneous execution times for the different services.

Globally, the results in these cases are good as must of them are no more worst than 10% from the optimal. So the response of the algorithms to the complexity of the workflow is good. There no need to presents the results of the algorithms on platform P F 5 as all the algorithms find nearly optimal solutions for these workflows, whatever the number of workflows is. The difference between the algorithms results are limited to the initialization phase and are lower than 2% from the optimal. For platform P F 7 , just adding two more processors gives very different results as shown on Fig. 11a and Fig. 11b. On Fig. 11b, all the algorithms performs well while on Fig. 11a, on-line and steady-state are 10% away from optimal, even for 500 jobs, and GATS decreases with the number of jobs.

The on-line algorithm and the steady-state algorithm performs equivalently due to the size of the steady-state period. The size of the period 100 and it terminates 37 jobs during this period. This means that the initialization phase have to execute a little bit less than 37 × 8 partial jobs before reaching the steady-state period. As a consequence, most of the 500 jobs are executed outside the period and the results are no so good.

For "chain like" jobs as J 4 and J 6 , GATS performs well until 250 jobs but its efficiency collapses for bigger sets of jobs, while for J 7 jobs the results are close to the optimal (see Fig. 11b). For J 5 , the efficiencies start to be unstable from 250 jobs. This probably depends on the interval size used. The explanation is in the length of the longest path in the workflow graph: the longest the path is the worst GATS behaves. When we have long path in the workflow's graph then the time spent by one workflow instance in the system increases. So the cost, in term of idle time on processors, of using several intervals for GATS also increases. One solution to this problem could be to use bigger periods to limit these waste of time, however this increases the computing complexity of the schedule as shown is the next part.

D. Computation time of the schedules

In this part we compare the time costs to compute a schedule. As the workflows are executed on a grid, what we want is to execute them as soon as we get the resource or the nodes from the reservation service. So the time spent to compute the schedule is of importance as during this time we cannot execute the workflows.

The Table 5 shows the average time needed on an Intel Xeon running at 3.2 GHz to compute the schedules depending on the number of workflows to execute. Both the on-line algorithm and the steady-state algorithm are very fast to compute the schedule. GATS gets reasonable execution time for less than 200 jobs but clearly does not support on the fly execution above this value.

VII. CONCLUSION AND FUTURE WORKS

The paper presents a study on three different scheduling algorithms for a set of jobs on SOA grids. Our application context focus on workflows applied to data and a typical use case of this work is the processing of sets of data for medical analysis and image rendering. The originality of the work is, on the one hand, the schedule of identical jobs which allows to use algorithms designed for flow optimization and, on the other hand, the SOA grid context where not all applications or services are available on all servers. Each of the three compared algorithm is suited for a specific need: the on-line algorithm is simple, the steady-state algorithm guaranties an optimal flow and the GATS algorithm generates schedules with good makespan.

This study exhibit several results: the impact of the platform and of the workflow characteristics on the efficiencies and some drawbacks in the algorithms design. The on-line algorithm suffers from a short view and use processors that will be needed in the close future for critical tasks. The steady-state algorithm has too long sub-optimal stages when the platform is heterogeneous or when the workflows are complex. The GATS algorithm becomes costly and instable or generates poor schedules in some cases when the number of workflows increases.

Our future works will concentrate on improving these algorithms to fill these deficiencies. For the on-line algorithm, we will try to extend its view by defining a scheduling window where critical tasks could be identified. For the GATS algorithm, we clearly need to reduce its cost. A possible way is to better tune the genetic parameters and adapt the interval size depending on the platform. Finally, the steady state scheduling can be improved by optimizing the period size and the initialization stage.

Fig. 2 :

 2 Fig. 1: Execution grid

1 Fig. 4a :

 14a Fig. 3: Simple problem

p 1 Fig. 4b :Fig. 5 :

 14b5 Fig. 4b: Gant diagram with buffers of size 1

Fig. 7a :

 7a Fig.7a: Simulation with platform P F 1 and job J 1

Fig. 7b :Fig. 7c :

 7b7c Fig. 7b: Simulation with platform P F 2 and job J 1

Fig. 8 :

 8 Fig. 8: Medium jobs

Fig. 9b :

 9b Fig. 9b: Simulation with platform P F 4 and job J 3

Fig. 10 :

 10 Fig. 10: Complex jobs

Fig. 11b :

 11b Fig.11b: Simulation with platform P F 6 and job J 7

TABLE I :

 I Exec. platform performances

			p 1	p 2	p 3	p 4
	Type	A B C	20 10 -	-10 10	--10	15 --
		D	-	-	10	10

Table

TABLE II :

 II Simulation platform P F 1 to P F 3

	Type		P F1		P F2			P F3
		p1	p2	p3	p4	p1	p2	p3	p1	p2	p3
	A	10	-	100 1000	10	50	40 100 100 100
	B	-	10	10	-	100	-	-	20	-	-
		1
		0.9
		0.8
	Efficiency	0.5 0.6 0.7
		0.3 0.4						On-line Steady state GATS
		0.2 50			100		250			500
						Batch size

TABLE III :

 III Simulation platforms P F 4

		1
		0.9
		0.8
	Efficiency	0.5 0.6 0.7
		0.3 0.4			On-line Steady state GATS
		0.2 50	100	250	500	1000
				Batch size
	Fig. 9a: Simulation with platform P F 4 and job J 2
		1
		0.9
		0.8
	Efficiency	0.5 0.6 0.7
		0.3 0.4			On-line Steady state GATS
		0.2 50	100	250	500	1000
				Batch size
						Type	P F4
						p1	p2	p3	p4
						A	20	-	-	20
						B	10	10	-	-
						C	-	10	10	-
						D	-	-	-	10

TABLE IV :

 IV Simulation platforms P F 5 and P F 6

	Type		P F5				P F6
		p1	p2	p3	p4	p1	p2	p3	p4	p5	p6
	A	10	-	-	-	10	-	-	-	100 1000
	B	-	10	-	-	-	10	-	-	10	-
	C	-	-	10	-	-	-	10	-	10	10
	D	-	-	-	10	-	-	-	10	-	-
		1
		0.9
		0.8
	Efficiency	0.5 0.6 0.7
		0.3 0.4						On-line Steady state GATS
		0.2 50			100		250			500
						Batch size
	Fig. 11a: Simulation with platform P F 6 and job J 4

TABLE V :

 V Schedule computation costs

	Size	On-line scheduler	Steady-state	GATS
	100	0.04s	0.05s	60.53s
	200	0.10s	0.11s	85.46s
	500	0.29s	0.23s	239.25s
	750	0.79s	0.75s	439.25s
	1000	1.09s	0.90s	617.43s


Jean-Marc Nicod
email: [nicod@lifc.univ-fcomte.fr

Laurent Philippe
email: philippe@lifc.univ-fcomte.fr

Hala Sabbah
email: sabbah]@lifc.univ-fcomte.fr

Optimizing the Cost of an Heterogeneous Distributed Platform

Keywords: grid, micro-factory, heterogeneous platform, cost optimization, workflow, scheduling

Distributed platforms become heterogeneous in more and more domains, as heterogeneous computing (HC) onto grids or reconfigurable factories in the industry. For production grids and factories, it is mandatory to control and optimize the economic cost of a such platforms regarding performance objectives. We present in this paper a study which purpose is to optimize the size of such environments depending on the workflow to execute or product to realize. The target platforms are either micro-factories, sized to manufacture products at the micrometric scale, or the heterogeneous computing domain where the key point is to reserve processors of an execution platform onto a grid to compute workflows like medical imaging applications. Thanks to the sizing of the platform, optimal or not, scheduling a workflow in HC environment or a production in the microfactory is easy because the size of the platform already takes the performance constraints into account. In this paper, we present general results on the platform size optimization. Numerical results are also presented to illustrate 3 cases of our study.

I. INTRODUCTION

Distributed platforms become heterogeneous in more and more domains. In particular this the case for the heterogeneous computing onto the grids and on reconfigurable factories in the production industry. This heterogeneity could come from different origins. The size of these platforms become larger and larger. It is thus too expensive to keep the homogeneity of the architecture when the platform size is extended. An other reason is that these platforms are often made by using existing processors or machines. It is also the case of the micro-factory production units (cells) that are dedicated to few tasks in a process.

The miniaturization of the products become mandatory in different domains such as mechanical, electronic, electromechanical or optic. New applications could be considered as the integration and the assembly of optic elements of very small size (mm) to achieve optic benches. Downsizing of manufacturing systems can lead to smart solutions, improving space utilization factor, reducing the price and energy consumption, including environmental conditioning such as temperature, humidity and cleanliness, as well as facility investment. The agility in reconfiguring the manufacturing lines in the factories will be elevated. Furthermore, the machines can be placed off the factory floor, to the design offices or classrooms, and distributed to small manufacturing laboratories, even in residential areas [?], [?].

However, the manipulation of this order of size poses several problems: the balance of the physical strengths in presence is not anymore the same that the one of the "macro" world and the capacities of human intervention are limits. Now a day, this type of production is mainly achieved by remoteoperation which limits its wider development. The automation is therefore necessary to consider a production at a bigger scale. This requires the collaboration between roboticians, producticians and programmers.

In this context, the platform behavior is very close to the grids in general and SOA grids in particular because of both heterogeneity and specialization of processors/cells. Indeed, designing a platform by reserving processors in a SOA grid is very similar to the design of a micro-factory with respect to a performance or cost objective. The dedicated processors, which are able to compute only the tasks defined by the libraries deployed on them, are similar to the actions performed by the reconfigurable micro-factory cells. The input or output data transfers can be compared with the moving of the micro-products. Moreover, because of the very small size of the products, we can easily buffer these products.

In the following, we present a study which purpose is to optimize the design of the micro-factory or grid context. The paper is organized as the following. Section II details the micro-factory specificities and the associated issues. The next section gives the architecture model and the notations we use to solve the optimization problem of the platform sizing. The section IV is the study of 5 different cases that cover the 16 possible cases. The section V shows algorithms and numerical results for the first three cases. The next section presents the scheduling step after the designing step. We conclude and give future work in the last section VII.

II. SPECIFICITIES OF THE MICRO-FACTORY

Micro-factory has a great potential for innovation of manufacturing systems for small sized products. The concept of micro-factory dates from the nineties [?] and becomes more closely related to our daily lives. It rests on two ideas: on the one hand to achieve a factory of very small size, that can hold in a case [?], and on the other hand to automate the production of micro-products [?].

A. Considerations on the size

In a research of flexibility, the micro-factory opposes the classic vision of the factories of the "macro" world by the size and functions of its robots. Macro-robots are complex and able to achieve a big number of operations. Micro-robots are rather of small size, i.e. few dozen centimeters large, and propose elementary operations. Some "macro" robots have a sufficient precision degree to manipulate objects of the "micro" world, but their precision is not on no account micrometric. On the other hand, for reasons of size, of flexibility, of energy consumption [?] or time of reconfiguration, they are not suited to the "micro" world. According to Tanaka [?], driving energies of facilities and energy required to control the environment of the system such as air conditioning and illumination decrease with decreasing size. The choice of microrobots, with little liberty degree and which cooperate, allows to reach the objective of size, precision and reconfiguration.

Here comes another thinking way about manufacturing systems. If the size of the manufacturing system is remarkably reduced, we will able to realize various styles of manufacturing, such as front shop manufacturing, mobile manufacturing in a vehicle. It implies a conception which is radically different from the factory in term of organization and management of the production: each micro-robots provides only a limited set of operations and it is necessary to cluster them to realize a complex function. This regrouping is called a cell. Then, the micro-factory is made by a set of cells.

The size of a cell is small, about ten centimeters. According to the task to be performed, the presence of independent actuators allows a configuration in the initialization phase for the calibration of the cell, and, in a least measure, a reconfiguration to dynamically change of the provided functions. These modifications can intervene in operate or inhibit some actuators or while modifying their order.

The factory designed to realize the final product is thus made by a cluster of basic cells on the same support. The size of this support is about one meter large and the organization of the cells is not necessarily linear there compared to most production units. The product moving function of the platform could be achieved by portico for instance. Because of the product size and the fact that products can be buffered, the transportation can be recovered by the work of the cells. Therefore, the micro-factory is very flexible.

B. The automation

The automation of the production of micro-product is a major issue of the micro-factory. Several factors act this level. First of all, it is necessary to note that strengths in presence to this order of size do not allow to use the traditional models of manipulation anymore. For example, the gravity strength of is not the most important anymore and uncontrollable electrostatic strengths can disrupt the products manipulation. For these reasons, the manner to handle the products must evolve to make place to a more flexible control that takes the increase of the mistakes into account. Besides these problems of order of size, the human intervention is difficult or generaly simply not possible. For instance, it is not possible to take such small products by hands or simply to see them without the help of a microscope.

Then one privilege an automated treatment where the nonmanaged cases are considered as mistakes. The organization is also an interesting point in the survey of the management of the micro-factories. Indeed, the regrouping of the actuators within cells allows to identify three levels of control for the automation. The order of the actuator is called a classic manner, that is to say some functions serve to enslave it in positioning and in time.

Cooperation between these actuators must also be managed since the action of just aone actuator is not sufficient for the realization of a function on the product. Therefore, we must integrate the synchronization between the actuators to guarantee the execution of a function. It is thus also submitted to strong temporal constraints and must offer real-time guarantees.

In opposite, the level of cooperation between cells is not necessarily synchronized since it is possible to stock the products between two cells: their very small size allows to consider buffer with a big number of products without difficulty. In this case, there is no real time constraints anymore and the organization of the production between the cells can be considered of the viwe point of the flow rather than of the control one. Thus, the automation of the cells management looks like the management of processes onto an heterogeneous distributed execution platform, as the grid.

C. Issues

The factory is known for the realization of micro-products. A product is achieved from components on which are applied a set of the functions, for example an assembly.

The application of a function to a component makes itself under the shape of a task. The set of the tasks of a product and their dependencies define a graph of tasks (DAG: Direct Acyclic Graph), called process. We limit it to DAGs without fork (intree) since it is not possible to duplicate a component. Different DAGs can generate the same product.

This context allows us to identify different optimization problems. We propose to optimize the design of an heterogeneous platform made of components (cells or processors) to ensure the fixed execution rate (number of DAGs per unit of time). The problem is well adapted to both contexts of the production of micro-products onto a micro-factory and the execution of workflows onto selected processors onto the grid. The scheduling step to allow the predicted execution rate is not difficult because the size of the platform already takes this constraint into account.

III. OPTIMIZATION

To simplify the reading of this section, we use the microfactory terminology. But when you read product, cell, microfactory, you can also understand respectively result, processor, heterogeneous set of processors on the grid. The both points of view are considered at the same level in this section.

In this section, we try to give an answer to the following question: What micro-factory for what production? Indeed, one of the issues for a micro-factory is the manner to size it in the perspective of a production of one or several products, each described by one or several graphs of tasks (DAG) as some alternative processes can exist for a given product.

We set he hypothesis where the cells exist and can perform the necessary operations for the tasks of the processes. Thus, every types of tasks can be done by at least one type of cell. In these conditions, knowing how to design a micro-factory consists in choosing how many cells of each types to use to allow one or several productions described by the tasks graph. The answer to the previous question consists then in guaranteing a level of performance, for example in number of finished products per time unit for a minimal cost. This last criteria not being the only one possible, the final size of the micro-factory is another one. The construction of a microfactory in this context is therefore a problem of optimization for which we propose some tracks for its resolution in different cases. But, before treating the most general case, it is important to exhibit intermediate cases for which optimal solutions to the optimization problem proposed here can be given. In the other cases, sub-optimal solutions must be proposed.

What impacts the level of generalities of the optimization problem is the fact that a cell is mono or multitask, the products defined with one or several processes or graphs of tasks and the productions thrown simultaneously with one or several products. From all combinations, we identify five cases:

(i) the cells are mono-task -can just perform one type of action -, one product is defined by only one process and only is manufactured for a production; (ii) same case that previously with simultaneously several products, so several processes, to be performed; (iii) the cells are always mono-task, but different cells can perform identical tasks with a different economical cost and with a different execution speed, for production of only one product defined by an unique DAG; (iv) cells are mono-task with the production of an unique product defined by several DAGs; (v) multi-tasks cells, only one product manufactured according to the definition of one process. All the other cases can be derive from the solutions exhibit here.

A. Architecture and Model

An heterogeneous computing grid is composed of processors P (hosts) which communicate between them by a network with high speed links. A grid G p is represented by a graph G p = (P, E). The nodes of P are the m processors P m of the grid. The Edges E are the network links between processors. The micro-factory is represented by the same description.

This grid treats a batch of I identical non preemptive tasks. The batch is then defined as a set of N instances G All tasks of G A may be all of different types or not. The example on figure Fig. 1 shows the graph of tasks and the table Table 1 is an example of platform.

T 1 200 ∞ ∞ ∞ T 2 ∞ 100 ∞ ∞ T 3 ∞ ∞ 200 ∞ T 4 ∞ ∞ ∞ 300
All the nodes of the platform are not able to perform all the task types. So, each tasks can just be executed only onto a sub-set of processors. The conditions of execution of each task type are given in matrices of execution cost that described the platform, as the table Table 1 for example. In the table, ∞ implies that the task described in the corrsponding line cannot be executed on the current processor.

One more time, this architecture and the model is available in the context of the micro-factory.

B. Notation

The following notations will be used in the following:

• M : number of processors used in the architecture platform; • m: processor (cell) index, m = 1, .., M ; • P T : Set of processor types;

• i: index of task types, i = 1, .., I with I different tasks in the application graph; • ♯i j : Occurrence number of task i in the graph (process) j; • r im : number of tasks of type i executed per time unit on the processor m; • r j : the quantity of instances of graph (process) j executed per unit of time or flow; • c im : execution cost of task of type i on a processor m;

• CT is the total cost by flow r;

• N : the total number of instances of graph executed on the platform.

IV. PROBLEM FORMALIZATION In this part we detail the five cases identified previously. a) Case i: In this case where one result of the workflow is computed by only one DAG and only one processor type can perform one task type. As in this case we have the following assumptions that a result is computed by only one DAG, and a processor type can perform only one task type, we introduce the following simplifications:

• Let c im = c i ;

• Let r im = r i ; • ♯i j = ♯i; • r j = r.
Therefore, the cost of the platform is:

CT = i ⌈ ♯i r i • r⌉c i
It is also possible to find the flow that optimizes the use of the platform and thus the minize the cost r min . This flow is the one that allows to ignore all the integer parts in the previous expression. We show how to obtain this value of r:

∀i, ♯i ri • r = k i with k i integer such that ai bi × r i = k i such that ⌈ ♯i ri • r min ⌉ = ♯i ri • r min we assume ♯i = a i • GCD(r i , ♯i) r i = b i • GCD(r i , ♯i)
for a given i we suppose that r min = b i , so ∀i, r min = ri GCD(ri,♯i)

for the set of i (to be integer everywhere):

r min = LCM i∈I ( ri GCD(ri,♯i) )
b) Case ii: Several results are concurrently computed at the same time by processors such that each of them is able to perform only one task type. Moreover, every results are described by only one DAG. For this case, we find the total number of processors needed to execute each type of tasks on all graphs ⌈ 1 ri j ♯i j • r j ⌉ . Then we multiply it by the economical cost of each processors. To get the total execution cost of a throughput r (CT (r)), we sum the previous value on all tasks as it is expressed by the following formula:

CT = i ⌈ 1 r i j ♯i j • r j ⌉ c i
We conclude that it is a similar case of the previous case except that we produce more than one result at the same time for this reason we introduce the term j in the expression of cost to summarize on all instances of process.

It is possible to find the flow that optimizes the use of the platform. This maximum flow is the one that allows to ignore all non integer parts in the previous expression. c) Case iii: Only one result defined by only one DAG, computed by processors performing only one task type. A same task can be done by processors of different types, of different speeds and of different costs.

A recursive expression computes the optimal cost of the platform according to the flow r of the DAG per unit of time. Let assume that α im is the number of processors of type m used in the execution platform and allowing the treatment of a task of type i view to a flow r im . The cost and the flow associated to the tasks of type i are therefore respectively m α im c im and m α im r im .

A dynamic programming algorithm allows to give this optimal cost thanks to its recursive expression the tasks of type i, knowing that their flow is r i = ♯i × r, with r the total flow of the workflow per unit of time. A sum on all tasks gives the global optimal cost of the factory offering a flow r:

C i (r i ) = min 1≤m≤M c im + C i (w(r i -r im ))
with w(x) = 0 if x ≤ 0 and x otherwise. The cost of the platform is then :

CT (r) = m C m (♯i × r)
d) case iv: It is the case where we have K possible DAGs for only one result, every type of tasks is being achieved by only one type of processor. The cost of a flow r is given by the following formula, with s k is the flow associated to the DAG k. r = k s k , #i k is the number of tasks of type i in the process k and r i is the flow attached to the task i:

CT (r) = i ⌈ 1 r i k ♯i k • s k ⌉ c i
The difficulty is to find how to decompose the sum of the s k . A sub-optimal solution could chooses first the low cost processors. An asymptotic approach to solve this case could also be considered. e) case v: In this last case, a processor can compute several different tasks, the speed of execution of a task is different according to the type of the task and the type of the processor. Finally, the unique result to compute is defined by only one DAG. The expression of the constraints of this case drives the writing of the quadratic-program, represented below:

Objective M in |T P | t=1 x t c t Subject To:          ∀t ∈ T P, |T | i=1 r t i rti < 1 ∀i ∈ T |T P | t=1 x t r t i = ♯i r ∀i ∈ T et ∀t ∈ T P, r t i rti < 1 r t i ≥ 0, ∀i ∈ T, ∀t ∈ T P with:
• ♯i: number of occurrence of task i in the process • r: flow of the graph; • r im : the maximal number of tasks of type i executed on the processor of type m; • r i : the number of tasks of type i per unit of time;

• r m i : the number of tasks of type i executed by a processor of type m; • x m : the number of tasks of processors of type m used in the architecture platform; • c im : the execution cost of task of type i by a processor of type m. In the following section, we give numerical results for the three first cases described before.

V. COMPUTING OF THE MINIMAL TOTAL EXECUTION COST OF I INDEPENDENT TASKS A. Computation of total execution cost for the first case

In this experience we suppose that our application graph is composed of four tasks (T 1 , T 2 , T 3 , T 4 ) as shown on figure Fig. 2, four processor/cells types (p 1 , p 2 , p 3 , p 4 ) each of them execute a type of tasks with a different speed as shown on table Table 1. The cost of each processor/cell is respectively 15 euro, 20 euro, 25 euro and 45 euro. To find the needed number of each type of processor/cell we have to know the number of occurrences of each type of tasks in the application graph. So we suppose that the occurrence of each type of tasks is respectively 3, 2, 2 and 3. This DAGs is shown in the figure Fig. 2. We aim to produce 500 graphs per time unit. Recall that the total execution cost of throughput r = 500 is calculated according to the formula CT (r) = i ⌈ ♯i ri •r⌉c i . The experience shows that the total execution cost for a throughput of 500 tasks per time unit is equal to: 670 euro; the size of the platform is 28 processors/cells among them 8 processors/cells of type p 1 , 10 processors/cells of type p 2 , 5 processors/cells of type p 3 , and 5 processors/cells of type p 4 . Also we provide the computation of the maximal throughput (r min ) that minimizes the total execution cost and we have obtained as result 200 tasks per time unit. We study the total execution cost in the interval of r from 0 to 500, we conclude that the function of cost increases obviously with r (see figure Fig. 3).

We consider another platform (Table 2) with the same input data as the previous experience the total execution cost become equal to 475 euro. The platform size is reduced to 18 processors: 5 processors/cells of type p 1 , 5 processors/cells of type p 2 , 3 processors/cells of type p 3 and 5 processors/cells

T 1 350 ∞ ∞ ∞ T 2 ∞ 200 ∞ ∞ T 3 ∞ ∞ 400 ∞ T 4 ∞ ∞ ∞ 350

B. Computation of the total execution cost for the second case

As mentioned above several products are collected at the same time by cells performing only one type of tasks, every product being defined by only one DAG. For this case the expression of cost is expressed as follow:

CT = i ⌈ 1 r i j ♯i j • r j ⌉ c i
The architecture platform we use in this section is shown in the table Table 3.

TABLE III: Matrix of processor performances

p 1 p 2 p 3 Tasks types T 1 150 ∞ ∞ T 2 ∞ 100 ∞ T 3 ∞ ∞ 200
In this case, we want to produce two products from two identical graphs. The throughput of the first graph is r 1 = 100 tasks per time unit and the occurrence of tasks T 1 , T 2 , T 3 is respectively 3, 2 and 2. The throughput of the second graph is r 2 = 150 tasks per time unit and the occurrence of tasks T 1 , T 2 , T 3 is respectively 2, 2, 3 . The corresponding DAGs are shown respectively in the figure Fig. 4 and Fig. 5. We suppose that the cost of the processor/cell p 1 is 8 euros, the cost of the processor/cell p 2 is 5 euro and the cost of the processor/cell p 3 is 10 euro. We obtain a cost of 97 euro with a platform formed of 13 processors/cells distributed as follow:

4 processors/cells of type p 1 , 5 processors/cells of type p 2 , 4 processors of type p 3 . The total number of executed task of each type is derived by the formula r i = j=J j=1 ♯i j r j , ∀i, where J is the number of graphs, and equals respectively 600 tasks per time of units of type T 1 , 500 tasks T.U of type T 2 , 650 Tasks T.U of type T 3 . The maximal throughput that minimizes the total execution cost is calculated by the formula r min = LCM i ( ri (GCD(ri,♯ij )) ) and is equal to 600 tasks per time unit. We study the total execution cost in the interval [0..250] and we conclude that the total execution cost of r increases with r as shown in figures Fig. 4 and Fig. 5, knowing that the total throughput is equal to the sum of the throughput of all graphs (r = r 1 + r 2 ). We take another platform (Table 4) with the same assumption as for the previous experience. The computation shows that the total execution cost to produce two products with two processes described above is equal to 61 euro. The total number of processors/cells from this platform is equal to 8 processors/cells, like follow 2 processors/cells of type p 1 , 3 processors/cells of type p 2 and 3 processors/cells of type p 3 . The maximal throughput that minimizes the total execution cost is equal to 300 tasks per time unit. We study the variation of cost with the variation of r on the interval ([0..250]) and we plot it on the figure Fig. 6.

TABLE IV: Matrix of processor performances

p 1 p 2 p 3 Tasks types T 1 300 ∞ ∞ T 2 ∞ 200 ∞ T 3 ∞ ∞ 300

C. Computation of total execution cost of the third case

In this case, a task can be executed in processors/cells of different types with different cost and speed. The table Table 5 shows the platform used in this section. As shown before, if we select a processor/cell, we dedicated the processor/cell to the task for which it is selected. So, we can compute the cost of the platform as the sum of cost of each task type (CT (r) = i CT (r i )). For the reason, we only give in this section numerical experiments for the optimal design for execution of the first task. Indeed, if we know the final throughput r, we can compute the throughput r i concerning each task T i (r i = ♯i × r). The processor/cell performances to perform the first task T 1 are shown in the first line of the table Table 5. The cost of the processors/cells are respectively 10 euros, 20 euros and 40 euros. The algorithm Fig. 1 shows the algorithm to find the greatest step size and the minimal number of iterations while studying the cost in the interval from 0 to r i . The algorithm Fig. 2 explains the computing of the total execution cost in this case. As we explained before, this algorithm is a dynamic programing based algorithm. w(x): the function which returns 0 or x if x < 0 or not r i [p]: the throughput available on the processor p for the type i k: the number of iterations d: the greatest step value that allows us to cover the possible values of the throughput before r C[p]: cost of the processor p cost[j]: optimal cost of the platform for the throughput j × d addedP roc [j]: processors added at the step j for the optimal solution with the current throughput j × d procT oAdd: number of the processor to add at this step to the platform to reach the optimal cost for the current throughput begin for j = 1 to k do min ← cost[w(j -

r i [0]/d)] + C[0] procT oAdd ← 0 for i = 1 to n -1 do if (cost[w(j -r i [i]/d] + C[i]) < min) then min ← cost[w(j -r i [i]/d)] + C[j]
procT oAdd ← i endif endfor cost[j] ← min addedP roc[j] ← procT oAdd ; endfor /*reconstruction of the solution to this optimization problem */ printf "throughput" k × d "with the cost" cost[k] j ← k while j > 0 do print ("processor" addedP roc[j], "next throughput"

j × d -r i [addedP roc[j]]) j ← j -r i [addedP roc[j]]/d endw return addedP roc, cost[k] end
We ran the two previous algorithms with two different throughputs, 450 and 300 tasks per time unit, and deduced the following:

• For a throughput of 450 tasks per time unit, we obtain the following results: the step to verify the cost is equal to 10, number of iterations is 45, the total execution cost is 150 euro, the size of platform is 5 processors/cells: 1 of type p , 1 of type p 2 and 3 of type p 3 . • For a throughput of 300 tasks per time unit, we obtain the following results: the step to verify the cost is equal to 10 , number of iterations is 30, the total execution cost is 100 euro, the size of platform is 2 processors/cells: 1 of type p 2 , 1 of type p 3 . The figure Fig. 7 gives the optimal cost of the platform for the execution of task T 1 in the case (iii) in the experimental conditions described before.

The table Table 6 shows the optimal number of processors/cells of each type p 1 , p 2 and p 3 each different target value of r 1 when optimizing the cost of the platform.

VI. SCHEDULING

In our study, we also interested ourselves to scheduling flows of micro-products on a set of processors/cells as we defined them. from the context description and according to the α|β|γ classification [?] of the scheduling problems, the problem is defined by: Ur-batch of intrees-Cmax. Indeed, the platform is heterogeneous as the execution times are not related and what we try to optimize is the Cmax -makespan or optimal execution time -of a flow of intrees. This problem is known to be NP-Complete [?] and we must therefore either use an heuristic or modify the problem. The model presented at the global level offers to come closer to the models used in the distributed systems and more especially of the computation grids. The main differences rest on the type of the products we perform and on the functions of transportation, but the realization of a function on a micro-product or a computer data is modulated in the same way. With regard to the type of the products, we have seen that it is limited to the intree since we cannot duplicate a micro-component without new task. We are therefore in one under-case of computer applications. Concerning the function of transportation, it is possible in spite of all to assimilate the network topology to a complete network in the case of a portico or to a graph in the case of transporter.

From these observations, we looked for what could be the solutions brought to this problem and explored three approaches [?], [?]. The first is a dynamic approach that allocates the tasks dynamically to the processors, according to their availability. The second [?], [?], [?], [?] uses a heuristic of scheduling, based on the genetic algorithm, having good results for one DAG and we adapted it for the flow. The third [?], [?], [?], rests on a vision of the problem a little different since it is interested to the flow but it gives an optimal solution, we also adapted it to the management of flows. The assessment of these three techniques has been achieved by simulation and the results show without big surprise that, in a general case, the dynamic solution almost always offers optimal results, the heuristic solution is good on the small flows and the solution-oriented flow is good on the flows of important size. The interest of work resides therefore more in the borders that limit these techniques and the differences of performances gotten. Another interesting result is the dependence of the results with the flow of the graph that characterizes the process, some approaches giving better results for certain processes of equivalent flow size.

We work currently to the optimization of these different approaches and more especially the flows oriented one because several issues can be addressed our context to improve its results when the number of workflows or products to perform decreases.

VII. CONCLUSION

In this paper we have presented several results for the optimization of cost in the context of distributed heterogeneous platforms as grids or micro-factories. In particular we give formal results for the simpliest cases and a dynamic programming algorithm for a much complex case. We have illustrated through examples of different platforms and products.

As we have just seen, the micro-factory presents many domains of interests with regard to its optimization: as much to the level of its scheduling as of its control, because of the flexibility and the new constraints that are attached. The multilevels aspects and the interactions between these levels defined new issues that will study in the future.

The automatic organization of micro-factories is not however in a phase of realization, even though some exploratory studies permit to consider its implementation in the coming years. The goal of our works is therefore to anticipate this realization in order to be able to come with it, to guide it and to put the potentialities of the view point of the production optimization forward.

  of work G A . The work G A is an oriented acyclic graph (DAG) composed of the T i tasks of T and the dependencies D, the set of edges between tasks.

Fig. 1 :

 1 Fig. 1: Graph of tasks

Fig. 2 :

 2 Fig. 2: Graph of tasks

2 Fig. 3 :

 23 Fig. 3: Cost of 2 platforms with the graph Fig.2

Fig. 5 :

 5 Fig. 4: Graph of tasks

Fig. 6 :

 6 Fig. 6: Cost of platform in the case (ii)

Algorithm 1 :

 1 cas3Parameters(r i : array of integer, n: integer): integer r i : array of integer from which we compute the gcd. n: the size of r i k: the number of iteration using in the algorithm 2 d: the greatest step to compute the platform design (algorithm 2)begin d ← gcdN(r i , n) /*gcd of n integer in r i */ k ← d/r if (d%r) > 0 then k ← r/d else k ← r/d + 1 endif return d, k endAlgorithm 2: TotalExecutionCost( cost, r i , C)

Fig. 7 :

 7 Fig. 7: Cost of the set of processors/cells which performed the task T 1 in the case (iii)

TABLE I :

 I Matrix of processors/cells performances

	p 1	p 2	p 3	p 4
	Tasks types

TABLE II :

 II Matrix of processor performances

	p 1	p 2	p 3	p 4
	Tasks types

TABLE V :

 V Matrix of processor/cell performances: r im

			p 1	p 2	p 3
	Tasks types	T 1 T 2 T 3	10 20 30	50 30 50	130 100 120

TABLE VI :

 VI Optimal number of processors/cells p 1 , p 2 and p 3 for each throughput r 1

			number of p i
			p 1	p 2	p 3
		50	0	1	0
		100	0	2	0
	r 1 throughput	150 200 250 300 350 400	2 2 0 0 0 1	0 1 0 1 2 0	1 1 2 2 2 3
		450	1	1	3
		500	0	0	4