We consider the practical problem of task assignment in a server farm, where each arriving job is immediately dispatched to a server in the farm. We are particularly interested in non-preemptive settings where jobs must be run to completion. We ask the question: which policy should be used for assigning jobs (tasks) to servers. Our analysis shows that the answer to this question is very much dependent on the workload, particularly the heavy-tailed properties of the workload. We show however that choosing the right task assignment policy can improve performance by orders of magnitude.
We next consider the additional benefit that cycle stealing offers in task assignment. The analysis of cycle stealing has remained open for many years because inherent in this problem is a Markov chain which is infinite in 2 dimensions, making it intractable. We have recently discovered a method for reducing a 2D-infinite Markov chain (intractable) to a 1D-infinite Markov chain (tractable) while retaining all the information we need. We will show how this dimensionality reduction method can be applied to evaluate the benefits of several cycle stealing algorithms.
This talk includes work spanning half a dozen years. See the following papers on my web page: [Sigmetrics 03], [ICDCS 03], [SPAA 03], [Journal of the ACM 2002], [HPDC 00], [Journal Parallel Distributed Computer 1999], [Sigmetrics 98], [Performance Tools 98], [Transactions on Computer Systems 1997].