37#if defined(GECODE_HAS_EXPERIMENTAL) && defined(GECODE_HAS_THREADS)
50 return const_cast<Runner*
>(
this);
86 std::unique_ptr<Task> t(
new Task);
87 t->expansion.select(std::unique_ptr<Space>(clone ? s->
clone() : s));
95 unsigned int n =
static_cast<unsigned int>(
opt.threads);
97 for (
unsigned int i=0; i<n; i++)
106 for (
unsigned int i=0; i<
started; i++)
108 for (
unsigned int i=0; i<n; i++)
122 }
else if (
runners !=
nullptr) {
123 for (
unsigned int i=0; i<static_cast<unsigned int>(
opt.threads); i++)
140 unsigned int n =
static_cast<unsigned int>(
opt.threads);
141 for (
unsigned int i=0; i<n; i++)
143 for (
unsigned int i=0; i<n; i++)
158 if (!
best.improves(b)) {
162 std::unique_ptr<Space> incumbent(s);
164 best.update(incumbent.release(),b);
171 Task* task =
nullptr;
172 std::unique_ptr<Space> incumbent;
173 unsigned long long int revision = 0;
174 std::optional<std::int64_t> cutoff;
178 unsigned int n_children = 0, submitted = 0;
179 std::unique_ptr<Space> solved;
180 std::int64_t solved_bound = 0;
188 if (task !=
nullptr) {
191 for (submitted=0; submitted<n_children; submitted++)
193 n_children = submitted = 0;
195 publish(solved.release(),solved_bound);
200 if (task !=
nullptr) {
225 std::unique_ptr<Space> s(e.
space);
241 if (task !=
nullptr) {
242 if (revision !=
best.revision)
245 incumbent.reset(
best.space->clone());
246 revision =
best.revision;
260 if (task ==
nullptr) {
273 for (
unsigned int i=0; (i<32) && task->
expansion; i++) {
276 incumbent.get(),revision);
281 (void) step.space->choice();
282 std::int64_t b =
guidance.bound(*step.space);
285 solved = std::move(step.space);
294 std::size_t k =
keyed ?
guidance.dominance_key(*step.space) : 0;
295 children[n_children++] =
296 {step.space.release(),b,r,k,task->
depth+1,0,revision};
297 if (n_children ==
batch)
308 for (
unsigned int i=submitted; i<n_children; i++)
309 delete children[i].space;
310 n_children = 0; submitted = 0;
312 if (task !=
nullptr) {
322 error = std::current_exception();
336 std::rethrow_exception(
error);
351 std::rethrow_exception(
error);
378 if (
best.improves(b)) {
386 std::unique_ptr<Space> replacement(s);
400 (void) replacement.release();
Engine(void)
Construct a meta engine without worker control.
WorkerControl worker_control
Control retained for the lifetime of a leaf engine.
Open node of a heuristic search engine.
Space * space
The stable space (owned by the container holding the entry).
unsigned long long int revision
Incumbent revision the space has been constrained with.
unsigned long int depth
Depth of the node.
std::int64_t bound
Bound and rank of the space.
Support::Terminator * terminator(void) const override
Return terminator.
void terminated(void) override
Signal termination.
void run(void) override
Run worker.
Runner(Frontier &e, unsigned int i)
Initialize.
Node leased by a worker, or partially expanded node.
unsigned long int depth
Depth of the node.
unsigned long long int revision
Incumbent revision the node is constrained with.
bool counted
Whether the node has been counted.
Seq::ChoiceExpansion expansion
The node with its remaining alternatives.
bool stopped(void) const override
Whether search has been stopped.
~Frontier(void) override
Destructor.
std::exception_ptr error
First exception thrown by a worker.
void reset(Space *s) override
Reset engine to restart at space s.
void wake(void)
Wake up all workers.
virtual Entry select(void)=0
Remove and return the next open node.
void work(unsigned int id)
Run worker id.
Support::Event changed
Signalled when search is idle.
unsigned long long int order
Number of created entries.
Space * next(void) override
Return next better solution (nullptr if none or stopped).
void constrain(const Space &s) override
Constrain future solutions to be better than s.
void publish(Space *s, std::int64_t b)
Make s with bound b the incumbent, if it improves.
Search::Statistics stat
Statistics.
Options opt
Search options.
virtual void started(const Space &r)
Called with the root r when search starts.
std::unique_ptr< Space > solution
Solution to be returned by next().
Support::Mutex mutex
Mutex protecting all data.
void terminate(void)
Stop all workers (must be called by subclass destructors).
bool enabled(unsigned int id)
Whether worker id is currently enabled.
bool keyed
Whether to compute dominance keys.
Runner ** runners
The threads (allocated on first next()).
HeuristicGuidance guidance
Guidance.
virtual bool open(void) const =0
Whether there are open nodes.
void initialize(Space *s, bool clone)
Start search from root s.
Support::DynamicQueue< Task *, Heap > pending
Partially expanded nodes.
virtual void clear(void)=0
Delete all open nodes.
unsigned int batch
Number of children a worker collects before submitting.
void push(Task *t)
Add pending task t.
void launch(void)
Start the threads.
virtual bool advance(void)=0
Called when all work is done, return whether there is new work.
Search::Statistics statistics(void) const override
Return statistics.
virtual void submit(const Entry &e, bool leased)=0
Add child e, or delete it; leased tells whether its parent is still leased.
bool limited(void) const override
Whether search stopped at the width or frontier limit.
bool running
Whether search is running, being shut down, stopped, or limited.
unsigned int n_pending
Number of partially expanded nodes.
unsigned int active
Number of workers holding a task.
Incumbent best
Best solution so far.
static const unsigned int max_batch
Maximal number of children a worker collects before submitting.
Frontier(const Options &o)
Initialize with options o.
ExpansionStep next(Worker &worker, unsigned long int depth, unsigned long long int node_revision, const Space *incumbent, unsigned long long int revision)
Commit and propagate the next alternative.
void select(std::unique_ptr< Space > s)
Take stable node s.
Result of expanding one alternative.
@ EXHAUSTED
Nothing, all alternatives have been expanded.
unsigned long long int fail
Number of failed nodes in search tree.
unsigned long long int node
Number of nodes expanded.
static void signal_all(WorkerControl &control)
Signal every worker event.
static void wait(WorkerControl &control, unsigned int worker)
Wait for the event belonging to worker worker.
static unsigned int requested(const WorkerControl &control)
Return the current request.
void reset(unsigned long int d=0)
Reset statistics with root depth d.
void stack_depth(unsigned long int d)
Record stack depth d.
A lock as a scoped frontend for a mutex.
Runnable(bool d=true)
Initialize, d defines whether object is deleted when terminated.
An interface for objects that can be called after a thread has terminated (after running the thread's...
static void run(Runnable *r)
Construct a new thread and run r.
Heap heap
The single global heap.
Space * clone(void) const
Clone space.
SpaceStatus status(StatusStatistics &stat)
Query space status.
@ SS_BRANCH
Space must be branched (at least one brancher left)
@ SS_SOLVED
Space is solved (no brancher left)
@ SS_FAILED
Space is failed
bool better(HeuristicGuidance::Sense s, std::int64_t a, std::int64_t b)
Whether bound a is better than bound b for objective direction s.
Support algorithms and datastructures
Gecode toplevel namespace