Generated on Tue Oct 22 2013 00:49:07 for Gecode by doxygen 1.8.4
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