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

Yang Zhang, Eric A. Hansen

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.

Subjects: 15.7 Search; 1. Applications

Submitted: May 17, 2006

This page is copyrighted by AAAI. All rights reserved. Your use of this site constitutes acceptance of all of AAAI's terms and conditions and privacy policy.