IIMB Management Review

Journal of Indian Institute of Management Bangalore

Sequential Grid Computing: Models and Computational Experiments

Prof. Sam Ransbotham, Ishwar Murthy, Sabyasachi Mitra and Sridhar Narasimhan
2009
Working Paper No
292
Body

Through recent technical advances, multiple resources can be connected to provide a computing grid for processing computationally intensive applications. In this paper, we build on an approach termed sequential grid computing that takes advantage of idle processing power, by routing jobs that require lengthy processing through a sequence of processors. We present two models that solve the static and dynamic versions of the sequential grid scheduling problem for a single job. In both static and dynamic versions, the model maximizes a reward function tied to the probability of completion within service level agreement parameters. In the dynamic version, the static model is modified to accommodate real-time deviations from the plan. We then extend the static model to accommodate multiple jobs. Extensive computational experiments highlight situations where (a) the models provide improvements over scheduling the job on a single processor, and b) the factors that affect the quality of solutions obtained. Key words:

Key words
grid computing; stochastic shortest path; dynamic programming

Sequential Grid Computing: Models and Computational Experiments

Author(s) Name: Prof. Sam Ransbotham, Ishwar Murthy, Sabyasachi Mitra and Sridhar Narasimhan, 2009
Working Paper No : 292
Abstract:

Through recent technical advances, multiple resources can be connected to provide a computing grid for processing computationally intensive applications. In this paper, we build on an approach termed sequential grid computing that takes advantage of idle processing power, by routing jobs that require lengthy processing through a sequence of processors. We present two models that solve the static and dynamic versions of the sequential grid scheduling problem for a single job. In both static and dynamic versions, the model maximizes a reward function tied to the probability of completion within service level agreement parameters. In the dynamic version, the static model is modified to accommodate real-time deviations from the plan. We then extend the static model to accommodate multiple jobs. Extensive computational experiments highlight situations where (a) the models provide improvements over scheduling the job on a single processor, and b) the factors that affect the quality of solutions obtained. Key words:

Keywords: grid computing; stochastic shortest path; dynamic programming