34namespace 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>
91 for (
unsigned int i=1U; i<
workers(); i++)
96 for (
unsigned int i=0U; i<
workers(); i++)
104 template<
class Tracer>
115 template<
class Tracer>
133 for (
unsigned int i=0U; i<
workers(); i++)
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>
180 for (
unsigned int i=0U; i<
workers(); i++)
185 template<
class Tracer>
199 for (
unsigned int i=0U; i<
workers(); i++)
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)) {
319 const Choice* ch =
path.push(*
this,cur,c,nid);
322 tracer.wid(), nid, *cur, ch);
333 }
else if (!
path.empty()) {
334 cur =
path.recompute(d,engine().
opt().a_d,*
this,*
best,mark,tracer);
358 template<
class Tracer>
371 for (
unsigned int i=1U; i<
workers(); i++)
387 template<
class Tracer>
410 template<
class Tracer>
415 template<
class Tracer>
struct Gecode::@603::NNF::@65::@66 b
For binary nodes (and, or, eqv)
Choice for performing commit
void rfree(void *p)
Free memory block starting at p.
void * ralloc(size_t s)
Allocate s bytes from heap.
No-goods recorded from restarts.
void invalidate(void)
Invalidate edge information (for stealing)
void init(unsigned int wid, unsigned int nid, unsigned int a)
Initialize.
unsigned int nid(void) const
Return parent node id.
@ DFS
Engine is a DFS engine.
SearchTracer * tracer
Tracer object for tracing search.
Parallel branch-and-bound search worker
void 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.
void better(Space *b)
Accept better solution b.
BAB & engine(void) const
Provide access to engine.
virtual ~Worker(void)
Destructor.
virtual void run(void)
Start execution of worker.
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 (NULL if no work available)
Path< Tracer > path
Current path ins search tree.
Parallel depth-first search engine
void idle(void)
Report that worker is idle.
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 stop(void)
Report that worker has been stopped.
void block(void)
Block all workers.
Support::Mutex m_wait_reset
Mutex for waiting for reset.
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.
void release(Cmd c)
Release all workers.
bool signal(void) const
Whether search state changed such that signal is needed.
void terminate(void)
For engine to peform 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.
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.
static void engine(SearchTracer *tracer, SearchTracer::EngineType t, unsigned int n)
Register engine.
void reset(void)
Reset information.
void wait(void)
Wait until the event becomes signalled.
void signal(void)
Signal the event.
void release(void)
Release the mutex.
void acquire(void)
Acquire the mutex and possibly block.
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.
SpaceStatus status(StatusStatistics &stat=unused_status)
Query space status.
Space * clone(CloneStatistics &stat=unused_clone) const
Clone space.
@ 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
void path(Home home, const IntVarArgs &x, IntVar s, IntVar e, IntPropLevel ipl=IPL_DEF)
Post propagator such that x forms a Hamiltonian path.
#define GECODE_NEVER
Assert that this command is never executed.