Generated on Wed Jan 1 2020 10:37:59 for Gecode by doxygen 1.8.16
dfs.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  * Basic access routines
38  */
39  template<class Tracer>
40  forceinline DFS<Tracer>&
42  return static_cast<DFS<Tracer>&>(_engine);
43  }
44  template<class Tracer>
46  DFS<Tracer>::worker(unsigned int i) const {
47  return _worker[i];
48  }
49 
50 
51  /*
52  * Engine: initialization
53  */
54  template<class Tracer>
57  : Engine<Tracer>::Worker(s,e) {}
58  template<class Tracer>
61  : Engine<Tracer>(o) {
62  WrapTraceRecorder::engine(o.tracer, SearchTracer::EngineType::DFS,
63  workers());
64  // Create workers
65  _worker = static_cast<Worker**>
66  (heap.ralloc(workers() * sizeof(Worker*)));
67  // The first worker gets the entire search tree
68  _worker[0] = new Worker(s,*this);
69  // All other workers start with no work
70  for (unsigned int i=1; i<workers(); i++)
71  _worker[i] = new Worker(NULL,*this);
72  // Block all workers
73  block();
74  // Create and start threads
75  for (unsigned int i=0U; i<workers(); i++)
77  }
78 
79 
80  /*
81  * Reset
82  */
83  template<class Tracer>
84  forceinline void
85  DFS<Tracer>::Worker::reset(Space* s, unsigned int ngdl) {
86  delete cur;
87  tracer.round();
88  path.reset((s != NULL) ? ngdl : 0);
89  d = 0;
90  idle = false;
91  if ((s == NULL) || (s->status(*this) == SS_FAILED)) {
92  delete s;
93  cur = NULL;
94  } else {
95  cur = s;
96  }
98  }
99 
100 
101  /*
102  * Engine: search control
103  */
104  template<class Tracer>
105  forceinline void
107  m_search.acquire();
108  bool bs = signal();
109  solutions.push(s);
110  if (bs)
111  e_search.signal();
112  m_search.release();
113  }
114 
115 
116 
117  /*
118  * Worker: finding and stealing working
119  */
120  template<class Tracer>
121  forceinline void
123  // Try to find new work (even if there is none)
124  for (unsigned int i=0U; i<engine().workers(); i++) {
125  unsigned long int r_d = 0ul;
126  typename Engine<Tracer>::Worker* wi = engine().worker(i);
127  if (Space* s = wi->steal(r_d,wi->tracer,tracer)) {
128  // Reset this guy
129  m.acquire();
130  idle = false;
131  // Not idle but also does not have the root of the tree
132  path.ngdl(0);
133  d = 0;
134  cur = s;
135  Statistics t = *this;
137  (*this) += t;
138  m.release();
139  return;
140  }
141  }
142  }
143 
144  /*
145  * Statistics
146  */
147  template<class Tracer>
148  Statistics
150  Statistics s;
151  for (unsigned int i=0U; i<workers(); i++)
152  s += worker(i)->statistics();
153  return s;
154  }
155 
156 
157  /*
158  * Engine: search control
159  */
160  template<class Tracer>
161  void
163  /*
164  * The engine maintains the following invariant:
165  * - If the current space (cur) is not NULL, the path always points
166  * to exactly that space.
167  * - If the current space (cur) is NULL, the path always points
168  * to the next space (if there is any).
169  *
170  * This invariant is needed so that no-goods can be extracted properly
171  * when the engine is stopped or has found a solution.
172  *
173  */
174  // Peform initial delay, if not first worker
175  if (this != engine().worker(0))
177  // Okay, we are in business, start working
178  while (true) {
179  switch (engine().cmd()) {
180  case C_WAIT:
181  // Wait
182  engine().wait();
183  break;
184  case C_TERMINATE:
185  // Acknowledge termination request
186  engine().ack_terminate();
187  // Wait until termination can proceed
188  engine().wait_terminate();
189  // Thread will be terminated by returning from run
190  return;
191  case C_RESET:
192  // Acknowledge reset request
193  engine().ack_reset_start();
194  // Wait until reset has been performed
195  engine().wait_reset();
196  // Acknowledge that reset cycle is over
197  engine().ack_reset_stop();
198  break;
199  case C_WORK:
200  // Perform exploration work
201  {
202  m.acquire();
203  if (idle) {
204  m.release();
205  // Try to find new work
206  find();
207  } else if (cur != NULL) {
208  start();
209  if (stop(engine().opt())) {
210  // Report stop
211  m.release();
212  engine().stop();
213  } else {
214  node++;
216  if (tracer) {
217  if (path.entries() > 0) {
218  typename Path<Tracer>::Edge& top = path.top();
219  ei.init(tracer.wid(), top.nid(), top.truealt(),
220  *cur, *top.choice());
221  } else if (*tracer.ei()) {
222  ei = *tracer.ei();
223  tracer.invalidate();
224  }
225  }
226  unsigned int nid = tracer.nid();
227  switch (cur->status(*this)) {
228  case SS_FAILED:
229  if (tracer) {
231  tracer.wid(), nid, *cur);
232  tracer.node(ei,ni);
233  }
234  fail++;
235  delete cur;
236  cur = NULL;
237  path.next();
238  m.release();
239  break;
240  case SS_SOLVED:
241  {
242  if (tracer) {
244  tracer.wid(), nid, *cur);
245  tracer.node(ei,ni);
246  }
247  // Deletes all pending branchers
248  (void) cur->choice();
249  Space* s = cur->clone();
250  delete cur;
251  cur = NULL;
252  path.next();
253  m.release();
254  engine().solution(s);
255  }
256  break;
257  case SS_BRANCH:
258  {
259  Space* c;
260  if ((d == 0) || (d >= engine().opt().c_d)) {
261  c = cur->clone();
262  d = 1;
263  } else {
264  c = NULL;
265  d++;
266  }
267  const Choice* ch = path.push(*this,cur,c,nid);
268  if (tracer) {
270  tracer.wid(), nid, *cur, ch);
271  tracer.node(ei,ni);
272  }
273  cur->commit(*ch,0);
274  m.release();
275  }
276  break;
277  default:
278  GECODE_NEVER;
279  }
280  }
281  } else if (!path.empty()) {
282  cur = path.recompute(d,engine().opt().a_d,*this,tracer);
283  if (cur == NULL)
284  path.next();
285  m.release();
286  } else {
287  idle = true;
288  path.ngdl(0);
289  m.release();
290  // Report that worker is idle
291  engine().idle();
292  }
293  }
294  break;
295  default:
296  GECODE_NEVER;
297  }
298  }
299  }
300 
301 
302  /*
303  * Perform reset
304  *
305  */
306  template<class Tracer>
307  void
309  // Grab wait lock for reset
311  // Release workers for reset
312  release(C_RESET);
313  // Wait for reset cycle started
315  // All workers are marked as busy again
316  n_busy = workers();
317  for (unsigned int i=1U; i<workers(); i++)
318  worker(i)->reset(NULL,0);
319  worker(0U)->reset(s,opt().nogoods_limit);
320  // Block workers again to ensure invariant
321  block();
322  // Release reset lock
324  // Wait for reset cycle stopped
326  }
327 
328 
329 
330  /*
331  * Create no-goods
332  *
333  */
334  template<class Tracer>
335  NoGoods&
337  NoGoods* ng;
338  // Grab wait lock for reset
340  // Release workers for reset
341  release(C_RESET);
342  // Wait for reset cycle started
344  ng = &worker(0)->nogoods();
345  // Block workers again to ensure invariant
346  block();
347  // Release reset lock
349  // Wait for reset cycle stopped
351  return *ng;
352  }
353 
354 
355  /*
356  * Termination and deletion
357  */
358  template<class Tracer>
360  terminate();
361  heap.rfree(_worker);
362  }
363 
364 }}}
365 
366 // STATISTICS: search-par
Run into wait lock.
Definition: engine.hh:95
void release(Cmd c)
Release all workers.
Definition: engine.hpp:79
unsigned int nid(void) const
Return node identifier.
Definition: path.hpp:70
void terminate(void)
For engine to peform thread termination.
Definition: engine.hpp:216
Space is solved (no brancher left)
Definition: core.hpp:1683
Parallel depth-first search worker
Definition: engine.hh:49
virtual void run(void)
Start execution of worker.
Definition: dfs.hpp:162
NoGoods & nogoods(void)
Return no-goods.
Definition: engine.hpp:289
Terminate.
Definition: engine.hh:97
Search engine options
Definition: search.hh:746
Support::Mutex m_search
Mutex for search.
Definition: engine.hh:167
void acquire(void)
Acquire the mutex and possibly block.
Definition: none.hpp:42
void find(void)
Try to find some work.
Definition: dfs.hpp:122
Statistics statistics(void)
Return statistics.
Definition: engine.hpp:134
Worker * worker(unsigned int i) const
Provide access to worker i.
Definition: dfs.hpp:46
Space must be branched (at least one brancher left)
Definition: core.hpp:1684
void * ralloc(size_t s)
Allocate s bytes from heap.
Definition: heap.hpp:357
NodeType t
Type of node.
Definition: bool-expr.cpp:230
Perform work.
Definition: engine.hh:94
Search tree edge for recomputation
Definition: path.hh:66
Parallel depth-first search engine
Definition: dfs.hh:43
Computation spaces.
Definition: core.hpp:1742
void invalidate(void)
Invalidate edge information (for stealing)
Definition: tracer.hpp:102
Support::Event e_reset_ack_start
Event for reset acknowledgment started.
Definition: engine.hh:149
unsigned int truealt(void) const
Return true number for alternatives (excluding lao optimization)
Definition: path.hpp:76
virtual void reset(Space *s)
Reset engine to restart at space s.
Definition: dfs.hpp:308
void stop(void)
Report that worker has been stopped.
Definition: engine.hpp:172
Support::Event e_search
Event for search (solution found, no more solutions, search stopped)
Definition: engine.hh:169
Gecode toplevel namespace
const Choice * choice(void) const
Return choice.
Definition: path.hpp:108
Space * clone(CloneStatistics &stat=unused_clone) const
Clone space.
Definition: core.hpp:3224
No-goods recorded from restarts.
Definition: core.hpp:1588
Support::DynamicQueue< Space *, Heap > solutions
Queue of solutions.
Definition: engine.hh:171
Perform reset operation.
Definition: engine.hh:96
Worker(void)
Initialize.
Definition: worker.hh:70
Engine & _engine
Reference to engine.
Definition: engine.hh:55
Parallel depth-first search engine
Definition: engine.hh:46
const Choice & choice(void) const
Return corresponding choice.
Definition: tracer.hpp:191
Node information.
Definition: search.hh:282
void idle(void)
Report that worker is idle.
Definition: engine.hpp:152
void solution(Space *s)
Report solution s.
Definition: dfs.hpp:106
virtual ~DFS(void)
Destructor.
Definition: dfs.hpp:359
const unsigned int nogoods_limit
Depth limit for no-good generation during search.
Definition: search.hh:131
DFS(Space *s, const Options &o)
Initialize for space s with options o.
Definition: dfs.hpp:60
Support::Event e_reset_ack_stop
Event for reset acknowledgment stopped.
Definition: engine.hh:151
static void run(Runnable *r)
Construct a new thread and run r.
Definition: thread.hpp:115
Worker ** _worker
Array of worker references.
Definition: dfs.hh:91
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
Space * cur
Current space being explored.
Definition: engine.hh:61
virtual Statistics statistics(void) const
Return statistics.
Definition: dfs.hpp:149
unsigned int d
Distance until next clone.
Definition: engine.hh:63
Node representing a branch.
Definition: spacenode.hh:47
#define GECODE_NEVER
Assert that this command is never executed.
Definition: macros.hpp:56
SpaceStatus status(StatusStatistics &stat=unused_status)
Query space status.
Definition: core.cpp:252
Tracer.
Definition: tracer.hpp:149
Support::Mutex m_wait_reset
Mutex for waiting for reset.
Definition: engine.hh:153
DFS & engine(void) const
Provide access to engine.
Definition: dfs.hpp:41
Heap heap
The single global heap.
Definition: heap.cpp:44
void reset(Space *s, unsigned int ngdl)
Reset worker to restart at space s.
Definition: dfs.hpp:85
Edge information.
Definition: search.hh:242
const Options & opt(void) const
Provide access to search options.
Definition: engine.hpp:47
void signal(void)
Signal the event.
Definition: none.hpp:59
Gecode::IntSet d(v, 7)
void init(unsigned int wid, unsigned int nid, unsigned int a)
Initialize.
Definition: tracer.hpp:107
volatile unsigned int n_busy
Number of busy workers.
Definition: engine.hh:173
Parallel depth-first search worker
Definition: dfs.hh:66
static void sleep(unsigned int ms)
Put current thread to sleep for ms milliseconds.
Definition: none.hpp:74
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
#define forceinline
Definition: config.hpp:185
virtual NoGoods & nogoods(void)
Return no-goods.
Definition: dfs.hpp:336
void block(void)
Block all workers.
Definition: engine.hpp:73
const unsigned int c_d
Create a clone after every c_d commits (commit distance)
Definition: search.hh:113
Space * steal(unsigned long int &d, Tracer &myt, Tracer &ot)
Hand over some work (NULL if no work available)
Definition: engine.hpp:265
const unsigned int a_d
Create a clone during recomputation if distance is greater than a_d (adaptive distance)
Definition: search.hh:115
Gecode::FloatVal c(-8, 8)
void reset(void)
Reset.
Definition: statistics.hpp:39
void release(void)
Release the mutex.
Definition: none.hpp:48
Choice for performing commit
Definition: core.hpp:1412
Path< Tracer > path
Current path ins search tree.
Definition: engine.hh:59
void rfree(void *p)
Free memory block starting at p.
Definition: heap.hpp:371
void wait(void)
Wait until the event becomes signalled.
Definition: none.hpp:61
unsigned int workers(void) const
Return number of workers.
Definition: engine.hpp:52
Cmd cmd(void) const
Return current command.
Definition: engine.hpp:68
Node representing failure.
Definition: spacenode.hh:46
Gecode::IntArgs i({1, 2, 3, 4})
Search engine statistics
Definition: search.hh:147
Space is failed
Definition: core.hpp:1682
Tracer tracer
Search tracer.
Definition: engine.hh:52
static void engine(SearchTracer *tracer, SearchTracer::EngineType t, unsigned int n)
Register engine.
bool idle
Whether the worker is idle.
Definition: engine.hh:65
Node representing a solution.
Definition: spacenode.hh:45
SearchTracer * tracer
Tracer object for tracing search.
Definition: search.hh:769