A cost-effective scheduling with load balancing for multiprocessor systems

Large-scale shared-memory multiprocessor systems are the current trend in high-performance multiprocessor systems, which are often divided into many nodes. These nodes contain a small number of processors connected by an internal bus. In this kind of system, load imbalance often occurs and can degrade the performance. This paper presents a cost-effective load balancing algorithm, which performs load redistribution only when the possible savings outweigh the redistribution costs. Furthermore, once the algorithm has decided to redistribute all of the iterations, some savings from those processors with heavy workloads can be migrated to some other processors with light workloads. Experiments show that our algorithm can enhance performance if it is used properly.