Stochastic
Scheduling with Availability Constraints in Heterogeneous Clusters
Tao XieXiao Qin*
Department
of Computer ScienceDepartment
of Computer Science
San Diego State UniversityNew Mexico Institute of Mining and Technology
San
Diego, California 92182Socorro, New Mexico 87801
xie@cs.sdsu.edu xqin@cs.nmt.edu
High
availability plays an important role in heterogeneous clusters, where
processors operate at different speeds and are not continuously
available for processing. Existing scheduling algorithms designed for
heterogeneous clusters do not factor in availability. We address in this
paper the stochastic scheduling problem for heterogeneous clusters with
availability constraints. Each node in a heterogeneous cluster is
modeled by its speed and availability, and different classes of tasks
submitted to the cluster are characterized by their execution times and
availability requirements. To incorporate availability and heterogeneity
into stochastic scheduling, we introduce metrics to quantify
availability and heterogeneity in the context of multiclass tasks. A
stochastic scheduling algorithm SSAC (Stochastic Scheduling with
Availability Constraints) is then proposed to improve availability of
heterogeneous clusters while reducing average response time of tasks.
Experimental results show that our algorithm achieves a good trade-off
between availability and responsiveness.
Proceedings
of the 8th
IEEE International Conference on Cluster Computing (Cluster
2006), Sept. 2006.