Parallel Search Algorithms I
Embedded Files
::: Home > Instruction > CMSC 280: Parallel Processing > Topic 07: Parallel Search Algorithms I
This topic introduces the principles of parallelizing tree and graph search algorithms common in discrete optimization, beginning with a brief recap of sequential DFS and BFS to set the context for parallel speedup. The primary focus is on parallelizing unstructured search, where the search space is dynamically explored, leading to challenges in load balancing, partitioning the search space, and managing the shared 'work pool' of unexplored nodes efficiently across processors.
Learning Outcomes
Learning Outcomes
The limitations of sequential search strategies such as DFS and BFS are identified, and their implications for parallel performance are analyzed.
The effects of heuristic pruning on computational workload and load imbalance are examined in the context of parallel discrete optimization.
The mechanisms of dynamic space partitioning and work stealing are understood and evaluated as strategies for achieving scalable parallel search.
Topic Outline
Topic Outline
Handout: Parallel Search Algorithms for Discrete Optimization I*
From Structure to Search
Sequential Search Strategies
DFS and BFS: Bottlenecks
Heuristics and Pruning
Parallel Unstructured Search
Dynamic Space Partitioning
Load Balancing: Work Stealing
Toward Cooperative Exploration
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
Foundations of Heuristic Search
Pearl, J. (1984). Heuristics: Intelligent search strategies for computer problem solving. Addison-Wesley.
Work Stealing and Parallel Unstructured Search
Blumofe, R. D., & Leiserson, C. E. (1994). Scheduling multithreaded computations by work stealing. Proceedings of the 35th Annual Symposium on Foundations of Computer Science, 356–368.
Parallel Combinatorial Optimization and Implementation
Quinn, M. J. (2004). Parallel programming in C with MPI and OpenMP. McGraw-Hill Science.
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 07: Parallel Search Algorithms I
Page updated
Report abuse