Performance evaluation and optimization of an adaptive scheduling approach for dependent grid jobs with unknown execution time

Most nowadays scheduling algorithms for grids are based on the assumption that the application (job) execution time is known before job run-time.This assumption significantly simplifies job-resource matchmaking, although it has proven to be inapplicable for most real-world applications.On the other hand, there exists a group of applications for which execution progress can be monitored at run-time.Often, when a correlation between job execution progress and total job execution time exists, progress information can serve as a good basis for the prediction of the remaining execution time.Another important issue in the domain of distributed computing is scheduling of jobs composed of tasks with input dependencies, whereby some tasks require inputs generated by other tasks.Since the overhead due to input dependencies is limited, this type of dependencies forms a potential for execution optimization by means of intelligent scheduling of dependent tasks on distributed resources.In this article a detailed performance evaluation and optimization is provided for an adaptive scheduling algorithm for grids that was proposed earlier.The algorithm operates on jobs with input inter-dependencies, whose sub-tasks are organized into a DAG (Directed Acyclic Graph) and for which no information of total execution time is available.The idea behind the approach is that parallel tasks (parent tasks), generating input for the same underlying set of tasks (dependent tasks), should finish more or less simultaneously.Since the dependent tasks can only be executed after all the required inputs are available, the longest parent task is assigned to the fastest available resource, while shorter tasks can be assigned to slower resources, as long as it does not prolong the execution time of the parent set as a whole.The latter creates a possibility for other tasks requiring fast processing to be executed on faster machines.At first, tasks are assigned randomly.Later, the algorithm reacts on dynamic changes in resource status and variations in task execution time predictions by possibly rescheduling parallel tasks.The algorithm's performance was evaluated using workload originating from an existing modeling and virtual experimentation tool for environmental systems (Tornado).Results have shown that significant system overhead is introduced, in terms of additional computational and network load due to the extended checkpointing and migration mechanisms.However, this overhead is compensated by more effective processing of parallel sub-tasks, which are now occupying only resources they strictly need in order not to delay the execution of the job as a whole.In this paper we measure the overhead introduced by the algorithm on network and computational resources and compare it to the overhead of a traditional static approach.It is clear that the effectiveness of the adaptive approach strongly depends on the degree of parallelism of subtasks and on their overall execution time heterogeneity.The boundaries for both parameters are studied.Furthermore, the performance of the algorithm can be improved by postponing migration in cases where the benefit of rescheduling is expected to be sufficiently low.Definition of the boundary for the migration postponement is also addressed.

Récupéré en direct depuis OpenAlex et désinversé. Les résumés ne sont pas conservés dans cette base de données : les index inversés représentent 8,6 Go des 9,3 Go de texte de la base, et le serveur dispose de 13 Go libres.