On Hash-Based Work Distribution Methods for Parallel Best-First Search

Yuu Jinnai, Alex Fukunaga

TL;DR

Parallel best-first search (like Hash Distributed A*) faces an inherent dilemma: uniform hashing achieves great load balance but floods the system with communication overhead, while spatial abstractions reduce communication at the cost of massive search overhead. This paper introduces Abstract Zobrist Hashing (AZH) and GRAZHDA*, a principled framework that models work distribution as graph partitioning over Domain Transition Graphs (DTGs) using a sparsest-cut objective, achieving state-of-the-art parallel speedups on up to 128 cores across multicore, cluster, and cloud environments.

What Problem Does This Paper Address?

In Hash Distributed A* (HDA*), search states are assigned to distinct processor queues via a global hash function, allowing fully asynchronous search without locks on centralized open lists. However, scaling HDA* is difficult because of a fundamental trade-off:

  • Search Overhead (SO): Parallel threads expanding states that sequential A* would never touch, often caused by load imbalance where idle workers explore unpromising paths.
  • Communication Overhead (CO): The cost of sending newly generated child states across threads or network nodes.

Standard Zobrist hashing distributes states uniformly, but because adjacent states almost always land on different threads, over 90% of generated states are sent across the network. Conversely, previous structured abstraction methods (like AHDA*) group neighboring states onto the same processor to slash communication, but create massive load imbalances that derail parallel efficiency.

Methods

The authors bridge this divide with two key developments:

  1. Abstract Zobrist Hashing (AZH): Rather than hashing raw state features directly, AZH introduces a feature projection function that groups raw features into abstract features, then computes the Zobrist hash on these abstract representations. Because this projection is precalculated at initialization into a lookup table, AZH incurs zero runtime computational overhead during the search.
  2. Workload Modeling as Graph Partitioning: Workload allocation is formalized as partitioning an implicit workload graph $G_W$ (states with $f < f^*$). The authors derive an estimated efficiency metric ($eff_{esti}$) linking edge cuts to communication overhead and partition balance to load imbalance.
  3. GRAZHDA*: Because partitioning the actual state space graph upfront is impossible (solving it would require already knowing the search space), GRAZHDA* uses Domain Transition Graphs (DTGs) extracted from classical planning tasks (PDDL/SAS+) as compact proxies for the search space. It partitions each DTG using an exact depth-first branch-and-bound solver optimizing for a sparsest-cut objective: $$\text{sparsity} := \frac{\prod_i^p |S_i|}{\sum_i^p \sum_{j > i}^p E(S_i, S_j)}$$ This objective balances load distribution against cut edges without enforcing rigid, artificial bisections.

Datasets

The authors evaluated their methods across diverse combinatorial search and automated planning benchmarks:

  • Domain-Specific Combinatorial Search:
  • Standard 100-instance 15-Puzzle benchmark (Korf, 1985) and harder randomly generated 15-puzzle instances.
  • 100 randomly generated 24-Puzzle instances evaluated with pattern database heuristics.
  • Multiple Sequence Alignment (MSA) using 10 real amino acid sequences from BAliBASE 3.0 alongside 50 synthetic instances.
  • $5000 \times 5000$ Grid Pathfinding instances with 45% obstacle density.
  • Domain-Independent Classical Planning: Benchmark problem suites from the International Planning Competition (IPC)—including Blocks, Elevators, Gripper, Logistics, Openstacks, Rovers, Scanalyzer, and others—using the Fast Downward planner with both fast (Merge-and-Shrink) and expensive (LM-cut) heuristics.

Key Insights and Ideas

  • Deconstructing Search Overhead: By comparing parallel expansion order against sequential A*, the authors identified two primary culprits for search overhead:
  • Burst Effect: A startup artifact where threads with initially empty queues expand bad nodes before promising ones arrive. This dominates very easy problems but disappears on harder tasks.
  • Band Effect: A persistent divergence from sequential expansion order directly proportional to load imbalance.
  • Communication Overhead Matters Everywhere: Even with slow node evaluations (like the LM-cut heuristic, which runs 14.5× slower than Merge-and-Shrink), reducing communication overhead still provided major speedup gains.
  • DTGs as Search Space Proxies: Graph partitioning on small, factored subgraphs (DTGs) reliably predicts state-space locality, closing the gap between domain-specific, hand-tuned work distribution and fully automated methods.

Key Results

  • Sliding-Tile Puzzles & MSA: On 16 multicore threads, hand-crafted AZH significantly outperformed standard Zobrist HDA* and AHDA*, delivering high efficiency by avoiding the extreme communication costs of Zobrist and the high search overhead of AHDA*.
  • 48-Core Commodity Cluster (Classical Planning): GRAZHDA*/sparsity achieved an average speedup of 30.92× (total wall-clock time 277.9s), substantially faster than baseline Zobrist HDA* (20.53×, 433.2s) and prior automated abstraction variants like FAZHDA* (28.68×, 301.4s).
  • 128-Core AWS Cloud Cluster: In a high-latency, virtualized cloud environment (32 m1.xlarge instances), GRAZHDA*/sparsity scaled robustly, completing the benchmark suite in 387.3s, compared to 594.0s for standard Zobrist HDA*.
  • Automated vs. Hand-Crafted: On the 24-puzzle, domain-independent GRAZHDA*/sparsity matched the performance of carefully hand-crafted feature projections (7.84× vs 7.85× speedup on 8 cores).

Limitations and Future Work

  • Uniform Network Assumptions: The graph model assumes identical communication latency between all pairs of cores, which does not reflect non-uniform memory access (NUMA) architectures, hierarchical cluster interconnects, or multi-cloud settings.
  • Independent Variable Partitioning: GRAZHDA* partitions DTGs independently for each SAS+ variable. The authors note that partitioning merged DTGs (similar to Merge-and-Shrink representations) could capture inter-variable dependencies and yield better graph cuts.
  • Heterogeneous Hardware: The framework was tested on CPUs; extending abstract-feature hashing to GPU-accelerated parallel search systems remains an open challenge.

Summary updated

Abstract

Parallel best-first search algorithms such as Hash Distributed A* (HDA*) distribute work among the processes using a global hash function. We analyze the search and communication overheads of state-of-the-art hash-based parallel best-first search algorithms, and show that although Zobrist hashing, the standard hash function used by HDA*, achieves good load balance for many domains, it incurs significant communication overhead since almost all generated nodes are transferred to a different processor than their parents. We propose Abstract Zobrist hashing, a new work distribution method for parallel search which, instead of computing a hash value based on the raw features of a state, uses a feature projection function to generate a set of abstract features which results in a higher locality, resulting in reduced communications overhead. We show that Abstract Zobrist hashing outperforms previous methods on search domains using hand-coded, domain specific feature projection functions. We then propose GRAZHDA*, a graph-partitioning based approach to automatically generating feature projection functions. GRAZHDA* seeks to approximate the partitioning of the actual search space graph by partitioning the domain transition graph, an abstraction of the state space graph. We show that GRAZHDA* outperforms previous methods on domain-independent planning.
BibTeX
@article{jinnai2017hash,
  author = {Yuu Jinnai and Alex Fukunaga},
  title = {{On Hash-Based Work Distribution Methods for Parallel Best-First Search}},
  journal = {J. Artif. Intell. Res.},
  year = {2017},
  url = {https://openreview.net/forum?id=hLHD3pSQmX},
}

Loading related content...

Figure