Generated on for Gecode by doxygen 1.17.0
Gecode::Search::Par::Frontier Class Referenceabstract

Parallel engine for heuristic search. More...

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

Classes

class  Task
 Node leased by a worker, or partially expanded node. More...
class  Runner
 Thread running a worker. More...

Protected Attributes

Options opt
 Search options.
HeuristicGuidance guidance
 Guidance.
Incumbent best
 Best solution so far.
std::unique_ptr< Space > solution
 Solution to be returned by next().
unsigned long long int order
 Number of created entries.
Support::DynamicQueue< Task *, Heap > pending
 Partially expanded nodes.
unsigned int n_pending
 Number of partially expanded nodes.
Runner ** runners
 The threads (allocated on first next()).
Support::Mutex mutex
 Mutex protecting all data.
Support::Event changed
 Signalled when search is idle.
Search::Statistics stat
 Statistics.
unsigned int active
 Number of workers holding a task.
bool running
 Whether search is running, being shut down, stopped, or limited.
bool shutdown
bool _stopped
bool _limited
std::exception_ptr error
 First exception thrown by a worker.
Protected Attributes inherited from Gecode::Search::Engine
WorkerControl worker_control
 Control retained for the lifetime of a leaf engine.

Open nodes (called with the mutex held)

unsigned int batch
 Number of children a worker collects before submitting.
bool keyed
 Whether to compute dominance keys.
static const unsigned int max_batch = 8
 Maximal number of children a worker collects before submitting.
virtual bool open (void) const =0
 Whether there are open nodes.
virtual Entry select (void)=0
 Remove and return the next open node.
virtual void submit (const Entry &e, bool leased)=0
 Add child e, or delete it; leased tells whether its parent is still leased.
virtual bool advance (void)=0
 Called when all work is done, return whether there is new work.
virtual void clear (void)=0
 Delete all open nodes.
virtual void started (const Space &r)
 Called with the root r when search starts.
 Frontier (const Options &o)
 Initialize with options o.
void initialize (Space *s, bool clone)
 Start search from root s.
void push (Task *t)
 Add pending task t.
void terminate (void)
 Stop all workers (must be called by subclass destructors).
void publish (Space *s, std::int64_t b)
 Make s with bound b the incumbent, if it improves.
void launch (void)
 Start the threads.
void wake (void)
 Wake up all workers.
bool enabled (unsigned int id)
 Whether worker id is currently enabled.
void work (unsigned int id)
 Run worker id.
 ~Frontier (void) override
 Destructor.
Space * next (void) override
 Return next better solution (nullptr if none or stopped).
Search::Statistics statistics (void) const override
 Return statistics.
bool stopped (void) const override
 Whether search has been stopped.
bool limited (void) const override
 Whether search stopped at the width or frontier limit.
void constrain (const Space &s) override
 Constrain future solutions to be better than s.
void reset (Space *s) override
 Reset engine to restart at space s.

Additional Inherited Members

Public Member Functions inherited from Gecode::Search::Engine
virtual NoGoods & nogoods (void)
 Return no-goods (the no-goods are empty).
virtual ~Engine (void)
 Destructor.
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.
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.

Detailed Description

Parallel engine for heuristic search.

Workers lease a node, expand it outside the lock, and submit its children. Subclasses decide how open nodes are stored and selected. All members are protected by the mutex.

Definition at line 53 of file frontier.hh.

Constructor & Destructor Documentation

◆ Frontier()

Gecode::Search::Par::Frontier::Frontier ( const Options & o)
protected

Initialize with options o.

Definition at line 58 of file frontier.cpp.

◆ ~Frontier()

Gecode::Search::Par::Frontier::~Frontier ( void )
override

Destructor.

Definition at line 149 of file frontier.cpp.

Member Function Documentation

◆ open()

virtual bool Gecode::Search::Par::Frontier::open ( void ) const
protectedpure virtual

Whether there are open nodes.

Implemented in Gecode::Search::Par::AStar, and Gecode::Search::Par::CABS.

◆ select()

virtual Entry Gecode::Search::Par::Frontier::select ( void )
protectedpure virtual

Remove and return the next open node.

Implemented in Gecode::Search::Par::AStar, and Gecode::Search::Par::CABS.

◆ submit()

virtual void Gecode::Search::Par::Frontier::submit ( const Entry & e,
bool leased )
protectedpure virtual

Add child e, or delete it; leased tells whether its parent is still leased.

Implemented in Gecode::Search::Par::AStar, and Gecode::Search::Par::CABS.

◆ advance()

virtual bool Gecode::Search::Par::Frontier::advance ( void )
protectedpure virtual

Called when all work is done, return whether there is new work.

Implemented in Gecode::Search::Par::AStar, and Gecode::Search::Par::CABS.

◆ clear()

virtual void Gecode::Search::Par::Frontier::clear ( void )
protectedpure virtual

Delete all open nodes.

Implemented in Gecode::Search::Par::AStar, and Gecode::Search::Par::CABS.

◆ started()

void Gecode::Search::Par::Frontier::started ( const Space & r)
protectedvirtual

Called with the root r when search starts.

Reimplemented in Gecode::Search::Par::CABS.

Definition at line 66 of file frontier.cpp.

◆ initialize()

void Gecode::Search::Par::Frontier::initialize ( Space * s,
bool clone )
protected

Start search from root s.

Definition at line 74 of file frontier.cpp.

◆ push()

void Gecode::Search::Par::Frontier::push ( Task * t)
protected

Add pending task t.

Definition at line 69 of file frontier.cpp.

◆ terminate()

void Gecode::Search::Par::Frontier::terminate ( void )
protected

Stop all workers (must be called by subclass destructors).

Definition at line 135 of file frontier.cpp.

◆ publish()

void Gecode::Search::Par::Frontier::publish ( Space * s,
std::int64_t b )
protected

Make s with bound b the incumbent, if it improves.

Definition at line 157 of file frontier.cpp.

◆ launch()

void Gecode::Search::Par::Frontier::launch ( void )
protected

Start the threads.

Definition at line 92 of file frontier.cpp.

◆ wake()

void Gecode::Search::Par::Frontier::wake ( void )
protected

Wake up all workers.

Definition at line 119 of file frontier.cpp.

◆ enabled()

bool Gecode::Search::Par::Frontier::enabled ( unsigned int id)
protected

Whether worker id is currently enabled.

Definition at line 129 of file frontier.cpp.

◆ work()

void Gecode::Search::Par::Frontier::work ( unsigned int id)
protected

Run worker id.

Definition at line 169 of file frontier.cpp.

◆ next()

Space * Gecode::Search::Par::Frontier::next ( void )
overridevirtual

Return next better solution (nullptr if none or stopped).

Implements Gecode::Search::Engine.

Definition at line 331 of file frontier.cpp.

◆ statistics()

Search::Statistics Gecode::Search::Par::Frontier::statistics ( void ) const
overridevirtual

Return statistics.

Implements Gecode::Search::Engine.

Definition at line 357 of file frontier.cpp.

◆ stopped()

bool Gecode::Search::Par::Frontier::stopped ( void ) const
overridevirtual

Whether search has been stopped.

Implements Gecode::Search::Engine.

Definition at line 363 of file frontier.cpp.

◆ limited()

bool Gecode::Search::Par::Frontier::limited ( void ) const
overridevirtual

Whether search stopped at the width or frontier limit.

Reimplemented from Gecode::Search::Engine.

Definition at line 369 of file frontier.cpp.

◆ constrain()

void Gecode::Search::Par::Frontier::constrain ( const Space & s)
overridevirtual

Constrain future solutions to be better than s.

Reimplemented from Gecode::Search::Engine.

Definition at line 375 of file frontier.cpp.

◆ reset()

void Gecode::Search::Par::Frontier::reset ( Space * s)
overridevirtual

Reset engine to restart at space s.

Reimplemented from Gecode::Search::Engine.

Definition at line 385 of file frontier.cpp.

Member Data Documentation

◆ opt

Options Gecode::Search::Par::Frontier::opt
protected

Search options.

Definition at line 88 of file frontier.hh.

◆ guidance

HeuristicGuidance Gecode::Search::Par::Frontier::guidance
protected

Guidance.

Definition at line 90 of file frontier.hh.

◆ best

Incumbent Gecode::Search::Par::Frontier::best
protected

Best solution so far.

Definition at line 92 of file frontier.hh.

◆ solution

std::unique_ptr<Space> Gecode::Search::Par::Frontier::solution
protected

Solution to be returned by next().

Definition at line 94 of file frontier.hh.

◆ order

unsigned long long int Gecode::Search::Par::Frontier::order
protected

Number of created entries.

Definition at line 96 of file frontier.hh.

◆ pending

Support::DynamicQueue<Task*,Heap> Gecode::Search::Par::Frontier::pending
protected

Partially expanded nodes.

Definition at line 98 of file frontier.hh.

◆ n_pending

unsigned int Gecode::Search::Par::Frontier::n_pending
protected

Number of partially expanded nodes.

Definition at line 100 of file frontier.hh.

◆ runners

Runner** Gecode::Search::Par::Frontier::runners
protected

The threads (allocated on first next()).

Definition at line 102 of file frontier.hh.

◆ mutex

Support::Mutex Gecode::Search::Par::Frontier::mutex
mutableprotected

Mutex protecting all data.

Definition at line 104 of file frontier.hh.

◆ changed

Support::Event Gecode::Search::Par::Frontier::changed
protected

Signalled when search is idle.

Definition at line 106 of file frontier.hh.

◆ stat

Search::Statistics Gecode::Search::Par::Frontier::stat
protected

Statistics.

Definition at line 108 of file frontier.hh.

◆ active

unsigned int Gecode::Search::Par::Frontier::active
protected

Number of workers holding a task.

Definition at line 110 of file frontier.hh.

◆ running

bool Gecode::Search::Par::Frontier::running
protected

Whether search is running, being shut down, stopped, or limited.

Definition at line 112 of file frontier.hh.

◆ shutdown

bool Gecode::Search::Par::Frontier::shutdown
protected

Definition at line 112 of file frontier.hh.

◆ _stopped

bool Gecode::Search::Par::Frontier::_stopped
protected

Definition at line 112 of file frontier.hh.

◆ _limited

bool Gecode::Search::Par::Frontier::_limited
protected

Definition at line 112 of file frontier.hh.

◆ error

std::exception_ptr Gecode::Search::Par::Frontier::error
protected

First exception thrown by a worker.

Definition at line 114 of file frontier.hh.

◆ max_batch

const unsigned int Gecode::Search::Par::Frontier::max_batch = 8
staticprotected

Maximal number of children a worker collects before submitting.

Definition at line 132 of file frontier.hh.

◆ batch

unsigned int Gecode::Search::Par::Frontier::batch
protected

Number of children a worker collects before submitting.

Definition at line 134 of file frontier.hh.

◆ keyed

bool Gecode::Search::Par::Frontier::keyed
protected

Whether to compute dominance keys.

Definition at line 136 of file frontier.hh.


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