An Adaptive Space-Sharing Scheduling Algorithm for PC-Based Clusters
In recent years, PC-based cluster has become a mainstream branch in high performance computing (HPC) systems. To improve performance of PC-based cluster, various scheduling algorithms have been proposed. However, they only focused on systems with all jobs
- PDF / 245,065 Bytes
- 10 Pages / 439.324 x 666.21 pts Page_size
- 72 Downloads / 231 Views
Ho Chi Minh City University of Technology [email protected] Ho Chi Minh City University of Technology [email protected] Ho Chi Minh City University of Technology [email protected]
Abstract In recent years, PC-based cluster has become a mainstream branch in high performance computing (HPC) systems. To improve performance of PC-based cluster, various scheduling algorithms have been proposed. However, they only focused on systems with all jobs are rigid or all jobs are moldable. This paper fills in the gap by building a scheduling algorithm for PC-based clusters running both rigid jobs and moldable jobs. As an extension of existing adaptive space-sharing solutions, the proposed scheduling algorithm helps to reduce the turnaround time. In addition, the algorithm satisfies some requirement about job-priority. Evaluation results show that even in extreme cases such as all jobs are rigid or all jobs are moldable, performance of the algorithm is competitive to the original algorithms.
1 Introduction PC-based clusters are getting more and more popular these days as they provide extremely high execution rates with great cost effectiveness. On par with the development of PC-based clusters, scheduling on PC-based clusters has been an interesting research topic in recent years. Most of the research to date on scheduling has focused on the scheduling of rigid jobs, i.e., jobs that require fixed number of processors. However, many parallel jobs are moldable [2, 4], i.e., they adapt to the number of processors that scheduler set at the beginning of the job executions. Due to this flexibility, schedulers can choose an effective number of processors for each job. If most of processors are free, jobs may be allocated a large number of processors, their execution time is reduced. On the other hand, if the load is heavy, the number of processors allocated for each job will be smaller, which reduces the wait time. These scenarios help to reduce the turnaround time. Older and recent studies in [1–3,8,12,14,16,17] have shown the effectiveness of scheduling for moldable jobs. Based on the scheduling mechanisms developed separately for rigid or moldable jobs, this paper proposes a scheduling solution for a class of PC-based clusters running both rigid and moldable jobs. This study
226
V.H. Doan et al.
is motivated from the fact that today PC-based clusters are commonly used as shared resources for difference purposes. The jobs run in these PC-based clusters are usually both rigid and moldable. The rest of this paper is organized as follows: Section 2 describes background knowledge on scheduling. Section 3 states the research problem addressed in this paper. Section 4 gives an overview of the previous approaches related to the problem. Sections 5 and 6 describe details of the proposed solution. Section 7 describes the evaluation of the new scheme. Section 8 concludes the paper.
2 Background Knowledge Scheduling algorithms are widely disparate both in their aims and methods. From user’s view point, a good scheduler should minimize t
Data Loading...
