Optimal sharing of bags of tasks in heterogeneous clusters

Publisher Website
Google Scholar
Abstract
We prove that "FIFO" worksharing protocols provide asymptotically optimal solutions to a problem related to sharing a bag of identically complex tasks in a heterogeneous network of workstations (HNOW) n. In the HNOW-Exploitation Problem, one seeks to accomplish as much work as possible on n during a prespecified fixed period of L time units. The worksharing protocols we study are crafted within an architectural model that characterizes n via parameters that measure workstations' computational and communicational powers. The protocols are self-scheduling, in that they determine completely both an amount of work to allocate to each of n's workstations and a schedule for all related interworkstation communications. A protocol observes a FIFO regimen if it has n's workstations finish their assigned work, and return their results, in the same order in which they are supplied with their workloads. The optimality of FIFO protocols resides in the fact that they accomplish at least as much work as any other protocol during all sufficiently long worksharing episodes. Simulation experiments indicate that the superiority of FIFO protocols is often observed during worksharing episodes of only a few minutes' duration.

This publication has 12 references indexed in Scilit: