Real-time divisible load scheduling for cluster computing

Cluster computing has emerged as a new paradigm for solv-ing large-scale problems. To enhance QoS and provide per-formance guarantees in cluster computing environments, vari-ous real-time scheduling algorithms and workload models have been investigated. Computational loads that can be arbitrarily divided into independent pieces represent many real-world ap-plications. Divisible load theory (DLT) provides insight into dis-tribution strategies for such computations. However, the prob-lem of providing performance guarantees to divisible load ap-plications has not yet been systematically studied. This paper investigates such algorithms for a cluster environment. Design parameters that affect the performance of these algorithms and scenarios when the choice of these parameters have significant effects are studied. A novel algorithmic approach integrating DLT and EDF (earliest deadline first) scheduling is proposed. For comparison, we also propose a heuristic algorithm. Inten-sive experimental results show that the application of DLT to real-time cluster-based scheduling leads to significantly better scheduling approaches.