Efficient job scheduling methods for cluster systems

Abstract

A cluster is a collection of workstations or PCs that are interconnected via network technology, which emerges as new way of achieving high performance at a reduced cost. Inappropriate scheduling of tasks may degenerate the true potential of a cluster and offset the gain from parallelism. The thesis presents a new queue delay model used in job scheduling system for clusters and presents a new processor management scheme based on the k-ary n-cube networks because arbitrary networks employed in clusters can be approximated to a high dimensional topology such as k-ary n-cube. In a dynamic scheduling, FCFS scheduling may not efficiently utilize a cluster due to two drawbacks - one is to block smaller jobs, the other is to frequently fragment the system. Reduing parallelism of jobs with a queue model overcomes the weaknesses of FCFS. In other words, If the immediate allocation fails, the job scheduler should decide whether to wait or to assign a smaller subcube to the job. The decision is made depending on the wait or queue delay time. An accurate queue model is critical for enhancing the system performance. Previous studies of queue delay model have attempted to predict the queue delay analytically based on the number of busy processors, not busy subcubes. A main disadvantage of the processor-based prediction is that the number of busy processors does not accurately explain the queue delay. We call our new queue delay model as job-based queue delay model because we view the allocation moment when all the existing jobs, not the busy processors, in one of the possible subcubes complete their execution. Since allocation on a cluster is difficult due to its topological irregularity, k-ary n-cube system is chosen as a rough approximation of the irregular topology of a cluster due to its topological generality and flexibility. Even if the topology of a cluster is irregular and very complex, the proposed allocation method - Isomorphic Allocation allocation method may...