Keywords: metric, scheduling, grid, heterogeneous environment, parallel jobs, performance evaluation, metascheduling.

The metrics used in evaluating the efficiency of schedulers have a strong influence on the results. In the literature, the metrics most commonly used to validate scheduling algorithms are waiting time, response time and slowdown. These metrics have been designed for homogeneous systems, and their direct application to distributed and heterogeneous resources present several drawbacks.

The target of the final user is to reduce response times. However, in practice, the response time is not a good indicator for a general study, since it presents significative variations introduced by the type of tasks which are not not always directly related to the scheduler. Then, to compare the scheduling of several user profiles with different applications, common on general propose infrastructures like a grid, this metric would not be appropriate.

The other two metrics previously referred, slowdown and waiting time, do not really reflect the effectiveness of the scheduling algorithm on heterogeneous environments; since the effect of the waiting time on the queues is not the only factor influenced by the scheduler. In addition, variations of the run time on the tasks may have a greater effect on the performance outcome.

In this paper we have introduced new metrics specially adapted to heterogeneous systems. They can be considered as generalisations of the previous ones, that do not present these drawbacks. They are named Greedy waiting time and Greedy slowdown. Both metrics are based on the concept of Greedy execution time, which represents the execution time in the best resource to run the task assuming that it is alone on the grid. Based on that, the definitions of these metrics are:

Greedy waiting time:

The difference in time between the execution on the best resource and the actual response time.

Greedy slowdown:

The ratio between the delay in the execution of a job and the execution time on the best resource of the empty grid.

The proposed metrics allows the comparison of scheduling decisions versus the most optimum situation for an heterogeneous environment. In this paper studies to validate the quality of these metrics over classical approaches are presented; and a consistence on this metric due to the error in the estimation of the best execution time estimation are shown.

purchase the full-text of this paper (price £20)

go to the previous paper
go to the next paper
return to the table of contents
return to the book description
purchase this book (price £72 +P&P)