Generated on Thu Apr 5 2018 19:44:19 for Gecode by doxygen 1.8.13
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  * 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  * Basic access routines
42  */
43  template<class Tracer>
44  forceinline DFS<Tracer>&
46  return static_cast<DFS<Tracer>&>(_engine);
47  }
48  template<class Tracer>
50  DFS<Tracer>::worker(unsigned int i) const {
51  return _worker[i];
52  }
53 
54 
55  /*
56  * Engine: initialization
57  */
58  template<class Tracer>
61  : Engine<Tracer>::Worker(s,e) {}
62  template<class Tracer>
65  : Engine<Tracer>(o) {
66  WrapTraceRecorder::engine(o.tracer, SearchTracer::EngineType::DFS,
67  workers());
68  // Create workers
69  _worker = static_cast<Worker**>
70  (heap.ralloc(workers() * sizeof(Worker*)));
71  // The first worker gets the entire search tree
72  _worker[0] = new Worker(s,*this);
73  // All other workers start with no work
74  for (unsigned int i=1; i<workers(); i++)
75  _worker[i] = new Worker(NULL,*this);
76  // Block all workers
77  block();
78  // Create and start threads
79  for (unsigned int i=0; i<workers(); i++)
81  }
82 
83 
84  /*
85  * Reset
86  */
87  template<class Tracer>
88  forceinline void
89  DFS<Tracer>::Worker::reset(Space* s, unsigned int ngdl) {
90  delete cur;
91  tracer.round();
92  path.reset((s != NULL) ? ngdl : 0);
93  d = 0;
94  idle = false;
95  if ((s == NULL) || (s->status(*this) == SS_FAILED)) {
96  delete s;
97  cur = NULL;
98  } else {
99  cur = s;
100  }
102  }
103 
104 
105  /*
106  * Engine: search control
107  */
108  template<class Tracer>
109  forceinline void
111  m_search.acquire();
112  bool bs = signal();
113  solutions.push(s);
114  if (bs)
115  e_search.signal();
116  m_search.release();
117  }
118 
119 
120 
121  /*
122  * Worker: finding and stealing working
123  */
124  template<class Tracer>
125  forceinline void
127  // Try to find new work (even if there is none)
128  for (unsigned int i=0; i<engine().workers(); i++) {
129  unsigned long int r_d = 0ul;
130  typename Engine<Tracer>::Worker* wi = engine().worker(i);
131  if (Space* s = wi->steal(r_d,wi->tracer,tracer)) {
132  // Reset this guy
133  m.acquire();
134  idle = false;
135  // Not idle but also does not have the root of the tree
136  path.ngdl(0);
137  d = 0;
138  cur = s;
139  Statistics t = *this;
141  (*this) += t;
142  m.release();
143  return;
144  }
145  }
146  }
147 
148  /*
149  * Statistics
150  */
151  template<class Tracer>
152  Statistics
154  Statistics s;
155  for (unsigned int i=0; i<workers(); i++)
156  s += worker(i)->statistics();
157  return s;
158  }
159 
160 
161  /*
162  * Engine: search control
163  */
164  template<class Tracer>
165  void
167  /*
168  * The engine maintains the following invariant:
169  * - If the current space (cur) is not NULL, the path always points
170  * to exactly that space.
171  * - If the current space (cur) is NULL, the path always points
172  * to the next space (if there is any).
173  *
174  * This invariant is needed so that no-goods can be extracted properly
175  * when the engine is stopped or has found a solution.
176  *
177  */
178  // Peform initial delay, if not first worker
179  if (this != engine().worker(0))
181  // Okay, we are in business, start working
182  while (true) {
183  switch (engine().cmd()) {
184  case C_WAIT:
185  // Wait
186  engine().wait();
187  break;
188  case C_TERMINATE:
189  // Acknowledge termination request
190  engine().ack_terminate();
191  // Wait until termination can proceed
192  engine().wait_terminate();
193  // Thread will be terminated by returning from run
194  return;
195  case C_RESET:
196  // Acknowledge reset request
197  engine().ack_reset_start();
198  // Wait until reset has been performed
199  engine().wait_reset();
200  // Acknowledge that reset cycle is over
201  engine().ack_reset_stop();
202  break;
203  case C_WORK:
204  // Perform exploration work
205  {
206  m.acquire();
207  if (idle) {
208  m.release();
209  // Try to find new work
210  find();
211  } else if (cur != NULL) {
212  start();
213  if (stop(engine().opt())) {
214  // Report stop
215  m.release();
216  engine().stop();
217  } else {
218  node++;
220  if (tracer) {
221  if (path.entries() > 0) {
222  typename Path<Tracer>::Edge& top = path.top();
223  ei.init(tracer.wid(), top.nid(), top.truealt(),
224  *cur, *top.choice());
225  } else if (*tracer.ei()) {
226  ei = *tracer.ei();
227  tracer.invalidate();
228  }
229  }
230  unsigned int nid = tracer.nid();
231  switch (cur->status(*this)) {
232  case SS_FAILED:
233  if (tracer) {
235  tracer.wid(), nid, *cur);
236  tracer.node(ei,ni);
237  }
238  fail++;
239  delete cur;
240  cur = NULL;
241  path.next();
242  m.release();
243  break;
244  case SS_SOLVED:
245  {
246  if (tracer) {
248  tracer.wid(), nid, *cur);
249  tracer.node(ei,ni);
250  }
251  // Deletes all pending branchers
252  (void) cur->choice();
253  Space* s = cur->clone();
254  delete cur;
255  cur = NULL;
256  path.next();
257  m.release();
258  engine().solution(s);
259  }
260  break;
261  case SS_BRANCH:
262  {
263  Space* c;
264  if ((d == 0) || (d >= engine().opt().c_d)) {
265  c = cur->clone();
266  d = 1;
267  } else {
268  c = NULL;
269  d++;
270  }
271  const Choice* ch = path.push(*this,cur,c,nid);
272  if (tracer) {
274  tracer.wid(), nid, *cur, ch);
275  tracer.node(ei,ni);
276  }
277  cur->commit(*ch,0);
278  m.release();
279  }
280  break;
281  default:
282  GECODE_NEVER;
283  }
284  }
285  } else if (!path.empty()) {
286  cur = path.recompute(d,engine().opt().a_d,*this,tracer);
287  if (cur == NULL)
288  path.next();
289  m.release();
290  } else {
291  idle = true;
292  path.ngdl(0);
293  m.release();
294  // Report that worker is idle
295  engine().idle();
296  }
297  }
298  break;
299  default:
300  GECODE_NEVER;
301  }
302  }
303  }
304 
305 
306  /*
307  * Perform reset
308  *
309  */
310  template<class Tracer>
311  void
313  // Grab wait lock for reset
315  // Release workers for reset
316  release(C_RESET);
317  // Wait for reset cycle started
319  // All workers are marked as busy again
320  n_busy = workers();
321  for (unsigned int i=1U; i<workers(); i++)
322  worker(i)->reset(NULL,0);
323  worker(0U)->reset(s,opt().nogoods_limit);
324  // Block workers again to ensure invariant
325  block();
326  // Release reset lock
328  // Wait for reset cycle stopped
330  }
331 
332 
333 
334  /*
335  * Create no-goods
336  *
337  */
338  template<class Tracer>
339  NoGoods&
341  NoGoods* ng;
342  // Grab wait lock for reset
344  // Release workers for reset
345  release(C_RESET);
346  // Wait for reset cycle started
348  ng = &worker(0)->nogoods();
349  // Block workers again to ensure invariant
350  block();
351  // Release reset lock
353  // Wait for reset cycle stopped
355  return *ng;
356  }
357 
358 
359  /*
360  * Termination and deletion
361  */
362  template<class Tracer>
364  terminate();
365  heap.rfree(_worker);
366  }
367 
368 }}}
369 
370 // 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
void solution(Space *s)
Report solution s.
Definition: dfs.hpp:110
Worker(void)
Initialize.
Definition: worker.hh:74
void stop(void)
Report that worker has been stopped.
Definition: engine.hpp:176
void reset(Space *s, unsigned int ngdl)
Reset worker to restart at space s.
Definition: dfs.hpp:89
NodeType t
Type of node.
Definition: bool-expr.cpp:234
Space must be branched (at least one brancher left)
Definition: core.hpp:1610
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
DFS & engine(void) const
Provide access to engine.
Definition: dfs.hpp:45
virtual Statistics statistics(void) const
Return statistics.
Definition: dfs.hpp:153
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
Search engine options
Definition: search.hh:748
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
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
Gecode::IntSet d(v, 7)
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)
virtual NoGoods & nogoods(void)
Return no-goods.
Definition: dfs.hpp:340
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
void release(Cmd c)
Release all workers.
Definition: engine.hpp:83
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
Parallel depth-first search worker
Definition: dfs.hh:70
SearchTracer * tracer
Tracer object for tracing search.
Definition: search.hh:771
Parallel depth-first search engine
Definition: dfs.hh:47
Worker ** _worker
Array of worker references.
Definition: dfs.hh:95
const Options & opt(void) const
Provide access to search options.
Definition: engine.hpp:51
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:173
Support::DynamicQueue< Space *, Heap > solutions
Queue of solutions.
Definition: engine.hh:175
virtual void run(void)
Start execution of worker.
Definition: dfs.hpp:166
Choice for performing commit
Definition: core.hpp:1338
virtual ~DFS(void)
Destructor.
Definition: dfs.hpp:363
No-goods recorded from restarts.
Definition: core.hpp:1514
Heap heap
The single global heap.
Definition: heap.cpp:48
void find(void)
Try to find some work.
Definition: dfs.hpp:126
SpaceStatus status(StatusStatistics &stat=unused_status)
Query space status.
Definition: core.cpp:229
void idle(void)
Report that worker is idle.
Definition: engine.hpp:156
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
Tracer.
Definition: tracer.hpp:153
virtual void reset(Space *s)
Reset engine to restart at space s.
Definition: dfs.hpp:312
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
void invalidate(void)
Invalidate edge information (for stealing)
Definition: tracer.hpp:106
Space is failed
Definition: core.hpp:1608
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
DFS(Space *s, const Options &o)
Initialize for space s with options o.
Definition: dfs.hpp:64
Worker * worker(unsigned int i) const
Provide access to worker i.
Definition: dfs.hpp:50
void reset(void)
Reset.
Definition: statistics.hpp:43
Space is solved (no brancher left)
Definition: core.hpp:1609