Title :
Load balancing technique for parallel search with statistical model
Author :
Lin, Wei-Ming ; Yang, Bo
Author_Institution :
Div. of Eng., Texas Univ., San Antonio, TX, USA
Abstract :
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
Keywords :
processor scheduling; resource allocation; shared memory systems; statistical analysis; constraint satisfaction problem; correlation coefficient; divide-and-conquer approach; load balancing technique; multi-processor shared memory system; parallel performance enhancement technique; parallel search; parallel system efficiency; statistical model; system performance prediction; Algorithm design and analysis; Artificial intelligence; Constraint theory; Graph theory; Image matching; Labeling; Layout; Load management; Petroleum; System performance;
Conference_Titel :
Computers and Communications, 1995., Conference Proceedings of the 1995 IEEE Fourteenth Annual International Phoenix Conference on
Conference_Location :
Scottsdale, AZ
Print_ISBN :
0-7803-2492-7
DOI :
10.1109/PCCC.1995.472511
