Generated on Thu Apr 5 2018 19:44:19 for Gecode by doxygen 1.8.13
bab.hpp
Go to the documentation of this file.
1 /* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
2 /*
3  * Main authors:
4  * Christian Schulte <schulte@gecode.org>
5  *
6  * Copyright:
7  * Christian Schulte, 2009
8  *
9  * Last modified:
10  * $Date$ by $Author$
11  * $Revision$
12  *
13  * This file is part of Gecode, the generic constraint
14  * development environment:
15  * http://www.gecode.org
16  *
17  * Permission is hereby granted, free of charge, to any person obtaining
18  * a copy of this software and associated documentation files (the
19  * "Software"), to deal in the Software without restriction, including
20  * without limitation the rights to use, copy, modify, merge, publish,
21  * distribute, sublicense, and/or sell copies of the Software, and to
22  * permit persons to whom the Software is furnished to do so, subject to
23  * the following conditions:
24  *
25  * The above copyright notice and this permission notice shall be
26  * included in all copies or substantial portions of the Software.
27  *
28  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
29  * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
30  * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
31  * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
32  * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
33  * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
34  * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
35  *
36  */
37 
38 namespace Gecode { namespace Search { namespace Par {
39 
40  /*
41  * Engine: basic access routines
42  */
43  template<class Tracer>
44  forceinline BAB<Tracer>&
46  return static_cast<BAB&>(_engine);
47  }
48  template<class Tracer>
50  BAB<Tracer>::worker(unsigned int i) const {
51  return _worker[i];
52  }
53 
54  template<class Tracer>
55  forceinline void
56  BAB<Tracer>::Worker::reset(Space* s, unsigned int ngdl) {
57  tracer.round();
58  delete cur;
59  delete best;
60  best = NULL;
61  path.reset((s == NULL) ? 0 : ngdl);
62  d = 0;
63  mark = 0;
64  idle = false;
65  if ((s == NULL) || (s->status(*this) == SS_FAILED)) {
66  delete s;
67  cur = NULL;
68  } else {
69  cur = s;
70  }
72  }
73 
74 
75  /*
76  * Engine: initialization
77  */
78  template<class Tracer>
81  : Engine<Tracer>::Worker(s,e), mark(0), best(NULL) {}
82 
83  template<class Tracer>
86  : Engine<Tracer>(o), best(NULL) {
87  WrapTraceRecorder::engine(o.tracer, SearchTracer::EngineType::DFS,
88  workers());
89  // Create workers
90  _worker = static_cast<Worker**>
91  (heap.ralloc(workers() * sizeof(Worker*)));
92  // The first worker gets the entire search tree
93  _worker[0] = new Worker(s,*this);
94  // All other workers start with no work
95  for (unsigned int i=1; i<workers(); i++)
96  _worker[i] = new Worker(NULL,*this);
97  // Block all workers
98  block();
99  // Create and start threads
100  for (unsigned int i=0; i<workers(); i++)
102  }
103 
104 
105  /*
106  * Engine: search control
107  */
108  template<class Tracer>
109  forceinline void
111  m.acquire();
112  delete best;
113  best = b->clone();
114  mark = path.entries();
115  if (cur != NULL)
116  cur->constrain(*best);
117  m.release();
118  }
119  template<class Tracer>
120  forceinline void
122  m_search.acquire();
123  if (best != NULL) {
124  s->constrain(*best);
125  if (s->status() == SS_FAILED) {
126  delete s;
127  m_search.release();
128  return;
129  } else {
130  delete best;
131  best = s->clone();
132  }
133  } else {
134  best = s->clone();
135  }
136  // Announce better solutions
137  for (unsigned int i=0; i<workers(); i++)
138  worker(i)->better(best);
139  bool bs = signal();
140  solutions.push(s);
141  if (bs)
142  e_search.signal();
143  m_search.release();
144  }
145 
146 
147  /*
148  * Worker: finding and stealing working
149  */
150  template<class Tracer>
151  forceinline void
153  // Try to find new work (even if there is none)
154  for (unsigned int i=0; i<engine().workers(); i++) {
155  unsigned long int r_d = 0ul;
156  typename Engine<Tracer>::Worker* wi = engine().worker(i);
157  if (Space* s = wi->steal(r_d,wi->tracer,tracer)) {
158  // Reset this guy
159  m.acquire();
160  idle = false;
161  // Not idle but also does not have the root of the tree
162  path.ngdl(0);
163  d = 0;
164  cur = s;
165  mark = 0;
166  if (best != NULL)
167  cur->constrain(*best);
168  Statistics t = *this;
170  (*this) += t;
171  m.release();
172  return;
173  }
174  }
175  }
176 
177  /*
178  * Statistics
179  */
180  template<class Tracer>
181  Statistics
183  Statistics s;
184  for (unsigned int i=0; i<workers(); i++)
185  s += worker(i)->statistics();
186  return s;
187  }
188 
189  template<class Tracer>
190  void
192  m_search.acquire();
193  if (best != NULL) {
194  best->constrain(b);
195  if (best->status() != SS_FAILED) {
196  m_search.release();
197  return;
198  }
199  delete best;
200  }
201  best = b.clone();
202  // Announce better solutions
203  for (unsigned int i=0; i<workers(); i++)
204  worker(i)->better(best);
205  m_search.release();
206  }
207 
208  /*
209  * Actual work
210  */
211  template<class Tracer>
212  void
214  /*
215  * The engine maintains the following invariant:
216  * - If the current space (cur) is not NULL, the path always points
217  * to exactly that space.
218  * - If the current space (cur) is NULL, the path always points
219  * to the next space (if there is any).
220  *
221  * This invariant is needed so that no-goods can be extracted properly
222  * when the engine is stopped or has found a solution.
223  *
224  * An additional invariant maintained by the engine is:
225  * For all nodes stored at a depth less than mark, there
226  * is no guarantee of betterness. For those above the mark,
227  * betterness is guaranteed.
228  *
229  */
230  // Peform initial delay, if not first worker
231  if (this != engine().worker(0))
233  // Okay, we are in business, start working
234  while (true) {
235  switch (engine().cmd()) {
236  case C_WAIT:
237  // Wait
238  engine().wait();
239  break;
240  case C_TERMINATE:
241  // Acknowledge termination request
242  engine().ack_terminate();
243  // Wait until termination can proceed
244  engine().wait_terminate();
245  // Thread will be terminated by returning from run
246  return;
247  case C_RESET:
248  // Acknowledge reset request
249  engine().ack_reset_start();
250  // Wait until reset has been performed
251  engine().wait_reset();
252  // Acknowledge that reset cycle is over
253  engine().ack_reset_stop();
254  break;
255  case C_WORK:
256  // Perform exploration work
257  {
258  m.acquire();
259  if (idle) {
260  m.release();
261  // Try to find new work
262  find();
263  } else if (cur != NULL) {
264  start();
265  if (stop(engine().opt())) {
266  // Report stop
267  m.release();
268  engine().stop();
269  } else {
270  node++;
272  if (tracer) {
273  if (path.entries() > 0) {
274  typename Path<Tracer>::Edge& top = path.top();
275  ei.init(tracer.wid(), top.nid(), top.truealt(),
276  *cur, *top.choice());
277  } else if (*tracer.ei()) {
278  ei = *tracer.ei();
279  tracer.invalidate();
280  }
281  }
282  unsigned int nid = tracer.nid();
283  switch (cur->status(*this)) {
284  case SS_FAILED:
285  if (tracer) {
287  tracer.wid(), nid, *cur);
288  tracer.node(ei,ni);
289  }
290  fail++;
291  delete cur;
292  cur = NULL;
293  path.next();
294  m.release();
295  break;
296  case SS_SOLVED:
297  {
298  if (tracer) {
300  tracer.wid(), nid, *cur);
301  tracer.node(ei,ni);
302  }
303  // Deletes all pending branchers
304  (void) cur->choice();
305  Space* s = cur->clone();
306  delete cur;
307  cur = NULL;
308  path.next();
309  m.release();
310  engine().solution(s);
311  }
312  break;
313  case SS_BRANCH:
314  {
315  Space* c;
316  if ((d == 0) || (d >= engine().opt().c_d)) {
317  c = cur->clone();
318  d = 1;
319  } else {
320  c = NULL;
321  d++;
322  }
323  const Choice* ch = path.push(*this,cur,c,nid);
324  if (tracer) {
326  tracer.wid(), nid, *cur, ch);
327  tracer.node(ei,ni);
328  }
329  cur->commit(*ch,0);
330  m.release();
331  }
332  break;
333  default:
334  GECODE_NEVER;
335  }
336  }
337  } else if (!path.empty()) {
338  cur = path.recompute(d,engine().opt().a_d,*this,*best,mark,tracer);
339  if (cur == NULL)
340  path.next();
341  m.release();
342  } else {
343  idle = true;
344  path.ngdl(0);
345  m.release();
346  // Report that worker is idle
347  engine().idle();
348  }
349  }
350  break;
351  default:
352  GECODE_NEVER;
353  }
354  }
355  }
356 
357 
358  /*
359  * Perform reset
360  *
361  */
362  template<class Tracer>
363  void
365  // Grab wait lock for reset
367  // Release workers for reset
368  release(C_RESET);
369  // Wait for reset cycle started
371  // All workers are marked as busy again
372  delete best;
373  best = NULL;
374  n_busy = workers();
375  for (unsigned int i=1; i<workers(); i++)
376  worker(i)->reset(NULL,0);
377  worker(0)->reset(s,opt().nogoods_limit);
378  // Block workers again to ensure invariant
379  block();
380  // Release reset lock
382  // Wait for reset cycle stopped
384  }
385 
386 
387  /*
388  * Create no-goods
389  *
390  */
391  template<class Tracer>
392  NoGoods&
394  NoGoods* ng;
395  // Grab wait lock for reset
397  // Release workers for reset
398  release(C_RESET);
399  // Wait for reset cycle started
401  ng = &worker(0)->nogoods();
402  // Block workers again to ensure invariant
403  block();
404  // Release reset lock
406  // Wait for reset cycle stopped
408  return *ng;
409  }
410 
411  /*
412  * Termination and deletion
413  */
414  template<class Tracer>
416  delete best;
417  }
418 
419  template<class Tracer>
421  terminate();
422  delete best;
423  heap.rfree(_worker);
424  }
425 
426 }}}
427 
428 // STATISTICS: search-par
Edge information.
Definition: search.hh:244
Statistics statistics(void)
Return statistics.
Definition: engine.hpp:138
Support::Event e_reset_ack_stop
Event for reset acknowledgment stopped.
Definition: engine.hh:155
Worker(void)
Initialize.
Definition: worker.hh:74
void stop(void)
Report that worker has been stopped.
Definition: engine.hpp:176
Worker ** _worker
Array of worker references.
Definition: bab.hh:104
NodeType t
Type of node.
Definition: bool-expr.cpp:234
Path< Tracer > path
Current path ins search tree.
Definition: engine.hh:63
Space must be branched (at least one brancher left)
Definition: core.hpp:1610
virtual NoGoods & nogoods(void)
Constrain Return no-goods.
Definition: bab.hpp:393
void reset(Space *s, unsigned int ngdl)
Reset engine to restart at space s.
Definition: bab.hpp:56
unsigned int workers(void) const
Return number of workers.
Definition: engine.hpp:56
Search engine statistics
Definition: search.hh:149
Support::Event e_reset_ack_start
Event for reset acknowledgment started.
Definition: engine.hh:153
int mark
Number of entries not yet constrained to be better.
Definition: bab.hh:84
void terminate(void)
For engine to peform thread termination.
Definition: engine.hpp:220
Node representing a branch.
Definition: spacenode.hh:51
void rfree(void *p)
Free memory block starting at p.
Definition: heap.hpp:375
virtual void run(void)
Start execution of worker.
Definition: bab.hpp:213
Search engine options
Definition: search.hh:748
Worker * worker(unsigned int i) const
Provide access to worker i.
Definition: bab.hpp:50
bool signal(void) const
Whether search state changed such that signal is needed.
Definition: engine.hpp:151
const unsigned int initial_delay
Initial delay in milliseconds for all but first worker thread.
Definition: search.hh:122
const Choice & choice(void) const
Return corresponding choice.
Definition: tracer.hpp:195
static void run(Runnable *r)
Construct a new thread and run r.
Definition: thread.hpp:119
Engine & _engine
Reference to engine.
Definition: engine.hh:59
void path(Home home, int offset, const IntVarArgs &x, IntVar s, IntVar e, IntPropLevel ipl)
Post propagator such that x forms a Hamiltonian path.
Definition: circuit.cpp:128
void acquire(void)
Acquire the mutex and possibly block.
Definition: none.hpp:46
void * ralloc(size_t s)
Allocate s bytes from heap.
Definition: heap.hpp:361
Node representing failure.
Definition: spacenode.hh:50
Support::Mutex m_search
Mutex for search.
Definition: engine.hh:171
void * mark(void *p)
Return marked pointer for unmarked pointer p.
Search tree edge for recomputation
Definition: path.hh:70
#define forceinline
Definition: config.hpp:182
Parallel depth-first search engine
Definition: engine.hh:50
void signal(void)
Signal the event.
Definition: none.hpp:63
Perform reset operation.
Definition: engine.hh:100
unsigned int nid(void) const
Return node identifier.
Definition: path.hpp:74
Computation spaces.
Definition: core.hpp:1668
virtual Statistics statistics(void) const
Return statistics.
Definition: bab.hpp:182
Gecode::IntSet d(v, 7)
BAB & engine(void) const
Provide access to engine.
Definition: bab.hpp:45
Space * best
Best solution so far.
Definition: bab.hh:106
void release(void)
Release the mutex.
Definition: none.hpp:52
Gecode::FloatVal c(-8, 8)
void init(unsigned int wid, unsigned int nid, unsigned int a)
Initialize.
Definition: tracer.hpp:111
Gecode::IntArgs i(4, 1, 2, 3, 4)
Space * cur
Current space being explored.
Definition: engine.hh:65
Cmd cmd(void) const
Return current command.
Definition: engine.hpp:72
Space * clone(CloneStatistics &stat=unused_clone) const
Clone space.
Definition: core.hpp:3144
const unsigned int a_d
Create a clone during recomputation if distance is greater than a_d (adaptive distance) ...
Definition: search.hh:117
Node representing a solution.
Definition: spacenode.hh:49
Run into wait lock.
Definition: engine.hh:99
Support::Mutex m_wait_reset
Mutex for waiting for reset.
Definition: engine.hh:157
static void sleep(unsigned int ms)
Put current thread to sleep for ms milliseconds.
Definition: none.hpp:78
virtual void constrain(const Space &best)
Constrain function for best solution search.
Definition: core.cpp:807
virtual ~BAB(void)
Destructor.
Definition: bab.hpp:420
Parallel branch-and-bound engine
Definition: bab.hh:47
void better(Space *b)
Accept better solution b.
Definition: bab.hpp:110
void release(Cmd c)
Release all workers.
Definition: engine.hpp:83
bool idle
Whether the worker is idle.
Definition: engine.hh:69
const Choice * choice(void) const
Return choice.
Definition: path.hpp:112
Space * steal(unsigned long int &d, Tracer &myt, Tracer &ot)
Hand over some work (NULL if no work available)
Definition: engine.hpp:269
SearchTracer * tracer
Tracer object for tracing search.
Definition: search.hh:771
const Options & opt(void) const
Provide access to search options.
Definition: engine.hpp:51
unsigned int d
Distance until next clone.
Definition: engine.hh:67
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)
Definition: engine.hh:173
Support::DynamicQueue< Space *, Heap > solutions
Queue of solutions.
Definition: engine.hh:175
virtual ~Worker(void)
Destructor.
Definition: bab.hpp:415
Choice for performing commit
Definition: core.hpp:1338
No-goods recorded from restarts.
Definition: core.hpp:1514
Space * best
Best solution found so far.
Definition: bab.hh:86
void find(void)
Try to find some work.
Definition: bab.hpp:152
Heap heap
The single global heap.
Definition: heap.cpp:48
void idle(void)
Report that worker is idle.
Definition: engine.hpp:156
SpaceStatus status(StatusStatistics &stat=unused_status)
Query space status.
Definition: core.cpp:229
Node information.
Definition: search.hh:284
const unsigned int c_d
Create a clone after every c_d commits (commit distance)
Definition: search.hh:115
virtual void constrain(const Space &b)
Constrain future solutions to be better than b.
Definition: bab.hpp:191
Tracer.
Definition: tracer.hpp:153
NoGoods & nogoods(void)
Return no-goods.
Definition: engine.hpp:293
Gecode toplevel namespace
const unsigned int nogoods_limit
Depth limit for no-good generation during search.
Definition: search.hh:133
unsigned int truealt(void) const
Return true number for alternatives (excluding lao optimization)
Definition: path.hpp:80
volatile unsigned int n_busy
Number of busy workers.
Definition: engine.hh:177
virtual void reset(Space *s)
Reset engine to restart at space s.
Definition: bab.hpp:364
void invalidate(void)
Invalidate edge information (for stealing)
Definition: tracer.hpp:106
Space is failed
Definition: core.hpp:1608
BAB(Space *s, const Options &o)
Initialize for space s with options o.
Definition: bab.hpp:85
Parallel branch-and-bound search worker
Definition: bab.hh:70
void block(void)
Block all workers.
Definition: engine.hpp:77
Tracer tracer
Search tracer.
Definition: engine.hh:56
#define GECODE_NEVER
Assert that this command is never executed.
Definition: macros.hpp:60
void wait(void)
Wait until the event becomes signalled.
Definition: none.hpp:65
Parallel depth-first search worker
Definition: engine.hh:53
void solution(Space *s)
Report solution s.
Definition: bab.hpp:121
void reset(void)
Reset.
Definition: statistics.hpp:43
Space is solved (no brancher left)
Definition: core.hpp:1609