Keywords: Réallocation, batch schedulers, métaordonnanceur, grilles de calcul

Analyse du replacement de tâches dans un environnement de grille dédié

Résumé : Dans ce rapport, nous étudions l'impact de la réallocation de tâches dans un environnement de grille. Plus précisément, la plate-forme cible qui nous intéresse est un environnement multi-grappes où les grappes peuvent être homogènes ou hétérogènes et utilisent différentes politiques d'ordonnancement local. Dans ce contexte, nous proposons un mécanisme de réallocation qui migre des tâches qui n'ont pas encore commencé leur exécution, d'une grappe à une autre. Nous réalisons des simulations utilisant des traces provenant de plates-formes réelles pour étudier l'impact de la réallocation. Nous comparons deux algorithmes de réallocation, chacun utilisant différentes heuristiques pour sélectionner l'ordre dans lequel ordonnancer les tâches.

Les résultats montrent que dans certains cas il est possible d'avoir un gain important sur le temps moyen de réponse des tâches (allant jusqu'à presque un facteur quatre). Dans la majorité des autres cas, la réallocation apporte un bénéfice pour les tâches des utilisateurs. Il est donc intéressant d'implanter un tel mécanisme dans un intergiciel de grille.

Introduction

In order to meet the evergrowing needs in computing capabilities of scientists of all horizons, new computing paradigms have been explored. Supercomputers were developed to perform massive parallel computations but their cost (acquisition and maintenance) is still prohibitive. Another approach was developed later and was called the Grid. The Grid is the aggregation of heterogeneous computing resources connected through high speed wide area networks. Computing resources can be sequential or parallel architectures (clusters of workstations or parallel machines), the later being generally managed by a local resources manager, also called batch scheduler. In such a case, the submission of a job necessitates a number of processors and a walltime. The walltime is the expected execution time for this job. Usually, it is given by the user or computed using data mining techniques.

In most local resources management systems, when the walltime is reached, the job is killed, so users tend to over-evaluate the walltime to be sure that their job finishes its execution. Furthermore, in [START_REF] Sonmez | Trace-Based Evaluation of Job Runtime and Queue Wait Time Predictions in Grids[END_REF] authors show that resources management systems are not able to put up with burst of submissions. A paper by Beltrán and Guzmán [START_REF] Beltrán | The Impact of Workload Variability on Load Balancing Algorithms[END_REF] presents the impact of the workload variability on the local resources management system and show that the variability leads to bad scheduling decisions.

In this paper, we place ourselves in a multi-cluster Grid connected through a high bandwidth network. We propose a reallocation mechanism that should better take into account the errors on walltime and the load bursts in the local resource management systems by moving waiting jobs from one cluster to another. The mechanism we propose is at the middleware level and thus it can be used to connect different clusters together while each cluster keeps its local scheduling or resource allocation policies. Each job submitted onto the platform will be executed on a cluster chosen by the middleware without intervention from the person submitting the job.

We propose two reallocations algorithms using six different heuristics each. We evaluate them by comparing them on different metrics to an execution where reallocation is not performed. Preliminary work was proposed in [START_REF] Caniou | Meta-Scheduling and Task Reallocation in a Grid Environment[END_REF] and we extend this work in several directions. We evaluate different algorithms to implement the reallocation mechanism, different heuristics to select the jobs, the automatic adjustment of the walltime to the speed of the cluster, and several other optimizations.

The remainder of the paper is as follows. In Section 2, we present the architecture we chose to implement reallocation algorithms and mechanisms. We also detail the different (re)scheduling heuristics used and compared in this work. Then we explain the experimental framework in Section 3, giving information on the simulator that we developed, on the platforms simulated with real-world traces, scenarios of experiments that were conducted as well as the metrics on which results are compared in Section 4. In Section 5 we present related work and we conclude in Section 6.

Tasks Reallocation

In this section, we describe the proposed tasks reallocation mechanism. First, we present the architecture (Section 2.1) of the components of the system. Then we present the different algorithms used for the tasks reallocation (Section 2.2).

Architecture of the Solution

The architecture that we propose in order to manage task reallocation, is close to the GridRPC standard from the Open Grid Forum. Thus it can be implemented in GridRPC compliant middleware such as Diet [START_REF] Caron | DIET: A Scalable Toolbox to Build Network Enabled Servers on the Grid[END_REF] and Ninf [START_REF] Sato | Ninf: A Network Based Information Library for Global World-Wide Computing Infras-In HPCN Europe[END_REF].

The architecture relies on three main components: servers which are deployed on computing resources, an agent (or a set of distributed agents), and clients that send computing requests. Servers and their services are registered to the agent. When a user performs a request, the client contacts the agent which can perform some meta-scheduling in order to determine the best server according to a given metric. Usually, the server able to finish the job the earliest is chosen. In such a case, transfers with the agent are required to communicate information concerning the service and monitoring and/or prediction information. Then the identity of the chosen server is sent back to the client that submits its request. Eventually some data transfers are also performed. Finally, the server returns the results to the client if needed.

Because such a middleware is deployed on existing resources and has limited possibilities of action on the local resources managers, we developed a mechanism that only uses simple queries such as submission, cancellation, and estimation of the completion time.

The server deployed onto the frontal of the parallel resource is in charge of the interactions with the resource manager. It also computes each estimation of the walltime hence depending on cluster characteristics (in our work, we focus on processor speed, but better models involving application detailed modeling with communications information with regard to the architecture, bandwidth, and latency of the parallel resource can be used).

The agent (meta-scheduler) has to assign to a computing resource any incoming job sent by the client. Different scheduling algorithms can be deployed. The two simplest are Random (choose a resource randomly) and Round Robin (each cluster is selected one after the other). Such mapping heuristics are sometimes available because monitoring may not be implemented or available on some servers. A Grid middleware may also use other INRIA online algorithms such as Minimum Completion Time (MCT) if some monitoring and performance prediction are available (see [START_REF] Muthucumaru Maheswaran | Dynamic Matching and Scheduling of a Class of Independent Tasks onto Heterogeneous Computing Systems[END_REF] for a taxonomy of online and offline heuristics). In this study, we consider that the metascheduler uses a MCT policy.

Algorithms

This section presents two versions of the reallocation algorithm (Section 2.2.1) and the heuristics used in the algorithm to select jobs (Section 2.2.2).

In the first version, the algorithm gets a copy of the list of jobs stored in the waiting queues of the local resources management systems on the different clusters and will try to reallocate the jobs. The second version of the algorithm cancels all the waiting jobs in all the queues and resubmits jobs in a new order.

Reallocation Algorithms

Algorithm 1 describes the reallocation algorithm in its first version. The algorithm works as follows: it gets all jobs in the waiting queues of all clusters; it selects a job with the implemented scheduling heuristic; if it is possible to submit the job somewhere else with a better estimated completion time (ECT) of at least a minute, it cancels the job at its current location and submits it on the other cluster; finally, it starts again on the remaining jobs.

Algorithm 1 Reallocation algorithm.

l ⇐ waiting jobs on all clusters while l = ∅ do Choose j ∈ l according to a scheduling heuristic if j.newECT + 60 < j.currentECT then Cancel j on its current cluster Submit j to the new cluster end if l = l \ {j} end while

To have a better idea of what is done, consider an example of two batch systems with different loads (see Figure 1). At time t, task f finishes before its walltime, thus releasing resources. Task j is then scheduled earlier by the local batch scheduler. When a reallocation is triggered by the meta-scheduler at t 1 , it reallocates tasks h and i to the second batch system because their expected completion time is better there. To reallocate the tasks, h and i are sequentially canceled on the first batch and then submitted to the second. In this example, the two clusters are homogeneous so the tasks have the same execution time on both clusters. In an heterogeneous context, the length of the tasks would change between the clusters. A task starting earlier on a cluster does not implies that it will also finish earlier. Algorithm 2 is a reallocation algorithm with cancellation. It starts by canceling all jobs in the waiting queues of all clusters. Then it selects a job according to a scheduling heuristic. Finally it submits the job to the cluster giving the best estimated completion time before and starts again on each of the remaining jobs.

Algorithm 2 Reallocation algorithm with cancellation.

l ⇐ waiting jobs on all clusters Cancel each job in l while l = ∅ do Choose j ∈ l using a heuristic Submit j to the cluster according to a scheduling heuristic l = l \ {j} end while

The reallocation event in both versions of the algorithm is triggered periodically. In the experiments presented in this paper, the frequency of reallocations is set to one hour. It is rare enough not to constantly send requests to the local resources managers to obtain updates, and is often enough to improve performances (see section 4.1 and 4.2).

INRIA

Scheduling Heuristics

To choose the job that will be selected for reallocation, several heuristics are used: one online heuristic and five offline heuristics. The online heuristic [START_REF] Schwiegelshohn | Online scheduling in grids[END_REF] takes jobs, one after another, while the offline heuristics are executed on a set of jobs. Offline heuristics are supposed to give better results, but their time complexity is bigger. The heuristics we compare are the following: MCT Online algorithm. Assigns a task to the cluster that gives the minimum expected completion time. MCT takes jobs sequentially in their submission order.

MinMin/MaxMin Offline algorithms. Ask the expected completion time of all tasks and selects the one with the minimum/maximum value. These heuristics try to give priority to respectively small/large tasks.

MaxGain Offline algorithm. It gets the minimum expected completion time of each task. Then it computes the gain of moving each task. The gain is the time in seconds that the task would gain if it is reallocated (Gain = CurrentECT -N ewECT ). The task with the highest gain is selected and the heuristic starts again on the remaining tasks.

MaxRelGain Offline algorithm. Same as MaxGain, but divides the gain by the number of processors of each task, thus preferring small tasks, except if a large task has a very large gain.

Sufferage Offline algorithm. It gets the two best estimated completion times for each task, computes the sufferage value as the difference between the two best estimated completion times and selects the task with the maximum sufferage value.

Concerning the execution time for each heuristic during the rescheduling event, MCT is the fastest. It takes the jobs in their arrival order without concern of the other jobs and it is executed n times, with n the number of waiting jobs, so its complexity is O(n). The offline heuristics on the other hand need to have information of all the jobs each time, so the execution time is O(n 2 ).

Experimental framework

In this section we depict the experimental framework by presenting the architecture of the simulator we used to run our experiments (Section 3.1), the simulated platforms (Section 3.2), the jobs injected on those platforms (Section 3.3) and the metrics used to compare the heuristics (Section 3.4).

Simulator

In order to simulate task reallocation in a distributed environment composed of several clusters, we use Simgrid [START_REF] Casanova | SimGrid: a Generic Framework for Large-Scale Distributed Experiments[END_REF], a distributed environment simulator, and Simbatch, a batch systems and parallel tasks simulator.

Simbatch [START_REF] Caniou | Simbatch: An API for and predicting the performance of parallel resources managed by batch In Workshop on Secure, Trusted, Manageable and Controllable Grid Services (SGS)[END_REF] is a C API developed to facilitate the conception and evaluation of local resources management systems algorithms [START_REF] Dror | Parallel job scheduling -a status report[END_REF]. It is built on top of the Simgrid library, which provides simple network description models as well as host descriptions and is able to take into account link contentions and latencies. Simbatch can simulate the main algorithms used in batch schedulers such as First Come First Served (FCFS) and Conservative Back-Filling (CBF). FCFS [START_REF] Schwiegelshohn | Analysis of first-comeparallel job scheduling[END_REF] gives the user the earliest slot at the end of the job queue. This algorithm is available as default policy in most batch systems such as PBS [START_REF] Bayucan | Portable batch system: Exreference specification[END_REF], Sun Grid Engine [START_REF] Gentzsch | Sun Grid Engine: Towards Creating a Compute Power Grid. Cluster Computing and the Grid[END_REF], Maui [START_REF] Jackson | Core Algorithms of the Maui Scheduler[END_REF]. CBF [START_REF] Lifka | The ANL/IBM SP scheduling system[END_REF] works almost like FCFS, but instead of choosing the slot at the end of the job queue, if it can find a slot earlier in the queue (back-filling) without delaying other jobs (Conservative), this slot is returned to the user. This scheduling algorithm is available in batch systems such as Maui, Loadleveler [START_REF] Subramanian Kannan | Workload Management with LoadLeveler[END_REF], and OAR [START_REF] Capit | A Batch Scheduler with High Level Components[END_REF] among others.

The simulator is divided in three main components:

The server part is running on the frontal of a cluster and interacts with the batch system. It is able to submit jobs, cancel a waiting job, return an estimation of the completion time of a job (already submitted to the batch system or not) and return the list of jobs in the waiting state.

The meta-scheduler part matches incoming jobs to a server according to a scheduling heuristic and periodically reallocates jobs in waiting time on the platform using one of the reallocation algorithms described in Section 2.2.1.

The client part sends jobs to the meta-scheduler. Jobs sent by the client are parallel rigid jobs with a number of processors fixed in advance.

Platforms

We consider two platforms with different numbers of cores distributed on three sites. Each platform is used in an homogeneous case (all clusters are similar in processor speed, but not in number of processors) and in an heterogeneous case (clusters differs in terms of CPU speed and number of processors).

The first platform corresponds to the simulation of three clusters of Grid'5000 [START_REF] Bolze | Grid'5000: A Large Scale and Highly Reconfigurable Ex-perimental Grid Testbed[END_REF]. The three clusters are Bordeaux, Lyon, and Toulouse. Bordeaux is composed of 640 cores and is the slowest cluster (if clusters are The second platform corresponds to experiments mixing the trace of Bordeaux from Grid'5000 and two traces from the Parallel Workload Archive1 . The three clusters are Bordeaux, CTC, and SDSC. Bordeaux has 640 cores and is the slowest cluster. CTC has 430 cores and is 20% faster than Bordeaux. Finally, SDSC has 128 cores and is 40% faster than Bordeaux.

Scenarios

We consider seven scenarios among which six scenarios use the traces of tasks submission on a one month long period, and taken from the Grid'5000 platform. Traces contain the jobs of the first six months of 2008. Table 1 gives the number of jobs per month on each cluster. The seventh scenario is a six month long simulation using two traces from the parallel workload archive (CTC and SDSC) and the trace of Bordeaux on Grid'5000. The trace from Bordeaux contains 74647 jobs. The trace from CTC has 42873 jobs. The trace from SDSC contains 15615 jobs. Thus, the total number of jobs of the seventh scenario is 133135.

In our simulations, we consider that all jobs are submissions. Traces from Grid'5000 include advance reservations but we consider them as normal submissions. It should not change the results because we compare simulations with other simulations. Furthermore, note that we add a metascheduler to map the jobs onto clusters at submission time, as if a grid middleware is used. In reality, users submit where they want (usually they submit to the site closest to them).

The traces taken from the Parallel Workload Archive were taken in their standard original format, i.e., they also contain "bad" jobs [START_REF] Dror | Workload Sanitation for Performance Evaluation[END_REF]: Since we want to reproduce the execution of jobs on a cluster, we need to keep all the "bad" jobs removed in the clean version of the logs because these jobs would have been submitted in reality.

Evaluation metrics

In order to evaluate the reallocation algorithm and the behavior of the scheduling heuristics, we use different metrics. The first type of metrics is system centered metrics. The second type is user centered metrics.

System metrics

Jobs impacted by reallocation: The percentage of jobs whose completion time is changed compared to an execution without reallocations. Only the jobs whose completion time changes are interesting in our study. Note that we use a time reference in this study to order performance of heuristics, but results on this metric are not transitive.

Number of reallocations: Number of times jobs were moved. A job can be counted several times if it was migrated several times. A small value is better because it means that there will be less transfers.

User metrics

Jobs finishing earlier: Percentage of jobs that finished earlier with reallocation than without. This percentage is taken only from the jobs whose completion time changed with reallocation. A value higher that 50% means that there were more jobs early than late.

Gain on average job response time: Gain on average response time of the jobs compared to the scenario without reallocation.

The response time corresponds to the time spent in the system from the submission to the completion [START_REF] Dror | Metrics and Benchmarking for Parallel Job Scheduling[END_REF]. The gain is computed only for the jobs whose completion time changed. This is the most important value for users because they generally want their jobs to finish as soon as possible.

Figure 2 illustrates why there are jobs delayed and others finishing earlier onto a platform composed of two clusters. At time 0 a reallocation event is triggered. A task is reallocated from cluster 1 to cluster 2. Thus, some tasks of cluster 2 are advanced in the schedule. On cluster 1, the task is back-filled. However, assume the task finishing at time 6 finishes at time 2 because the walltime was wrongly defined (see the task with the dashed line). Thus, because of the newly inserted task, the large task on cluster 1 is delayed (and all the tasks after if there are some).

With FCFS, reallocation can also cause delay: if a job is sent to a cluster, all the jobs submitted after may be delayed. Inversely, the job that was reallocated to another cluster now leaves some free space and it may be used by other jobs to diminish their completion time.

Results

In this section, we study the two versions of the reallocation algorithm onto several scenarios: homogeneous or heterogeneous platforms; using FCFS or CBF as local resource manager; using different sets of jobs traces; metaheuristic implemented as a reallocation scheduling policy. For a single experiment, each cluster uses the same batch algorithm. Thus, we have performed a total of 364 experiments among which 28 experiments without reallocation (one for each job trace, heterogeneity and batch algorithm) as reference experiments, against which we compare our solutions.

First, we evaluate the reallocation algorithm without canceling the jobs in Section 4.1 and then, in Section 4.2, we present the results on the algorithm with cancellation. Finally, we compare our results two versions in the algorithm in Section 4.3.

Results without Cancellation

This section presents the results obtained for the different metrics for the reallocation without cancellation of jobs (see Algorithm 1). The reallocation algorithm was triggered every hour starting one hour after the first job submission.

Table 2 shows the percentage of jobs whose completion time changed on homogeneous platforms when reallocation was performed. The percentage is quite low because quite a large amount of jobs are able to start execution as soon as they are submitted. This percentage is higher on platforms using FCFS. Indeed, jobs are not back-filled, thus waiting queues are longer, and thus more jobs can be delayed and reallocated. The percentage of jobs impacted when reallocation is performed mainly depends on the submissions. If the platform is quite empty, submitted jobs will start execution as soon as they are submitted so reallocation will not take them into account. On the other hand, when the platform is very loaded, most jobs will not have the opportunity to be reallocated because it would not be possible for them to finish earlier, thus reallocation will also not take them into account.

Table 3 shows the percentage of jobs whose completion time changed on heterogeneous platforms when reallocation was performed. In the heterogeneous case, there are sometimes more jobs whose completion time changed with CBF than with FCFS. This percentage is still quite low because it depends partly on the submissions of the jobs. During low load, jobs start execution as soon as they are submitted. When the platform is very loaded, waiting queues are long and jobs have less chance to be reallocated because they would be submitted at the end of other queues. Tables 4 and5 show the number of reallocations per experiment on homogeneous and heterogeneous platforms respectively. Note that a same job can be reallocated several times. In all cases, the number of reallocation is small relative to the number of tasks of each experiment. On average, the number of reallocations corresponds to 2.3% and the maximum value is 13.5%. The small number of reallocation implies that there would not be too many reallocations of jobs between clusters thus not overloading the network.

Tables 6 and7 show the percentage of jobs finishing earlier with reallocation than without reallocation. This percentage only takes into account the jobs whose completion times changed (cf. Tables 2 and3). Thus, a value higher than 50 means that there are more than half of the jobs that finish earlier with reallocation than without.

Table 6 shows the percentage of jobs finishing earlier with reallocation than without on homogeneous platforms. In most cases there are more jobs finishing earlier than later. The different heuristics behave differently depending on the trace. For example, MinMin is the only heuristic that gives more jobs early in April with FCFS but is one of the two heuristics that have more jobs late in June. On average, MinMin gives the bests results for FCFS by a few percents. On CBF platforms, heuristics based on the gain are usually less good than the other heuristics. The other heuristics give similar results on average. MinMin differentiates itself from the other with worse results in February, but better results in June.

Table 7 shows the percentage of jobs finishing earlier with reallocation than without on heterogeneous platforms. In this case, MinMin is the best on average in both FCFS and CBF platforms, and except in the case (homogeneous/apr) where all reallocation policies give worst results on this metric, reallocation with the MinMin heuristic always improves the final schedule. There are more cases where there are more jobs late than early with CBF than with FCFS. We can see the impact of the batch algorithm on the reallocation results. Indeed, on FCFS platforms, all results are negative for April while they are all positive with CBF. We can see the opposite behavior in February or May.

The relative average response time is compared with no reallocation for the jobs whose completion time changed. A value of 0.85 means that the reallocation provided a gain of 15% on the average response time of the jobs. A value higher than 1 means that the average response time is bigger than without reallocation.

Table 8 shows the relative average response time of the heuristics on homogeneous platforms. In the FCFS setup, MinMin gives the best results. It is the only heuristic than never has a higher average response time than the experiments without reallocation, with a peak performance of 23% for (FCFS/jan), achieving to beat MaxGain and MaxRelGain which are a priori specifically designed for this metric. With CBF, the difference between heuristics is smaller but MinMin still have the best average on the seven experiments by one percent. MCT is the second best in average for CBF while it was the worst with FCFS.

Table 9 shows the relative average response time of the heuristics on heterogeneous platforms. Here, MCT has the best average in both the FCFS and CBF setups. These good results come from one experiment (January) where in both cases MCT improves a lot the average response time while other heuristics give less satisfactory results. Without this experiment, MCT would give results close to the other heuristics on average. On FCFS platforms, MinMin and MaxRelGain perform well and are better than the other heuristics on average, excluding MCT. On CBF platforms, all heuristics are close and none has a big advantage on the others. Still, MCT has a 3% advantage on the second best and can improve the relative average response time by 12% on average. The previous tables (8 and 9) show that to diminish the average response time of jobs, the choice of the heuristic can not really be made based on the results since they are too close. Then, the heuristic of choice would be MCT because of its simplicity of implementation compared to the others. Furthermore, average results of MCT on heterogeneous platforms with CBF (which seem to be the most realistic platforms) are quite good, so this choice seems the best. It is possible to implement MinMin which usually gives better results but it will make more requests to obtain estimations of the completion time of jobs.

Results with Cancellation

This section presents the results obtained on the different metrics for the reallocation algorithm with cancellation (see Algorithm 2), thus heuristics are postfixed with "-C" in tables presenting the results. As for the previous version of the algorithm, the reallocation is triggered every hour.

Tables 10 and11 show the percentage of jobs whose completion time changed on homogeneous and heterogeneous platforms when reallocation with cancellation is performed. The percentage depends on the trace used and usually is between 10% and 30%. On both homogeneous and heterogeneous platforms, there are more jobs whose completion time changed with reallocation with FCFS than with CBF. CBF is able to execute the jobs faster thanks to back-filling, so the waiting queues are smaller.

Table 12 and 13 show the number of reallocations per experiment on homogeneous and heterogeneous platforms. To count the number of reallocations, we save the location of a job and if it is submitted on another cluster, we counts this as a reallocation. The number of reallocations is small compared to the number of jobs per experiment. On average, the number of reallocations corresponds to 5.8% and the maximum is 28.8%. There are more reallocations on FCFS platforms. It is for the same reason that more jobs had a different completion time with FCFS than CBF. CBF executes jobs more quickly so the waiting queues are smaller. Table 14 shows the percentage of jobs finishing earlier with reallocation than without on homogeneous platforms. The percentage of jobs finishing earlier with reallocation than without is most of the time higher than 60%. There is only one case where there are more jobs late than early, thus to the user point of view, more of his jobs finish sooner using reallocation. The results with FCFS give MinMin and MaxGains heuristics as winners. On CBF platforms, results are closer, but MinMin becomes the second worst heuristic on average.

Table 15 shows the percentage of jobs finishing earlier with reallocation than without on heterogeneous platforms. There are a few cases where more jobs are late than early, but on the average all heuristics give positive results, with around 10% finishing sooner when reallocation with cancellation. MCT is the heuristic that produces the less jobs early on average. The other heuristics give results close to one another. Table 16 shows the relative average response time of the heuristics on homogeneous platforms. On FCFS platforms, in the best case, the average response time of the jobs can be divided by a factor of 4 (MinMin-C in April). The MinMin heuristic gives always a gain of at least 17% and is the best in all but one experiment. There are only two cases where reallocation increased the average response time: in February with MCT and MaxMin. MCT being slower is in concordance with its results from the percentage of jobs finishing early. 59% of the jobs were late, so it seems normal that the relative average response time is higher. To have a gain the jobs early should have a huge gain to compensate, which was not the case. However, MaxMin had more jobs early than late, so it means that the jobs that were delayed were delayed for a long time.

On CBF homogeneous platforms, there is only one case where the reallocation worsens the average response time, but only by 2%. In the other cases, reallocation usually brings an improvement of more than 10%. All heuristics give close results with CBF with a small advantage for MaxGain.

Table 17 shows the relative average response time of the heuristics on heterogeneous platforms. In all experiments, there are only two cases with an increase of the average response time. When using FCFS, MinMin gives the best results and MaxMin the worst. On CBF heterogeneous platforms, all heuristics give similar results on average, with a difference between the best and the worse of less than 2%. There is no experiment with CBF were reallocation gave worse results than the experiment without reallocation. The gain is always at least 4%.

Finally, we can conclude that MCT or MinMin should be the heuristics to implement in a middleware able to perform reallocation with cancellation. Indeed, MCT is not the best one, but it gives satisfactory results for a better time complexity. The only setup where it should not be used (given the results of the experiments) is on an homogeneous platform with FCFS batch managers. In the most realistic platform (heterogeneous and CBF) it gives good results (all heuristics do). MinMin seems to be the best heuristic, but only by a small improvement over the other heuristics.

Comparison

In this section, we give some points of comparison between the two versions of the reallocation algorithm: without and with cancellation of the jobs in the batch waiting queues (see Algorithms 1 and 2).

Concerning the percentage of jobs whose completion time changed on homogeneous platforms, there are more jobs concerned with cancellation (see Tables 2 and10). With both batch algorithms there are almost always more jobs concerned with reallocation when there is cancellation. In some cases, January for example, there are 8% more jobs concerned when canceling. In other cases, April for example, there are less than 1% more jobs concerned. In February with CBF, there are more jobs concerned by reallocation without cancellation. On heterogeneous platforms with CBF, the percentage of jobs whose completion time changed with reallocation is a little higher on average with cancellation than without (see Tables 3 and11). This behavior is not always true, for example in January. With FCFS there are less jobs on average whose completion time changed with cancellation.

both homogeneous and heterogeneous platforms, the number of reallocations is higher when cancellations are involved (see Tables 4,[START_REF] Caniou | Simbatch: An API for and predicting the performance of parallel resources managed by batch In Workshop on Secure, Trusted, Manageable and Controllable Grid Services (SGS)[END_REF][START_REF] Gentzsch | Sun Grid Engine: Towards Creating a Compute Power Grid. Cluster Computing and the Grid[END_REF][START_REF] Guim | A Job Self-scheduling Policy for HPC Infrastructures[END_REF]. With cancellations, all waiting queues are reduced to the currently running jobs only and when resubmitting, most jobs can migrate. Without cancellation, the waiting queues stay full so chances for a job to be reallocated are smaller. Reallocating without canceling induces less migrations.

The percentage of jobs early on an homogeneous platform using FCFS is higher with cancellations (see Tables 6 and14). When there are more jobs late than early without cancellation, adding the cancellation correct this bad behavior and the results obtained are better. However, MCT in February gives really worse results with cancellation so cancellation can degrade performances. With CBF, the results are mostly a little better with cancellation. When there are more jobs finishing late than early, cancellation reverses the results. For example, for the six months experiments where all heuristics gave negative results we can see an improvement of nearly 10%. On the average, the cancellation always improves the results by a few percents.

On heterogeneous platforms, results (given in Tables 7 and15) are different than on homogeneous platforms. First, with FCFS, the results are often in favor of the reallocation without cancellation. There is only a big improvement for reallocation with canceling in June. For the 6-month experiment, results are a little better with cancellation, but only by a few percents. On the average, results are mixed. Sometimes the cancellation improves the number of jobs early, other times, it degrades it. With CBF, the cancellation improves the results on average. If we consider each experiment separately, we can see a improvement in the number of cases where reallocation brings a gain on the number of jobs completed earlier.

On the job response time on homogeneous platforms (see Tables 8 and 16), cancellation brings a large improvement over the algorithm without cancellation. With FCFS without cancellation, the maximum average gain is for MinMin with a gain of 10%. The maximum gain with cancellation is still MinMin but it brings an improvement of nearly 40%. The worst heuristic on the average with cancellation is MaxMin, but it is still better than the best heuristic without cancellation. There are only a few cases where the reallocation without cancellation is better, all of them in January or February. In the CBF setup, there is still the same comparison (worst with cancellation better than best without cancellation), but with less difference. On homogeneous platforms, it is clearly beneficial to cancel and resubmit the jobs.

Concerning heterogeneous platforms (see Tables 9 and17), the average job response time is also improved with cancellation. With FCFS, there is just one case where the cancellation worsened the result (in May with MaxMin). In all the other cases it is better with cancellation. With CBF, there are several cases where cancellation worsens the average response time of the jobs by a few percents. They all occur in February, March or April. On average, cancellation improves the results between 4 and 10%.

We can conclude that in the different cases studied here, cancellation usually brings improvement over the first version of the reallocation algorithm. The drawback of canceling jobs and resubmitting them is that there are more reallocations, thus batch systems are issuing more requests (submissions as well as cancellations). Another drawback of the canceling version of the algorithm is that it can produce starvation. It is possible for a job to be canceled each time and resubmitted after new jobs. Starvation never INRIA occurred in the simulations because there are phases of low load so waiting queues can be entirely executed.

The reallocation can be used to improve the average response time of the jobs with a small number of reallocations. Consequently, it should be considered in Grids to improve performance.

Related work

In [START_REF] Sabin | Scheduling of Parallel Jobs in a Heterogeneous Multisite Environment[END_REF] Sonmez et al. concentrate their study on the scheduling of parallel jobs onto several heterogeneous multi-site environment, where each site has an homogeneous cluster of processors. They use a meta-scheduler to select a cluster where to submit a job choosing the less loaded one. In order to take advantage of the different sites, the heuristic is modified to use multiple on all or a subset of the sites to minimize the response time. a task starts, it is canceled on the other site. Then, they compare different resources management algorithms and find that the conservative back-filling strategy is superior to the aggressive back-filling. In our work, we use the reallocation to try to minimize the response time while they rely on multiple submissions. Another difference is that our meta-scheduler chooses the site with the minimum expected completion time while theirs the site with the less instantaneous load. Netto and Buyya [START_REF] Marco | Rescheduling Co-Allocation Requests based on Flexible Advance Reservations and Processor Remapping[END_REF] study the rescheduling of co-allocated tasks on several sites. They use flexible advance reservations to obtain the proper synchronization between sites. The flexibility of the reservations provides the ability to change the processors mapping of the reservations (to regroup a reservation on a single site) and the start time (if all needed resources are available earlier than expected). In our work, there is no advance reservation and tasks have to be on a single site. Once a task has been submitted, the only possible action being the task cancellation in order to resubmit it on another site.

In [START_REF] Guim | A Job Self-scheduling Policy for HPC Infrastructures[END_REF], Guim and Corbalán present a detailed study of different metascheduling policies. The different policies include the Less-JobWaitTime, the Less-JobsInQueue, the Less-WotkLeft and Less-SubmittedJobs. Each task uses its own scheduler to be mapped on a parallel resource. Once submitted, the task is managed by the local scheduler and is never reallocated. The local policies are Shortest Job First and FCFS. In our work, we use the same two level architecture: a global scheduler and a local one, but our global scheduler is centralized and it adapts to the current platform load and can reschedule and decide to migrate tasks. Furthermore, local policies in our work are FCFS and CBF.

In [START_REF] Yue | Global Backfilling Scheduling in Multiclusters[END_REF], each cluster sends a snapshot of its state to a central scheduler. This data exchange is done at fixed intervals. Then the central scheduler chooses jobs in round robin or fixed order and tries to back-fill jobs in queues of other clusters. In this approach, computation done by the central scheduler is enormous since it needs the Gantt chart of all sites and it make all the computations itself. All the clusters are homogeneous in power and size. In our work, the central scheduler just asks the local scheduler when a task would complete, but it does not perform complex computations. Our algorithm without canceling is close to theirs in the sense that we verify if a job can be moved to another cluster to finish earlier, but we use different heuristics to select the jobs. The study we presented in our paper also takes into account the heterogeneity between the sites.

Sonmez et al. [START_REF] Sonmez | Trace-Based Evaluation of Job Runtime and Queue Wait Time Predictions in Grids[END_REF] present a method to diminish the errors made during a jobs burst in a multi-cluster environment. The method used consists in submitting the same job to several clusters (from 2 to all clusters) and when a job starts, all the other copies are canceled. To select the clusters, they use different heuristics such as MCT, Load Balancing, and Fastest Processor First. This method provides good results but adds an important load to the local resources management systems. Their approach is close to ours because it is also a middleware on top of an existing architecture. They use the multiple submissions to diminish the job response time while we use the reallocation mechanism. Our technique will keep the local resources management system less loaded because each job is only in one queue, but it will need more communications. With the multiple submissions, the first job that starts will send cancellation messages to the other, so this technique is not well suited for heterogeneous platforms where a job starting later can finish earlier.

Conclusion and perspectives

We presented two tasks reallocation algorithms and the study of their behavior in the context of a multi-cluster grid environment. These reallocation algorithms are designed to be used in the meta-scheduling component of a grid framework for example. They perform scheduling and rescheduling with possible reallocations (migration of tasks from one site to another one) with information gathered from local resources managements, which use FCFS or CBF local scheduling policies.

The MCT online heuristic is used to map tasks as soon as they are submitted to the framework, and a reallocation event is triggered once every hour to attempt to improve the schedule. Each reallocation algorithm implements a rescheduling heuristic among MCT, MinMin, MaxMin, MaxGain, MaxRelGain, and Sufferage, and we analyzed and compared results of experimental simulations performed on the basis of traces of real distributed systems (taken from Grid'5000 and from the Parallel Workload Archive) on different metrics, among which the percentage of tasks finishing sooner that if not re-scheduled, and the gain obtained on the average response time.

INRIA

The key difference between our reallocation algorithms is that the first one considers each task sequentially, both in rescheduling and migrating which implies also possible cancellation; the second one cancels all jobs on every sites, and runs the rescheduling heuristic.

First, the study shows that on average reallocation is beneficial on the considered metrics. Thus, such a mechanism should be embedded in a Grid framework. Second, reallocation achieves even better results when all tasks are canceled and submitted again as a whole bag of tasks. Third, from the simulation experiments involved in this study, one can expect, on average and depending on the platform (level of heterogeneity, local systems load, local resource management policy, etc.), around 5% of tasks finishing sooner with a 10% average gain on the response time compared to a system which does not implement such a mechanism.

However, the first reallocation mechanism is less complex to implement and maintain, and ensures gain, in the sens that we can be sure that everything will go as planned even in a non-dedicated environment: a task can be submitted to another site, the server can ensure that the ECT is as expected by the meta-scheduler with some contract checking mechanisms, and then be canceled from the originating site's batch system. In a non-dedicated environment, the second algorithm would issue the fact that other-and-direct submissions to the local resource manager can take place, and all canceled tasks would be delayed. Nonetheless, we plan as future work for SPADES2 to maintain a set of reserved resources of a site which are managed by our own batch scheduler. In this context resources are dedicated to our Grid framework and thus, this second mechanism can be fully exploited.

Figure 1 :

 1 Figure 1: Example of reallocation between two clusters.

Table 1 :

 1 Number of jobs per month and in total for each site trace.

	INRIA

heterogeneous). Lyon has 270 cores and is 20% faster than Bordeaux (in the heterogeneous case). Finally, Toulouse has 434 cores and is 40% faster than Bordeaux (still in the heterogeneous case).

Table 2 :

 2 Percentage of jobs that have their completion time changed when reallocation is performed on homogeneous platforms.

	Batch	Heuristic	jan	feb	mar	apr	may	jun	pwa-g5k AVG
		Mct	3.75 13.49 21.95 36.58 23.81 24.87	17.07	20.22
		MinMin	3.76 12.87 21.55 35.80 24.09 28.08	16.78	20.42
	FCFS	MaxMin MaxGain	3.89 13.13 21.75 36.17 24.21 26.91 3.59 13.32 16.99 35.55 24.13 27.75	17.19 16.97	20.46 19.76
		MaxRelGain 3.30 13.24 17.66 36.36 24.19 26.90	16.82	19.78
		Sufferage	3.69 13.16 21.92 36.10 22.80 26.71	17.02	20.20
		Mct	3.55 11.15 17.65 22.90 16.75 18.23	11.16	14.48
		MinMin	3.54 11.31 17.67 21.37 16.42 17.84	11.22	14.20
	CBF	MaxMin MaxGain	3.75 11.51 17.72 22.54 16.00 19.38 3.40 11.21 14.26 20.64 16.30 17.71	11.15 11.25	14.58 13.54
		MaxRelGain 3.10 11.29 14.35 22.36 16.53 17.16	11.11	13.70
		Sufferage	3.55 11.36 17.70 23.19 16.83 18.25	11.10	14.57
	Batch	Heuristic	jan	feb	mar	apr	may	jun	pwa-g5k AVG
		Mct	10.46 11.54 19.68 16.98 16.16 22.54	29.23	18.08
		MinMin	10.24 11.37 19.72 18.22 15.69 21.99	29.67	18.13
	FCFS	MaxMin MaxGain	10.08 11.38 19.64 16.92 15.42 24.08 10.41 11.42 19.80 18.25 16.64 24.20	27.96 29.98	17.93 18.67
		MaxRelGain 10.42 11.41 19.76 18.52 16.62 22.03	30.40	18.45
		Sufferage	10.12 11.61 19.66 18.38 15.83 23.89	29.28	18.40
		Mct	8.55	3.68	20.40 13.52 17.27 19.98	28.52	15.99
		MinMin	8.36	3.55	20.46 12.79 17.12 20.01	29.34	15.95
	CBF	MaxMin MaxGain	8.10 8.46	3.38 3.41	20.61 13.91 17.05 21.93 20.70 13.77 18.50 22.59	28.08 29.04	16.15 16.64
		MaxRelGain	8.46	3.55	20.69 14.03 18.30 22.04	29.08	16.59
		Sufferage	8.11	3.59	20.58 12.84 17.51 19.84	28.64	15.87

Table 3 :

 3 Percentage of jobs that have their completion time changed when reallocation is performed on heterogeneous platforms.

Table 4 :

 4 Number of reallocations on homogeneous platforms.

	INRIA

Table 5 :

 5 Number of reallocations on heterogeneous platforms.

Table 6 :

 6 Percentage of jobs finishing earlier when reallocation is performed on homogeneous platforms.

	Batch	Heuristic	jan	feb	mar	apr	may	jun	pwa-g5k AVG
		Mct	83.80 51.23	62.60	46.67 46.57	60.03	58.13	58.43
		MinMin	82.52 61.69	64.16	50.47	51.60	49.50	60.30	60.03
	FCFS	MaxMin MaxGain	84.03 60.79 82.48 71.81 44.25 45.38 42.24 47.45 55.51 46.80 45.94 53.50	57.70 58.55	57.75 56.02
		MaxRelGain 81.80 73.12	57.52	46.23 46.11	54.09	58.98	59.69
		Sufferage	82.18 62.30	54.23	42.98 48.29	51.37	59.85	57.31
		Mct	76.10 72.74	68.04	52.26	52.89	59.44	48.83	61.47
		MinMin	75.10 55.32	68.18	55.19	57.50	68.19	47.58	61.01
	CBF	MaxMin MaxGain	76.79 72.52 74.43 55.69	63.75 62.49	56.48 50.21	58.88 57.88	54.13 58.86	49.76 47.36	61.76 58.13
		MaxRelGain 72.67 56.34	60.35	49.34	58.63	60.60	48.80	58.10
		Sufferage	74.90 71.69	68.20	43.12	61.69	61.69	48.00	61.33

Table 7 :

 7 Percentage of jobs finishing earlier when reallocation is performed on heterogeneous platforms.

	INRIA

Table 8 :

 8 Relative average response time on homogeneous platforms.

Table 9 :

 9 Relative average response time on heterogeneous platforms.

	Batch	Heuristic	jan	feb	mar	apr	may	jun	pwa-g5k AVG
		Mct	0.65 1.08 0.74 0.98	0.97 0.94	0.92	0.90
		MinMin	0.98 1.17 0.77 0.93	0.86 0.93	0.92	0.94
	FCFS	MaxMin MaxGain	0.99 1.11 0.73 1.20 1.00 0.94 0.93 1.10 0.73 1.30 0.93 0.93	0.95 0.94	0.99 0.98
		MaxRelGain 0.93 1.15 0.75 0.97	0.91 0.89	0.92	0.93
		Sufferage	0.98 1.19 0.74 1.11 0.94 0.97	0.96	0.98
		Mct	0.66 0.94 0.71 0.85 1.11 0.94	0.96	0.88
		MinMin	1.00 0.94 0.71 0.83 1.06 0.96	0.95	0.92
	CBF	MaxMin MaxGain	1.00 0.88 0.72 0.91 1.05 0.96 1.00 0.88 0.72 0.83 1.03 0.97	0.96 0.96	0.93 0.91
		MaxRelGain 1.00 0.95 0.72 0.90 1.06 0.95	0.96	0.93
		Sufferage	1.00 0.95 0.72 0.85 1.05 0.91	0.95	0.92

Table 10 :

 10 Percentage of jobs that have their completion time changed when reallocation is performed on homogeneous platforms.

	Batch	Heuristic	jan	feb	mar	apr	may	jun	pwa-g5k AVG
		Mct-C	7.79 4.28 23.91 17.72 22.51 24.47	31.04	18.82
		MinMin-C	7.89 4.65	8.44	19.47 24.16 24.59	32.16	17.34
	FCFS	MaxMin-C MaxGain-C	7.82 4.12 19.13 18.19 24.95 26.85 8.02 5.79 7.90 17.78 24.86 25.58	31.54 31.19	18.94 17.30
		MaxRelGain-C 8.04 4.95	7.83	17.99 22.66 24.89	32.25	16.94
		Sufferage-C	7.83 4.15 18.76 19.73 23.14 26.79	32.06	18.92
		Mct-C	6.86 3.13 18.84 14.50 21.64 22.58	30.20	16.82
		MinMin-C	7.01 3.35 16.00 14.91 21.80 23.68	31.85	16.94
	CBF	MaxMin-C MaxGain-C	6.83 3.03 19.37 14.64 21.35 24.04 7.16 4.12 18.87 13.76 21.99 23.65	29.88 32.35	17.02 17.41
		MaxRelGain-C 7.18 3.54 18.88 14.03 22.08 23.63	30.67	17.14
		Sufferage-C	6.84 3.15 18.93 16.02 22.55 23.15	30.35	17.28

Table 11 :

 11 Percentage of jobs that have their completion time changed when reallocation is performed on heterogeneous platforms.

	Batch	Heuristic	jan	feb	mar	apr	may	jun	pwa-g5k
		Mct-C	363	838	1432 6930 1573 2460	8317
		MinMin-C	384	327	1411 3311 1563 2228	7791
	FCFS	MaxMin-C MaxGain-C	410 1206 1466 8199 1441 2562 585 365 1678 5495 1523 2653	11821 9038
		MaxRelGain-C 597	307	1476 6651 1463 2570	9881
		Sufferage-C	474	362	1501 7318 1414 2542	8088
		Mct-C	364	149	773	2486	594	1686	3299
		MinMin-C	389	186	758	2112	693	1353	2899
	CBF	MaxMin-C MaxGain-C	424 581	182 180	714 835	1596	619 705	1091 1298	3168 3851
		MaxRelGain-C 578	180	807	2272	834	1361	3738
		Sufferage-C	413	172	568	2231	706	1174	3454

Table 12 :

 12 Number of reallocations on homogeneous platforms.

	Batch	Heuristic	jan feb mar	apr	may	jun	pwa-g5k
		Mct-C	255 34	282	934	628	731	3082
		MinMin-C	257 27	246 1379	724	1186	3362
	FCFS	MaxMin-C MaxGain-C	258 31 326 41	431 1468 276 1517	716 702	899 1025	3416 4282
		MaxRelGain-C 326 50	278 2022	856	1437	4620
		Sufferage-C	260 44	369 1645	596	656	3056
		Mct-C	248	7	141	512	262	491	1814
		MinMin-C	250 12	186	501	230	455	1805
	CBF	MaxMin-C MaxGain-C	246 22 329 30	140 175	536 690	258 329	520 570	1758 2170
		MaxRelGain-C 327 30	185	677	335	570	2447
		Sufferage-C	250 14	180	446	238	505	1819

Table 13 :

 13 Number of reallocations on heterogeneous platforms.

Table 14 :

 14 Percentage of jobs finishing earlier when reallocation is performed on homogeneous platforms.

	INRIA

Table 15 :

 15 Percentage of jobs finishing earlier when reallocation is performed on heterogeneous platforms.

	Batch	Heuristic	jan	feb	mar	apr	may	jun	pwa-g5k AVG
		Mct-C	0.84 1.37 0.60 0.48 0.73 0.73	0.59	0.76
		MinMin-C	0.83 0.71 0.57 0.26 0.69 0.68	0.52	0.61
	FCFS	MaxMin-C MaxGain-C	0.86 1.57 0.62 0.50 0.75 0.75 0.86 0.79 0.59 0.35 0.66 0.71	0.70 0.55	0.82 0.64
		MaxRelGain-C 0.87 0.75 0.58 0.37 0.65 0.68	0.54	0.63
		Sufferage-C	0.89 0.84 0.62 0.49 0.70 0.77	0.57	0.70
		Mct-C	0.88 0.88 0.85 0.91 0.77 0.82	0.90	0.86
		MinMin-C	0.88 1.02 0.84 0.78 0.81 0.75	0.85	0.85
	CBF	MaxMin-C MaxGain-C	0.91 0.92 0.95 0.70 0.79 0.69 0.90 0.89 0.89 0.66 0.78 0.73	0.86 0.86	0.83 0.82
		MaxRelGain-C 0.90 0.89 0.89 0.74 0.85 0.73	0.86	0.84
		Sufferage-C	0.90 0.90 0.92 0.81 0.84 0.73	0.88	0.86

Table 16 :

 16 Relative average response time on homogeneous platforms.

Table 17 :

 17 Relative average response time on heterogeneous platforms.

	INRIA

RR n 7226

http://www.cs.huji.ac.il/labs/parallel/workload/ RR n 7226

ANR Project 08-ANR-SEGI-025 RR n 7226