Ant colony inspired method for reducing load imbalance in multiprocessor systems

摘要

Parallel processing is crucial for accelerating computation in many high-performance applications and modern technologies including computational modeling, optimization and simulation, Web and DNS servers, peer-to-peer systems, grid computing and cloud computing. Due to the heterogeneity nature of various processing nodes and the differences of workloads of various tasks, some processors can be idle while others are overloaded. In this paper, we present a simple, yet efficient, solution inspired by the intelligence of ant colonies to adequately mitigate the load imbalance and communication overhead problems in multiprocessor environments. The proposed approach is based on defining and maintaining data structures to dynamically track the load of each processor. We implemented the proposed algorithm and evaluated its performance under different scenarios against the baseline round-robin algorithm. The results showed that the proposed algorithm has more effective properties than the round-robin algorithm.