Equipartitioning versus Marginal Analysis for Parallel Job Scheduling

摘要

Given n malleable and non-preemptable parallel jobs that arrive for execution at time 0, we examine and compare two job scheduling strategies that allocate m identical processors among the n competing jobs. In all cases, n ＜ m. The first strategy is based on the heuristic paradigm of equipartitioning, and the second is based on the notion of marginal analysis. Equipartitioning uses no a priori information when processor allocations are made to parallel jobs. Marginal analysis, on the other hand, assumes full a priori information in order to maximize processor utility. In this paper, we compare both strategies with respect to average time-to-completion (system performance) and overall time-to-completion (system efficiency). Using a simple job model characterized by sequential time-tocompletion and degree of parallelism, it is demonstrated via simulation that in most cases, the uninformed strategy of equipartitioning outperforms marginal analysis with respect to system performance and without a commensurate degradation in system efficiency.