A LAZY SCHEDULING SCHEME FOR HYPERCUBE COMPUTERS

Processor allocation and job scheduling are two complementary techniqu es for improving the performance of multiprocessors. It has been obser ved that all the hypercube allocation policies with the FCFS schedulin g provide only incremental performance improvement. A greater impact o n the performance can be obtained by efficient job scheduling. This pa per presents an effort in that direction by introducing a new scheduli ng algorithm called lazy scheduling for hypercubes, The motivation of this scheme is to eliminate the limitations of the FCFS scheduling. Th is is done by maintaining separate queues for different job sizes and delaying the allocation of a job if any other job(s) of the same dimen sion is(are) running in the system. Processor allocation is done using the buddy strategy. The scheduling and allocation complexity is O(n) for an n-cube. Simulation studies show that the performance is dramati cally enhanced by using the lazy scheduling scheme as compared to the FCFS scheduling. Comparison with a recently proposed scheme called sca n indicates that the lazy scheme performs better than the scan schedul ing under a wide range of workloads. (C) 1995 Academic Press, Inc