برنامه ریزی کار ایستا و پویا همراه با سیاست آگاه ارتباط در محاسبات خوشه ای

Parallel jobs submitted to processors should be efficiently scheduled to achieve high performance. Early scheduling strategies for parallel jobs make use of either space-sharing approach or time-sharing approach. The scheduling strategy proposed in this work, makes use of both the policies for parallel jobs while scheduling under clusters. Static and dynamic scheduling algorithms were developed for communication intensive jobs. The algorithms are used to handle different types of jobs such as serial, parallel and mixed jobs. For performance evaluation, the workload from Grid5000 platform is considered. The main objective is to achieve performance and power improvement. The dynamic scheduling algorithm with communication aware policy gives better performance when compared to static scheduling algorithm that is tested under the given workload.

Parallel job scheduling is an important topic in the field of research. The main issue is how to share the available processors from the existing parallel computing environment to the tasks that are submitted by the users or processes. There are different parallel computing environments: (i) the parallel computers in which the systems come under are desktops and laptops with multi-core chips, (ii) the grids in which large scale heterogeneous distributed shared computing environment, (iii) the web servers, in which large scale latency sensitive online services are provided and (iv) the virtualization, in which the resource management is performed inside and among multiple virtual machines [1]. It is easily understood that the parallel computing environments are existing and rather continue to aid future technologies. Clusters offer considerable computational power, which can be used to solve problems with large computational requirements. Proper scheduling is fundamental to performance in distributed systems. The most important aspect of a distributed system is the scheduling algorithm. The scheduling algorithm is responsible for the allocation of processors to jobs and also determines the order in which jobs will be executed on processors. Scheduling of parallel jobs on parallel machines has a significant impact on the system utilization. A good task scheduling method is needed to reduce the total time taken for job execution. Scheduling algorithms can be classified into static and dynamic. The static algorithms are in need of some prior information before scheduling the jobs and dynamic algorithms can execute the jobs in runtime without the prior information cost. Parallel jobs consist of independent tasks which can be executed on any processor and in any order or independent group of tasks or tasks which need to frequently communicate with each other – they start essentially at the same time and execute for the same amount of time. In this work, the communication intensive jobs are considered for parallel jobs. A new scheduling algorithm is developed that utilizes both time-sharing and space-sharing policies as well as to meet the requirements of communication intensive jobs by developing the communication aware policy. It is the extension of the work [2], in which the static algorithms are explained and this work proposed the dynamic scheduling algorithm for scheduling different kinds as well as different mix of jobs in clusters. The plan of the paper is as follows: Section 2 presents the motivation for this work. Section 3 describes the system set up for experimental evaluation and the workload considered for job scheduling towards this work and explains about the communication aware policy. Section 4 describes the different types of scheduling algorithms developed and section 5 discusses the experimental output. Section 6 gives the detailed conclusion for this work. In this paper, processor is also denoted as node.

Static and dynamic algorithms for scheduling parallel jobs are designed in which the parallel jobs make use of communication aware policy. Static algorithms are used to schedule different types of jobs. These algorithms can be used if the scheduler comes across particular job types. Dynamic algorithm is used to handle any combination of job types. While scheduling, all the related parallel jobs are assigned to same node and hence context switching is avoided and there is no process thrashing. The experimental results prove that the algorithm works well for mixed jobs. But the algorithm is designed in such a way that it needs two queues for storing incoming serial and parallel jobs and they can be scheduled only when the queues are filled with 25 jobs each. The total wait time for scheduling increases, while scheduling all co-scheduled jobs. Algorithm for scheduling serial jobs had poor performance when compared to other scheduling algorithms. There is no wait time for dynamic jobs, for sample 300 jobs considered, but a little idle time prevails on the nodes. But for dynamic jobs, one queue is enough and it is used only when scheduler comes across parallel jobs. From average idle time of nodes and the average wait time of jobs, it is concluded that algorithm for scheduling of mixed jobs is good, when compared to other scheduling algorithms with no idle time of nodes and wait time of jobs. But this algorithm makes use of two queues. Hence the dynamic algorithm performs better with negligible idle time of nodes with only one queue for storing job details. Hence it is concluded that dynamic algorithm for scheduling jobs performs well when compared to other scheduling algorithms for the sample workloads and the objective of better performance and power is achieved.