How to "Exploit" a Heterogeneous Cluster of Workstations (Asymptotically) Optimally

Abstract

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.