Heuristics for Scheduling Parameter Sweep Applications in Grid Environments

Henri Casanova, Arnaud Legrand, Dmitrii Zagorodnov and Fran Berman
October 14, 1999

The computational Grid provides a promising platform for the efficient execution of parameter sweep applications over very large parameter spaces. Scheduling such applications is challenging because target resources are heterogeneous, because their load and availability varies dynamically, and because tasks may share common data files. In this paper, we propose a scheduling algorithm for parameter sweep applications on the Grid. We consider standard heuristics for task/host assignment (Max-min, Min-min, Sufferage), and we propose an extension of Sufferage called XSufferage. Using simulation, we demonstrate 3 results: 1) that XSufferage can take advantage of file sharing to achieve better performance than the other heuristics under a wide variety of load conditions, 2) that it is possible to characterize the environments under which different heuristics perform best, and 3) that it is possible to characterize the performance of different heuristics under the (realistic) assumption of varying accuracy of performance estimations.

How to view this document

The authors of these documents have submitted their reports to this technical report series for the purpose of non-commercial dissemination of scientific work. The reports are copyrighted by the authors, and their existence in electronic format does not imply that the authors have relinquished any rights. You may copy a report for scholarly, non-commercial purposes, such as research or instruction, provided that you agree to respect the author's copyright. For information concerning the use of this document for other than research or instructional purposes, contact the authors. Other information concerning this technical report series can be obtained from the Computer Science and Engineering Department at the University of California at San Diego, techreports@cs.ucsd.edu.

[ Search ]

This server operates at UCSD Computer Science and Engineering.
Send email to webmaster@cs.ucsd.edu