PERFORMANCE ANALYSIS OF SCHEDULING POLICIES FOR DISTRIBUTED MEMORY MULTICOMPUTERS

Abstract

Scheduling algorithms can improve the performance of multiprocessor systems by judiciously redistributing the workload among its processors. Time- sharing schemes tend to perform better system utilization for highly parallel systems when solving non-uniform problems with medium to high system load, Space sharing schemes perform well under low system loads. Hierarchical Scheduling Policy (HSP) is integrated scheduling scheme that combines both the timesharing and space sharing schemes. It is beneficial to use HSP for large-scale systems. Hierarchical Scheduling Policy is based on the hierarchical task queue organization. In this organization, a set of task queues are organized as a tree with all the processors with their local queues attached to the bottom level of the tree. It achieves efficiency by adaptively distributing the system load based on the current load, HSP employs self-scheduling while transferring work, that is, jobs and tasks. This implies that there is no central scheduler making processor allocation decisions. Simulation is carried out for performance comparison of this approach with the existing time-sharing schemes. The contribution of this dissertation with regard to HSP is to modify the algorithm to make it more optimal. The software is developed in c++ language and runs in any Posix compatible UNIX systems and is tested under Linux OS.