Distribution.h

Go to the documentation of this file.

/*--------------------------------------------------------------------------*/
/*-------------------------- File Distribution.h ---------------------------*/
/*--------------------------------------------------------------------------*/
/*--------------------------------------------------------------------------*/
/*------------------------------ DEFINITIONS -------------------------------*/
/*--------------------------------------------------------------------------*/
 
#ifndef __PBeFS_Distribution
 #define __PBeFS_Distribution
                      /* self-identification: #endif at the end of the file */
 
/*--------------------------------------------------------------------------*/
/*-------------------------------- INCLUDES --------------------------------*/
/*--------------------------------------------------------------------------*/
 
#include <concepts>
 
#include <cstddef>
 
#include <cstdint>
 
#include <random>
 
#include <string>
 
#include <utility>
 
#include <vector>
 
#if defined( _MSC_VER )
 #include <intrin.h>
#endif
 
#include "PBeFS/astar/Domain.h"
 
#include "ADS/dictionary/RandomHashing.h"
 
/*--------------------------------------------------------------------------*/
/*------------------------------- NAMESPACE --------------------------------*/
/*--------------------------------------------------------------------------*/

namespace PBeFS_di_unipi_it
{
 
/*--------------------------------------------------------------------------*/
/*------------------------------- FUNCTIONS --------------------------------*/
/*--------------------------------------------------------------------------*/

 
[[nodiscard]] inline unsigned reduce( std::uint64_t h , unsigned p ) noexcept
{
 #if defined( __SIZEOF_INT128__ )
  __extension__ using u128 = unsigned __int128;
  return( unsigned( ( u128( h ) * p ) >> 64 ) );
 #elif defined( _MSC_VER )
  return( unsigned( __umulh( h , p ) ) );
 #else
  return( unsigned( h % p ) );
 #endif
 }
 
/*--------------------------------------------------------------------------*/

 
[[nodiscard]] inline unsigned key_owner( std::uint32_t k , unsigned p )
 noexcept
{
 return( reduce( std::uint64_t( k ) << 32 , p ) );
 }
 
/*--------------------------------------------------------------------------*/
/*----------------------- CLASS ZobristDistribution ------------------------*/
/*--------------------------------------------------------------------------*/

 
template< FeatureDomain D >
class ZobristDistribution {
 
 public:

 
 explicit ZobristDistribution( const D & domain , std::uint64_t seed = 1 )
  : f_domain( domain ) , f_r( domain.num_features() , 1 , seed ) {}

 
 [[nodiscard]] std::uint64_t hash( const state_t< D > & s ) const {
  std::uint64_t z = 0;
  f_domain.for_each_feature( s , [ & ]( std::size_t i ) {
   z ^= f_r( i , 0 );
   } );
  return( z );
  }

 
 [[nodiscard]] std::uint32_t key( const state_t< D > & s ) const {
  return( std::uint32_t( hash( s ) >> 32 ) );
  }

 
 [[nodiscard]] unsigned owner( const state_t< D > & s , unsigned p ) const {
  return( key_owner( key( s ) , p ) );
  }


 
 [[nodiscard]] std::uint32_t key( std::uint32_t k , const state_t< D > & s ,
                                  const state_t< D > & t ) const
  requires IncrementalFeatureDomain< D > {
  f_domain.for_each_feature_change( s , t , [ & ]( std::size_t i ) {
   k ^= std::uint32_t( f_r( i , 0 ) >> 32 );
   } );
  return( k );
  }

 
 [[nodiscard]] static std::string name( void ) { return( "Z" ); }
 
 private:
 
 const D & f_domain;                                   
 ADS::ZobristTable f_r;                                
 
 };  // end( class( ZobristDistribution ) )
 
/*--------------------------------------------------------------------------*/
/*------------------- CLASS AbstractZobristDistribution --------------------*/
/*--------------------------------------------------------------------------*/

 
template< AbstractFeatureDomain D >
class AbstractZobristDistribution {
 
 public:

 
 explicit AbstractZobristDistribution( const D & domain ,
                                       std::uint64_t seed = 1 )
  : f_domain( domain ) , v_r( domain.num_features() ) {
  const ADS::ZobristTable r0( domain.num_abstract_features() , 1 , seed );
  for( std::size_t i = 0 ; i < v_r.size() ; ++i )
   v_r[ i ] = r0( domain.abstract_feature( i ) , 0 );
  }

 
 [[nodiscard]] std::uint64_t hash( const state_t< D > & s ) const {
  std::uint64_t z = 0;
  f_domain.for_each_feature( s , [ & ]( std::size_t i ) { z ^= v_r[ i ]; } );
  return( z );
  }

 
 [[nodiscard]] std::uint32_t key( const state_t< D > & s ) const {
  return( std::uint32_t( hash( s ) >> 32 ) );
  }

 
 [[nodiscard]] unsigned owner( const state_t< D > & s , unsigned p ) const {
  return( key_owner( key( s ) , p ) );
  }


 
 [[nodiscard]] std::uint32_t key( std::uint32_t k , const state_t< D > & s ,
                                  const state_t< D > & t ) const
  requires IncrementalFeatureDomain< D > {
  f_domain.for_each_feature_change( s , t , [ & ]( std::size_t i ) {
   k ^= std::uint32_t( v_r[ i ] >> 32 );
   } );
  return( k );
  }

 
 [[nodiscard]] static std::string name( void ) { return( "AZ" ); }
 
 private:
 
 const D & f_domain;                                   
 std::vector< std::uint64_t > v_r;           
 
 };  // end( class( AbstractZobristDistribution ) )
 
/*--------------------------------------------------------------------------*/
/*-------------------- CLASS AbstractStateDistribution ---------------------*/
/*--------------------------------------------------------------------------*/

 
template< AbstractStateDomain D >
class AbstractStateDistribution {
 
 public:
 
 explicit AbstractStateDistribution( const D & domain ,
                                     std::uint64_t seed = 1 )
  : f_domain( domain ) , f_seed( ADS::splitmix64( seed ) ) {}

 
 [[nodiscard]] unsigned owner( const state_t< D > & s , unsigned p ) const {
  return( reduce( ADS::splitmix64( f_domain.abstract_state( s ) ^
                                   f_seed ) , p ) );
  }

 
 [[nodiscard]] static std::string name( void ) { return( "A" ); }
 
 private:
 
 const D & f_domain;                                   
 std::uint64_t f_seed;                         
 
 };  // end( class( AbstractStateDistribution ) )
 
/*--------------------------------------------------------------------------*/
/*--------------------- CLASS PerfectHashDistribution ----------------------*/
/*--------------------------------------------------------------------------*/

 
template< PerfectHashDomain D >
class PerfectHashDistribution {
 
 public:
 
 explicit PerfectHashDistribution( const D & domain , std::uint64_t = 1 )
  : f_domain( domain ) {}
 
 [[nodiscard]] unsigned owner( const state_t< D > & s , unsigned p ) const {
  return( unsigned( f_domain.perfect_hash( s ) % p ) );
  }
 
 [[nodiscard]] static std::string name( void ) { return( "P" ); }
 
 private:
 
 const D & f_domain;                                   
 
 };  // end( class( PerfectHashDistribution ) )
 
/*--------------------------------------------------------------------------*/
/*---------------------- CLASS StateHashDistribution -----------------------*/
/*--------------------------------------------------------------------------*/

 
template< Domain D >
class StateHashDistribution {
 
 public:
 
 explicit StateHashDistribution( const D & domain , std::uint64_t seed = 1 )
  : f_domain( domain ) , f_seed( ADS::splitmix64( seed ) ) {}
 
 [[nodiscard]] unsigned owner( const state_t< D > & s , unsigned p ) const {
  return( reduce( ADS::splitmix64( f_domain.hash( s ) ^ f_seed ) , p ) );
  }
 
 [[nodiscard]] static std::string name( void ) { return( "H" ); }
 
 private:
 
 const D & f_domain;                                   
 std::uint64_t f_seed;                         
 
 };  // end( class( StateHashDistribution ) )
 
/*--------------------------------------------------------------------------*/
/*------------------------ CLASS RandomDistribution ------------------------*/
/*--------------------------------------------------------------------------*/

 
template< Domain D >
class RandomDistribution {
 
 public:
 
 explicit RandomDistribution( const D & , std::uint64_t seed = 1 )
  : f_gen( seed ) {}
 
 [[nodiscard]] unsigned owner( const state_t< D > & , unsigned p ) const {
  return( reduce( f_gen() , p ) );
  }
 
 [[nodiscard]] static std::string name( void ) { return( "R" ); }

 static constexpr bool per_worker = true;
 
 private:
 
 mutable std::mt19937_64 f_gen;                        
 
 };  // end( class( RandomDistribution ) )
 
/*--------------------------------------------------------------------------*/
/*-------------------------------- CONCEPTS --------------------------------*/
/*--------------------------------------------------------------------------*/

 
template< class X , class D >
concept IncrementalDistribution =
 requires( const X & x , const state_t< D > & s , std::uint32_t k ,
           unsigned p ) {
  { x.key( s ) } -> std::same_as< std::uint32_t >;
  { x.key( k , s , s ) } -> std::same_as< std::uint32_t >;
  { x.owner( s , p ) } -> std::convertible_to< unsigned >;
  };
 
/*--------------------------------------------------------------------------*/
/*------------------------------- FUNCTIONS --------------------------------*/
/*--------------------------------------------------------------------------*/
 
template< Domain D , class X >
[[nodiscard]] std::uint32_t distribution_key( const X & x ,
                                              const state_t< D > & s ) {
 if constexpr( IncrementalDistribution< X , D > )
  return( x.key( s ) );
 else
  return( 0 );
 }
 
/*--------------------------------------------------------------------------*/

 
template< Domain D , class X >
[[nodiscard]] auto successor_owners( const X & x , const state_t< D > & s ,
                                     std::uint32_t k , unsigned p ) {
 if constexpr( IncrementalDistribution< X , D > )
  return( [ & x , & s , k , p ]( const state_t< D > & t ) {
   const std::uint32_t kt = x.key( k , s , t );
   return( std::pair( key_owner( kt , p ) , kt ) );
   } );
 else
  return( [ & x , p ]( const state_t< D > & t ) {
   return( std::pair( unsigned( x.owner( t , p ) ) , std::uint32_t( 0 ) ) );
   } );
 }
 
}  // end( namespace PBeFS_di_unipi_it )
 
/*--------------------------------------------------------------------------*/
 
#endif  /* __PBeFS_Distribution */
 
/*--------------------------------------------------------------------------*/
/*------------------------ End File Distribution.h -------------------------*/
/*--------------------------------------------------------------------------*/