A Lazy Scheduling Scheme for Hypercube Computers |
| |
Affiliation: | 1. Department of Computer Science, University of Pisa, Pisa, I-56127, Italy;2. School of Technology, Pontifical Catholic University of Rio Grande do Sul (PUCRS), Porto Alegre, 30332–0250, Brazil;3. Laboratory of Advanced Research on Cloud Computing (LARCC), Três de Maio Faculty (SETREM), Três de Maio, Brazil;4. Department of Information Engineering, University of Pisa, Pisa, I-56122, Italy;1. Faculty of Mechanical and Electronic Engineering, Shaanxi University of Science and Technology, Xi’an 710021, China;2. Xi’an Aerospace Precision Electromechanical Institute, Xi’an 710010, China |
| |
Abstract: | Processor allocation and job scheduling are two complementary techniques for improving the performance of multiprocessors. It has been observed that all the hypercube allocation policies with the FCFS scheduling provide only incremental performance improvement. A greater impact on the performance can be obtained by efficient job scheduling. This paper presents an effort in that direction by introducing a new scheduling algorithm called lazy scheduling for hypercubes, The motivation of this scheme is to eliminate the limitations of the FCFS scheduling. This 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 dimension 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 dramatically enhanced by using the lazy scheduling scheme as compared to the FCFS scheduling. Comparison with a recently proposed scheme called scan indicates that the lazy scheme performs better than the scan scheduling under a wide range of workloads. |
| |
Keywords: | |
本文献已被 ScienceDirect 等数据库收录! |
|