It is proved that "FIFO" worksharing protocols provide asymptotically
optimal solutions to two problems related to sharing bags of tasks in
a heterogeneous cluster of workstations (HC) C. In the
HC-Exploitation Problem, one seeks to accomplish as much work as
possible on C during a prespecified fixed period of L time units. In
the HC-Rental Problem, one seeks to complete W units of work by
"renting" C for as short a time as necessary. The worksharing
protocols we study are crafted within an architectural model that
characterizes C via parameters that measure C's workstations'
computational and communicational powers. The protocols are
self-scheduling, in the sense that they determine completely both an
amount of work to allocate to each of C's workstations and a schedule
for all related interworkstation communications. The schedules
provide either a value for W given L, or a value for L given W, hence
solve both of the motivating problems. A protocol observes a FIFO
regimen if it has C's workstations finish their assigned work, and
return their results, in the same order in which they are supplied
with their workloads. The proven 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, and that
they complete sufficiently large given bags of work at least as fast
as any other protocol. Simulation experiments illustrate that the
superiority of FIFO protocols is often observed during worksharing
episodes of duration less than one minute.
Last modified 1 October 2002