main page
modules
namespaces
classes
files
Gecode home
Generated on Sat May 25 2013 18:00:40 for Gecode by
doxygen
1.8.3.1
gecode
search
parallel
path.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, 2003
8
*
9
* Last modified:
10
* $Date: 2013-02-26 10:47:43 +0100 (Tue, 26 Feb 2013) $ by $Author: schulte $
11
* $Revision: 13414 $
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_PATH_HH__
39
#define __GECODE_SEARCH_PARALLEL_PATH_HH__
40
41
#include <
gecode/search.hh
>
42
43
namespace
Gecode {
namespace
Search {
namespace
Parallel {
44
58
class
Path
{
59
public
:
61
class
Edge
{
62
protected
:
64
Space
*
_space
;
66
unsigned
int
_alt
;
68
unsigned
int
_alt_max
;
70
const
Choice
*
_choice
;
71
public
:
73
Edge
(
void
);
75
Edge
(
Space
* s,
Space
*
c
);
76
78
Space
*
space
(
void
)
const
;
80
void
space
(
Space
* s);
81
83
const
Choice
*
choice
(
void
)
const
;
84
86
unsigned
int
alt
(
void
)
const
;
88
bool
rightmost
(
void
)
const
;
90
bool
lao
(
void
)
const
;
92
bool
work
(
void
)
const
;
94
void
next
(
void
);
96
unsigned
int
steal
(
void
);
97
99
void
dispose
(
void
);
100
};
101
protected
:
103
Support::DynamicStack<Edge,Heap>
ds
;
105
unsigned
int
n_work
;
106
public
:
108
Path
(
void
);
110
const
Choice
*
push
(
Worker
& stat,
Space
* s,
Space
*
c
);
112
bool
next
(
Worker
& s);
114
Edge
&
top
(
void
)
const
;
116
bool
empty
(
void
)
const
;
118
int
lc
(
void
)
const
;
120
void
unwind
(
int
l
);
122
void
commit
(
Space
* s,
int
i
)
const
;
124
Space
*
recompute
(
unsigned
int
&
d
,
unsigned
int
a_d
,
Worker
& s);
126
Space
*
recompute
(
unsigned
int
&
d
,
unsigned
int
a_d
,
Worker
& s,
127
const
Space
* best,
int
&
mark
);
129
int
entries
(
void
)
const
;
131
size_t
size
(
void
)
const
;
133
void
reset
(
void
);
135
bool
steal
(
void
)
const
;
137
Space
*
steal
(
Worker
& stat,
unsigned
long
int
&
d
);
138
};
139
140
141
/*
142
* Edge for recomputation
143
*
144
*/
145
forceinline
146
Path::Edge::Edge
(
void
) {}
147
148
forceinline
149
Path::Edge::Edge
(
Space
* s,
Space
*
c
)
150
: _space(c), _alt(0), _choice(s->choice()) {
151
_alt_max
=
_choice
->
alternatives
()-1;
152
}
153
154
forceinline
Space
*
155
Path::Edge::space
(
void
)
const
{
156
return
_space;
157
}
158
forceinline
void
159
Path::Edge::space
(
Space
* s) {
160
_space = s;
161
}
162
163
forceinline
unsigned
int
164
Path::Edge::alt
(
void
)
const
{
165
return
_alt;
166
}
167
forceinline
bool
168
Path::Edge::rightmost
(
void
)
const
{
169
return
_alt >= _alt_max;
170
}
171
forceinline
bool
172
Path::Edge::lao
(
void
)
const
{
173
return
_alt > _alt_max;
174
}
175
forceinline
bool
176
Path::Edge::work
(
void
)
const
{
177
return
_alt < _alt_max;
178
}
179
forceinline
void
180
Path::Edge::next
(
void
) {
181
_alt++;
182
}
183
forceinline
unsigned
int
184
Path::Edge::steal
(
void
) {
185
assert(work());
186
return
_alt_max--;
187
}
188
189
forceinline
const
Choice
*
190
Path::Edge::choice
(
void
)
const
{
191
return
_choice;
192
}
193
194
forceinline
void
195
Path::Edge::dispose
(
void
) {
196
delete
_space;
197
delete
_choice;
198
}
199
200
201
202
/*
203
* Depth-first stack with recomputation
204
*
205
*/
206
207
forceinline
208
Path::Path
(
void
) :
ds
(
heap
),
n_work
(0) {}
209
210
forceinline
const
Choice
*
211
Path::push
(
Worker
& stat,
Space
* s,
Space
*
c
) {
212
if
(!
ds
.empty() &&
ds
.top().lao()) {
213
// Topmost stack entry was LAO -> reuse
214
stat.
pop
(
ds
.top().space(),
ds
.top().choice());
215
ds
.pop().dispose();
216
}
217
Edge
sn(s,c);
218
if
(sn.
work
())
219
n_work
++;
220
ds
.push(sn);
221
stat.
stack_depth
(static_cast<unsigned long int>(
ds
.entries()));
222
return
sn.
choice
();
223
}
224
225
forceinline
bool
226
Path::next
(
Worker
& stat) {
227
while
(!
ds
.empty())
228
if
(
ds
.top().rightmost()) {
229
stat.
pop
(
ds
.top().space(),
ds
.top().choice());
230
ds
.pop().dispose();
231
}
else
{
232
assert(
ds
.top().work());
233
ds
.top().next();
234
if
(!
ds
.top().work())
235
n_work
--;
236
return
true
;
237
}
238
return
false
;
239
}
240
241
forceinline
Path::Edge
&
242
Path::top
(
void
)
const
{
243
assert(!
ds
.empty());
244
return
ds
.top();
245
}
246
247
forceinline
bool
248
Path::empty
(
void
)
const
{
249
return
ds
.empty();
250
}
251
252
forceinline
void
253
Path::commit
(
Space
* s,
int
i
)
const
{
254
const
Edge
&
n
=
ds
[
i
];
255
s->
commit
(*n.
choice
(),n.
alt
());
256
}
257
258
forceinline
int
259
Path::lc
(
void
)
const
{
260
int
l
=
ds
.entries()-1;
261
while
(
ds
[l].space() == NULL)
262
l--;
263
return
l
;
264
}
265
266
forceinline
int
267
Path::entries
(
void
)
const
{
268
return
ds
.entries();
269
}
270
271
forceinline
size_t
272
Path::size
(
void
)
const
{
273
return
ds
.size();
274
}
275
276
forceinline
void
277
Path::unwind
(
int
l
) {
278
assert((
ds
[l].space() == NULL) ||
ds
[l].space()->failed());
279
int
n
=
ds
.entries();
280
for
(
int
i
=l;
i
<
n
;
i
++) {
281
if
(
ds
.top().work())
282
n_work
--;
283
ds
.pop().dispose();
284
}
285
assert(
ds
.entries() ==
l
);
286
}
287
288
forceinline
void
289
Path::reset
(
void
) {
290
n_work
= 0;
291
while
(!
ds
.empty())
292
ds
.pop().dispose();
293
}
294
295
forceinline
bool
296
Path::steal
(
void
)
const
{
297
return
n_work
>
Config::steal_limit
;
298
}
299
300
forceinline
Space
*
301
Path::steal
(
Worker
& stat,
unsigned
long
int
&
d
) {
302
// Find position to steal: leave sufficient work
303
int
n
=
ds
.entries()-1;
304
unsigned
int
w = 0;
305
while
(n >= 0) {
306
if
(
ds
[n].work())
307
w++;
308
if
(w >
Config::steal_limit
) {
309
// Okay, there is sufficient work left
310
int
l
=
n
;
311
// Find last copy
312
while
(
ds
[l].space() == NULL)
313
l--;
314
Space
*
c
=
ds
[
l
].space()->clone(
false
);
315
// Recompute, if necessary
316
for
(
int
i
=l;
i
<
n
;
i
++)
317
commit
(c,
i
);
318
c->
commit
(*
ds
[n].choice(),
ds
[n].
steal
());
319
if
(!
ds
[n].work())
320
n_work
--;
321
d = stat.
steal_depth
(static_cast<unsigned long int>(n+1));
322
return
c
;
323
}
324
n--;
325
}
326
return
NULL;
327
}
328
329
forceinline
Space
*
330
Path::recompute
(
unsigned
int
&
d
,
unsigned
int
a_d
,
Worker
& stat) {
331
assert(!
ds
.empty());
332
// Recompute space according to path
333
// Also say distance to copy (d == 0) requires immediate copying
334
335
// Check for LAO
336
if
((
ds
.top().space() != NULL) &&
ds
.top().rightmost()) {
337
Space
* s =
ds
.top().space();
338
stat.
lao
(s);
339
s->
commit
(*
ds
.top().choice(),
ds
.top().alt());
340
assert(
ds
.entries()-1 ==
lc
());
341
ds
.top().space(NULL);
342
// Mark as reusable
343
ds
.top().next();
344
d = 0;
345
return
s;
346
}
347
// General case for recomputation
348
int
l
=
lc
();
// Position of last clone
349
int
n
=
ds
.entries();
// Number of stack entries
350
// New distance, if no adaptive recomputation
351
d =
static_cast<
unsigned
int
>
(n -
l
);
352
353
Space
* s =
ds
[
l
].space()->clone();
// Last clone
354
355
if
(d < a_d) {
356
// No adaptive recomputation
357
for
(
int
i
=l;
i
<
n
;
i
++)
358
commit
(s,
i
);
359
}
else
{
360
int
m = l +
static_cast<
int
>
(d >> 1);
// Middle between copy and top
361
int
i
=
l
;
// To iterate over all entries
362
// Recompute up to middle
363
for
(; i<m; i++ )
364
commit
(s,i);
365
// Skip over all rightmost branches
366
for
(; (i<
n
) &&
ds
[i].rightmost(); i++)
367
commit
(s,i);
368
// Is there any point to make a copy?
369
if
(i<n-1) {
370
// Propagate to fixpoint
371
SpaceStatus
ss = s->
status
(stat);
372
/*
373
* Again, the space might already propagate to failure (due to
374
* weakly monotonic propagators).
375
*/
376
if
(ss ==
SS_FAILED
) {
377
// s must be deleted as it is not on the stack
378
delete
s;
379
stat.
fail
++;
380
unwind
(i);
381
return
NULL;
382
}
383
ds
[
i
].space(s->
clone
());
384
stat.
adapt
(
ds
[i].space());
385
d =
static_cast<
unsigned
int
>
(n-
i
);
386
}
387
// Finally do the remaining commits
388
for
(; i<
n
; i++)
389
commit
(s,i);
390
}
391
return
s;
392
}
393
394
forceinline
Space
*
395
Path::recompute
(
unsigned
int
&
d
,
unsigned
int
a_d
,
Worker
& stat,
396
const
Space
* best,
int
&
mark
) {
397
assert(!
ds
.empty());
398
// Recompute space according to path
399
// Also say distance to copy (d == 0) requires immediate copying
400
401
// Check for LAO
402
if
((
ds
.top().space() != NULL) &&
ds
.top().rightmost()) {
403
Space
* s =
ds
.top().space();
404
stat.
lao
(s);
405
s->
commit
(*
ds
.top().choice(),
ds
.top().alt());
406
assert(
ds
.entries()-1 ==
lc
());
407
if
(mark >
ds
.entries()-1) {
408
mark =
ds
.entries()-1;
409
s->
constrain
(*best);
410
}
411
ds
.top().space(NULL);
412
// Mark as reusable
413
ds
.top().next();
414
d = 0;
415
return
s;
416
}
417
// General case for recomputation
418
int
l
=
lc
();
// Position of last clone
419
int
n
=
ds
.entries();
// Number of stack entries
420
// New distance, if no adaptive recomputation
421
d =
static_cast<
unsigned
int
>
(n -
l
);
422
423
Space
* s =
ds
[
l
].space();
// Last clone
424
425
if
(l < mark) {
426
mark =
l
;
427
s->
constrain
(*best);
428
// The space on the stack could be failed now as an additional
429
// constraint might have been added.
430
if
(s->
status
(stat) ==
SS_FAILED
) {
431
// s does not need deletion as it is on the stack (unwind does this)
432
stat.
fail
++;
433
unwind
(l);
434
return
NULL;
435
}
436
// It is important to replace the space on the stack with the
437
// copy: a copy might be much smaller due to flushed caches
438
// of propagators
439
Space
*
c
= s->
clone
();
440
ds
[
l
].space(c);
441
stat.
constrained
(s,c);
442
}
else
{
443
s = s->
clone
();
444
}
445
446
if
(d < a_d) {
447
// No adaptive recomputation
448
for
(
int
i
=l;
i
<
n
;
i
++)
449
commit
(s,
i
);
450
}
else
{
451
int
m = l +
static_cast<
int
>
(d >> 1);
// Middle between copy and top
452
int
i
=
l
;
// To iterate over all entries
453
// Recompute up to middle
454
for
(; i<m; i++ )
455
commit
(s,i);
456
// Skip over all rightmost branches
457
for
(; (i<
n
) &&
ds
[i].rightmost(); i++)
458
commit
(s,i);
459
// Is there any point to make a copy?
460
if
(i<n-1) {
461
// Propagate to fixpoint
462
SpaceStatus
ss = s->
status
(stat);
463
/*
464
* Again, the space might already propagate to failure
465
*
466
* This can be for two reasons:
467
* - constrain is true, so we fail
468
* - the space has weakly monotonic propagators
469
*/
470
if
(ss ==
SS_FAILED
) {
471
// s must be deleted as it is not on the stack
472
delete
s;
473
stat.
fail
++;
474
unwind
(i);
475
return
NULL;
476
}
477
ds
[
i
].space(s->
clone
());
478
stat.
adapt
(
ds
[i].space());
479
d =
static_cast<
unsigned
int
>
(n-
i
);
480
}
481
// Finally do the remaining commits
482
for
(; i<
n
; i++)
483
commit
(s,i);
484
}
485
return
s;
486
}
487
488
}}}
489
490
#endif
491
492
// STATISTICS: search-parallel