Go to the documentation of this file.
34 namespace Gecode {
namespace Search {
namespace Par {
39 template<
class Tracer>
44 template<
class Tracer>
50 template<
class Tracer>
57 path.reset((s == NULL) ? 0 : ngdl);
74 template<
class Tracer>
79 template<
class Tracer>
104 template<
class Tracer>
115 template<
class Tracer>
146 template<
class Tracer>
150 for (
unsigned int i=0U;
i<engine().workers();
i++) {
151 unsigned long int r_d = 0ul;
163 cur->constrain(*
best);
176 template<
class Tracer>
185 template<
class Tracer>
207 template<
class Tracer>
227 if (
this != engine().
worker(0))
231 switch (engine().
cmd()) {
238 engine().ack_terminate();
240 engine().wait_terminate();
245 engine().ack_reset_start();
247 engine().wait_reset();
249 engine().ack_reset_stop();
259 }
else if (cur != NULL) {
269 if (
path.entries() > 0) {
273 }
else if (*tracer.ei()) {
278 unsigned int nid = tracer.nid();
279 switch (cur->status(*
this)) {
283 tracer.wid(), nid, *cur);
296 tracer.wid(), nid, *cur);
300 (void) cur->choice();
306 engine().solution(s);
312 if ((
d == 0) || (
d >= engine().
opt().
c_d)) {
322 tracer.wid(), nid, *cur, ch);
333 }
else if (!
path.empty()) {
358 template<
class Tracer>
387 template<
class Tracer>
410 template<
class Tracer>
415 template<
class Tracer>
@ C_WAIT
Run into wait lock.
void solution(Space *s)
Report solution s.
void release(Cmd c)
Release all workers.
unsigned int nid(void) const
Return node identifier.
void terminate(void)
For engine to peform thread termination.
Worker * worker(unsigned int i) const
Provide access to worker i.
Space * best
Best solution found so far.
@ SS_SOLVED
Space is solved (no brancher left)
Parallel depth-first search worker
NoGoods & nogoods(void)
Return no-goods.
void find(void)
Try to find some work.
virtual void constrain(const Space &best)
Constrain function for best solution search.
Support::Mutex m_search
Mutex for search.
void acquire(void)
Acquire the mutex and possibly block.
void better(Space *b)
Accept better solution b.
Statistics statistics(void)
Return statistics.
void * mark(void *p)
Return marked pointer for unmarked pointer p.
Space * best
Best solution so far.
@ SS_BRANCH
Space must be branched (at least one brancher left)
void * ralloc(size_t s)
Allocate s bytes from heap.
Search tree edge for recomputation
virtual NoGoods & nogoods(void)
Constrain Return no-goods.
virtual ~Worker(void)
Destructor.
void invalidate(void)
Invalidate edge information (for stealing)
Support::Event e_reset_ack_start
Event for reset acknowledgment started.
virtual void reset(Space *s)
Reset engine to restart at space s.
unsigned int truealt(void) const
Return true number for alternatives (excluding lao optimization)
virtual void constrain(const Space &b)
Constrain future solutions to be better than b.
void stop(void)
Report that worker has been stopped.
Support::Event e_search
Event for search (solution found, no more solutions, search stopped)
Gecode toplevel namespace
const Choice * choice(void) const
Return choice.
virtual ~BAB(void)
Destructor.
Space * clone(CloneStatistics &stat=unused_clone) const
Clone space.
No-goods recorded from restarts.
Support::DynamicQueue< Space *, Heap > solutions
Queue of solutions.
@ C_RESET
Perform reset operation.
Engine & _engine
Reference to engine.
void reset(Space *s, unsigned int ngdl)
Reset engine to restart at space s.
Parallel depth-first search engine
Parallel branch-and-bound search worker
void idle(void)
Report that worker is idle.
const unsigned int nogoods_limit
Depth limit for no-good generation during search.
Support::Event e_reset_ack_stop
Event for reset acknowledgment stopped.
static void run(Runnable *r)
Construct a new thread and run r.
Worker ** _worker
Array of worker references.
bool signal(void) const
Whether search state changed such that signal is needed.
const unsigned int initial_delay
Initial delay in milliseconds for all but first worker thread.
struct Gecode::@602::NNF::@65::@66 b
For binary nodes (and, or, eqv)
Space * cur
Current space being explored.
Parallel branch-and-bound engine
@ BRANCH
Node representing a branch.
#define GECODE_NEVER
Assert that this command is never executed.
SpaceStatus status(StatusStatistics &stat=unused_status)
Query space status.
Support::Mutex m_wait_reset
Mutex for waiting for reset.
int mark
Number of entries not yet constrained to be better.
Heap heap
The single global heap.
virtual void run(void)
Start execution of worker.
BAB & engine(void) const
Provide access to engine.
const Options & opt(void) const
Provide access to search options.
void signal(void)
Signal the event.
void init(unsigned int wid, unsigned int nid, unsigned int a)
Initialize.
volatile unsigned int n_busy
Number of busy workers.
static void sleep(unsigned int ms)
Put current thread to sleep for ms milliseconds.
void path(Home home, int offset, const IntVarArgs &x, IntVar s, IntVar e, IntPropLevel ipl)
Post propagator such that x forms a Hamiltonian path.
void block(void)
Block all workers.
const unsigned int c_d
Create a clone after every c_d commits (commit distance)
Space * steal(unsigned long int &d, Tracer &myt, Tracer &ot)
Hand over some work (NULL if no work available)
const unsigned int a_d
Create a clone during recomputation if distance is greater than a_d (adaptive distance)
virtual Statistics statistics(void) const
Return statistics.
Gecode::FloatVal c(-8, 8)
BAB(Space *s, const Options &o)
Initialize for space s with options o.
void release(void)
Release the mutex.
Choice for performing commit
Path< Tracer > path
Current path ins search tree.
void rfree(void *p)
Free memory block starting at p.
void wait(void)
Wait until the event becomes signalled.
unsigned int workers(void) const
Return number of workers.
Cmd cmd(void) const
Return current command.
@ FAILED
Node representing failure.
Gecode::IntArgs i({1, 2, 3, 4})
@ SS_FAILED
Space is failed
Tracer tracer
Search tracer.
static void engine(SearchTracer *tracer, SearchTracer::EngineType t, unsigned int n)
Register engine.
Support::Mutex m
Mutex for access to worker.
@ SOLVED
Node representing a solution.
SearchTracer * tracer
Tracer object for tracing search.