Generated on Tue Feb 11 2025 17:33:26 for Gecode by doxygen 1.12.0
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
34namespace 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
77 template<class Tracer>
78 forceinline void
83 template<class Tracer>
84 forceinline void
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
154 bool bs = signal();
155 n_busy--;
156 if (bs && (n_busy == 0))
159 }
160
161 template<class Tracer>
162 forceinline void
165 assert(n_busy > 0);
166 n_busy++;
168 }
169
170 template<class Tracer>
171 forceinline void
174 bool bs = signal();
175 has_stopped = true;
176 if (bs)
179 }
180
181
182 /*
183 * Engine: termination control
184 */
185 template<class Tracer>
186 forceinline void
188 unsigned int n;
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
206
207 template<class Tracer>
208 forceinline void
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
223 // Release waiting threads
225 // Wait until all threads have in fact terminated
227 // Now all threads are terminated!
228 }
229
230 /*
231 * Engine: reset control
232 */
233 template<class Tracer>
234 forceinline void
241
242 template<class Tracer>
243 forceinline void
250
251 template<class Tracer>
252 forceinline void
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
301 if (!solutions.empty()) {
302 // No search needs to be done, take leftover solution
303 Space* s = solutions.pop();
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) {
312 return NULL;
313 }
315 // Okay, now search has to continue, make the guys 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();
327 if (!solutions.empty()) {
328 // Report solution
329 Space* s = solutions.pop();
331 // Make workers wait again
332 block();
333 return s;
334 }
335 // No more solutions or stopped?
336 if ((n_busy == 0) || has_stopped) {
338 // Make workers wait again
339 block();
340 return NULL;
341 }
343 }
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
int n
Number of negative literals for node type.
No-goods recorded from restarts.
Definition core.hpp:1588
Search engine options
Definition search.hh:746
double threads
Number of threads to use.
Definition search.hh:751
Support::Mutex m
Mutex for access to worker.
Definition engine.hh:57
Engine & _engine
Reference to engine.
Definition engine.hh:55
NoGoods & nogoods(void)
Return no-goods.
Definition engine.hpp:289
Statistics statistics(void)
Return statistics.
Definition engine.hpp:134
Space * cur
Current space being explored.
Definition engine.hh:61
virtual ~Worker(void)
Destructor.
Definition engine.hpp:358
Tracer tracer
Search tracer.
Definition engine.hh:52
Space * steal(unsigned long int &d, Tracer &myt, Tracer &ot)
Hand over some work (NULL if no work available)
Definition engine.hpp:265
virtual Support::Terminator * terminator(void) const
Terminator (engine)
Definition engine.hpp:350
Engine & engine(void) const
Provide access to engine.
Definition engine.hpp:42
Parallel depth-first search engine
Definition engine.hh:46
void idle(void)
Report that worker is idle.
Definition engine.hpp:152
void wait(void)
Ensure that worker waits.
Definition engine.hpp:85
Support::Event _e_terminate
Event for termination (all threads have terminated)
Definition engine.hh:129
void ack_reset_stop(void)
For worker to acknowledge stop of reset cycle.
Definition engine.hpp:244
const Options & opt(void) const
Provide access to search options.
Definition engine.hpp:47
Support::Mutex _m_wait_terminate
Mutex for waiting for termination.
Definition engine.hh:125
Support::Event e_reset_ack_stop
Event for reset acknowledgment stopped.
Definition engine.hh:151
Support::Mutex _m_wait
Mutex for forcing workers to wait.
Definition engine.hh:103
Support::Event e_search
Event for search (solution found, no more solutions, search stopped)
Definition engine.hh:169
volatile bool has_stopped
Whether a worker had been stopped.
Definition engine.hh:175
virtual Space * next(void)
Return next solution (NULL, if none exists or search has been stopped)
Definition engine.hpp:298
Support::Event _e_term_ack
Event for termination acknowledgment.
Definition engine.hh:123
Support::DynamicQueue< Space *, Heap > solutions
Queue of solutions.
Definition engine.hh:171
virtual bool stopped(void) const
Check whether engine has been stopped.
Definition engine.hpp:57
void stop(void)
Report that worker has been stopped.
Definition engine.hpp:172
void block(void)
Block all workers.
Definition engine.hpp:73
Support::Mutex m_wait_reset
Mutex for waiting for reset.
Definition engine.hh:153
Support::Mutex m_search
Mutex for search.
Definition engine.hh:167
Support::Event e_reset_ack_start
Event for reset acknowledgment started.
Definition engine.hh:149
Support::Mutex _m_term
Mutex for access to termination information.
Definition engine.hh:119
Cmd cmd(void) const
Return current command.
Definition engine.hpp:68
Engine(const Options &o)
Initialize with options o.
Definition engine.hpp:116
Options _opt
Search options.
Definition engine.hh:83
void busy(void)
Report that worker is busy.
Definition engine.hpp:163
volatile Cmd _cmd
The current command.
Definition engine.hh:101
volatile unsigned int _n_reset_not_ack
Number of workers that have not yet acknowledged reset.
Definition engine.hh:147
void release(Cmd c)
Release all workers.
Definition engine.hpp:79
bool signal(void) const
Whether search state changed such that signal is needed.
Definition engine.hpp:147
void ack_reset_start(void)
For worker to acknowledge start of reset cycle.
Definition engine.hpp:235
volatile unsigned int _n_term_not_ack
Number of workers that have not yet acknowledged termination.
Definition engine.hh:121
void wait_reset(void)
For worker to wait for all workers to reset.
Definition engine.hpp:253
volatile unsigned int _n_not_terminated
Number of not yet terminated workers.
Definition engine.hh:127
virtual void terminated(void)
For worker to register termination.
Definition engine.hpp:187
void terminate(void)
For engine to peform thread termination.
Definition engine.hpp:216
Support::Mutex _m_reset
Mutex for access to reset information.
Definition engine.hh:145
volatile unsigned int n_busy
Number of busy workers.
Definition engine.hh:173
void wait_terminate(void)
For worker to wait until termination is legal.
Definition engine.hpp:209
unsigned int workers(void) const
Return number of workers.
Definition engine.hpp:52
Cmd
Commands from engine to workers.
Definition engine.hh:93
@ C_WORK
Perform work.
Definition engine.hh:94
@ C_WAIT
Run into wait lock.
Definition engine.hh:95
void ack_terminate(void)
For worker to acknowledge termination command.
Definition engine.hpp:200
Search engine statistics
Definition search.hh:147
unsigned long int fail
Number of failed nodes in search tree.
Definition search.hh:150
Worker(void)
Initialize.
Definition worker.hh:70
Computation spaces.
Definition core.hpp:1742
void wait(void)
Wait until the event becomes signalled.
Definition none.hpp:61
void signal(void)
Signal the event.
Definition none.hpp:59
void release(void)
Release the mutex.
Definition none.hpp:48
void acquire(void)
Acquire the mutex and possibly block.
Definition none.hpp:42
An interface for objects that can be called after a thread has terminated (after running the thread's...
Definition thread.hpp:251
Heap heap
The single global heap.
Definition heap.cpp:44
SpaceStatus status(StatusStatistics &stat=unused_status)
Query space status.
Definition core.cpp:252
@ SS_FAILED
Space is failed
Definition core.hpp:1682
Space * snapshot(Space *s, const Options &o)
Clone space s dependening on options o.
Definition support.hh:71
Gecode toplevel namespace
void path(Home home, const IntVarArgs &x, IntVar s, IntVar e, IntPropLevel ipl=IPL_DEF)
Post propagator such that x forms a Hamiltonian path.
Definition circuit.cpp:169
#define forceinline
Definition config.hpp:187
#define GECODE_NEVER
Assert that this command is never executed.
Definition macros.hpp:56