main page
modules
namespaces
classes
files
Gecode home
Generated on Tue Oct 22 2013 00:49:07 for Gecode by
doxygen
1.8.4
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: 2013-07-11 12:30:18 +0200 (Thu, 11 Jul 2013) $ by $Author: schulte $
11
* $Revision: 13840 $
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,
Engine
& e);
70
Space
*
steal
(
unsigned
long
int
&
d
);
72
Statistics
statistics
(
void
);
74
Engine
&
engine
(
void
)
const
;
76
NoGoods
&
nogoods
(
void
);
78
virtual
~Worker
(
void
);
79
};
81
const
Options
_opt
;
82
public
:
84
const
Options
&
opt
(
void
)
const
;
86
unsigned
int
workers
(
void
)
const
;
87
89
90
enum
Cmd
{
92
C_WORK
,
93
C_WAIT
,
94
C_RESET
,
95
C_TERMINATE
96
};
97
protected
:
99
volatile
Cmd
_cmd
;
101
Support::Mutex
_m_wait
;
102
public
:
104
Cmd
cmd
(
void
)
const
;
106
void
block
(
void
);
108
void
release
(
Cmd
c
);
110
void
wait
(
void
);
112
114
115
protected
:
117
Support::Mutex
_m_term
;
119
volatile
unsigned
int
_n_term_not_ack
;
121
Support::Event
_e_term_ack
;
123
Support::Mutex
_m_wait_terminate
;
125
volatile
unsigned
int
_n_not_terminated
;
127
Support::Event
_e_terminate
;
128
public
:
130
void
ack_terminate
(
void
);
132
void
terminated
(
void
);
134
void
wait_terminate
(
void
);
136
void
terminate
(
void
);
138
140
141
protected
:
143
Support::Mutex
_m_reset
;
145
volatile
unsigned
int
_n_reset_not_ack
;
147
Support::Event
e_reset_ack_start
;
149
Support::Event
e_reset_ack_stop
;
151
Support::Mutex
m_wait_reset
;
152
public
:
154
void
ack_reset_start
(
void
);
156
void
ack_reset_stop
(
void
);
158
void
wait_reset
(
void
);
160
162
163
protected
:
165
Support::Mutex
m_search
;
167
Support::Event
e_search
;
169
Support::DynamicQueue<Space*,Heap>
solutions
;
171
volatile
unsigned
int
n_busy
;
173
volatile
bool
has_stopped
;
175
bool
signal
(
void
)
const
;
176
public
:
178
void
idle
(
void
);
180
void
busy
(
void
);
182
void
stop
(
void
);
184
186
187
Engine
(
const
Options
& o);
190
virtual
Space
*
next
(
void
);
192
virtual
bool
stopped
(
void
)
const
;
194
};
195
196
197
/*
198
* Basic access routines
199
*/
200
forceinline
Engine
&
201
Engine::Worker::engine
(
void
)
const
{
202
return
_engine
;
203
}
204
forceinline
const
Options
&
205
Engine::opt
(
void
)
const
{
206
return
_opt
;
207
}
208
forceinline
unsigned
int
209
Engine::workers
(
void
)
const
{
210
return
static_cast<
unsigned
int
>
(
opt
().
threads
);
211
}
212
213
214
/*
215
* Engine: command and wait handling
216
*/
217
forceinline
Engine::Cmd
218
Engine::cmd
(
void
)
const
{
219
return
_cmd
;
220
}
221
forceinline
void
222
Engine::block
(
void
) {
223
_cmd
=
C_WAIT
;
224
_m_wait
.
acquire
();
225
}
226
forceinline
void
227
Engine::release
(
Cmd
c
) {
228
_cmd
=
c
;
229
_m_wait
.
release
();
230
}
231
forceinline
void
232
Engine::wait
(
void
) {
233
_m_wait
.
acquire
();
_m_wait
.
release
();
234
}
235
236
237
/*
238
* Engine: initialization
239
*/
240
forceinline
241
Engine::Worker::Worker
(
Space
* s,
Engine
& e)
242
: _engine(e),
243
path
(s == NULL ? 0 : static_cast<int>(e.
opt
().
nogoods_limit
)),
d
(0),
244
idle
(false) {
245
if
(s != NULL) {
246
if
(s->
status
(*
this
) ==
SS_FAILED
) {
247
fail
++;
248
cur
= NULL;
249
if
(!
engine
().
opt
().
clone
)
250
delete
s;
251
}
else
{
252
cur
=
snapshot
(s,
engine
().
opt
(),
false
);
253
}
254
}
else
{
255
cur
= NULL;
256
}
257
}
258
259
forceinline
260
Engine::Engine
(
const
Options
& o)
261
:
_opt
(o),
solutions
(
heap
) {
262
// Initialize termination information
263
_n_term_not_ack
=
workers
();
264
_n_not_terminated
=
workers
();
265
// Initialize search information
266
n_busy
=
workers
();
267
has_stopped
=
false
;
268
// Initialize reset information
269
_n_reset_not_ack
=
workers
();
270
}
271
272
273
/*
274
* Statistics
275
*/
276
forceinline
Statistics
277
Engine::Worker::statistics
(
void
) {
278
m
.
acquire
();
279
Statistics
s = *
this
;
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
* Return No-Goods
416
*/
417
forceinline
NoGoods
&
418
Engine::Worker::nogoods
(
void
) {
419
return
path
;
420
}
421
422
}}}
423
424
#endif
425
426
// STATISTICS: search-parallel