Loading...
Please wait, while we are loading the content...
New Anticipatory Load Balancing Strategies for Parallel A* Algorithms (1995)
| Content Provider | CiteSeerX |
|---|---|
| Author | Shantanu, Nihar Mahapatra Dutt, Shantanu |
| Description | In this paper, we develop load balancing strategies for scalable highperformance parallel A* algorithms suitable for distributed-memory machines. In parallel A* search, inefficiencies such as processor starvation and search of non-essential spaces (search spaces not explored by the sequential algorithm) grow with the number of processors P used, thus 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(logP ) time and, in addition, achieves good initial load balance. The QE strategy employs near-neighbor quantitative and qualitative load balancing schemes to achieve load balance. These schemes utilize anticipatory mechanisms to detect and correct load imbalance before its actual occurrence; such mechanisms are particularly useful at lower work densities (the ratio of the problem size to P )... |
| File Format | |
| Language | English |
| Publisher | American Mathematical Society |
| Publisher Date | 1995-01-01 |
| Publisher Institution | In Proceedings of the DIMACS Series on Discrete Mathematics and Theoretical Computer Science |
| Access Restriction | Open |
| Subject Keyword | Problem Size Load Balancing Strategy New Parallel Startup Scheme New Anticipatory Load Balancing Strategy Scalable Highperformance Actual Occurrence Parallel Algorithm Distributed-memory Machine Qualitative Load Non-essential Space Load Imbalance Work Density Good Initial Load Balance Novel Parallel Startup Phase Processor Starvation Efficient Dynamic Load Quality Equalizing Sequential Algorithm Anticipatory Mechanism Qe Strategy Load Balance Parallel Search |
| Content Type | Text |
| Resource Type | Article |
