Load balancing technique for parallel search with statistical model

A parallel performance enhancement technique using statistical model to increase parallel system efficiency is discussed in this paper. This idea is applied to solving the constraint satisfaction problem (CSP) on a multi-processor shared memory system. The combination of reducing standard deviation of the execution time in each processor and increasing the correlation coefficient between every two processors´ execution times proves to be a very effective method in balancing load without resorting to dynamic approaches. Significant improvement in system efficiency over a traditional divide-and-conquer approach is shown in solving CSP in parallel. A near-optimal (100%) average load balance result is obtained. The underlying theory can also be easily applied to other problems and can be further extended to provide system performance prediction and evaluation