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