E. Xia, I. Jurisica, J. Waterhouse, and V. Sloan (Canada)
Grid scheduling, scheduling heuristics, runtime estimation error, scheduler performance
It has been shown that runtime estimation errors have a large impact on scheduler performance. In previous research, scheduling algorithms were mainly used in a homogeneous environment. In this paper, we investigate several scheduling heuristics that are commonly used in the grid environment. We systematically study how runtime relative estimation errors affect the scheduler performance in different grid scenarios by conducting experiments using simulation. We choose Dynamic-selection, Min-min, Seg-min-min, Max-min, and Sufferage as our scheduling algorithms for the experiments. Our results show interesting trends: (1) increased estimation error results in degrading performance of all tested scheduling heuristics, making them even worse than the basic “Round-Robin” approach if errors are large; however, locally, performance is sometimes better and, in some special cases, estimation errors do not affect scheduler performance; (2) unlike in general, increased estimation errors diminish the performance difference among individual heuristics; (3) there is a performance threshold, no matter how large the estimation errors are; (4) increased accuracy of runtime estimation improves performance in general.
Important Links:
Go Back
