Abstract
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.
Introduction
Parallelizing graph search algorithms like A is a notoriously difficult challenge in computer science. The primary bottleneck is "duplicate detection"—the process of checking whether a newly generated state has been visited before. In a multi-threaded environment, this typically requires threads to lock a global "Closed List," leading to heavy synchronization overhead. When multiple threads spend more time waiting for locks than exploring the state space, performance scales poorly. This paper introduces Parallel Edge Partitioning (PEP)*, a method designed to minimize synchronization by shrinking the scope of duplicate checks to a single block of memory.
From PSDD to Parallel Edge Partitioning
To understand the innovation of PEP, one must first look at its predecessor, Structured Duplicate Detection (SDD) and its parallel variant (PSDD). SDD partitions the search space into "nblocks" based on an abstract version of the state graph. While PSDD improved concurrency, it remained susceptible to contention: if the abstract graph was too dense, threads would frequently compete for the same sets of nblocks, leading to performance degradation.
PEP shifts the focus from nodes to edges. Instead of expanding all successors of an nblock simultaneously, PEP processes them one abstract edge at a time. By focusing on a single outgoing edge in the abstract graph, the duplicate-detection scope is narrowed to exactly one nblock.
Key Advantages of PEP
- Enhanced Concurrency: PEP allows for a degree of concurrency equal to the number of nodes in the abstract graph, significantly exceeding the limits of previous methods.
- Deadlock-Free Design: In PEP, a thread only needs to secure a single resource (one nblock) to perform its work. This design inherently breaks the circular wait conditions required for deadlocks, simplifying the parallel architecture.
- Operator Abstraction: In domain-independent planning, checking the validity of an action (operator) is computationally expensive. PEP allows the system to pre-calculate which operators apply to which abstract edges. This allows the search to skip unnecessary precondition tests, providing a significant speed boost.
Experimental Evaluation
The researchers evaluated PEP using eight benchmark domains from the International Planning Competition (IPC) and hard instances of the 15-Puzzle formulated as STRIPS (Stanford Research Institute Problem Solver) planning problems.
Performance and Efficiency
The results demonstrated that PEP is highly effective for domain-independent search:
- Speed: PEP was 27% faster than PSDD when utilizing 7 threads. Interestingly, PEP achieved this despite performing ten times more "incremental" node expansions, proving that the reduction in synchronization and improved memory locality far outweigh the cost of additional expansions.
- Scalability: PEP functioned effectively even with very coarse abstractions, utilizing abstract graphs ten times smaller than those required by PSDD.
- Problem Solving: On the 15-Puzzle, PEP solved 95 out of 100 hard instances within minutes. In contrast, previous state-of-the-art domain-independent solvers required hours to solve only 93 instances.
- Memory Robustness: Unlike other parallel algorithms such as Hash-Distributed A (HDA) or Parallel Best-NBlock-First (PBNF), PEP successfully solved these complex instances without exhausting available memory.
Insights on Locality and Preconditions
A central insight of this research is that restricting the immediate scope of a thread actually increases the system's total throughput. By forcing a thread to follow only one type of edge at a time, PEP ensures that the CPU interacts with a very specific slice of memory. This high degree of locality aligns with modern CPU cache architectures, improving performance even in single-threaded scenarios.
Furthermore, the "precondition bottleneck"—the overhead of checking if an action is legal—is often overlooked in parallel search literature. PEP’s ability to ignore irrelevant operators for specific abstract edges addresses this bottleneck directly, offering a specialized advantage for domain-independent planning tasks.
Conclusion and Future Work
Parallel Edge Partitioning represents a significant step forward in making parallel graph search more efficient and scalable. While the method can be more memory-intensive than some alternatives due to the information required for edge partitioning, its speed and robustness make it a superior choice for complex planning problems.
Future research will focus on integrating PEP with external-memory graph search. By utilizing disk space alongside RAM, the authors aim to extend PEP’s capabilities to search spaces that exceed the limits of modern multi-core servers, potentially solving even more massive and complex planning challenges.
Summary updated