Abstract
Heuristic search algorithms like A are often limited by memory constraints when exploring large state spaces. This paper presents FA-DDD and its parallel version PFA*-DDD, which integrate Frontier Search with Delayed Duplicate Detection. By addressing the "leak-back" problem and implementing an interval-based workload distribution, these algorithms enable large-scale search on distributed clusters. Experimental results on Multiple Sequence Alignment (MSA) problems demonstrate super-linear speedups and the ability to solve problems requiring over 50 GB of memory.
Introduction
Heuristic best-first search algorithms, most notably A, are essential for finding optimal paths in complex state spaces. However, they face a significant "memory wall": to avoid cycles and redundant computations, A must maintain a "Closed" list of every visited state. In high-dimensional problems such as Multiple Sequence Alignment (MSA), this list can quickly exhaust available RAM, halting the search.
To mitigate this, researchers have developed Frontier Search (FS), which stores only the search frontier, and Delayed Duplicate Detection (DDD), which processes duplicates in batches to improve memory locality and enable disk-based storage. This paper introduces FA-DDD and PFA-DDD, the first algorithms to successfully combine these two techniques by resolving the "leak-back" problem—a condition where delayed detection causes the unintended re-expansion of previously processed nodes.
Methodology
FA*-DDD: Solving the Leak-Back Problem
The integration of FS and DDD is non-trivial because delaying duplicate detection can lead to infinite loops if a node is re-added to the frontier after its initial expansion. FA*-DDD solves this by maintaining two specialized edge lists: ClosedIn (edges leading into closed vertices) and ClosedOut (edges leading out of closed vertices). These lists provide sufficient context to filter newly generated vertices without requiring the full storage of the closed set.
PFA*-DDD: Parallel Distribution and Load Balancing
For distributed-memory clusters, PFA*-DDD introduces an interval-based workload distribution strategy. States are represented as integers, and the total range is partitioned into $n$ intervals corresponding to the number of workstations. The algorithm employs a two-tier strategy for load balancing:
- Strategy A: Maintains existing intervals for low-overhead processing of small workloads.
- Strategy B: Uses sampling-based re-partitioning to calculate new interval boundaries, ensuring an even workload distribution for larger tasks.
Communication is optimized using double-buffered data streaming, which hides network latency by overlapping data transfer with computation.
Experimental Results
The algorithms were evaluated using the Multiple Sequence Alignment (MSA) problem on two benchmark instances: gal4 (requiring ~4.6 GB RAM) and 1pama (requiring ~55.8 GB RAM).
Scalability and Efficiency
On the gal4 problem, PFA*-DDD demonstrated exceptional scalability. As shown in the performance data, the algorithm achieved a 19.5x speedup using 32 nodes on a distributed cluster.
A key observation was the occurrence of super-linear speedup (efficiency > 100%). This phenomenon typically occurs when distributing the search frontier across multiple nodes allows the data to fit into faster CPU caches or higher tiers of the memory hierarchy, reducing overall management overhead.
Capability Expansion
The 1pama instance represents a problem size that is impossible to solve on a single workstation due to its 55.8 GB memory requirement. PFA*-DDD successfully solved this instance by aggregating the memory resources of 16 to 32 workstations.
Conclusion
FA-DDD and PFA-DDD provide a scalable solution for memory-intensive heuristic searches. By combining Frontier Search with Delayed Duplicate Detection and implementing adaptive load balancing, these algorithms overcome traditional memory bottlenecks. Future work will focus on extending these methods to disk-based storage and refining data streaming protocols for even larger state spaces.
Summary updated