Statistical prediction of task execution times through analytic benchmarking for scheduling in a heterogeneous environment

In this paper, a method for estimating task execution times is presented in order to facilitate dynamic scheduling in a heterogeneous metacomputing en vironment. Execution time is treated as a random variable and is statistica lly estimated from past observations. This method predicts the execution ti me as a function of several parameters of the input data and does not requi re any direct information about the algorithms used by the tasks or the arc hitecture of the machines. Techniques based upon the concept of analytic be nchmaiking/code profiling [1] are used to characterize the performance diff erences between machines. allowing observations from dissimilar machines to be used when making a prediction. Experimental results are presented which use actual execution time data gathered from 16 heterogeneous machines.