Sequential and Parallel Algorithms for Frontier A* with Delayed Duplicate Detection

Robert Niewiadomski, José Nelson Amaral, Robert C. HolteAAAI 2006

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.

Performance results for the gal4 MSA problem instance, showing super-linear speedup efficiency.

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.

Performance results for the 1pama MSA problem instance, demonstrating the ability to solve large-scale problems through distributed memory.

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

BibTeX
@inproceedings{niewiadomski2006sequential,
  author = {Robert Niewiadomski and José Nelson Amaral and Robert C. Holte},
  title = {{Sequential and Parallel Algorithms for Frontier A* with Delayed Duplicate Detection}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2006},
}
Figure