Execution Time Prediction of Imperative Paradigm Tasks for Grid Scheduling Optimization

摘要

An efficient functioning of a complicated and dynamic grid environment requires a resource manager to monitor and identify the idling resources and to schedule users' submitted jobs (or programs) accordingly. A common problem arising in grid computing is to select the most efficient resource to run a particular program. At present the execution time of any program submission depends mostly on guesswork by the user. The inaccuracy of guesswork leads to inefficient resource usage, incurring extra operational costs such as idling queues or machines. Thus, in this paper we propose a job execution time prediction module to aid the user. The proposed system will function as a standalone unit where its services can be offered to users as part of a grid portal. This system focuses on imperative paradigm tasks as they are commonly used in a grid environment. We propose a novel methodology and architecture to predict the execution time of jobs using aspects of static analysis, analytical benchmarking and compiler based approach. Essentially a program is analyzed in segments for execution time and these times are combined together to give the total execution time of the program. The experimental results show that the technique is successful in achieving a prediction accuracy of greater than 80%. Future work may involve handling other paradigms such as object-oriented programming and investigating the possibility of integrating the prediction module into a real grid environment.