Task Scheduling Technlques for Distrlbuted/Parallel Processing Systems

Abstract

This dissertation discusses the principles, techniques and approaches adopted in the design of task scheduling algorithms for Distributed Parallel Processing Computer Systems (DPCSs) connected with network of front-end systems (FSs), The primary goal in the design of scheduling algorithms is to minimise the total turnaround time of the jobs to be scheduled by maximizing the utilisation of the resources of the DPCS with minimum data communication overhead, The users present their jobs to be scheduled at the FS, The FS receives a job and generates a finite set of independent tasks based on mutually independent sections having inherent parallelism, Each task could be scheduled to different available processors of DPCS for concurrent execution, The tasks are of three groups viz,, compute intensive tasks, input. output intensive tasks and the combination of compute and input-output intensive tasks. They may have the execution time almost the same. Some of the tasks may have the execution time larger due to precedence constraints than that of other tasks and they are provided with logical breakpoints which can be utilised to further break the tasks into subtasks during scheduling, The technique of using breakpoint of the tasks is more appropriate when the number of available processors is more than the number of tasks to be scheduled. The tasks of a job thus generated are sent to the front-end processor (FEP or the host processor) of the DPCS in the form of data flow graph (DFG), The DFG is used to model the tasks and represent the precedence (or data dependencies) among the tasks, In order to preserve the constraints among the tasks during scheduling and realise efficient utilisation of the resources of DPCS, the DFG is structured in the form of levels, The FBP of DPCS has a resident Task Manager (TM). The key function of the TM is to schedule the tasks to the appropriate processors of DPCS either statically or dynamically based on the required resources. To realise efficient scheduling and utilisation of the processors of DPCS, the TM uses a set of buffers known as Task Forwarding Buffer (TFB), Task Output Buffer (TOB) and Task Status Buffer (TSB) maintained by the FEP of DPCS. The tasks of a job from the FS are received at the TFB. The TM picks up a set of tasks pertaining to a level for scheduling into a temporary buffer C and obtains the status of the processors of DPCS. In order to realise both static and dynamic approaches of allocation, task to processor relation is considered in the scheduling algorithm. If the number of tasks in C is equal to or greater than the number of processors available, one task per processor is allocated, the remaining tasks of C are scheduled subsequently as and when the processors become available. This method of allocation is called static approach. If the number of tasks in C is less than the number of processors available, the TM makes use of the logical breakpoints of the tasks to generate subtasks equal to the number of available processors. Each subtask is scheduled to a processor. This method of scheduling is called the dynamic approach. In all the case the precedence constraints among the tasks are preserved by scheduling the successor task to the parent processor or near neighbouring processor, maintaining minimum data communication between them. Various examples of Computational Fluid Dynamics problems' were tested and the objective of reduced total turnaround time and maximum utilisation of the processors was achieved. The total turnaround time achieved for different jobs varies between 51% and 86% with static approach and 16% and 89% with dynamic approach. The utilisation of the processors varies between the 50% and 92.5%. Hence a speed-up of 5 to 8 folds is realised.