A robust dynamic load-balancing scheme for data parallel application on message passing architecture

The working condition of a multicomputer system based on message passing communication is changeable and unpredictable. Any good algorithm for the system must be adaptive to the dynamic change of working condition. In this paper, we propose a new algorithm called RAS(Reservation And Work stealing). RAS treats load balancing, fault-tolerance and processor selection problems by work stealing and reservation based distribution. According to our experiment on the IBM SP2 with a matrix multiplication program, RAS is proven superior to the weighted factoring under the shared running environment and comparable under the dedicated running environment.