38 namespace Gecode {
namespace Search {
namespace Par {
43 template<
class Tracer>
48 template<
class Tracer>
54 template<
class Tracer>
61 path.reset((s == NULL) ? 0 : ngdl);
78 template<
class Tracer>
83 template<
class Tracer>
108 template<
class Tracer>
116 cur->constrain(*
best);
119 template<
class Tracer>
150 template<
class Tracer>
154 for (
unsigned int i=0;
i<engine().workers();
i++) {
155 unsigned long int r_d = 0ul;
167 cur->constrain(*
best);
180 template<
class Tracer>
189 template<
class Tracer>
211 template<
class Tracer>
231 if (
this != engine().
worker(0))
235 switch (engine().
cmd()) {
242 engine().ack_terminate();
244 engine().wait_terminate();
249 engine().ack_reset_start();
251 engine().wait_reset();
253 engine().ack_reset_stop();
263 }
else if (cur != NULL) {
273 if (
path.entries() > 0) {
277 }
else if (*tracer.ei()) {
282 unsigned int nid = tracer.nid();
283 switch (cur->status(*
this)) {
287 tracer.wid(), nid, *cur);
300 tracer.wid(), nid, *cur);
310 engine().solution(s);
316 if ((
d == 0) || (
d >= engine().
opt().
c_d)) {
323 const Choice* ch =
path.push(*
this,cur,c,nid);
326 tracer.wid(), nid, *cur, ch);
337 }
else if (!
path.empty()) {
362 template<
class Tracer>
391 template<
class Tracer>
414 template<
class Tracer>
419 template<
class Tracer>
Statistics statistics(void)
Return statistics.
Support::Event e_reset_ack_stop
Event for reset acknowledgment stopped.
void stop(void)
Report that worker has been stopped.
Worker ** _worker
Array of worker references.
Path< Tracer > path
Current path ins search tree.
Space must be branched (at least one brancher left)
virtual NoGoods & nogoods(void)
Constrain Return no-goods.
void reset(Space *s, unsigned int ngdl)
Reset engine to restart at space s.
unsigned int workers(void) const
Return number of workers.
Support::Event e_reset_ack_start
Event for reset acknowledgment started.
int mark
Number of entries not yet constrained to be better.
void terminate(void)
For engine to peform thread termination.
Node representing a branch.
void rfree(void *p)
Free memory block starting at p.
virtual void run(void)
Start execution of worker.
Worker * worker(unsigned int i) const
Provide access to worker i.
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.
const Choice & choice(void) const
Return corresponding choice.
static void run(Runnable *r)
Construct a new thread and run r.
Engine & _engine
Reference to engine.
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 acquire(void)
Acquire the mutex and possibly block.
void * ralloc(size_t s)
Allocate s bytes from heap.
Node representing failure.
Support::Mutex m_search
Mutex for search.
void * mark(void *p)
Return marked pointer for unmarked pointer p.
Search tree edge for recomputation
Parallel depth-first search engine
void signal(void)
Signal the event.
unsigned int nid(void) const
Return node identifier.
virtual Statistics statistics(void) const
Return statistics.
BAB & engine(void) const
Provide access to engine.
Space * best
Best solution so far.
void release(void)
Release the mutex.
Gecode::FloatVal c(-8, 8)
void init(unsigned int wid, unsigned int nid, unsigned int a)
Initialize.
Gecode::IntArgs i(4, 1, 2, 3, 4)
Space * cur
Current space being explored.
Cmd cmd(void) const
Return current command.
Space * clone(CloneStatistics &stat=unused_clone) const
Clone space.
const unsigned int a_d
Create a clone during recomputation if distance is greater than a_d (adaptive distance) ...
Node representing a solution.
Support::Mutex m_wait_reset
Mutex for waiting for reset.
static void sleep(unsigned int ms)
Put current thread to sleep for ms milliseconds.
virtual void constrain(const Space &best)
Constrain function for best solution search.
virtual ~BAB(void)
Destructor.
Parallel branch-and-bound engine
void better(Space *b)
Accept better solution b.
void release(Cmd c)
Release all workers.
bool idle
Whether the worker is idle.
const Choice * choice(void) const
Return choice.
Space * steal(unsigned long int &d, Tracer &myt, Tracer &ot)
Hand over some work (NULL if no work available)
SearchTracer * tracer
Tracer object for tracing search.
const Options & opt(void) const
Provide access to search options.
unsigned int d
Distance until next clone.
static void engine(SearchTracer *tracer, SearchTracer::EngineType t, unsigned int n)
Register engine.
struct Gecode::@585::NNF::@62::@63 b
For binary nodes (and, or, eqv)
Support::Event e_search
Event for search (solution found, no more solutions, search stopped)
Support::DynamicQueue< Space *, Heap > solutions
Queue of solutions.
virtual ~Worker(void)
Destructor.
Choice for performing commit
No-goods recorded from restarts.
Space * best
Best solution found so far.
void find(void)
Try to find some work.
Heap heap
The single global heap.
void idle(void)
Report that worker is idle.
SpaceStatus status(StatusStatistics &stat=unused_status)
Query space status.
const unsigned int c_d
Create a clone after every c_d commits (commit distance)
virtual void constrain(const Space &b)
Constrain future solutions to be better than b.
NoGoods & nogoods(void)
Return no-goods.
Gecode toplevel namespace
const unsigned int nogoods_limit
Depth limit for no-good generation during search.
unsigned int truealt(void) const
Return true number for alternatives (excluding lao optimization)
volatile unsigned int n_busy
Number of busy workers.
virtual void reset(Space *s)
Reset engine to restart at space s.
void invalidate(void)
Invalidate edge information (for stealing)
BAB(Space *s, const Options &o)
Initialize for space s with options o.
Parallel branch-and-bound search worker
void block(void)
Block all workers.
Tracer tracer
Search tracer.
#define GECODE_NEVER
Assert that this command is never executed.
void wait(void)
Wait until the event becomes signalled.
Parallel depth-first search worker
void solution(Space *s)
Report solution s.
Space is solved (no brancher left)