this repo has no description
dekker.one
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>&
42 Engine<Tracer>::Worker::engine(void) const {
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
52 Engine<Tracer>::workers(void) const {
53 return static_cast<unsigned int>(opt().threads);
54 }
55 template<class Tracer>
56 forceinline bool
57 Engine<Tracer>::stopped(void) const {
58 return has_stopped;
59 }
60
61
62
63 /*
64 * Engine: command and wait handling
65 */
66 template<class Tracer>
67 forceinline typename Engine<Tracer>::Cmd
68 Engine<Tracer>::cmd(void) const {
69 return _cmd;
70 }
71 template<class Tracer>
72 forceinline void
73 Engine<Tracer>::block(void) {
74 _cmd = C_WAIT;
75 Support::Thread::acquireGlobalMutex(&_m_wait);
76 }
77 template<class Tracer>
78 forceinline void
79 Engine<Tracer>::release(Cmd c) {
80 _cmd = c;
81 Support::Thread::releaseGlobalMutex(&_m_wait);
82 }
83 template<class Tracer>
84 forceinline void
85 Engine<Tracer>::wait(void) {
86 _m_wait.acquire(); _m_wait.release();
87 }
88
89
90 /*
91 * Engine: initialization
92 */
93 template<class Tracer>
94 forceinline
95 Engine<Tracer>::Worker::Worker(Space* s, Engine& e)
96 : tracer(e.opt().tracer), _engine(e),
97 path(s == nullptr ? 0 : e.opt().nogoods_limit), d(0),
98 idle(false) {
99 tracer.worker();
100 if (s != nullptr) {
101 if (s->status(*this) == SS_FAILED) {
102 fail++;
103 cur = nullptr;
104 if (!engine().opt().clone)
105 delete s;
106 } else {
107 cur = snapshot(s,engine().opt());
108 }
109 } else {
110 cur = nullptr;
111 }
112 }
113
114 template<class Tracer>
115 forceinline
116 Engine<Tracer>::Engine(const Options& o)
117 : _opt(o), solutions(heap) {
118 // Initialize termination information
119 _n_term_not_ack = workers();
120 _n_not_terminated = workers();
121 // Initialize search information
122 n_busy = workers();
123 has_stopped = false;
124 // Initialize reset information
125 _n_reset_not_ack = workers();
126 }
127
128
129 /*
130 * Statistics
131 */
132 template<class Tracer>
133 forceinline Statistics
134 Engine<Tracer>::Worker::statistics(void) {
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
147 Engine<Tracer>::signal(void) const {
148 return solutions.empty() && (n_busy > 0) && !has_stopped;
149 }
150 template<class Tracer>
151 forceinline void
152 Engine<Tracer>::idle(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
163 Engine<Tracer>::busy(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
172 Engine<Tracer>::stop(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
187 Engine<Tracer>::terminated(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)
195 _e_terminate.signal();
196 }
197
198 template<class Tracer>
199 forceinline void
200 Engine<Tracer>::ack_terminate(void) {
201 _m_term.acquire();
202 if (--_n_term_not_ack == 0)
203 _e_term_ack.signal();
204 _m_term.release();
205 }
206
207 template<class Tracer>
208 forceinline void
209 Engine<Tracer>::wait_terminate(void) {
210 _m_wait_terminate.acquire();
211 _m_wait_terminate.release();
212 }
213
214 template<class Tracer>
215 forceinline void
216 Engine<Tracer>::terminate(void) {
217 // Grab the wait mutex for termination
218 _m_wait_terminate.acquire();
219 // Release all threads
220 release(C_TERMINATE);
221 // Wait until all threads have acknowledged termination request
222 _e_term_ack.wait();
223 // Release waiting threads
224 _m_wait_terminate.release();
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
235 Engine<Tracer>::ack_reset_start(void) {
236 _m_reset.acquire();
237 if (--_n_reset_not_ack == 0)
238 e_reset_ack_start.signal();
239 _m_reset.release();
240 }
241
242 template<class Tracer>
243 forceinline void
244 Engine<Tracer>::ack_reset_stop(void) {
245 _m_reset.acquire();
246 if (++_n_reset_not_ack == workers())
247 e_reset_ack_stop.signal();
248 _m_reset.release();
249 }
250
251 template<class Tracer>
252 forceinline void
253 Engine<Tracer>::wait_reset(void) {
254 m_wait_reset.acquire();
255 m_wait_reset.release();
256 }
257
258
259
260 /*
261 * Worker: finding and stealing working
262 */
263 template<class Tracer>
264 forceinline Space*
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 nullptr;
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 != nullptr)
280 engine().busy();
281 return s;
282 }
283
284 /*
285 * Return No-Goods
286 */
287 template<class Tracer>
288 forceinline NoGoods&
289 Engine<Tracer>::Worker::nogoods(void) {
290 return path;
291 }
292
293 /*
294 * Engine: search control
295 */
296 template<class Tracer>
297 Space*
298 Engine<Tracer>::next(void) {
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 nullptr;
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 nullptr;
341 }
342 m_search.release();
343 }
344 GECODE_NEVER;
345 return nullptr;
346 }
347
348 template<class Tracer>
349 Support::Terminator*
350 Engine<Tracer>::Worker::terminator(void) const {
351 return &_engine;
352 }
353
354 /*
355 * Termination and deletion
356 */
357 template<class Tracer>
358 Engine<Tracer>::Worker::~Worker(void) {
359 delete cur;
360 path.reset(0);
361 tracer.done();
362 }
363
364}}}
365
366// STATISTICS: search-par