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

Yuu Jinnai, Alex Fukunaga

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.

Introduction

Parallelizing the A algorithm is a complex task due to the interplay between three primary overheads: Search Overhead (SO), Communication Overhead (CO), and Coordination Overhead. While sequential A expands nodes in a strict order, parallel versions must distribute these expansions across multiple processors.

The Hash Distributed A (HDA) framework has emerged as a state-of-the-art solution, utilizing a hash function to assign states to specific processors. However, the choice of hash function is critical. Traditional Zobrist hashing (ZHDA*) excels at load balancing (low SO) but results in high CO because nearly every generated node is sent to a different processor. Conversely, abstraction-based methods reduce CO by keeping related nodes local but often suffer from high SO due to idle processors. This research introduces methods to bridge this gap, seeking a "Goldilocks" solution that balances load while maintaining locality.

Methods and Taxonomy

The landscape of work distribution in parallel best-first search can be categorized by how they manage open lists and distribute work. As shown in Figure 1, HDA* variants fall under decentralized, hash-based work distribution methods.

Taxonomy of work distribution methods for parallel best-first search.

Baseline: Zobrist Hashing

The standard approach, $HDA^*[Z]$, uses Zobrist hashing to map states to processors. The algorithm initializes a set of random values for each feature and computes the hash using XOR operations, as detailed in Figure 2.

Extracted table from page 7 of On Hash-Based Work Distribution Methods for Parallel Best-First Search

Proposed Methods

  1. Abstract Zobrist Hashing (AZH): This hybrid scheme projects raw features into "abstract features" before applying Zobrist hashing. By grouping states with similar high-level characteristics on the same processor, AZH reduces communication while the hashing step maintains load balance.
  2. GRAZHDA*: To automate feature projection for domain-independent planning, GRAZHDA* employs graph partitioning on Domain Transition Graphs (DTGs). DTGs serve as small, manageable abstractions of the state space.
  3. Sparsity Objective: A novel objective function for DTG partitioning that balances the number of cut edges (CO) against partition balance (SO).

Experimental Evaluation

The proposed methods were evaluated on classic benchmarks (15/24-puzzle, Multiple Sequence Alignment, Grid-based pathfinding) and IPC domain-independent planning tasks. Testing spanned various architectures, from 8-core local machines to 128-core Amazon EC2 clusters.

Key Results

  • Efficiency in Planning: GRAZHDA with the sparsity objective outperformed previous HDA variants in domain-independent planning, showing significant speedups on large-scale clusters.
  • Scaling in Puzzles: On the 24-puzzle, AZH achieved a 7.8x speedup on 8 cores, nearly reaching ideal linear scaling and outperforming standard ZHDA* (5.9x).
  • Robustness: The methods proved effective even in high-latency cloud environments, where minimizing communication is paramount.

Discussion and Future Work

The research highlights that in domains with fast node expansion, such as grid pathfinding, communication overhead is the primary bottleneck. AZH effectively addresses this by enhancing locality.

Future research directions include:

  • Non-Uniform Memory Access (NUMA): Adapting hash functions to account for varying communication costs between cores in modern data centers.
  • Merged DTGs: Combining multiple variables in DTGs to create more accurate state-space proxies.
  • GPU Acceleration: Extending these hash-based distribution strategies to massively parallel GPU architectures.

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},
}
Figure