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()
|
protected |
Initialize with options o.
◆ ~Frontier()
|
override |
Destructor.
Member Function Documentation
◆ open()
|
protectedpure virtual |
Whether there are open nodes.
◆ select()
|
protectedpure virtual |
Remove and return the next open node.
◆ submit()
|
protectedpure virtual |
Add child e, or delete it; leased tells whether its parent is still leased.
◆ advance()
|
protectedpure virtual |
Called when all work is done, return whether there is new work.
◆ clear()
|
protectedpure virtual |
Delete all open nodes.
◆ started()
|
protectedvirtual |
Called with the root r when search starts.
◆ initialize()
|
protected |
Start search from root s.
◆ push()
|
protected |
Add pending task t.
◆ terminate()
|
protected |
Stop all workers (must be called by subclass destructors).
◆ publish()
|
protected |
Make s with bound b the incumbent, if it improves.
◆ launch()
|
protected |
Start the threads.
◆ wake()
|
protected |
Wake up all workers.
◆ enabled()
|
protected |
Whether worker id is currently enabled.
◆ work()
|
protected |
Run worker id.
◆ next()
|
overridevirtual |
Return next better solution (nullptr if none or stopped).
Implements Gecode::Search::Engine.
◆ statistics()
|
overridevirtual |
Return statistics.
Implements Gecode::Search::Engine.
◆ stopped()
|
overridevirtual |
Whether search has been stopped.
Implements Gecode::Search::Engine.
◆ limited()
|
overridevirtual |
Whether search stopped at the width or frontier limit.
Reimplemented from Gecode::Search::Engine.
◆ constrain()
|
overridevirtual |
Constrain future solutions to be better than s.
Reimplemented from Gecode::Search::Engine.
◆ reset()
|
overridevirtual |
Reset engine to restart at space s.
Reimplemented from Gecode::Search::Engine.
Member Data Documentation
◆ opt
|
protected |
Search options.
Definition at line 88 of file frontier.hh.
◆ guidance
|
protected |
Guidance.
Definition at line 90 of file frontier.hh.
◆ best
|
protected |
Best solution so far.
Definition at line 92 of file frontier.hh.
◆ solution
|
protected |
Solution to be returned by next().
Definition at line 94 of file frontier.hh.
◆ order
|
protected |
Number of created entries.
Definition at line 96 of file frontier.hh.
◆ pending
|
protected |
Partially expanded nodes.
Definition at line 98 of file frontier.hh.
◆ n_pending
|
protected |
Number of partially expanded nodes.
Definition at line 100 of file frontier.hh.
◆ runners
|
protected |
The threads (allocated on first next()).
Definition at line 102 of file frontier.hh.
◆ mutex
|
mutableprotected |
Mutex protecting all data.
Definition at line 104 of file frontier.hh.
◆ changed
|
protected |
Signalled when search is idle.
Definition at line 106 of file frontier.hh.
◆ stat
|
protected |
Definition at line 108 of file frontier.hh.
◆ active
|
protected |
Number of workers holding a task.
Definition at line 110 of file frontier.hh.
◆ running
|
protected |
Whether search is running, being shut down, stopped, or limited.
Definition at line 112 of file frontier.hh.
◆ shutdown
|
protected |
Definition at line 112 of file frontier.hh.
◆ _stopped
|
protected |
Definition at line 112 of file frontier.hh.
◆ _limited
|
protected |
Definition at line 112 of file frontier.hh.
◆ error
|
protected |
First exception thrown by a worker.
Definition at line 114 of file frontier.hh.
◆ max_batch
|
staticprotected |
Maximal number of children a worker collects before submitting.
Definition at line 132 of file frontier.hh.
◆ batch
|
protected |
Number of children a worker collects before submitting.
Definition at line 134 of file frontier.hh.
◆ 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 file:
- gecode/search/par/frontier.hh
