Generated on Sat May 25 2013 18:00:40 for Gecode by doxygen 1.8.3.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: 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:
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:
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  */
147 
150  : _space(c), _alt(0), _choice(s->choice()) {
152  }
153 
155  Path::Edge::space(void) const {
156  return _space;
157  }
158  forceinline void
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
181  _alt++;
182  }
183  forceinline unsigned int
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
196  delete _space;
197  delete _choice;
198  }
199 
200 
201 
202  /*
203  * Depth-first stack with recomputation
204  *
205  */
206 
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
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 
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
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 
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 
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 
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