Generated on for Gecode by doxygen 1.17.0
Gecode::Search::Par::Engine< Tracer > Class Template Reference

Parallel depth-first search engine More...

#include <gecode/search/par/engine.hh>

Classes

class  Worker
 Parallel depth-first search worker More...
struct  SchedulerWorker
 Per-worker adjustable parallel admission state. More...

Public Member Functions

const Options & opt (void) const
 Provide access to search options.
unsigned int workers (void) const
 Return number of workers.
void scheduler_enable (bool root_owner)
 Enable adjustable parallel admission.
void scheduler_reset (bool root_owner)
 Reset adjustable parallel state while all workers are blocked.
bool scheduler_admit (unsigned int worker)
 Admit worker worker for one exploration action.
bool scheduler_paused (void) const
 Whether the external worker request currently pauses the engine.
void scheduler_owner (unsigned int worker)
 Record that worker worker owns search.
void scheduler_idle (unsigned int worker)
 Record that worker worker is idle.
void scheduler_handoff (unsigned int worker, bool work_remains)
 Hand worker worker's lease to a parked logical worker.
Public Member Functions inherited from Gecode::Search::Engine
virtual Statistics statistics (void) const =0
 Return statistics.
virtual bool limited (void) const
 Whether the engine stopped at a local limit (such as a CABS width limit) and cannot continue.
virtual void constrain (const Space &b)
 Constrain future solutions to be better than b (raises exception).
virtual void reset (Space *s)
 Reset engine to restart at space s (does nothing).
virtual NoGoods & nogoods (void)
 Return no-goods (the no-goods are empty).
Public Member Functions inherited from Gecode::Support::Terminator
virtual ~Terminator ()
 Destructor.

Protected Types

enum class  SchedulerLogical { OWNER , PENDING , IDLE }
 Logical worker state used by adjustable parallel admission. More...

Protected Member Functions

unsigned int scheduler_select (SchedulerLogical logical, unsigned int exclude) const
 Select a no-lease worker by logical state (scheduler_mutex held).
bool scheduler_grow (void)
 Grant leases up to the current request (scheduler_mutex held).
Protected Member Functions inherited from Gecode::Search::Engine
 Engine (void)
 Construct a meta engine without worker control.
 Engine (const Options &o, unsigned int capacity)
 Construct a leaf engine and bind worker control to capacity.

Protected Attributes

Options _opt
 Search options.
bool scheduler_enabled
 Whether adjustable parallel admission is enabled.
const std::atomic< bool > * scheduler_fast_admit
 Unchanged-capacity admission fast path.
Support::Mutex scheduler_mutex
 Mutex for adjustable parallel admission.
SchedulerWorker * scheduler_worker
 Per-worker adjustable parallel admission state.
unsigned int scheduler_requested
 Current requested lease count.
unsigned int scheduler_leases
 Current lease count.
unsigned int scheduler_cursor
 Round-robin cursor for lease handoff.
std::atomic< unsigned long long int > scheduler_generation
 Last request generation reconciled by the scheduler.
Protected Attributes inherited from Gecode::Search::Engine
WorkerControl worker_control
 Control retained for the lifetime of a leaf engine.

Commands from engine to workers and wait management

enum  Cmd { C_WORK , C_WAIT , C_RESET , C_TERMINATE }
 Commands from engine to workers. More...
std::atomic< Cmd > _cmd
 The current command.
Support::Mutex _m_wait
 Mutex for forcing workers to wait.
Cmd cmd (void) const
 Return current command.
void block (void)
 Block all workers.
void release (Cmd c)
 Release all workers.
void wait (void)
 Ensure that worker waits.

Termination control

Support::Mutex _m_term
 Mutex for access to termination information.
volatile unsigned int _n_term_not_ack
 Number of workers that have not yet acknowledged termination.
Support::Event _e_term_ack
 Event for termination acknowledgment.
Support::Mutex _m_wait_terminate
 Mutex for waiting for termination.
volatile unsigned int _n_not_terminated
 Number of not yet terminated workers.
Support::Event _e_terminate
 Event for termination (all threads have terminated).
void ack_terminate (void)
 For worker to acknowledge termination command.
virtual void terminated (void)
 For worker to register termination.
void wait_terminate (void)
 For worker to wait until termination is legal.
void terminate (void)
 For engine to perform thread termination.

Reset control

Support::Mutex _m_reset
 Mutex for access to reset information.
volatile unsigned int _n_reset_not_ack
 Number of workers that have not yet acknowledged reset.
Support::Event e_reset_ack_start
 Event for reset acknowledgment started.
Support::Event e_reset_ack_stop
 Event for reset acknowledgment stopped.
Support::Mutex m_wait_reset
 Mutex for waiting for reset.
void ack_reset_start (void)
 For worker to acknowledge start of reset cycle.
void ack_reset_stop (void)
 For worker to acknowledge stop of reset cycle.
void wait_reset (void)
 For worker to wait for all workers to reset.

Search control

Support::Mutex m_search
 Mutex for search.
Support::Event e_search
 Event for search (solution found, no more solutions, search stopped).
Support::DynamicQueue< Space *, Heap > solutions
 Queue of solutions.
volatile unsigned int n_busy
 Number of busy workers.
std::atomic< bool > has_stopped
 Whether a worker had been stopped.
std::atomic< unsigned long long int > n_runs
 Number of calls to next() that have started search.
bool signal (void) const
 Whether search state changed such that signal is needed.
void idle (void)
 Report that worker is idle.
void busy (void)
 Report that worker is busy.
unsigned long long int run (void) const
 Return the current call of next().
void stop (unsigned long long int r)
 Report that a worker was stopped during call r of next().
bool work_remains (void)
 Whether logical search work remains.

Engine interface

 Engine (const Options &o)
 Initialize with options o.
virtual Space * next (void)
 Return next solution (nullptr, if none exists or search has been stopped).
virtual bool stopped (void) const
 Check whether engine has been stopped.
virtual ~Engine (void)
 Destructor.

Additional Inherited Members

Static Public Member Functions inherited from Gecode::HeapAllocated
static void * operator new (size_t s)
 Memory management.
static void operator delete (void *p)
 Free memory allocated from heap.

Detailed Description

template<class Tracer>
class Gecode::Search::Par::Engine< Tracer >

Parallel depth-first search engine

Definition at line 52 of file engine.hh.

Member Enumeration Documentation

◆ SchedulerLogical

template<class Tracer>
enum class Gecode::Search::Par::Engine::SchedulerLogical
strongprotected

Logical worker state used by adjustable parallel admission.

Construction and reset count every worker in n_busy. A pending worker must receive a lease and report idle even if it starts without a tree.

Enumerator
OWNER 

Owns local search or has not yet reported its exhaustion.

PENDING 

Has not yet reported its initial idle state.

IDLE 

Has reported idle and owns no local search.

Definition at line 96 of file engine.hh.

◆ Cmd

Commands from engine to workers.

Enumerator
C_WORK 

Perform work.

C_WAIT 

Run into wait lock.

C_RESET 

Perform reset operation.

C_TERMINATE 

Terminate.

Definition at line 162 of file engine.hh.

Constructor & Destructor Documentation

◆ Engine()

template<class Tracer>
Gecode::Search::Par::Engine< Tracer >::Engine ( const Options & o)
inline

Initialize with options o.

Definition at line 123 of file engine.hpp.

◆ ~Engine()

template<class Tracer>
Gecode::Search::Par::Engine< Tracer >::~Engine ( void )
virtual

Destructor.

Reimplemented from Gecode::Search::Engine.

Definition at line 594 of file engine.hpp.

Member Function Documentation

◆ scheduler_select()

template<class Tracer>
unsigned int Gecode::Search::Par::Engine< Tracer >::scheduler_select ( SchedulerLogical logical,
unsigned int exclude ) const
protected

Select a no-lease worker by logical state (scheduler_mutex held).

Definition at line 143 of file engine.hpp.

◆ scheduler_grow()

template<class Tracer>
bool Gecode::Search::Par::Engine< Tracer >::scheduler_grow ( void )
protected

Grant leases up to the current request (scheduler_mutex held).

Definition at line 157 of file engine.hpp.

◆ opt()

template<class Tracer>
const Options & Gecode::Search::Par::Engine< Tracer >::opt ( void ) const
inline

Provide access to search options.

Definition at line 51 of file engine.hpp.

◆ workers()

template<class Tracer>
unsigned int Gecode::Search::Par::Engine< Tracer >::workers ( void ) const
inline

Return number of workers.

Definition at line 56 of file engine.hpp.

◆ scheduler_enable()

template<class Tracer>
void Gecode::Search::Par::Engine< Tracer >::scheduler_enable ( bool root_owner)

Enable adjustable parallel admission.

Definition at line 183 of file engine.hpp.

◆ scheduler_reset()

template<class Tracer>
void Gecode::Search::Par::Engine< Tracer >::scheduler_reset ( bool root_owner)

Reset adjustable parallel state while all workers are blocked.

Definition at line 207 of file engine.hpp.

◆ scheduler_admit()

template<class Tracer>
bool Gecode::Search::Par::Engine< Tracer >::scheduler_admit ( unsigned int worker)

Admit worker worker for one exploration action.

Definition at line 230 of file engine.hpp.

◆ scheduler_paused()

template<class Tracer>
bool Gecode::Search::Par::Engine< Tracer >::scheduler_paused ( void ) const
inline

Whether the external worker request currently pauses the engine.

Definition at line 278 of file engine.hpp.

◆ scheduler_owner()

template<class Tracer>
void Gecode::Search::Par::Engine< Tracer >::scheduler_owner ( unsigned int worker)

Record that worker worker owns search.

Definition at line 285 of file engine.hpp.

◆ scheduler_idle()

template<class Tracer>
void Gecode::Search::Par::Engine< Tracer >::scheduler_idle ( unsigned int worker)

Record that worker worker is idle.

Definition at line 295 of file engine.hpp.

◆ scheduler_handoff()

template<class Tracer>
void Gecode::Search::Par::Engine< Tracer >::scheduler_handoff ( unsigned int worker,
bool work_remains )

Hand worker worker's lease to a parked logical worker.

Definition at line 305 of file engine.hpp.

◆ cmd()

template<class Tracer>
Engine< Tracer >::Cmd Gecode::Search::Par::Engine< Tracer >::cmd ( void ) const
inline

Return current command.

Definition at line 72 of file engine.hpp.

◆ block()

template<class Tracer>
void Gecode::Search::Par::Engine< Tracer >::block ( void )
inline

Block all workers.

Definition at line 77 of file engine.hpp.

◆ release()

template<class Tracer>
void Gecode::Search::Par::Engine< Tracer >::release ( Cmd c)
inline

Release all workers.

Definition at line 83 of file engine.hpp.

◆ wait()

template<class Tracer>
void Gecode::Search::Par::Engine< Tracer >::wait ( void )
inline

Ensure that worker waits.

Definition at line 92 of file engine.hpp.

◆ ack_terminate()

template<class Tracer>
void Gecode::Search::Par::Engine< Tracer >::ack_terminate ( void )
inline

For worker to acknowledge termination command.

Definition at line 427 of file engine.hpp.

◆ terminated()

template<class Tracer>
void Gecode::Search::Par::Engine< Tracer >::terminated ( void )
inlinevirtual

For worker to register termination.

Implements Gecode::Support::Terminator.

Definition at line 414 of file engine.hpp.

◆ wait_terminate()

template<class Tracer>
void Gecode::Search::Par::Engine< Tracer >::wait_terminate ( void )
inline

For worker to wait until termination is legal.

Definition at line 436 of file engine.hpp.

◆ terminate()

template<class Tracer>
void Gecode::Search::Par::Engine< Tracer >::terminate ( void )
inline

For engine to perform thread termination.

Definition at line 443 of file engine.hpp.

◆ ack_reset_start()

template<class Tracer>
void Gecode::Search::Par::Engine< Tracer >::ack_reset_start ( void )
inline

For worker to acknowledge start of reset cycle.

Definition at line 462 of file engine.hpp.

◆ ack_reset_stop()

template<class Tracer>
void Gecode::Search::Par::Engine< Tracer >::ack_reset_stop ( void )
inline

For worker to acknowledge stop of reset cycle.

Definition at line 471 of file engine.hpp.

◆ wait_reset()

template<class Tracer>
void Gecode::Search::Par::Engine< Tracer >::wait_reset ( void )
inline

For worker to wait for all workers to reset.

Definition at line 480 of file engine.hpp.

◆ signal()

template<class Tracer>
bool Gecode::Search::Par::Engine< Tracer >::signal ( void ) const
inlineprotected

Whether search state changed such that signal is needed.

Definition at line 352 of file engine.hpp.

◆ idle()

template<class Tracer>
void Gecode::Search::Par::Engine< Tracer >::idle ( void )
inline

Report that worker is idle.

Definition at line 358 of file engine.hpp.

◆ busy()

template<class Tracer>
void Gecode::Search::Par::Engine< Tracer >::busy ( void )
inline

Report that worker is busy.

Definition at line 369 of file engine.hpp.

◆ run()

template<class Tracer>
unsigned long long int Gecode::Search::Par::Engine< Tracer >::run ( void ) const
inline

Return the current call of next().

Definition at line 378 of file engine.hpp.

◆ stop()

template<class Tracer>
void Gecode::Search::Par::Engine< Tracer >::stop ( unsigned long long int r)
inline

Report that a worker was stopped during call r of next().

Definition at line 384 of file engine.hpp.

◆ work_remains()

template<class Tracer>
bool Gecode::Search::Par::Engine< Tracer >::work_remains ( void )
inline

Whether logical search work remains.

Definition at line 401 of file engine.hpp.

◆ next()

template<class Tracer>
Space * Gecode::Search::Par::Engine< Tracer >::next ( void )
virtual

Return next solution (nullptr, if none exists or search has been stopped).

Implements Gecode::Search::Engine.

Reimplemented in Gecode::Search::Par::PBS< Collect >, and Gecode::Search::Par::PBS< Gecode::Search::Par::CollectBest >.

Definition at line 523 of file engine.hpp.

◆ stopped()

template<class Tracer>
bool Gecode::Search::Par::Engine< Tracer >::stopped ( void ) const
inlinevirtual

Check whether engine has been stopped.

Implements Gecode::Search::Engine.

Reimplemented in Gecode::Search::Par::PBS< Collect >, and Gecode::Search::Par::PBS< Gecode::Search::Par::CollectBest >.

Definition at line 61 of file engine.hpp.

Member Data Documentation

◆ _opt

template<class Tracer>
Options Gecode::Search::Par::Engine< Tracer >::_opt
protected

Search options.

Definition at line 89 of file engine.hh.

◆ scheduler_enabled

template<class Tracer>
bool Gecode::Search::Par::Engine< Tracer >::scheduler_enabled
protected

Whether adjustable parallel admission is enabled.

Definition at line 113 of file engine.hh.

◆ scheduler_fast_admit

template<class Tracer>
const std::atomic<bool>* Gecode::Search::Par::Engine< Tracer >::scheduler_fast_admit
protected

Unchanged-capacity admission fast path.

Definition at line 115 of file engine.hh.

◆ scheduler_mutex

template<class Tracer>
Support::Mutex Gecode::Search::Par::Engine< Tracer >::scheduler_mutex
protected

Mutex for adjustable parallel admission.

Protects scheduler_worker, scheduler_requested, scheduler_leases, and scheduler_cursor. Initial setup runs before worker threads start; scheduler_enabled and scheduler_fast_admit remain fixed after setup.

Definition at line 123 of file engine.hh.

◆ scheduler_worker

template<class Tracer>
SchedulerWorker* Gecode::Search::Par::Engine< Tracer >::scheduler_worker
protected

Per-worker adjustable parallel admission state.

Definition at line 125 of file engine.hh.

◆ scheduler_requested

template<class Tracer>
unsigned int Gecode::Search::Par::Engine< Tracer >::scheduler_requested
protected

Current requested lease count.

Definition at line 127 of file engine.hh.

◆ scheduler_leases

template<class Tracer>
unsigned int Gecode::Search::Par::Engine< Tracer >::scheduler_leases
protected

Current lease count.

Definition at line 129 of file engine.hh.

◆ scheduler_cursor

template<class Tracer>
unsigned int Gecode::Search::Par::Engine< Tracer >::scheduler_cursor
protected

Round-robin cursor for lease handoff.

Definition at line 131 of file engine.hh.

◆ scheduler_generation

template<class Tracer>
std::atomic<unsigned long long int> Gecode::Search::Par::Engine< Tracer >::scheduler_generation
protected

Last request generation reconciled by the scheduler.

Definition at line 133 of file engine.hh.

◆ _cmd

template<class Tracer>
std::atomic<Cmd> Gecode::Search::Par::Engine< Tracer >::_cmd
protected

The current command.

Definition at line 170 of file engine.hh.

◆ _m_wait

template<class Tracer>
Support::Mutex Gecode::Search::Par::Engine< Tracer >::_m_wait
protected

Mutex for forcing workers to wait.

Definition at line 172 of file engine.hh.

◆ _m_term

template<class Tracer>
Support::Mutex Gecode::Search::Par::Engine< Tracer >::_m_term
protected

Mutex for access to termination information.

Definition at line 188 of file engine.hh.

◆ _n_term_not_ack

template<class Tracer>
volatile unsigned int Gecode::Search::Par::Engine< Tracer >::_n_term_not_ack
protected

Number of workers that have not yet acknowledged termination.

Definition at line 190 of file engine.hh.

◆ _e_term_ack

template<class Tracer>
Support::Event Gecode::Search::Par::Engine< Tracer >::_e_term_ack
protected

Event for termination acknowledgment.

Definition at line 192 of file engine.hh.

◆ _m_wait_terminate

template<class Tracer>
Support::Mutex Gecode::Search::Par::Engine< Tracer >::_m_wait_terminate
protected

Mutex for waiting for termination.

Definition at line 194 of file engine.hh.

◆ _n_not_terminated

template<class Tracer>
volatile unsigned int Gecode::Search::Par::Engine< Tracer >::_n_not_terminated
protected

Number of not yet terminated workers.

Definition at line 196 of file engine.hh.

◆ _e_terminate

template<class Tracer>
Support::Event Gecode::Search::Par::Engine< Tracer >::_e_terminate
protected

Event for termination (all threads have terminated).

Definition at line 198 of file engine.hh.

◆ _m_reset

template<class Tracer>
Support::Mutex Gecode::Search::Par::Engine< Tracer >::_m_reset
protected

Mutex for access to reset information.

Definition at line 214 of file engine.hh.

◆ _n_reset_not_ack

template<class Tracer>
volatile unsigned int Gecode::Search::Par::Engine< Tracer >::_n_reset_not_ack
protected

Number of workers that have not yet acknowledged reset.

Definition at line 216 of file engine.hh.

◆ e_reset_ack_start

template<class Tracer>
Support::Event Gecode::Search::Par::Engine< Tracer >::e_reset_ack_start
protected

Event for reset acknowledgment started.

Definition at line 218 of file engine.hh.

◆ e_reset_ack_stop

template<class Tracer>
Support::Event Gecode::Search::Par::Engine< Tracer >::e_reset_ack_stop
protected

Event for reset acknowledgment stopped.

Definition at line 220 of file engine.hh.

◆ m_wait_reset

template<class Tracer>
Support::Mutex Gecode::Search::Par::Engine< Tracer >::m_wait_reset
protected

Mutex for waiting for reset.

Definition at line 222 of file engine.hh.

◆ m_search

template<class Tracer>
Support::Mutex Gecode::Search::Par::Engine< Tracer >::m_search
protected

Mutex for search.

Definition at line 236 of file engine.hh.

◆ e_search

template<class Tracer>
Support::Event Gecode::Search::Par::Engine< Tracer >::e_search
protected

Event for search (solution found, no more solutions, search stopped).

Definition at line 238 of file engine.hh.

◆ solutions

template<class Tracer>
Support::DynamicQueue<Space*,Heap> Gecode::Search::Par::Engine< Tracer >::solutions
protected

Queue of solutions.

Definition at line 240 of file engine.hh.

◆ n_busy

template<class Tracer>
volatile unsigned int Gecode::Search::Par::Engine< Tracer >::n_busy
protected

Number of busy workers.

Definition at line 242 of file engine.hh.

◆ has_stopped

template<class Tracer>
std::atomic<bool> Gecode::Search::Par::Engine< Tracer >::has_stopped
protected

Whether a worker had been stopped.

Definition at line 244 of file engine.hh.

◆ n_runs

template<class Tracer>
std::atomic<unsigned long long int> Gecode::Search::Par::Engine< Tracer >::n_runs
protected

Number of calls to next() that have started search.

Definition at line 246 of file engine.hh.


The documentation for this class was generated from the following files: