Edge Partitioning in Parallel Structured Duplicate Detection
DOI:
https://doi.org/10.1609/socs.v1i1.18183Keywords:
parallel search, heuristic search, planningAbstract
We show how edge partitioning, a technique originally developed for external-memory search, can be used to reduce the number of slow synchronization operations needed in parallel graph search. We show that edge partitioning improves on a previous technique called parallel structured duplicate detection by allowing a higher degree of concurrency, even for search problems with little or no inherent locality. For domain-independent graph search, we also show that edge partitioning significantly improves search speed by improving the efficiency of precondition checking. We demonstrate the effectiveness of this approach to parallel graph search for domain-independent STRIPS planning.
Downloads
Published
2010-08-25
Issue
Section
Posters