HDAStar.h

Go to the documentation of this file.

/*--------------------------------------------------------------------------*/
/*----------------------------- File HDAStar.h -----------------------------*/
/*--------------------------------------------------------------------------*/
/*--------------------------------------------------------------------------*/
/*------------------------------ DEFINITIONS -------------------------------*/
/*--------------------------------------------------------------------------*/
 
#ifndef __PBeFS_HDAStar
 #define __PBeFS_HDAStar
                      /* self-identification: #endif at the end of the file */
 
/*--------------------------------------------------------------------------*/
/*-------------------------------- INCLUDES --------------------------------*/
/*--------------------------------------------------------------------------*/
 
#include <atomic>
 
#include <memory>
 
#include <mutex>
 
#include <optional>
 
#include <string>
 
#include <type_traits>
 
#include <vector>
 
#include "PBeFS/astar/AStar.h"
 
#include "PBeFS/astar/Distribution.h"
 
#include "PBeFS/core/SearchUtils.h"
 
#include "ADS/parallel/Channels.h"
 
#include "ADS/parallel/Mailbox.h"
 
/*--------------------------------------------------------------------------*/
/*------------------------------- NAMESPACE --------------------------------*/
/*--------------------------------------------------------------------------*/

namespace PBeFS_di_unipi_it
{
 
/*--------------------------------------------------------------------------*/
/*------------------------- CLASS ParallelOptions --------------------------*/
/*--------------------------------------------------------------------------*/
 
struct ParallelOptions : public SearchOptions , public ParallelParams {
 };  // end( struct( ParallelOptions ) )
 
/*--------------------------------------------------------------------------*/
/*----------------------------- CLASS HDAStar ------------------------------*/
/*--------------------------------------------------------------------------*/

 
template< Domain D , class Dist = StateHashDistribution< D > ,
          ADS::WorkerExecutor Executor = ADS::ThreadPool ,
          class Open = std::conditional_t<
           std::is_integral_v< cost_t< D > > ,
           BucketOpenList< Node< state_t< D > , cost_t< D > > > ,
           HeapOpenList< Node< state_t< D > , cost_t< D > > > > >
class HDAStar {
 
/*------------------------ PUBLIC PART OF THE CLASS ------------------------*/
 
 public:
 
/*------------------------------ PUBLIC TYPES ------------------------------*/
 
 using State = state_t< D >;                       
 using Cost = cost_t< D >;                         
 using NodeT = Node< State , Cost >;               
 using SolutionT = Solution< State , Cost >;       

 struct Msg {
  State s;
  Cost g;
  Cost h;
  NodeT * parent;
  [[no_unique_address]] OperatorOf< D > o;        // the operator of s
  std::uint32_t key;                               // the key of s
  };
 
/*------------------------------ CONSTRUCTOR -------------------------------*/

 
 HDAStar( const D & domain , const Dist & dist ,
          const ParallelOptions & options = {} )
  : f_domain( domain ) , f_dist( dist ) , f_options( options ) {
  f_options.normalize();
  }
 
/*------------------------- OTHER INITIALIZATIONS --------------------------*/
 
 void set_executor( Executor & ex ) noexcept { f_ex = &ex; }
 
/*-------------------------------- SOLVING ---------------------------------*/
 
 [[nodiscard]] SolutionT solve( void ) const
 {
  const unsigned p = f_options.threads;
  Stopwatch clock;
  Shared sh( p , f_options.batch );
 
  // the root, which its owner inserts before the first expansion
  const State s0 = f_domain.initial_state();
  sh.root.emplace( Msg{ s0 , Cost( 0 ) , Cost( f_domain.heuristic( s0 ) ) ,
                        nullptr , no_op ,
                        distribution_key< D >( f_dist , s0 ) } );
  sh.root_owner = f_dist.owner( s0 , p );
 
  std::vector< std::unique_ptr< Worker > > w( p );
  for( unsigned i = 0 ; i < p ; ++i )
   w[ i ] = std::make_unique< Worker >( *this , sh , i );
 
  run_workers( f_ex , p , [ & ]( unsigned i ) { w[ i ]->run(); } );
 
  SolutionT sol;
  SearchStats & st = sol.stats;
  for( auto & x : w ) {
   st.expanded += x->f_st.expanded;
   st.reexpanded += x->f_st.reexpanded;
   st.generated += x->f_st.generated;
   st.duplicates += x->f_st.duplicates;
   st.sent += x->f_st.sent;
   st.messages += sh.mail.batches( x->f_id );
   st.stored += x->f_pool.size();
   st.expanded_by.push_back( x->f_st.expanded );
   st.stored_by.push_back( x->f_pool.size() );
   }
  if( sh.limit_hit.load() )
   sol.status = Status::node_limit;
  else
   if( sh.goal ) {
    sol.status = Status::solved;
    sol.cost = sh.goal->g;
    sol.path = trace_path( sh.goal );
    }
  st.seconds = clock.seconds();
  return( sol );
  }
 
/*----------------------- PRIVATE PART OF THE CLASS ------------------------*/
 
 private:
 
 using Mailbox = ADS::Mailbox< Msg , ADS::DefaultChannels< Msg , Executor > >;
 
/*- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -*/
 // the data shared by the workers
 
 struct Shared {
 
  Shared( unsigned np , std::size_t batch ) : p( np ) , mail( np , batch )
  {}
 
  unsigned p;                                   // the number of workers
  Mailbox mail;                                 // the messages
  std::optional< Msg > root;                    // the root
  unsigned root_owner = 0;                      // its owner
  alignas( cache_line ) std::atomic< Cost > incumbent{
                                                   infinite_cost< Cost >() };
  std::atomic< bool > limit_hit{ false };
  std::mutex goal_mutex;                        // protects goal
  NodeT * goal = nullptr;                       // the best goal found
  };
 
/*- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -*/
 // a worker: its OPEN and CLOSED lists, its outboxes and its counters
 
 struct alignas( cache_line ) Worker {
 
  Worker( const HDAStar & a , Shared & s , unsigned i )
   : f_a( a ) , f_sh( s ) , f_id( i ) , f_dist( a.f_dist ) {}
 
  // the main loop
  void run( void ) {
   if( f_id == f_sh.root_owner )
    insert( *f_sh.root , f_a.f_domain.hash( f_sh.root->s ) );
   unsigned since_flush = 0;
   ADS::Backoff backoff;
   while( ! f_sh.mail.stopped() ) {
    v_in.clear();
    f_sh.mail.poll( f_id , [ & ]( Msg && m ) {
     v_in.push_back( std::move( m ) );
     } );
    if( const std::size_t n = v_in.size() ) {
     // the hashes and the prefetches of the whole batch first, so that
     // the cache misses of the lookups overlap
     v_hash.resize( n );
     for( std::size_t k = 0 ; k < n ; ++k ) {
      v_hash[ k ] = f_a.f_domain.hash( v_in[ k ].s );
      f_table.prefetch( v_hash[ k ] );
      }
     for( std::size_t k = 0 ; k < n ; ++k )
      insert( v_in[ k ] , v_hash[ k ] );
     }
 
    if( NodeT * n = next() ) {
     backoff.reset();
     expand( n );
     if( ++since_flush >= f_a.f_options.flush_period ) {
      since_flush = 0;
      f_sh.mail.flush( f_id );
      }
     if( f_a.f_options.node_limit &&
         ( f_pool.size() >= f_a.f_options.node_limit ) ) {
      f_sh.limit_hit.store( true );
      f_sh.mail.stop();
      }
     continue;
     }
 
    // nothing to expand: send everything, and end if no worker has work
    // and no message is in transit
    if( f_sh.mail.quiescent( f_id ) )
     return;
    backoff.pause();
    }
   }
 
  // the best node of OPEN with f < incumbent, removed; nullptr if none
  NodeT * next( void ) {
   while( ! f_open.empty() ) {
    const OpenEntry< NodeT > e = f_open.top();
    if( e.stale() ) {
     f_open.pop();
     continue;
     }
    if( e.node->g + e.node->h >= f_sh.incumbent.load(
                                                std::memory_order_relaxed ) )
     return( nullptr );
    f_open.pop();
    return( e.node );
    }
   return( nullptr );
   }
 
  // expands n, or records it as the incumbent if it is a goal
  void expand( NodeT * n ) {
   n->closed = true;
   ++f_st.expanded;
   if( n->expanded )
    ++f_st.reexpanded;
   n->expanded = true;
 
   if( f_a.f_domain.is_goal( n->state ) ) {
    std::lock_guard< std::mutex > lock( f_sh.goal_mutex );
    if( n->g < f_sh.incumbent.load() ) {
     f_sh.incumbent.store( n->g );
     f_sh.goal = n;
     }
    return;
    }
 
   const auto owner = successor_owners< D >( f_dist , n->state , n->key ,
                                             f_sh.p );
   for_each_child( f_a.f_domain , n->state , n->h , n->op ,
                   [ & ]( const State & t , Cost c , Cost ht ,
                          std::uint8_t ot ) {
    ++f_st.generated;
    const Cost g = n->g + c;
    if( g + ht >= f_sh.incumbent.load( std::memory_order_relaxed ) )
     return;
    const auto [ dst , key ] = owner( t );
    if( dst == f_id ) {
     insert( Msg{ t , g , ht , n , ot , key } , f_a.f_domain.hash( t ) );
     return;
     }
    f_sh.mail.send( f_id , dst , Msg{ t , g , ht , n , ot , key } );
    ++f_st.sent;
    } );
   }
 
  // adds the node of m, whose state has hash h, to OPEN, unless it is a
  // duplicate
  void insert( const Msg & m , std::uint64_t h ) {
   if( m.g + m.h >= f_sh.incumbent.load( std::memory_order_relaxed ) )
    return;
   auto [ x , fresh ] = f_table.find_or_insert( m.s , h , [ & ] {
    NodeT * y = f_pool.allocate();
    *y = NodeT{ m.s , m.g , m.h , m.parent , false , false , m.o.op ,
                m.key };
    return( y );
    } );
   if( fresh )
    f_open.push( x );
   else
    if( m.g < x->g ) {
     x->g = m.g;
     x->parent = m.parent;
     x->op = m.o.op;
     x->closed = false;
     f_open.push( x );
     }
    else
     ++f_st.duplicates;
   }
 
  const HDAStar & f_a;                          // the search
  Shared & f_sh;                                // the shared data
  unsigned f_id;                                // the index of the worker
  Dist f_dist;                                  // its distribution
  NodePool< NodeT > f_pool;                     // its nodes
  NodeTable< NodeT > f_table;                   // its CLOSED list
  Open f_open;                                  // its OPEN list
  std::vector< Msg > v_in;                      // the last inbox received
  std::vector< std::uint64_t > v_hash;          // the hashes of v_in
  SearchStats f_st;                             // its counters
  };
 
/*- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -*/
 
 const D & f_domain;                                   
 const Dist & f_dist;                    
 ParallelOptions f_options;                            
 Executor * f_ex = nullptr;                            
 
 };  // end( class( HDAStar ) )
 
/*--------------------------------------------------------------------------*/
 
}  // end( namespace PBeFS_di_unipi_it )
 
/*--------------------------------------------------------------------------*/
 
#endif  /* __PBeFS_HDAStar */
 
/*--------------------------------------------------------------------------*/
/*--------------------------- End File HDAStar.h ---------------------------*/
/*--------------------------------------------------------------------------*/