Towards Decentralized Load Balancing in a Computational Grid Environment

摘要

Load balancing has been a key concern for locally distributed multiprocessor systems. The emergence of computational grid extends this problem, such as scalability, heterogeneity of computing resources and considerable communication delay. In this paper, we study the problem of scheduling a large number of CPU-intensive jobs on such systems. The time spent by a job in the system is considered as the main issue that needs to be minimized. The proposed dynamic algorithm of scheduling jobs consists of two policies: Instantaneous Distribution Policy (IDP) and Load Adjustment Policy (LAP). Our algorithm does not address directly the load balancing problem since it is completely unrealistic in such large environments, but we will show that even a non-perfectly load balanced system can behave reasonably well by taking into account the jobs' time demands. The proposed algorithm is evaluated by a series of simulations.