SCALABLE LOAD BALANCING STRATEGIES FOR PARALLEL A-ASTERISK ALGORITHMS

In this paper, we develop load balancing strategies for scalable high- performance parallel A algorithms suitable for distributed-memory mac hines. In parallel A search, inefficiencies such as processor starvat ion and search of nonessential spaces (search spaces not explored by t he sequential algorithm) grow with the number of processors P used, th us restricting its scalability. To alleviate this effect, we propose a novel parallel startup phase and an efficient dynamic load balancing strategy called the quality equalizing (QE) strategy. Our new parallel startup scheme executes optimally in THETA(log P) time and, in additi on, achieves good initial load balance. The QE strategy prossess certa in unique quantitative and qualitative load balancing properties that enable it to significantly reduce starvation and nonessential work. Co nsequently, we obtain a highly scalable parallel A algorithm with an almost-linear speedup. The startup and load balancing schemes were emp loyed in parallel A algorithms to solve the Traveling Salesman Proble m on an nCUBE2 hypercube multicomputer. The QE strategy yields average speedup improvements of about 20-185% and 15-120% at low and intermed iate work densities (the ratio of the problem size to P), respectively , over three well-known load balancing methods-the round-robin (RR), t he random communication (RC), and the neighborhood averaging (NA) stra tegies. The average speedup observed on 1024 processors is about 985, representing a very high efficiency of 0.96. Finally, we analyze and e mpirically evaluate the scalability of parallel A algorithms in terms of the isoefficiency metric. Our analysis gives (1) a THETA(P log P) lower bound on the isoefficiency function of any parallel A algorithm , and (2) a general expression for the upper bound on the isoefficienc y function of our parallel A algorithm using the QE strategy on any t opology-for the hypercube and 2-D mesh architectures the upper bounds on the isoefficiency function are found to be THETA(P log2 P) and THET A(P square-root P), respectively. Experimental results validate our an alysis, and also show that parallel A search has better scalability u sing the QE load balancing strategy than using the RR, RC, or NA strat egies. (C) 1994 Academic Press, Inc.