Generated on Wed Nov 5 2014 05:18:31 for Gecode by doxygen 1.7.6.1
path.hh
Go to the documentation of this file.
00001 /* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
00002 /*
00003  *  Main authors:
00004  *     Christian Schulte <schulte@gecode.org>
00005  *
00006  *  Copyright:
00007  *     Christian Schulte, 2003
00008  *
00009  *  Last modified:
00010  *     $Date: 2013-07-12 18:20:11 +0200 (Fri, 12 Jul 2013) $ by $Author: schulte $
00011  *     $Revision: 13877 $
00012  *
00013  *  This file is part of Gecode, the generic constraint
00014  *  development environment:
00015  *     http://www.gecode.org
00016  *
00017  *  Permission is hereby granted, free of charge, to any person obtaining
00018  *  a copy of this software and associated documentation files (the
00019  *  "Software"), to deal in the Software without restriction, including
00020  *  without limitation the rights to use, copy, modify, merge, publish,
00021  *  distribute, sublicense, and/or sell copies of the Software, and to
00022  *  permit persons to whom the Software is furnished to do so, subject to
00023  *  the following conditions:
00024  *
00025  *  The above copyright notice and this permission notice shall be
00026  *  included in all copies or substantial portions of the Software.
00027  *
00028  *  THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
00029  *  EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
00030  *  MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
00031  *  NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
00032  *  LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
00033  *  OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
00034  *  WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
00035  *
00036  */
00037 
00038 #ifndef __GECODE_SEARCH_PARALLEL_PATH_HH__
00039 #define __GECODE_SEARCH_PARALLEL_PATH_HH__
00040 
00041 #include <gecode/search.hh>
00042 #include <gecode/search/support.hh>
00043 #include <gecode/search/worker.hh>
00044 #include <gecode/search/meta/nogoods.hh>
00045 
00046 namespace Gecode { namespace Search { namespace Parallel {
00047 
00061   class Path : public NoGoods {
00062     friend class Search::Meta::NoGoodsProp;
00063   public:
00065     class Edge {
00066     protected:
00068       Space* _space;
00070       unsigned int _alt;
00072       unsigned int _alt_max;
00074       const Choice* _choice;
00075     public:
00077       Edge(void);
00079       Edge(Space* s, Space* c);
00080       
00082       Space* space(void) const;
00084       void space(Space* s);
00085       
00087       const Choice* choice(void) const;
00088       
00090       unsigned int alt(void) const;
00092       unsigned int truealt(void) const;
00094       bool rightmost(void) const;
00096       bool lao(void) const;
00098       bool work(void) const;
00100       void next(void);
00102       unsigned int steal(void);
00103       
00105       void dispose(void);
00106     };
00107   protected:
00109     Support::DynamicStack<Edge,Heap> ds;
00111     int _ngdl;
00113     unsigned int n_work;
00114   public:
00116     Path(int l);
00118     int ngdl(void) const;
00120     void ngdl(int l);
00122     const Choice* push(Worker& stat, Space* s, Space* c);
00124     bool next(void);
00126     Edge& top(void) const;
00128     bool empty(void) const;
00130     int lc(void) const;
00132     void unwind(int l);
00134     void commit(Space* s, int i) const;
00136     Space* recompute(unsigned int& d, unsigned int a_d, Worker& s);
00138     Space* recompute(unsigned int& d, unsigned int a_d, Worker& s,
00139                      const Space* best, int& mark);
00141     int entries(void) const;
00143     void reset(int l);
00145     bool steal(void) const;
00147     Space* steal(Worker& stat, unsigned long int& d);
00149     void virtual post(Space& home);
00150   };
00151 
00152 
00153   /*
00154    * Edge for recomputation
00155    *
00156    */
00157   forceinline
00158   Path::Edge::Edge(void) {}
00159 
00160   forceinline
00161   Path::Edge::Edge(Space* s, Space* c)
00162     : _space(c), _alt(0), _choice(s->choice()) {
00163     _alt_max = _choice->alternatives()-1;
00164   }
00165 
00166   forceinline Space*
00167   Path::Edge::space(void) const {
00168     return _space;
00169   }
00170   forceinline void
00171   Path::Edge::space(Space* s) {
00172     _space = s;
00173   }
00174 
00175   forceinline unsigned int
00176   Path::Edge::alt(void) const {
00177     return _alt;
00178   }
00179   forceinline unsigned int
00180   Path::Edge::truealt(void) const {
00181     assert(_alt < _choice->alternatives());
00182     return _alt;
00183   }
00184   forceinline bool
00185   Path::Edge::rightmost(void) const {
00186     return _alt >= _alt_max;
00187   }
00188   forceinline bool
00189   Path::Edge::lao(void) const {
00190     return _alt > _alt_max;
00191   }
00192   forceinline bool
00193   Path::Edge::work(void) const {
00194     return _alt < _alt_max;
00195   }
00196   forceinline void
00197   Path::Edge::next(void) {
00198     _alt++;
00199   }
00200   forceinline unsigned int
00201   Path::Edge::steal(void) {
00202     assert(work());
00203     return _alt_max--;
00204   }
00205 
00206   forceinline const Choice*
00207   Path::Edge::choice(void) const {
00208     return _choice;
00209   }
00210 
00211   forceinline void
00212   Path::Edge::dispose(void) {
00213     delete _space;
00214     delete _choice;
00215   }
00216 
00217 
00218 
00219   /*
00220    * Depth-first stack with recomputation
00221    *
00222    */
00223 
00224   forceinline
00225   Path::Path(int l) 
00226     : ds(heap), _ngdl(l), n_work(0) {}
00227 
00228   forceinline int
00229   Path::ngdl(void) const {
00230     return _ngdl;
00231   }
00232 
00233   forceinline void
00234   Path::ngdl(int l) {
00235     _ngdl = l;
00236   }
00237 
00238   forceinline const Choice*
00239   Path::push(Worker& stat, Space* s, Space* c) {
00240     if (!ds.empty() && ds.top().lao()) {
00241       // Topmost stack entry was LAO -> reuse
00242       ds.pop().dispose();
00243     }
00244     Edge sn(s,c);
00245     if (sn.work())
00246       n_work++;
00247     ds.push(sn);
00248     stat.stack_depth(static_cast<unsigned long int>(ds.entries()));
00249     return sn.choice();
00250   }
00251 
00252   forceinline bool
00253   Path::next(void) {
00254     while (!ds.empty())
00255       if (ds.top().rightmost()) {
00256         ds.pop().dispose();
00257       } else {
00258         assert(ds.top().work());
00259         ds.top().next();
00260         if (!ds.top().work())
00261           n_work--;
00262         return true;
00263       }
00264     return false;
00265   }
00266 
00267   forceinline Path::Edge&
00268   Path::top(void) const {
00269     assert(!ds.empty());
00270     return ds.top();
00271   }
00272 
00273   forceinline bool
00274   Path::empty(void) const {
00275     return ds.empty();
00276   }
00277 
00278   forceinline void
00279   Path::commit(Space* s, int i) const {
00280     const Edge& n = ds[i];
00281     s->commit(*n.choice(),n.alt());
00282   }
00283 
00284   forceinline int
00285   Path::lc(void) const {
00286     int l = ds.entries()-1;
00287     while (ds[l].space() == NULL)
00288       l--;
00289     return l;
00290   }
00291 
00292   forceinline int
00293   Path::entries(void) const {
00294     return ds.entries();
00295   }
00296 
00297   forceinline void
00298   Path::unwind(int l) {
00299     assert((ds[l].space() == NULL) || ds[l].space()->failed());
00300     int n = ds.entries();
00301     for (int i=l; i<n; i++) {
00302       if (ds.top().work())
00303         n_work--;
00304       ds.pop().dispose();
00305     }
00306     assert(ds.entries() == l);
00307   }
00308 
00309   forceinline void
00310   Path::reset(int l) {
00311     n_work = 0;
00312     while (!ds.empty())
00313       ds.pop().dispose();
00314     _ngdl = l;
00315   }
00316 
00317   forceinline bool
00318   Path::steal(void) const {
00319     return n_work > Config::steal_limit;
00320   }
00321 
00322   forceinline Space*
00323   Path::steal(Worker& stat, unsigned long int& d) {
00324     // Find position to steal: leave sufficient work
00325     int n = ds.entries()-1;
00326     unsigned int w = 0;
00327     while (n >= 0) {
00328       if (ds[n].work())
00329         w++;
00330       if (w > Config::steal_limit) {
00331         // Okay, there is sufficient work left
00332         int l=n;
00333         // Find last copy
00334         while (ds[l].space() == NULL)
00335           l--;
00336         Space* c = ds[l].space()->clone(false);
00337         // Recompute, if necessary
00338         for (int i=l; i<n; i++)
00339           commit(c,i);
00340         c->commit(*ds[n].choice(),ds[n].steal());
00341         if (!ds[n].work())
00342           n_work--;
00343         // No no-goods can be extracted above n
00344         ngdl(std::min(ngdl(),n));
00345         d = stat.steal_depth(static_cast<unsigned long int>(n+1));
00346         return c;
00347       }
00348       n--;
00349     }
00350     return NULL;
00351   }
00352 
00353   forceinline Space*
00354   Path::recompute(unsigned int& d, unsigned int a_d, Worker& stat) {
00355     assert(!ds.empty());
00356     // Recompute space according to path
00357     // Also say distance to copy (d == 0) requires immediate copying
00358 
00359     // Check for LAO
00360     if ((ds.top().space() != NULL) && ds.top().rightmost()) {
00361       Space* s = ds.top().space();
00362       s->commit(*ds.top().choice(),ds.top().alt());
00363       assert(ds.entries()-1 == lc());
00364       ds.top().space(NULL);
00365       // Mark as reusable
00366       if (ds.entries() > ngdl())
00367         ds.top().next();
00368       d = 0;
00369       return s;
00370     }
00371     // General case for recomputation
00372     int l = lc();             // Position of last clone
00373     int n = ds.entries();     // Number of stack entries
00374     // New distance, if no adaptive recomputation
00375     d = static_cast<unsigned int>(n - l);
00376 
00377     Space* s = ds[l].space()->clone(); // Last clone
00378 
00379     if (d < a_d) {
00380       // No adaptive recomputation
00381       for (int i=l; i<n; i++)
00382         commit(s,i);
00383     } else {
00384       int m = l + static_cast<int>(d >> 1); // Middle between copy and top
00385       int i = l; // To iterate over all entries
00386       // Recompute up to middle
00387       for (; i<m; i++ )
00388         commit(s,i);
00389       // Skip over all rightmost branches
00390       for (; (i<n) && ds[i].rightmost(); i++)
00391         commit(s,i);
00392       // Is there any point to make a copy?
00393       if (i<n-1) {
00394         // Propagate to fixpoint
00395         SpaceStatus ss = s->status(stat);
00396         /*
00397          * Again, the space might already propagate to failure (due to
00398          * weakly monotonic propagators).
00399          */
00400         if (ss == SS_FAILED) {
00401           // s must be deleted as it is not on the stack
00402           delete s;
00403           stat.fail++;
00404           unwind(i);
00405           return NULL;
00406         }
00407         ds[i].space(s->clone());
00408         d = static_cast<unsigned int>(n-i);
00409       }
00410       // Finally do the remaining commits
00411       for (; i<n; i++)
00412         commit(s,i);
00413     }
00414     return s;
00415   }
00416 
00417   forceinline Space*
00418   Path::recompute(unsigned int& d, unsigned int a_d, Worker& stat,
00419                   const Space* best, int& mark) {
00420     assert(!ds.empty());
00421     // Recompute space according to path
00422     // Also say distance to copy (d == 0) requires immediate copying
00423 
00424     // Check for LAO
00425     if ((ds.top().space() != NULL) && ds.top().rightmost()) {
00426       Space* s = ds.top().space();
00427       s->commit(*ds.top().choice(),ds.top().alt());
00428       assert(ds.entries()-1 == lc());
00429       if (mark > ds.entries()-1) {
00430         mark = ds.entries()-1;
00431         s->constrain(*best);
00432       }
00433       ds.top().space(NULL);
00434       // Mark as reusable
00435       if (ds.entries() > ngdl())
00436         ds.top().next();
00437       d = 0;
00438       return s;
00439     }
00440     // General case for recomputation
00441     int l = lc();             // Position of last clone
00442     int n = ds.entries();     // Number of stack entries
00443     // New distance, if no adaptive recomputation
00444     d = static_cast<unsigned int>(n - l);
00445 
00446     Space* s = ds[l].space(); // Last clone
00447 
00448     if (l < mark) {
00449       mark = l;
00450       s->constrain(*best);
00451       // The space on the stack could be failed now as an additional
00452       // constraint might have been added.
00453       if (s->status(stat) == SS_FAILED) {
00454         // s does not need deletion as it is on the stack (unwind does this)
00455         stat.fail++;
00456         unwind(l);
00457         return NULL;
00458       }
00459       // It is important to replace the space on the stack with the
00460       // copy: a copy might be much smaller due to flushed caches
00461       // of propagators
00462       Space* c = s->clone();
00463       ds[l].space(c);
00464     } else {
00465       s = s->clone();
00466     }
00467 
00468     if (d < a_d) {
00469       // No adaptive recomputation
00470       for (int i=l; i<n; i++)
00471         commit(s,i);
00472     } else {
00473       int m = l + static_cast<int>(d >> 1); // Middle between copy and top
00474       int i = l;            // To iterate over all entries
00475       // Recompute up to middle
00476       for (; i<m; i++ )
00477         commit(s,i);
00478       // Skip over all rightmost branches
00479       for (; (i<n) && ds[i].rightmost(); i++)
00480         commit(s,i);
00481       // Is there any point to make a copy?
00482       if (i<n-1) {
00483         // Propagate to fixpoint
00484         SpaceStatus ss = s->status(stat);
00485         /*
00486          * Again, the space might already propagate to failure
00487          *
00488          * This can be for two reasons:
00489          *  - constrain is true, so we fail
00490          *  - the space has weakly monotonic propagators
00491          */
00492         if (ss == SS_FAILED) {
00493           // s must be deleted as it is not on the stack
00494           delete s;
00495           stat.fail++;
00496           unwind(i);
00497           return NULL;
00498         }
00499         ds[i].space(s->clone());
00500         d = static_cast<unsigned int>(n-i);
00501       }
00502       // Finally do the remaining commits
00503       for (; i<n; i++)
00504         commit(s,i);
00505     }
00506     return s;
00507   }
00508 
00509 }}}
00510 
00511 #endif
00512 
00513 // STATISTICS: search-parallel