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