Generated on Tue Sep 16 2014 20:36:49 for Gecode by doxygen 1.8.8
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-07-12 18:20:11 +0200 (Fri, 12 Jul 2013) $ by $Author: schulte $
11  * $Revision: 13877 $
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 #include <gecode/search/support.hh>
43 #include <gecode/search/worker.hh>
45 
46 namespace Gecode { namespace Search { namespace Parallel {
47 
61  class Path : public NoGoods {
63  public:
65  class Edge {
66  protected:
70  unsigned int _alt;
72  unsigned int _alt_max;
74  const Choice* _choice;
75  public:
77  Edge(void);
79  Edge(Space* s, Space* c);
80 
82  Space* space(void) const;
84  void space(Space* s);
85 
87  const Choice* choice(void) const;
88 
90  unsigned int alt(void) const;
92  unsigned int truealt(void) const;
94  bool rightmost(void) const;
96  bool lao(void) const;
98  bool work(void) const;
100  void next(void);
102  unsigned int steal(void);
103 
105  void dispose(void);
106  };
107  protected:
111  int _ngdl;
113  unsigned int n_work;
114  public:
116  Path(int l);
118  int ngdl(void) const;
120  void ngdl(int l);
122  const Choice* push(Worker& stat, Space* s, Space* c);
124  bool next(void);
126  Edge& top(void) const;
128  bool empty(void) const;
130  int lc(void) const;
132  void unwind(int l);
134  void commit(Space* s, int i) const;
136  Space* recompute(unsigned int& d, unsigned int a_d, Worker& s);
138  Space* recompute(unsigned int& d, unsigned int a_d, Worker& s,
139  const Space* best, int& mark);
141  int entries(void) const;
143  void reset(int l);
145  bool steal(void) const;
147  Space* steal(Worker& stat, unsigned long int& d);
149  void virtual post(Space& home);
150  };
151 
152 
153  /*
154  * Edge for recomputation
155  *
156  */
159 
162  : _space(c), _alt(0), _choice(s->choice()) {
164  }
165 
167  Path::Edge::space(void) const {
168  return _space;
169  }
170  forceinline void
172  _space = s;
173  }
174 
175  forceinline unsigned int
176  Path::Edge::alt(void) const {
177  return _alt;
178  }
179  forceinline unsigned int
180  Path::Edge::truealt(void) const {
181  assert(_alt < _choice->alternatives());
182  return _alt;
183  }
184  forceinline bool
185  Path::Edge::rightmost(void) const {
186  return _alt >= _alt_max;
187  }
188  forceinline bool
189  Path::Edge::lao(void) const {
190  return _alt > _alt_max;
191  }
192  forceinline bool
193  Path::Edge::work(void) const {
194  return _alt < _alt_max;
195  }
196  forceinline void
198  _alt++;
199  }
200  forceinline unsigned int
202  assert(work());
203  return _alt_max--;
204  }
205 
206  forceinline const Choice*
207  Path::Edge::choice(void) const {
208  return _choice;
209  }
210 
211  forceinline void
213  delete _space;
214  delete _choice;
215  }
216 
217 
218 
219  /*
220  * Depth-first stack with recomputation
221  *
222  */
223 
225  Path::Path(int l)
226  : ds(heap), _ngdl(l), n_work(0) {}
227 
228  forceinline int
229  Path::ngdl(void) const {
230  return _ngdl;
231  }
232 
233  forceinline void
234  Path::ngdl(int l) {
235  _ngdl = l;
236  }
237 
238  forceinline const Choice*
239  Path::push(Worker& stat, Space* s, Space* c) {
240  if (!ds.empty() && ds.top().lao()) {
241  // Topmost stack entry was LAO -> reuse
242  ds.pop().dispose();
243  }
244  Edge sn(s,c);
245  if (sn.work())
246  n_work++;
247  ds.push(sn);
248  stat.stack_depth(static_cast<unsigned long int>(ds.entries()));
249  return sn.choice();
250  }
251 
252  forceinline bool
253  Path::next(void) {
254  while (!ds.empty())
255  if (ds.top().rightmost()) {
256  ds.pop().dispose();
257  } else {
258  assert(ds.top().work());
259  ds.top().next();
260  if (!ds.top().work())
261  n_work--;
262  return true;
263  }
264  return false;
265  }
266 
268  Path::top(void) const {
269  assert(!ds.empty());
270  return ds.top();
271  }
272 
273  forceinline bool
274  Path::empty(void) const {
275  return ds.empty();
276  }
277 
278  forceinline void
279  Path::commit(Space* s, int i) const {
280  const Edge& n = ds[i];
281  s->commit(*n.choice(),n.alt());
282  }
283 
284  forceinline int
285  Path::lc(void) const {
286  int l = ds.entries()-1;
287  while (ds[l].space() == NULL)
288  l--;
289  return l;
290  }
291 
292  forceinline int
293  Path::entries(void) const {
294  return ds.entries();
295  }
296 
297  forceinline void
299  assert((ds[l].space() == NULL) || ds[l].space()->failed());
300  int n = ds.entries();
301  for (int i=l; i<n; i++) {
302  if (ds.top().work())
303  n_work--;
304  ds.pop().dispose();
305  }
306  assert(ds.entries() == l);
307  }
308 
309  forceinline void
310  Path::reset(int l) {
311  n_work = 0;
312  while (!ds.empty())
313  ds.pop().dispose();
314  _ngdl = l;
315  }
316 
317  forceinline bool
318  Path::steal(void) const {
319  return n_work > Config::steal_limit;
320  }
321 
323  Path::steal(Worker& stat, unsigned long int& d) {
324  // Find position to steal: leave sufficient work
325  int n = ds.entries()-1;
326  unsigned int w = 0;
327  while (n >= 0) {
328  if (ds[n].work())
329  w++;
330  if (w > Config::steal_limit) {
331  // Okay, there is sufficient work left
332  int l=n;
333  // Find last copy
334  while (ds[l].space() == NULL)
335  l--;
336  Space* c = ds[l].space()->clone(false);
337  // Recompute, if necessary
338  for (int i=l; i<n; i++)
339  commit(c,i);
340  c->commit(*ds[n].choice(),ds[n].steal());
341  if (!ds[n].work())
342  n_work--;
343  // No no-goods can be extracted above n
344  ngdl(std::min(ngdl(),n));
345  d = stat.steal_depth(static_cast<unsigned long int>(n+1));
346  return c;
347  }
348  n--;
349  }
350  return NULL;
351  }
352 
354  Path::recompute(unsigned int& d, unsigned int a_d, Worker& stat) {
355  assert(!ds.empty());
356  // Recompute space according to path
357  // Also say distance to copy (d == 0) requires immediate copying
358 
359  // Check for LAO
360  if ((ds.top().space() != NULL) && ds.top().rightmost()) {
361  Space* s = ds.top().space();
362  s->commit(*ds.top().choice(),ds.top().alt());
363  assert(ds.entries()-1 == lc());
364  ds.top().space(NULL);
365  // Mark as reusable
366  if (ds.entries() > ngdl())
367  ds.top().next();
368  d = 0;
369  return s;
370  }
371  // General case for recomputation
372  int l = lc(); // Position of last clone
373  int n = ds.entries(); // Number of stack entries
374  // New distance, if no adaptive recomputation
375  d = static_cast<unsigned int>(n - l);
376 
377  Space* s = ds[l].space()->clone(); // Last clone
378 
379  if (d < a_d) {
380  // No adaptive recomputation
381  for (int i=l; i<n; i++)
382  commit(s,i);
383  } else {
384  int m = l + static_cast<int>(d >> 1); // Middle between copy and top
385  int i = l; // To iterate over all entries
386  // Recompute up to middle
387  for (; i<m; i++ )
388  commit(s,i);
389  // Skip over all rightmost branches
390  for (; (i<n) && ds[i].rightmost(); i++)
391  commit(s,i);
392  // Is there any point to make a copy?
393  if (i<n-1) {
394  // Propagate to fixpoint
395  SpaceStatus ss = s->status(stat);
396  /*
397  * Again, the space might already propagate to failure (due to
398  * weakly monotonic propagators).
399  */
400  if (ss == SS_FAILED) {
401  // s must be deleted as it is not on the stack
402  delete s;
403  stat.fail++;
404  unwind(i);
405  return NULL;
406  }
407  ds[i].space(s->clone());
408  d = static_cast<unsigned int>(n-i);
409  }
410  // Finally do the remaining commits
411  for (; i<n; i++)
412  commit(s,i);
413  }
414  return s;
415  }
416 
418  Path::recompute(unsigned int& d, unsigned int a_d, Worker& stat,
419  const Space* best, int& mark) {
420  assert(!ds.empty());
421  // Recompute space according to path
422  // Also say distance to copy (d == 0) requires immediate copying
423 
424  // Check for LAO
425  if ((ds.top().space() != NULL) && ds.top().rightmost()) {
426  Space* s = ds.top().space();
427  s->commit(*ds.top().choice(),ds.top().alt());
428  assert(ds.entries()-1 == lc());
429  if (mark > ds.entries()-1) {
430  mark = ds.entries()-1;
431  s->constrain(*best);
432  }
433  ds.top().space(NULL);
434  // Mark as reusable
435  if (ds.entries() > ngdl())
436  ds.top().next();
437  d = 0;
438  return s;
439  }
440  // General case for recomputation
441  int l = lc(); // Position of last clone
442  int n = ds.entries(); // Number of stack entries
443  // New distance, if no adaptive recomputation
444  d = static_cast<unsigned int>(n - l);
445 
446  Space* s = ds[l].space(); // Last clone
447 
448  if (l < mark) {
449  mark = l;
450  s->constrain(*best);
451  // The space on the stack could be failed now as an additional
452  // constraint might have been added.
453  if (s->status(stat) == SS_FAILED) {
454  // s does not need deletion as it is on the stack (unwind does this)
455  stat.fail++;
456  unwind(l);
457  return NULL;
458  }
459  // It is important to replace the space on the stack with the
460  // copy: a copy might be much smaller due to flushed caches
461  // of propagators
462  Space* c = s->clone();
463  ds[l].space(c);
464  } else {
465  s = s->clone();
466  }
467 
468  if (d < a_d) {
469  // No adaptive recomputation
470  for (int i=l; i<n; i++)
471  commit(s,i);
472  } else {
473  int m = l + static_cast<int>(d >> 1); // Middle between copy and top
474  int i = l; // To iterate over all entries
475  // Recompute up to middle
476  for (; i<m; i++ )
477  commit(s,i);
478  // Skip over all rightmost branches
479  for (; (i<n) && ds[i].rightmost(); i++)
480  commit(s,i);
481  // Is there any point to make a copy?
482  if (i<n-1) {
483  // Propagate to fixpoint
484  SpaceStatus ss = s->status(stat);
485  /*
486  * Again, the space might already propagate to failure
487  *
488  * This can be for two reasons:
489  * - constrain is true, so we fail
490  * - the space has weakly monotonic propagators
491  */
492  if (ss == SS_FAILED) {
493  // s must be deleted as it is not on the stack
494  delete s;
495  stat.fail++;
496  unwind(i);
497  return NULL;
498  }
499  ds[i].space(s->clone());
500  d = static_cast<unsigned int>(n-i);
501  }
502  // Finally do the remaining commits
503  for (; i<n; i++)
504  commit(s,i);
505  }
506  return s;
507  }
508 
509 }}}
510 
511 #endif
512 
513 // STATISTICS: search-parallel
Space * space(void) const
Return space for edge.
Definition: path.hh:167
Depth-first path (stack of edges) supporting recomputation.
Definition: path.hh:61
NNF * l
Left subtree.
Definition: bool-expr.cpp:244
Search tree edge for recomputation
Definition: path.hh:65
bool steal(void) const
Make a quick check whether stealing might be feasible.
Definition: path.hh:318
Edge & top(void) const
Provide access to topmost edge.
Definition: path.hh:268
Space * clone(bool share=true, CloneStatistics &stat=unused_clone) const
Clone space.
Definition: core.hpp:2777
SpaceStatus
Space status
Definition: core.hpp:1263
Edge(void)
Default constructor.
Definition: path.hh:158
unsigned int truealt(void) const
Return true number for alternatives (excluding lao optimization)
Definition: path.hh:180
unsigned long int fail
Number of failed nodes in search tree.
Definition: search.hh:139
unsigned int n_work
Number of edges that have work for stealing.
Definition: path.hh:113
unsigned int alternatives(void) const
Return number of alternatives.
Definition: core.hpp:3096
void * mark(void *p)
Return marked pointer for p.
const Choice * _choice
Choice.
Definition: path.hh:74
Computation spaces.
Definition: core.hpp:1325
Heap heap
The single global heap.
Definition: heap.cpp:49
Gecode::IntSet d(v, 7)
const Choice * choice(void) const
Return choice.
Definition: path.hh:207
void next(void)
Move to next alternative.
Definition: path.hh:197
Gecode::FloatVal c(-8, 8)
bool empty(void) const
Test whether path is empty.
Definition: path.hh:274
const FloatNum min
Smallest allowed float value.
Definition: float.hh:833
Gecode::IntArgs i(4, 1, 2, 3, 4)
void unwind(int l)
Unwind the stack up to position l (after failure)
Definition: path.hh:298
unsigned int steal(void)
Steal rightmost alternative and return its number.
Definition: path.hh:201
const unsigned int a_d
Create a clone during recomputation if distance is greater than a_d (adaptive distance) ...
Definition: search.hh:99
int _ngdl
Depth limit for no-good generation.
Definition: path.hh:111
No-good propagator.
Definition: nogoods.hh:67
bool next(void)
Generate path for next node and return whether a next node exists.
Definition: path.hh:253
const Choice * push(Worker &stat, Space *s, Space *c)
Push space c (a clone of s or NULL)
Definition: path.hh:239
void commit(const Choice &c, unsigned int a, CommitStatistics &stat=unused_commit)
Commit choice c for alternative a.
Definition: core.hpp:2785
virtual void constrain(const Space &best)
Constrain function for best solution search.
Definition: core.cpp:644
Support::DynamicStack< Edge, Heap > ds
Stack to store edge information.
Definition: path.hh:109
unsigned int _alt
Current alternative.
Definition: path.hh:70
int entries(void) const
Return number of entries on stack.
Definition: path.hh:293
unsigned int alt(void) const
Return number for alternatives.
Definition: path.hh:176
bool work(void) const
Test whether there is an alternative that can be stolen.
Definition: path.hh:193
Space * _space
Space corresponding to this edge (might be NULL)
Definition: path.hh:68
Space * recompute(unsigned int &d, unsigned int a_d, Worker &s)
Recompute space according to path.
Definition: path.hh:354
void dispose(void)
Free memory for edge.
Definition: path.hh:212
Search worker statistics
Definition: worker.hh:48
Path(int l)
Initialize with no-good depth limit l.
Definition: path.hh:225
int ngdl(void) const
Return no-good depth limit.
Definition: path.hh:229
Choice for performing commit
Definition: core.hpp:1036
No-goods recorded from restarts.
Definition: core.hpp:1240
virtual void post(Space &home)
Post no-goods.
Definition: path.cpp:43
#define forceinline
Definition: config.hpp:167
Stack with arbitrary number of elements.
SpaceStatus status(StatusStatistics &stat=unused_status)
Query space status.
Definition: core.cpp:251
int lc(void) const
Return position on stack of last copy.
Definition: path.hh:285
void commit(Space *s, int i) const
Commit space s as described by stack entry at position i.
Definition: path.hh:279
void stack_depth(unsigned long int d)
Record stack depth d.
Definition: worker.hh:104
bool rightmost(void) const
Test whether current alternative is rightmost.
Definition: path.hh:185
Gecode toplevel namespace
unsigned int _alt_max
Number of alternatives left.
Definition: path.hh:72
Space is failed
Definition: core.hpp:1264
unsigned long int n
Number of no-goods.
Definition: core.hpp:1243
const unsigned int steal_limit
Minimal number of open nodes for stealing.
Definition: search.hh:102
void reset(int l)
Reset stack and set no-good depth limit to l.
Definition: path.hh:310
unsigned long int steal_depth(unsigned long int d) const
Return steal depth.
Definition: worker.hh:110
bool lao(void) const
Test whether current alternative was LAO.
Definition: path.hh:189