astar/Distribution.h

Header of the layer astar, in the group Work distributions; the same header on the site of Doxygen, its source on GitHub.

Classes

Class

Description

ZobristDistribution

HDA*[Z]: Zobrist hashing of the features of the state.

AbstractZobristDistribution

HDA*[Z,Afeature]: Zobrist hashing of the abstract features (AZHDA*).

AbstractStateDistribution

HDA*[Z,Astate]: the abstract state of the Domain, hashed (AHDA*).

PerfectHashDistribution

HDA*[P]: the perfect hash of the Domain modulo p.

StateHashDistribution

The hash of the closed list, remixed with a seed

RandomDistribution

A random worker for each generated state

Concepts

template<class X, class D>
concept IncrementalDistribution
#include <PBeFS/astar/Distribution.h>

a distribution whose owners follow the moves

key( s ) is a 32-bit key of s, whose owner among p workers is key_owner( key( s ) , p ), and key( k , s , t ), with k = key( s ) and t a successor of s, is key( t ): a search that keeps the key of each node computes the key, and then the owner, of each successor in the time of the features that its move changes.

Functions

inline unsigned PBeFS_di_unipi_it::reduce(std::uint64_t h, unsigned p) noexcept

the worker in \( \{ 0 , \ldots , p - 1 \} \) of a 64-bit hash value

Maps h to \( \lfloor h p / 2^{64} \rfloor \), the multiply-high reduction of Lemire, which uses the high bits of \( h \) and is unbiased for a uniform \( h \).

inline unsigned PBeFS_di_unipi_it::key_owner(std::uint32_t k, unsigned p) noexcept

the worker in \( \{ 0 , \ldots , p - 1 \} \) of a 32-bit key

reduce( k \( 2^{32} \) , p ), i.e., \( \lfloor k p / 2^{32} \rfloor \), the key standing for the high bits of a hash.

template<Domain D, class X>
std::uint32_t PBeFS_di_unipi_it::distribution_key(
const X &x,
const state_t<D> &s
)

the key of s for x, 0 if X is not an IncrementalDistribution

template<Domain D, class X>
auto PBeFS_di_unipi_it::successor_owners(
const X &x,
const state_t<D> &s,
std::uint32_t k,
unsigned p
)

the owner among p workers and the key of each successor of s

Returns a callable that maps a successor t of s to the pair of x.owner( t , p ) and distribution_key( x , t ), computed from the key k of s if X is an IncrementalDistribution; s and x must outlive it.

Description of the header

Header file for the work distribution functions of hash-based parallel A*: each one maps a state to its owner among p workers [see section 6 of Fukunaga et al., 2017, and Jinnai and Fukunaga, JAIR 2017].

A distribution is a class with a method owner( s , p ) returning the worker in \( \{ 0 , \ldots , p - 1 \} \) that owns the state \( s \). In the notation of Jinnai and Fukunaga, HDA*[ hash , abstraction ]:

  • ZobristDistribution is HDA*[Z] (Kishimoto, Fukunaga and Botea);

  • AbstractZobristDistribution is HDA*[Z,Afeature], i.e., AZHDA*;

  • AbstractStateDistribution is HDA*[Z,Astate], i.e., AHDA* with Zobrist hashing of the abstract state (Burns et al.);

  • PerfectHashDistribution is HDA*[P], the perfect hash modulo p;

  • StateHashDistribution uses the hash of the closed list;

  • RandomDistribution sends a state to a random worker, so that the duplicates are not detected across the workers (Kumar, Ramesh and Rao; Karp and Zhang): it is the baseline that HDA* is compared to.

Author

Donato Meoli

Dipartimento di Informatica

Università di Pisa

Copyright

© by Donato Meoli