REQUIREMENT- AWARE STRATEGIES FOR SCHEDULING MULTIPLE DIVISIBLE LOADS IN CLUSTER ENVIRONMENTS

Abstract

Divisible load applications occur in many fields of science and engineering. Such applications can be easily parallelized in a master-worker fashion, but pose several scheduling challenges. This thesis investigates the problem of scheduling multiple divisible loads in cluster systems with a particular emphasis in capturing two important real-life constraints, various processing requirements of different loads, and different load types.

We first study the problem of scheduling multiple divisible loads with different processing requirements. Since the divisible loads to be performed may widely vary in terms of their required hardware and software, we capture the loads¿ various processing requirements in our load distribution strategies, a unique feature that is applicable for running proprietary applications only on certain eligible processing nodes. Thus in our formulation each task may only be processed by some certain nodes due to their different processing requirements.

We also study the scheduling of hybrid tasks comprising both divisible and indivisible loads. Indivisible loads are characterized by the property that they need to be processed on their entirety on a single processor while divisible loads can be distributed across several processing nodes by exploiting the underlying data parallelism. Since clusters are designed to handle any types of loads, handling hybrid tasks comprising both divisible and indivisible loads is common in practice.

We thoroughly investigate the above problems for both real-time and non-real-time tasks. We contribute several efficient scheduling algorithms that are aware of different processing requirements and load types of the tasks. Also, we perform extensive performance evaluations to demonstrate the effectiveness and competitiveness of our algorithms on various scenarios.