Sharing partitionable workloads in heterogeneous NOWs: greedier is not better

Abstract

We craft protocols for solving two problems related to sharing a large partitionable bag-of-tasks workload in a heterogeneous network of workstations (NOW) N. In the NOW-Rental Problem, one must complete W units of work and wishes to rent N for as short a time as necessary. In the NOW-Exploitation Problem, one has access to N for L time units and wishes to accomplish as much work as possible. Our protocols are crafted within an architectural model that characterizes N via parameters that measure its workstations' computational and communicational efficiencies; hence, our solutions are robust across a broad range of actual NOWs. The protocols determine both an allocation of work for each of N's workstations and a schedule for transmitting that work; hence, they are self-scheduling. The schedules provide a value for either L or W, given the other, thereby solving both motivating problems. By studying two specific protocols, we prove that the intuitive strategy of supplying as much work as possible to faster workstations is not optimal; this nonoptimality is often discernible for values of L less than one minute.