Generated on Mon Aug 27 2012 17:15:47 for Gecode by doxygen 1.8.1.2
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:
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:
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  */
145 
148  : _space(c), _alt(0), _choice(s->choice()) {
150  }
151 
153  Path::Edge::space(void) const {
154  return _space;
155  }
156  forceinline void
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
175  _alt++;
176  }
177  forceinline unsigned int
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
190  delete _space;
191  delete _choice;
192  }
193 
194 
195 
196  /*
197  * Depth-first stack with recomputation
198  *
199  */
200 
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
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 
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 
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 
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 
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