Generated on Sat Feb 7 2015 02:01:29 for Gecode by doxygen 1.8.9.1
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: 2015-01-08 15:07:24 +0100 (Thu, 08 Jan 2015) $ by $Author: schulte $
11  * $Revision: 14341 $
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  void 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) const;
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 void
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;
263  }
264  }
265 
267  Path::top(void) const {
268  assert(!ds.empty());
269  return ds.top();
270  }
271 
272  forceinline bool
273  Path::empty(void) const {
274  return ds.empty();
275  }
276 
277  forceinline void
278  Path::commit(Space* s, int i) const {
279  const Edge& n = ds[i];
280  s->commit(*n.choice(),n.alt());
281  }
282 
283  forceinline int
284  Path::lc(void) const {
285  int l = ds.entries()-1;
286  while (ds[l].space() == NULL)
287  l--;
288  return l;
289  }
290 
291  forceinline int
292  Path::entries(void) const {
293  return ds.entries();
294  }
295 
296  forceinline void
298  assert((ds[l].space() == NULL) || ds[l].space()->failed());
299  int n = ds.entries();
300  for (int i=l; i<n; i++) {
301  if (ds.top().work())
302  n_work--;
303  ds.pop().dispose();
304  }
305  assert(ds.entries() == l);
306  }
307 
308  forceinline void
309  Path::reset(int l) {
310  n_work = 0;
311  while (!ds.empty())
312  ds.pop().dispose();
313  _ngdl = l;
314  }
315 
316  forceinline bool
317  Path::steal(void) const {
318  return n_work > Config::steal_limit;
319  }
320 
322  Path::steal(Worker& stat, unsigned long int& d) {
323  // Find position to steal: leave sufficient work
324  int n = ds.entries()-1;
325  unsigned int w = 0;
326  while (n >= 0) {
327  if (ds[n].work())
328  w++;
329  if (w > Config::steal_limit) {
330  // Okay, there is sufficient work left
331  int l=n;
332  // Find last copy
333  while (ds[l].space() == NULL)
334  l--;
335  Space* c = ds[l].space()->clone(false);
336  // Recompute, if necessary
337  for (int i=l; i<n; i++)
338  commit(c,i);
339  c->commit(*ds[n].choice(),ds[n].steal());
340  if (!ds[n].work())
341  n_work--;
342  // No no-goods can be extracted above n
343  ngdl(std::min(ngdl(),n));
344  d = stat.steal_depth(static_cast<unsigned long int>(n+1));
345  return c;
346  }
347  n--;
348  }
349  return NULL;
350  }
351 
353  Path::recompute(unsigned int& d, unsigned int a_d, Worker& stat) {
354  assert(!ds.empty());
355  // Recompute space according to path
356  // Also say distance to copy (d == 0) requires immediate copying
357 
358  // Check for LAO
359  if ((ds.top().space() != NULL) && ds.top().rightmost()) {
360  Space* s = ds.top().space();
361  s->commit(*ds.top().choice(),ds.top().alt());
362  assert(ds.entries()-1 == lc());
363  ds.top().space(NULL);
364  // Mark as reusable
365  if (ds.entries() > ngdl())
366  ds.top().next();
367  d = 0;
368  return s;
369  }
370  // General case for recomputation
371  int l = lc(); // Position of last clone
372  int n = ds.entries(); // Number of stack entries
373  // New distance, if no adaptive recomputation
374  d = static_cast<unsigned int>(n - l);
375 
376  Space* s = ds[l].space()->clone(); // Last clone
377 
378  if (d < a_d) {
379  // No adaptive recomputation
380  for (int i=l; i<n; i++)
381  commit(s,i);
382  } else {
383  int m = l + static_cast<int>(d >> 1); // Middle between copy and top
384  int i = l; // To iterate over all entries
385  // Recompute up to middle
386  for (; i<m; i++ )
387  commit(s,i);
388  // Skip over all rightmost branches
389  for (; (i<n) && ds[i].rightmost(); i++)
390  commit(s,i);
391  // Is there any point to make a copy?
392  if (i<n-1) {
393  // Propagate to fixpoint
394  SpaceStatus ss = s->status(stat);
395  /*
396  * Again, the space might already propagate to failure (due to
397  * weakly monotonic propagators).
398  */
399  if (ss == SS_FAILED) {
400  // s must be deleted as it is not on the stack
401  delete s;
402  stat.fail++;
403  unwind(i);
404  return NULL;
405  }
406  ds[i].space(s->clone());
407  d = static_cast<unsigned int>(n-i);
408  }
409  // Finally do the remaining commits
410  for (; i<n; i++)
411  commit(s,i);
412  }
413  return s;
414  }
415 
417  Path::recompute(unsigned int& d, unsigned int a_d, Worker& stat,
418  const Space& best, int& mark) {
419  assert(!ds.empty());
420  // Recompute space according to path
421  // Also say distance to copy (d == 0) requires immediate copying
422 
423  // Check for LAO
424  if ((ds.top().space() != NULL) && ds.top().rightmost()) {
425  Space* s = ds.top().space();
426  s->commit(*ds.top().choice(),ds.top().alt());
427  assert(ds.entries()-1 == lc());
428  if (mark > ds.entries()-1) {
429  mark = ds.entries()-1;
430  s->constrain(best);
431  }
432  ds.top().space(NULL);
433  // Mark as reusable
434  if (ds.entries() > ngdl())
435  ds.top().next();
436  d = 0;
437  return s;
438  }
439  // General case for recomputation
440  int l = lc(); // Position of last clone
441  int n = ds.entries(); // Number of stack entries
442  // New distance, if no adaptive recomputation
443  d = static_cast<unsigned int>(n - l);
444 
445  Space* s = ds[l].space(); // Last clone
446 
447  if (l < mark) {
448  mark = l;
449  s->constrain(best);
450  // The space on the stack could be failed now as an additional
451  // constraint might have been added.
452  if (s->status(stat) == SS_FAILED) {
453  // s does not need deletion as it is on the stack (unwind does this)
454  stat.fail++;
455  unwind(l);
456  return NULL;
457  }
458  // It is important to replace the space on the stack with the
459  // copy: a copy might be much smaller due to flushed caches
460  // of propagators
461  Space* c = s->clone();
462  ds[l].space(c);
463  } else {
464  s = s->clone();
465  }
466 
467  if (d < a_d) {
468  // No adaptive recomputation
469  for (int i=l; i<n; i++)
470  commit(s,i);
471  } else {
472  int m = l + static_cast<int>(d >> 1); // Middle between copy and top
473  int i = l; // To iterate over all entries
474  // Recompute up to middle
475  for (; i<m; i++ )
476  commit(s,i);
477  // Skip over all rightmost branches
478  for (; (i<n) && ds[i].rightmost(); i++)
479  commit(s,i);
480  // Is there any point to make a copy?
481  if (i<n-1) {
482  // Propagate to fixpoint
483  SpaceStatus ss = s->status(stat);
484  /*
485  * Again, the space might already propagate to failure
486  *
487  * This can be for two reasons:
488  * - constrain is true, so we fail
489  * - the space has weakly monotonic propagators
490  */
491  if (ss == SS_FAILED) {
492  // s must be deleted as it is not on the stack
493  delete s;
494  stat.fail++;
495  unwind(i);
496  return NULL;
497  }
498  ds[i].space(s->clone());
499  d = static_cast<unsigned int>(n-i);
500  }
501  // Finally do the remaining commits
502  for (; i<n; i++)
503  commit(s,i);
504  }
505  return s;
506  }
507 
508 }}}
509 
510 #endif
511 
512 // 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:317
Edge & top(void) const
Provide access to topmost edge.
Definition: path.hh:267
Space * clone(bool share=true, CloneStatistics &stat=unused_clone) const
Clone space.
Definition: core.hpp:2854
SpaceStatus
Space status
Definition: core.hpp:1300
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:3173
void * mark(void *p)
Return marked pointer for p.
const Choice * _choice
Choice.
Definition: path.hh:74
Computation spaces.
Definition: core.hpp:1362
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:273
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:297
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
virtual void post(Space &home) const
Post no-goods.
Definition: path.cpp:43
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:2862
virtual void constrain(const Space &best)
Constrain function for best solution search.
Definition: core.cpp:645
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:292
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:353
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
void next(void)
Generate path for next node.
Definition: path.hh:253
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
#define forceinline
Definition: config.hpp:132
Stack with arbitrary number of elements.
SpaceStatus status(StatusStatistics &stat=unused_status)
Query space status.
Definition: core.cpp:252
int lc(void) const
Return position on stack of last copy.
Definition: path.hh:284
void commit(Space *s, int i) const
Commit space s as described by stack entry at position i.
Definition: path.hh:278
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:1301
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:309
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