Parallel Breadth-First Heuristic Search on a Shared-Memory Architecture

Contents

We consider a breadth-first approach to memory-efficient graph search and discuss how to parallelize it on a shared-memory architecture that uses multithreading to achieve parallelism. The approach we develop for parallelizing breadth-first search uses layer synchronization, in which threads expand all nodes in one layer of the breadth-first search graph before considering any nodes in the next layer. We show that this allows simple and effective techniques for termination detection, dynamic load balancing, and concurrent access to shared data structures. The Fifteen Puzzle is used as an initial test domain.