Volume 5, Number 4, 379-405, DOI: 10.1007/s10723-007-9063-y

Scheduling Task Parallel Applications for Rapid Turnaround on Enterprise Desktop Grids

Derrick Kondo, Andrew A. Chien and Henri Casanova

View Related Documents

Abstract

Desktop Grids are popular platforms for high throughput applications, but due to their inherent resource volatility it is difficult to exploit them for applications that require rapid turnaround. Efficient desktop Grid execution of short-lived applications is an attractive proposition and we claim that it is achievable via intelligent resource selection. We propose three general techniques for resource selection: resource prioritization, resource exclusion, and task duplication. We use these techniques to instantiate several scheduling heuristics. We evaluate these heuristics through trace-driven simulations of four representative desktop Grid configurations. We find that ranking desktop resources according to their clock rates, without taking into account their availability history, is surprisingly effective in practice. Our main result is that a heuristic that uses the appropriate combination of resource prioritization, resource exclusion, and task replication can achieve performance within a factor of 1.7 of optimal in practice.

Key words  Desktop Grids - Network of workstations - Resource management - Scheduling

Fulltext Preview

Image of the first page of the fulltext document