Load Balance of Efficient Splitting Strategy

Load balance is the key factor to the efficiency of distributed processing. There have been many research results about static load balance, especially in numeric computation. But for artificial intelligence problems such as parallel combinatorial search, the implementation efficiency of existing load balancing algorithms is not good because of the dynamic behavior of load. This paper discusses dynamic load balance and puts emphasis on analysing the influence of parallel combinatorial search on efficiency. The paper concludes that effectiveness of task splitting strategies is an important faetor influencing the time overhead of load balance. The simulation of distributed computing has been done on shared memory multiprocessor ENCORE Multimax 520. Better efficiency has been gotten when applying efficient splitting strategy to parallel depth-first search algorithm solving the N-queens problm, and parallel branch-and-bound algorithm solving the travelling salesman problem.