Load-sharing in heterogeneous systems via weighted factoring
Susan Flynn Hummel, Jeanette P. Schmidt, R. N. Uma, Joel M. Wein · 1996
We consider the problem of scheduling a parallel loop with independent iterations on a network of heterogeneous workstations, and demonstrate the effectiveness of a variant of factoring, a scheduling policy originating in the context of shared address-space homogeneous multiprocessors. In the new scheme, weighted factoring, processors are dynamically assigned decreasing size chunks of iterations in proportion to their processing speeds. Through experiments on a network of SUN Sparc workstations we show that weighted factoring significantly outperforms variants of a work-stealing load-balancing algorithm and on certain applications dramatically outperforms factoring as well. We then study weighted work assignment analytically, giving upper and lower bounds on its performance under the assumption that the processor iteration execution times can be modeled as weighted random variables. Department of Computer Science, Polytechnic University, Brooklyn, NY, 11201. Research supported by AR...