Parallel Search Algorithms II
Embedded Files
::: Home > Instruction > CMSC 280: Parallel Processing > Topic 08: Parallel Search Algorithms II
Building on general search, this module focuses on parallelizing heuristic search techniques for discrete optimization, specifically the Branch-and-Bound (B&B) method. Students will analyze how to efficiently manage the global bound, dynamically distribute the search tree's subproblems, and implement techniques like termination detection and intelligent pruning to maximize parallel efficiency in optimization problems.
Learning Outcomes
Learning Outcomes
The operation of the parallel Branch-and-Bound algorithm is understood, and the influence of communication frequency and synchronization cost on scalability is analyzed.
The principles and challenges of global termination detection in distributed search environments are explained.
The structure and performance characteristics of parallel A* search, including distributed open lists and hybrid CPU–GPU implementations, are evaluated.
Topic Outline
Topic Outline
Handout: Parallel Search Algorithms for Discrete Optimization II*
When Cooperation Becomes Coordination
Parallel Discrete Optimization
Branch-and-Bound: Global Pruning
Termination and Imbalance
Parallel A* Search
Distributed Open Lists for A*
Heterogeneous A* (CPU-GPU)
From Search to Strategy
Note: Links marked with an asterisk (*) lead to materials accessible only to members of the University community. Please log in with your official University account to view them.
Readings
Readings
Parallel Branch-and-Bound
Lai, T. H., & Sprague, A. (1988). Performance of parallel branch-and-bound algorithms. IEEE Transactions on Computers, 37(8), 962–971.
General Parallel Search Algorithms and Models
Grama, A., Gupta, A., Karypis, G., & Kumar, V. (2003). Introduction to parallel computing. Addison-Wesley.
Heterogeneous/GPU A* Search
Jabbar, S., & Im, S. (2018). Accelerating A* search algorithm using graphics processing units. International Journal of Advanced Computer Science and Applications, 9(1), 1–8.
Access Note: Published research articles and books are linked to their respective sources. Some materials are freely accessible within the University network or when logged in with official University credentials. Others will be provided to enrolled students through the class learning management system (LMS).
::: Home > Instruction > CMSC 280: Parallel Processing > Topic 08: Parallel Search Algorithms II
Page updated
Report abuse