Generated on Thu Apr 5 2018 19:44:19 for Gecode by doxygen 1.8.13
engine.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  /*
42  * Basic access routines
43  */
44  template<class Tracer>
45  forceinline Engine<Tracer>&
47  return _engine;
48  }
49  template<class Tracer>
50  forceinline const Options&
51  Engine<Tracer>::opt(void) const {
52  return _opt;
53  }
54  template<class Tracer>
55  forceinline unsigned int
57  return static_cast<unsigned int>(opt().threads);
58  }
59  template<class Tracer>
60  forceinline bool
62  return has_stopped;
63  }
64 
65 
66 
67  /*
68  * Engine: command and wait handling
69  */
70  template<class Tracer>
72  Engine<Tracer>::cmd(void) const {
73  return _cmd;
74  }
75  template<class Tracer>
76  forceinline void
78  _cmd = C_WAIT;
79  _m_wait.acquire();
80  }
81  template<class Tracer>
82  forceinline void
84  _cmd = c;
85  _m_wait.release();
86  }
87  template<class Tracer>
88  forceinline void
91  }
92 
93 
94  /*
95  * Engine: initialization
96  */
97  template<class Tracer>
100  : tracer(e.opt().tracer), _engine(e),
101  path(s == NULL ? 0 : e.opt().nogoods_limit), d(0),
102  idle(false) {
103  tracer.worker();
104  if (s != NULL) {
105  if (s->status(*this) == SS_FAILED) {
106  fail++;
107  cur = NULL;
108  if (!engine().opt().clone)
109  delete s;
110  } else {
111  cur = snapshot(s,engine().opt());
112  }
113  } else {
114  cur = NULL;
115  }
116  }
117 
118  template<class Tracer>
121  : _opt(o), solutions(heap) {
122  // Initialize termination information
125  // Initialize search information
126  n_busy = workers();
127  has_stopped = false;
128  // Initialize reset information
130  }
131 
132 
133  /*
134  * Statistics
135  */
136  template<class Tracer>
139  m.acquire();
140  Statistics s = *this;
141  m.release();
142  return s;
143  }
144 
145 
146  /*
147  * Engine: search control
148  */
149  template<class Tracer>
150  forceinline bool
152  return solutions.empty() && (n_busy > 0) && !has_stopped;
153  }
154  template<class Tracer>
155  forceinline void
157  m_search.acquire();
158  bool bs = signal();
159  n_busy--;
160  if (bs && (n_busy == 0))
161  e_search.signal();
162  m_search.release();
163  }
164 
165  template<class Tracer>
166  forceinline void
168  m_search.acquire();
169  assert(n_busy > 0);
170  n_busy++;
171  m_search.release();
172  }
173 
174  template<class Tracer>
175  forceinline void
177  m_search.acquire();
178  bool bs = signal();
179  has_stopped = true;
180  if (bs)
181  e_search.signal();
182  m_search.release();
183  }
184 
185 
186  /*
187  * Engine: termination control
188  */
189  template<class Tracer>
190  forceinline void
192  unsigned int n;
193  _m_term.acquire();
194  n = --_n_not_terminated;
195  _m_term.release();
196  // The signal must be outside of the look, otherwise a thread might be
197  // terminated that still holds a mutex.
198  if (n == 0)
200  }
201 
202  template<class Tracer>
203  forceinline void
205  _m_term.acquire();
206  if (--_n_term_not_ack == 0)
208  _m_term.release();
209  }
210 
211  template<class Tracer>
212  forceinline void
216  }
217 
218  template<class Tracer>
219  forceinline void
221  // Grab the wait mutex for termination
223  // Release all threads
225  // Wait until all threads have acknowledged termination request
226  _e_term_ack.wait();
227  // Release waiting threads
229  // Wait until all threads have in fact terminated
230  _e_terminate.wait();
231  // Now all threads are terminated!
232  }
233 
234  /*
235  * Engine: reset control
236  */
237  template<class Tracer>
238  forceinline void
240  _m_reset.acquire();
241  if (--_n_reset_not_ack == 0)
243  _m_reset.release();
244  }
245 
246  template<class Tracer>
247  forceinline void
249  _m_reset.acquire();
250  if (++_n_reset_not_ack == workers())
252  _m_reset.release();
253  }
254 
255  template<class Tracer>
256  forceinline void
260  }
261 
262 
263 
264  /*
265  * Worker: finding and stealing working
266  */
267  template<class Tracer>
269  Engine<Tracer>::Worker::steal(unsigned long int& d,
270  Tracer& myt, Tracer& ot) {
271  /*
272  * Make a quick check whether the worker might have work
273  *
274  * If that is not true any longer, the worker will be asked
275  * again eventually.
276  */
277  if (!path.steal())
278  return NULL;
279  m.acquire();
280  Space* s = path.steal(*this,d,myt,ot);
281  m.release();
282  // Tell that there will be one more busy worker
283  if (s != NULL)
284  engine().busy();
285  return s;
286  }
287 
288  /*
289  * Return No-Goods
290  */
291  template<class Tracer>
294  return path;
295  }
296 
297  /*
298  * Engine: search control
299  */
300  template<class Tracer>
301  Space*
303  // Invariant: the worker holds the wait mutex
304  m_search.acquire();
305  if (!solutions.empty()) {
306  // No search needs to be done, take leftover solution
307  Space* s = solutions.pop();
308  m_search.release();
309  return s;
310  }
311  // We ignore stopped (it will be reported again if needed)
312  has_stopped = false;
313  // No more solutions?
314  if (n_busy == 0) {
315  m_search.release();
316  return NULL;
317  }
318  m_search.release();
319  // Okay, now search has to continue, make the guys work
320  release(C_WORK);
321 
322  /*
323  * Wait until a search related event has happened. It might be that
324  * the event has already been signalled in the last run, but the
325  * solution has been removed. So we have to try until there has
326  * something new happened.
327  */
328  while (true) {
329  e_search.wait();
330  m_search.acquire();
331  if (!solutions.empty()) {
332  // Report solution
333  Space* s = solutions.pop();
334  m_search.release();
335  // Make workers wait again
336  block();
337  return s;
338  }
339  // No more solutions or stopped?
340  if ((n_busy == 0) || has_stopped) {
341  m_search.release();
342  // Make workers wait again
343  block();
344  return NULL;
345  }
346  m_search.release();
347  }
348  GECODE_NEVER;
349  return NULL;
350  }
351 
352  template<class Tracer>
355  return &_engine;
356  }
357 
358  /*
359  * Termination and deletion
360  */
361  template<class Tracer>
363  delete cur;
364  path.reset(0);
365  tracer.done();
366  }
367 
368 }}}
369 
370 // STATISTICS: search-par
virtual Space * next(void)
Return next solution (NULL, if none exists or search has been stopped)
Definition: engine.hpp:302
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
virtual ~Worker(void)
Destructor.
Definition: engine.hpp:362
void stop(void)
Report that worker has been stopped.
Definition: engine.hpp:176
void ack_terminate(void)
For worker to acknowledge termination command.
Definition: engine.hpp:204
Path< Tracer > path
Current path ins search tree.
Definition: engine.hh:63
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
void terminate(void)
For engine to peform thread termination.
Definition: engine.hpp:220
Search engine options
Definition: search.hh:748
volatile bool has_stopped
Whether a worker had been stopped.
Definition: engine.hh:179
void wait_terminate(void)
For worker to wait until termination is legal.
Definition: engine.hpp:213
bool signal(void) const
Whether search state changed such that signal is needed.
Definition: engine.hpp:151
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
Support::Mutex _m_term
Mutex for access to termination information.
Definition: engine.hh:123
unsigned long int fail
Number of failed nodes in search tree.
Definition: search.hh:152
Support::Mutex m_search
Mutex for search.
Definition: engine.hh:171
void ack_reset_stop(void)
For worker to acknowledge stop of reset cycle.
Definition: engine.hpp:248
#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
volatile unsigned int _n_reset_not_ack
Number of workers that have not yet acknowledged reset.
Definition: engine.hh:151
Computation spaces.
Definition: core.hpp:1668
Gecode::IntSet d(v, 7)
Cmd
Commands from engine to workers.
Definition: engine.hh:97
void release(void)
Release the mutex.
Definition: none.hpp:52
Gecode::FloatVal c(-8, 8)
double threads
Number of threads to use.
Definition: search.hh:753
int n
Number of negative literals for node type.
Definition: bool-expr.cpp:238
Space * cur
Current space being explored.
Definition: engine.hh:65
Engine(const Options &o)
Initialize with options o.
Definition: engine.hpp:120
Cmd cmd(void) const
Return current command.
Definition: engine.hpp:72
Options _opt
Search options.
Definition: engine.hh:87
void wait(void)
Ensure that worker waits.
Definition: engine.hpp:89
volatile unsigned int _n_term_not_ack
Number of workers that have not yet acknowledged termination.
Definition: engine.hh:125
Run into wait lock.
Definition: engine.hh:99
Support::Mutex m_wait_reset
Mutex for waiting for reset.
Definition: engine.hh:157
bool clone
Whether engines create a clone when being initialized.
Definition: search.hh:751
void release(Cmd c)
Release all workers.
Definition: engine.hpp:83
bool idle
Whether the worker is idle.
Definition: engine.hh:69
Space * steal(unsigned long int &d, Tracer &myt, Tracer &ot)
Hand over some work (NULL if no work available)
Definition: engine.hpp:269
Support::Mutex _m_reset
Mutex for access to reset information.
Definition: engine.hh:149
void busy(void)
Report that worker is busy.
Definition: engine.hpp:167
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
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
Support::Mutex _m_wait_terminate
Mutex for waiting for termination.
Definition: engine.hh:129
No-goods recorded from restarts.
Definition: core.hpp:1514
virtual bool stopped(void) const
Check whether engine has been stopped.
Definition: engine.hpp:61
Heap heap
The single global heap.
Definition: heap.cpp:48
Engine & engine(void) const
Provide access to engine.
Definition: engine.hpp:46
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
void wait_reset(void)
For worker to wait for all workers to reset.
Definition: engine.hpp:257
Tracer.
Definition: tracer.hpp:153
volatile Cmd _cmd
The current command.
Definition: engine.hh:105
NoGoods & nogoods(void)
Return no-goods.
Definition: engine.hpp:293
void ack_reset_start(void)
For worker to acknowledge start of reset cycle.
Definition: engine.hpp:239
An interface for objects that can be called after a thread has terminated (after running the thread&#39;s...
Definition: thread.hpp:254
Support::Event _e_terminate
Event for termination (all threads have terminated)
Definition: engine.hh:133
Gecode toplevel namespace
virtual void terminated(void)
For worker to register termination.
Definition: engine.hpp:191
const unsigned int nogoods_limit
Depth limit for no-good generation during search.
Definition: search.hh:133
volatile unsigned int n_busy
Number of busy workers.
Definition: engine.hh:177
volatile unsigned int _n_not_terminated
Number of not yet terminated workers.
Definition: engine.hh:131
Space * snapshot(Space *s, const Options &o)
Clone space s dependening on options o.
Definition: support.hh:75
Space is failed
Definition: core.hpp:1608
virtual Support::Terminator * terminator(void) const
Terminator (engine)
Definition: engine.hpp:354
void block(void)
Block all workers.
Definition: engine.hpp:77
Tracer tracer
Search tracer.
Definition: engine.hh:56
Support::Mutex _m_wait
Mutex for forcing workers to wait.
Definition: engine.hh:107
#define GECODE_NEVER
Assert that this command is never executed.
Definition: macros.hpp:60
Support::Event _e_term_ack
Event for termination acknowledgment.
Definition: engine.hh:127
void wait(void)
Wait until the event becomes signalled.
Definition: none.hpp:65