main page
modules
namespaces
classes
files
Gecode home
Generated on Mon Aug 27 2012 17:15:47 for Gecode by
doxygen
1.8.1.2
gecode
search
parallel
engine.hh
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: 2011-05-04 19:27:49 +1000 (Wed, 04 May 2011) $ by $Author: tack $
11
* $Revision: 11992 $
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
#ifndef __GECODE_SEARCH_PARALLEL_ENGINE_HH__
39
#define __GECODE_SEARCH_PARALLEL_ENGINE_HH__
40
41
#include <
gecode/search.hh
>
42
#include <
gecode/search/support.hh
>
43
#include <
gecode/search/worker.hh
>
44
#include <
gecode/search/parallel/path.hh
>
45
46
namespace
Gecode {
namespace
Search {
namespace
Parallel {
47
49
class
Engine
:
public
Search::Engine
{
50
protected
:
52
class
Worker
:
public
Search::Worker
,
public
Support::Runnable
{
53
protected
:
55
Engine
&
_engine
;
57
Support::Mutex
m
;
59
Path
path
;
61
Space
*
cur
;
63
unsigned
int
d
;
65
bool
idle
;
66
public
:
68
Worker
(
Space
* s,
size_t
sz,
Engine
& e);
70
Space
*
steal
(
unsigned
long
int
&
d
);
72
Statistics
statistics
(
void
);
74
Engine
&
engine
(
void
)
const
;
76
virtual
~Worker
(
void
);
77
};
79
const
Options
_opt
;
80
public
:
82
const
Options
&
opt
(
void
)
const
;
84
unsigned
int
workers
(
void
)
const
;
85
87
88
89
enum
Cmd
{
90
C_WORK
,
91
C_WAIT
,
92
C_RESET
,
93
C_TERMINATE
94
};
95
protected
:
97
volatile
Cmd
_cmd
;
99
Support::Mutex
_m_wait
;
100
public
:
102
Cmd
cmd
(
void
)
const
;
104
void
block
(
void
);
106
void
release
(
Cmd
c
);
108
void
wait
(
void
);
110
112
113
protected
:
115
Support::Mutex
_m_term
;
117
volatile
unsigned
int
_n_term_not_ack
;
119
Support::Event
_e_term_ack
;
121
Support::Mutex
_m_wait_terminate
;
123
volatile
unsigned
int
_n_not_terminated
;
125
Support::Event
_e_terminate
;
126
public
:
128
void
ack_terminate
(
void
);
130
void
terminated
(
void
);
132
void
wait_terminate
(
void
);
134
void
terminate
(
void
);
136
138
139
protected
:
141
Support::Mutex
_m_reset
;
143
volatile
unsigned
int
_n_reset_not_ack
;
145
Support::Event
e_reset_ack_start
;
147
Support::Event
e_reset_ack_stop
;
149
Support::Mutex
m_wait_reset
;
150
public
:
152
void
ack_reset_start
(
void
);
154
void
ack_reset_stop
(
void
);
156
void
wait_reset
(
void
);
158
160
161
protected
:
163
Support::Mutex
m_search
;
165
Support::Event
e_search
;
167
Support::DynamicQueue<Space*,Heap>
solutions
;
169
volatile
unsigned
int
n_busy
;
171
volatile
bool
has_stopped
;
173
bool
signal
(
void
)
const
;
174
public
:
176
void
idle
(
void
);
178
void
busy
(
void
);
180
void
stop
(
void
);
182
184
185
186
Engine
(
const
Options
& o);
188
virtual
Space
*
next
(
void
);
190
virtual
bool
stopped
(
void
)
const
;
192
};
193
194
195
/*
196
* Basic access routines
197
*/
198
forceinline
Engine
&
199
Engine::Worker::engine
(
void
)
const
{
200
return
_engine
;
201
}
202
forceinline
const
Options
&
203
Engine::opt
(
void
)
const
{
204
return
_opt
;
205
}
206
forceinline
unsigned
int
207
Engine::workers
(
void
)
const
{
208
return
static_cast<
unsigned
int
>
(
opt
().
threads
);
209
}
210
211
212
/*
213
* Engine: command and wait handling
214
*/
215
forceinline
Engine::Cmd
216
Engine::cmd
(
void
)
const
{
217
return
_cmd
;
218
}
219
forceinline
void
220
Engine::block
(
void
) {
221
_cmd
=
C_WAIT
;
222
_m_wait
.
acquire
();
223
}
224
forceinline
void
225
Engine::release
(
Cmd
c
) {
226
_cmd
=
c
;
227
_m_wait
.
release
();
228
}
229
forceinline
void
230
Engine::wait
(
void
) {
231
_m_wait
.
acquire
();
_m_wait
.
release
();
232
}
233
234
235
/*
236
* Engine: initialization
237
*/
238
forceinline
239
Engine::Worker::Worker
(
Space
* s,
size_t
sz,
Engine
& e)
240
: Search::
Worker
(sz), _engine(e),
d
(0),
idle
(false) {
241
current
(s);
242
if
(s != NULL) {
243
if
(s->
status
(*
this
) ==
SS_FAILED
) {
244
fail
++;
245
cur
= NULL;
246
if
(!
engine
().
opt
().
clone
)
247
delete
s;
248
}
else
{
249
cur
=
snapshot
(s,
engine
().
opt
(),
false
);
250
}
251
}
else
{
252
cur
= NULL;
253
}
254
current
(NULL);
255
current
(
cur
);
256
}
257
258
forceinline
259
Engine::Engine
(
const
Options
& o)
260
:
_opt
(o),
solutions
(
heap
) {
261
// Initialize termination information
262
_n_term_not_ack
=
workers
();
263
_n_not_terminated
=
workers
();
264
// Initialize search information
265
n_busy
=
workers
();
266
has_stopped
=
false
;
267
// Initialize reset information
268
_n_reset_not_ack
=
workers
();
269
}
270
271
272
/*
273
* Statistics
274
*/
275
forceinline
Statistics
276
Engine::Worker::statistics
(
void
) {
277
m
.
acquire
();
278
Statistics
s = *
this
;
279
s.
memory
+=
path
.
size
();
280
m
.
release
();
281
return
s;
282
}
283
284
285
/*
286
* Engine: search control
287
*/
288
forceinline
bool
289
Engine::signal
(
void
)
const
{
290
return
solutions
.
empty
() && (
n_busy
> 0) && !
has_stopped
;
291
}
292
forceinline
void
293
Engine::idle
(
void
) {
294
m_search
.
acquire
();
295
bool
bs =
signal
();
296
n_busy
--;
297
if
(bs && (
n_busy
== 0))
298
e_search
.
signal
();
299
m_search
.
release
();
300
}
301
forceinline
void
302
Engine::busy
(
void
) {
303
m_search
.
acquire
();
304
assert(
n_busy
> 0);
305
n_busy
++;
306
m_search
.
release
();
307
}
308
forceinline
void
309
Engine::stop
(
void
) {
310
m_search
.
acquire
();
311
bool
bs =
signal
();
312
has_stopped
=
true
;
313
if
(bs)
314
e_search
.
signal
();
315
m_search
.
release
();
316
}
317
318
319
/*
320
* Engine: termination control
321
*/
322
forceinline
void
323
Engine::terminated
(
void
) {
324
unsigned
int
n;
325
_m_term
.
acquire
();
326
n = --
_n_not_terminated
;
327
_m_term
.
release
();
328
// The signal must be outside of the look, otherwise a thread might be
329
// terminated that still holds a mutex.
330
if
(n == 0)
331
_e_terminate
.
signal
();
332
}
333
334
forceinline
void
335
Engine::ack_terminate
(
void
) {
336
_m_term
.
acquire
();
337
if
(--
_n_term_not_ack
== 0)
338
_e_term_ack
.
signal
();
339
_m_term
.
release
();
340
}
341
342
forceinline
void
343
Engine::wait_terminate
(
void
) {
344
_m_wait_terminate
.
acquire
();
345
_m_wait_terminate
.
release
();
346
}
347
348
forceinline
void
349
Engine::terminate
(
void
) {
350
// Grab the wait mutex for termination
351
_m_wait_terminate
.
acquire
();
352
// Release all threads
353
release
(
C_TERMINATE
);
354
// Wait until all threads have acknowledged termination request
355
_e_term_ack
.
wait
();
356
// Release waiting threads
357
_m_wait_terminate
.
release
();
358
// Wait until all threads have in fact terminated
359
_e_terminate
.
wait
();
360
// Now all threads are terminated!
361
}
362
363
364
365
/*
366
* Engine: reset control
367
*/
368
forceinline
void
369
Engine::ack_reset_start
(
void
) {
370
_m_reset
.
acquire
();
371
if
(--
_n_reset_not_ack
== 0)
372
e_reset_ack_start
.
signal
();
373
_m_reset
.
release
();
374
}
375
376
forceinline
void
377
Engine::ack_reset_stop
(
void
) {
378
_m_reset
.
acquire
();
379
if
(++
_n_reset_not_ack
==
workers
())
380
e_reset_ack_stop
.
signal
();
381
_m_reset
.
release
();
382
}
383
384
forceinline
void
385
Engine::wait_reset
(
void
) {
386
m_wait_reset
.
acquire
();
387
m_wait_reset
.
release
();
388
}
389
390
391
392
/*
393
* Worker: finding and stealing working
394
*/
395
forceinline
Space
*
396
Engine::Worker::steal
(
unsigned
long
int
&
d
) {
397
/*
398
* Make a quick check whether the worker might have work
399
*
400
* If that is not true any longer, the worker will be asked
401
* again eventually.
402
*/
403
if
(!
path
.steal())
404
return
NULL;
405
m
.acquire();
406
Space
* s =
path
.steal(*
this
,d);
407
m
.release();
408
// Tell that there will be one more busy worker
409
if
(s != NULL)
410
engine().busy();
411
return
s;
412
}
413
414
}}}
415
416
#endif
417
418
// STATISTICS: search-parallel