43 template<
class Tracer>
48 template<
class Tracer>
54 template<
class Tracer>
61 path.reset((s ==
nullptr) ? 0 : ngdl);
78 template<
class Tracer>
81 return (
cur !=
nullptr) || !
path.empty();
88 template<
class Tracer>
93 template<
class Tracer>
105 for (
unsigned int i=1U; i<
workers(); i++)
111 for (
unsigned int i=0U; i<
workers(); i++)
119 template<
class Tracer>
130 template<
class Tracer>
134 if (
best !=
nullptr) {
148 for (
unsigned int i=0U; i<
workers(); i++)
161 template<
class Tracer>
165 for (
unsigned int i=0U; i<
engine().workers(); i++) {
166 unsigned long int r_d = 0ul;
193 template<
class Tracer>
197 for (
unsigned int i=0U; i<
workers(); i++)
202 template<
class Tracer>
206 if (
best !=
nullptr) {
216 for (
unsigned int i=0U; i<
workers(); i++)
224 template<
class Tracer>
257 engine().wait_terminate();
262 engine().ack_reset_start();
266 engine().ack_reset_stop();
271 const unsigned long long int run =
engine().run();
288 }
else if (
cur !=
nullptr) {
298 if (
path.entries() > 0) {
302 }
else if (*
tracer.ei()) {
307 unsigned int nid =
tracer.nid();
308 switch (
cur->status(*
this)) {
329 (void)
cur->choice();
362 }
else if (!
path.empty()) {
389 template<
class Tracer>
402 for (
unsigned int i=1U; i<
workers(); i++)
419 template<
class Tracer>
442 template<
class Tracer>
447 template<
class Tracer>
Choice for performing commit
No-goods recorded from restarts.
void init(unsigned int wid, unsigned int nid, unsigned int a)
Initialize.
@ DFS
Engine is a DFS engine.
SearchTracer * tracer
Tracer object for tracing search.
Parallel branch-and-bound search worker
bool find(void)
Try to find some work.
Space * best
Best solution found so far.
int mark
Number of entries not yet constrained to be better.
Worker(Space *s, BAB &e, unsigned int index)
Initialize for space s with engine e.
void better(Space *b)
Accept better solution b.
BAB & engine(void) const
Provide access to engine.
bool owns_work(void) const
Whether this worker currently owns local search.
virtual ~Worker(void)
Destructor.
virtual void run(void)
Start execution of worker.
unsigned int index
Fixed worker index.
void reset(Space *s, unsigned int ngdl)
Reset engine to restart at space s.
Parallel branch-and-bound engine
Worker ** _worker
Array of worker references.
void solution(Space *s)
Report solution s.
Worker * worker(unsigned int i) const
Provide access to worker i.
virtual void constrain(const Space &b)
Constrain future solutions to be better than b.
virtual void reset(Space *s)
Reset engine to restart at space s.
virtual ~BAB(void)
Destructor.
Space * best
Best solution so far.
BAB(Space *s, const Options &o)
Initialize for space s with options o.
virtual Statistics statistics(void) const
Return statistics.
virtual NoGoods & nogoods(void)
Constrain Return no-goods.
Parallel depth-first search worker
Support::Mutex m
Mutex for access to worker.
Engine & _engine
Reference to engine.
NoGoods & nogoods(void)
Return no-goods.
Statistics statistics(void)
Return statistics.
Space * cur
Current space being explored.
Tracer tracer
Search tracer.
Space * steal(unsigned long int &d, Tracer &myt, Tracer &ot)
Hand over some work (nullptr if no work available).
unsigned int d
Distance until next clone.
bool idle
Whether the worker is idle.
Path< Tracer > path
Current path ins search tree.
const Options & opt(void) const
Provide access to search options.
Support::Event e_reset_ack_stop
Event for reset acknowledgment stopped.
Support::Event e_search
Event for search (solution found, no more solutions, search stopped).
Support::DynamicQueue< Space *, Heap > solutions
Queue of solutions.
void block(void)
Block all workers.
Support::Mutex m_wait_reset
Mutex for waiting for reset.
void scheduler_enable(bool root_owner)
Enable adjustable parallel admission.
Support::Mutex m_search
Mutex for search.
Support::Event e_reset_ack_start
Event for reset acknowledgment started.
Cmd cmd(void) const
Return current command.
Engine(const Options &o)
Initialize with options o.
bool scheduler_admit(unsigned int worker)
Admit worker worker for one exploration action.
void release(Cmd c)
Release all workers.
bool signal(void) const
Whether search state changed such that signal is needed.
void stop(unsigned long long int r)
Report that a worker was stopped during call r of next().
void scheduler_reset(bool root_owner)
Reset adjustable parallel state while all workers are blocked.
bool scheduler_paused(void) const
Whether the external worker request currently pauses the engine.
void terminate(void)
For engine to perform thread termination.
volatile unsigned int n_busy
Number of busy workers.
unsigned int workers(void) const
Return number of workers.
@ C_RESET
Perform reset operation.
@ C_WAIT
Run into wait lock.
bool work_remains(void)
Whether logical search work remains.
Search tree edge for recomputation
unsigned int truealt(void) const
Return true number for alternatives (excluding lao optimization).
unsigned int nid(void) const
Return node identifier.
const Choice * choice(void) const
Return choice.
Statistics(void)
Initialize.
unsigned long long int fail
Number of failed nodes in search tree.
unsigned long long int node
Number of nodes expanded.
void start(void)
Reset stop information.
static void engine(SearchTracer *tracer, SearchTracer::EngineType t, unsigned int n)
Register engine.
void reset(void)
Reset information.
static void run(Runnable *r)
Construct a new thread and run r.
static void sleep(unsigned int ms)
Put current thread to sleep for ms milliseconds.
Heap heap
The single global heap.
virtual void constrain(const Space &best)
Constrain function for best solution search.
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
const unsigned int initial_delay
Initial delay in milliseconds for all but first worker thread.
Gecode toplevel namespace
#define GECODE_NEVER
Assert that this command is never executed.