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