Distribution.h File Reference

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]. More...

#include <concepts>
#include <cstddef>
#include <cstdint>
#include <random>
#include <string>
#include <utility>
#include <vector>
#include "PBeFS/astar/Domain.h"
#include "ADS/dictionary/RandomHashing.h"

Go to the source code of this file.

Classes
class	ZobristDistribution< D >
	HDA*[Z]: Zobrist hashing of the features of the state. More...
class	AbstractZobristDistribution< D >
	HDA*[Z,Afeature]: Zobrist hashing of the abstract features (AZHDA*). More...
class	AbstractStateDistribution< D >
	HDA*[Z,Astate]: the abstract state of the Domain, hashed (AHDA*). More...
class	PerfectHashDistribution< D >
	HDA*[P]: the perfect hash of the Domain modulo p. More...
class	StateHashDistribution< D >
	the hash of the closed list, remixed with a seed More...
class	RandomDistribution< D >
	a random worker for each generated state More...

Namespaces
namespace	PBeFS_di_unipi_it
	namespace for the Parallel Best-First Search library

Concepts
concept	PBeFS_di_unipi_it::IncrementalDistribution
	a distribution whose owners follow the moves

Functions
unsigned	reduce (std::uint64_t h, unsigned p) noexcept
	the worker in \( \{ 0 , \ldots , p - 1 \} \) of a 64-bit hash value
unsigned	key_owner (std::uint32_t k, unsigned p) noexcept
	the worker in \( \{ 0 , \ldots , p - 1 \} \) of a 32-bit key
template<Domain D, class X>
std::uint32_t	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	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

Detailed Description

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