In this report we describe a greedy algorithm to schedule parallel jobs that consist of independent, identical, compute-bound tasks on desktop grids that consist of volatile compute resources. We assume that the algorithm has full knowledge of future resource availability and we prove that it achieves the optimal schedule (i.e., the one with the minimum makespan). Although this algorithm cannot be implemented in practice, it is a good comparator to evaluate other scheduling heuristics and the makespan it achieves can be computed in a straightforward manner.

Pre-2018 CSE ID: CS2004-0796

Desktop resources are attractive for running compute-intensive distributed applications. Several systems that aggregate these resources in desktop grids have been developed. While these systems have been successfully used for a wide variety of high throughput applications there has been little insight into the detailed temporal structure of CPU availability of desktop grid resources. Yet, this structure is critical to characterize the utility of desktop grid platforms for both task parallel and even data parallel applications. We address the following questions: (i) What are the temporal characteristics of desktop CPU availability in an enterprise setting? (ii) How do these characteristics affect the utility of desktop grids? (iii) Based on these characteristics, can we construct a model of server "equivalents" for the desktop grids, which can be used to predict application performance? We present measurements of an enterprise desktop grid with over 220 hosts running the Entropia commercial desktop grid software. We utilize these measurements to characterize CPU availability and develop a performance model for desktop grid applications for various task granularities, showing that there is an optimal task size. We then introduce a new metric, cluster equivalence, which we use to quantify the utility of the desktop grid relative to that of a dedicated cluster.

Pre-2018 CSE ID: CS2003-0769