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: 2010-07-22 12:00:29 +0200 (Thu, 22 Jul 2010) $ by $Author: schulte $ 00011 * $Revision: 11249 $ 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 00043 namespace Gecode { namespace Search { namespace Parallel { 00044 00058 class Path { 00059 public: 00061 class Edge { 00062 protected: 00064 Space* _space; 00066 unsigned int _alt; 00068 unsigned int _alt_max; 00070 const Choice* _choice; 00071 public: 00073 Edge(void); 00075 Edge(Space* s, Space* c); 00076 00078 Space* space(void) const; 00080 void space(Space* s); 00081 00083 const Choice* choice(void) const; 00084 00086 unsigned int alt(void) const; 00088 bool rightmost(void) const; 00090 bool work(void) const; 00092 void next(void); 00094 unsigned int steal(void); 00095 00097 void dispose(void); 00098 }; 00099 protected: 00101 Support::DynamicStack<Edge,Heap> ds; 00103 unsigned int n_work; 00104 public: 00106 Path(void); 00108 const Choice* push(Worker& stat, Space* s, Space* c); 00110 bool next(Worker& s); 00112 Edge& top(void) const; 00114 bool empty(void) const; 00116 int lc(void) const; 00118 void unwind(int l); 00120 void commit(Space* s, int i) const; 00122 Space* recompute(unsigned int& d, unsigned int a_d, Worker& s); 00124 Space* recompute(unsigned int& d, unsigned int a_d, Worker& s, 00125 const Space* best, int& mark); 00127 int entries(void) const; 00129 size_t size(void) const; 00131 void reset(void); 00133 bool steal(void) const; 00135 Space* steal(Worker& stat, unsigned long int& d); 00136 }; 00137 00138 00139 /* 00140 * Edge for recomputation 00141 * 00142 */ 00143 forceinline 00144 Path::Edge::Edge(void) {} 00145 00146 forceinline 00147 Path::Edge::Edge(Space* s, Space* c) 00148 : _space(c), _alt(0), _choice(s->choice()) { 00149 _alt_max = _choice->alternatives()-1; 00150 } 00151 00152 forceinline Space* 00153 Path::Edge::space(void) const { 00154 return _space; 00155 } 00156 forceinline void 00157 Path::Edge::space(Space* s) { 00158 _space = s; 00159 } 00160 00161 forceinline unsigned int 00162 Path::Edge::alt(void) const { 00163 return _alt; 00164 } 00165 forceinline bool 00166 Path::Edge::rightmost(void) const { 00167 return _alt == _alt_max; 00168 } 00169 forceinline bool 00170 Path::Edge::work(void) const { 00171 return _alt != _alt_max; 00172 } 00173 forceinline void 00174 Path::Edge::next(void) { 00175 _alt++; 00176 } 00177 forceinline unsigned int 00178 Path::Edge::steal(void) { 00179 assert(work()); 00180 return _alt_max--; 00181 } 00182 00183 forceinline const Choice* 00184 Path::Edge::choice(void) const { 00185 return _choice; 00186 } 00187 00188 forceinline void 00189 Path::Edge::dispose(void) { 00190 delete _space; 00191 delete _choice; 00192 } 00193 00194 00195 00196 /* 00197 * Depth-first stack with recomputation 00198 * 00199 */ 00200 00201 forceinline 00202 Path::Path(void) : ds(heap), n_work(0) {} 00203 00204 forceinline const Choice* 00205 Path::push(Worker& stat, Space* s, Space* c) { 00206 Edge sn(s,c); 00207 if (sn.work()) 00208 n_work++; 00209 ds.push(sn); 00210 stat.stack_depth(static_cast<unsigned long int>(ds.entries())); 00211 return sn.choice(); 00212 } 00213 00214 forceinline bool 00215 Path::next(Worker& stat) { 00216 while (!ds.empty()) 00217 if (ds.top().rightmost()) { 00218 stat.pop(ds.top().space(),ds.top().choice()); 00219 ds.pop().dispose(); 00220 } else { 00221 assert(ds.top().work()); 00222 ds.top().next(); 00223 if (!ds.top().work()) 00224 n_work--; 00225 return true; 00226 } 00227 return false; 00228 } 00229 00230 forceinline Path::Edge& 00231 Path::top(void) const { 00232 assert(!ds.empty()); 00233 return ds.top(); 00234 } 00235 00236 forceinline bool 00237 Path::empty(void) const { 00238 return ds.empty(); 00239 } 00240 00241 forceinline void 00242 Path::commit(Space* s, int i) const { 00243 const Edge& n = ds[i]; 00244 s->commit(*n.choice(),n.alt()); 00245 } 00246 00247 forceinline int 00248 Path::lc(void) const { 00249 int l = ds.entries()-1; 00250 while (ds[l].space() == NULL) 00251 l--; 00252 return l; 00253 } 00254 00255 forceinline int 00256 Path::entries(void) const { 00257 return ds.entries(); 00258 } 00259 00260 forceinline size_t 00261 Path::size(void) const { 00262 return ds.size(); 00263 } 00264 00265 forceinline void 00266 Path::unwind(int l) { 00267 assert((ds[l].space() == NULL) || ds[l].space()->failed()); 00268 int n = ds.entries(); 00269 for (int i=l; i<n; i++) { 00270 if (ds.top().work()) 00271 n_work--; 00272 ds.pop().dispose(); 00273 } 00274 assert(ds.entries() == l); 00275 } 00276 00277 forceinline void 00278 Path::reset(void) { 00279 n_work = 0; 00280 while (!ds.empty()) 00281 ds.pop().dispose(); 00282 } 00283 00284 forceinline bool 00285 Path::steal(void) const { 00286 return n_work > Config::steal_limit; 00287 } 00288 00289 forceinline Space* 00290 Path::steal(Worker& stat, unsigned long int& d) { 00291 // Find position to steal: leave sufficient work 00292 int n = ds.entries()-1; 00293 unsigned int w = 0; 00294 while (n >= 0) { 00295 if (ds[n].work()) 00296 w++; 00297 if (w > Config::steal_limit) { 00298 // Okay, there is sufficient work left 00299 int l=n; 00300 // Find last copy 00301 while (ds[l].space() == NULL) 00302 l--; 00303 Space* c = ds[l].space()->clone(false); 00304 // Recompute, if necessary 00305 for (int i=l; i<n; i++) 00306 commit(c,i); 00307 c->commit(*ds[n].choice(),ds[n].steal()); 00308 if (!ds[n].work()) 00309 n_work--; 00310 d = stat.steal_depth(static_cast<unsigned long int>(n+1)); 00311 return c; 00312 } 00313 n--; 00314 } 00315 return NULL; 00316 } 00317 00318 forceinline Space* 00319 Path::recompute(unsigned int& d, unsigned int a_d, Worker& stat) { 00320 assert(!ds.empty()); 00321 // Recompute space according to path 00322 // Also say distance to copy (d == 0) requires immediate copying 00323 00324 // Check for LAO 00325 if ((ds.top().space() != NULL) && ds.top().rightmost()) { 00326 Space* s = ds.top().space(); 00327 stat.lao(s); 00328 s->commit(*ds.top().choice(),ds.top().alt()); 00329 assert(ds.entries()-1 == lc()); 00330 ds.top().space(NULL); 00331 d = 0; 00332 return s; 00333 } 00334 // General case for recomputation 00335 int l = lc(); // Position of last clone 00336 int n = ds.entries(); // Number of stack entries 00337 // New distance, if no adaptive recomputation 00338 d = static_cast<unsigned int>(n - l); 00339 00340 Space* s = ds[l].space()->clone(); // Last clone 00341 00342 if (d < a_d) { 00343 // No adaptive recomputation 00344 for (int i=l; i<n; i++) 00345 commit(s,i); 00346 } else { 00347 int m = l + static_cast<int>(d >> 1); // Middle between copy and top 00348 int i = l; // To iterate over all entries 00349 // Recompute up to middle 00350 for (; i<m; i++ ) 00351 commit(s,i); 00352 // Skip over all rightmost branches 00353 for (; (i<n) && ds[i].rightmost(); i++) 00354 commit(s,i); 00355 // Is there any point to make a copy? 00356 if (i<n-1) { 00357 // Propagate to fixpoint 00358 SpaceStatus ss = s->status(stat); 00359 /* 00360 * Again, the space might already propagate to failure (due to 00361 * weakly monotonic propagators). 00362 */ 00363 if (ss == SS_FAILED) { 00364 // s must be deleted as it is not on the stack 00365 delete s; 00366 stat.fail++; 00367 unwind(i); 00368 return NULL; 00369 } 00370 ds[i].space(s->clone()); 00371 stat.adapt(ds[i].space()); 00372 d = static_cast<unsigned int>(n-i); 00373 } 00374 // Finally do the remaining commits 00375 for (; i<n; i++) 00376 commit(s,i); 00377 } 00378 return s; 00379 } 00380 00381 forceinline Space* 00382 Path::recompute(unsigned int& d, unsigned int a_d, Worker& stat, 00383 const Space* best, int& mark) { 00384 assert(!ds.empty()); 00385 // Recompute space according to path 00386 // Also say distance to copy (d == 0) requires immediate copying 00387 00388 // Check for LAO 00389 if ((ds.top().space() != NULL) && ds.top().rightmost()) { 00390 Space* s = ds.top().space(); 00391 stat.lao(s); 00392 s->commit(*ds.top().choice(),ds.top().alt()); 00393 assert(ds.entries()-1 == lc()); 00394 if (mark > ds.entries()-1) { 00395 mark = ds.entries()-1; 00396 s->constrain(*best); 00397 } 00398 ds.top().space(NULL); 00399 d = 0; 00400 return s; 00401 } 00402 // General case for recomputation 00403 int l = lc(); // Position of last clone 00404 int n = ds.entries(); // Number of stack entries 00405 // New distance, if no adaptive recomputation 00406 d = static_cast<unsigned int>(n - l); 00407 00408 Space* s = ds[l].space(); // Last clone 00409 00410 if (l < mark) { 00411 mark = l; 00412 s->constrain(*best); 00413 // The space on the stack could be failed now as an additional 00414 // constraint might have been added. 00415 if (s->status(stat) == SS_FAILED) { 00416 // s does not need deletion as it is on the stack (unwind does this) 00417 stat.fail++; 00418 unwind(l); 00419 return NULL; 00420 } 00421 // It is important to replace the space on the stack with the 00422 // copy: a copy might be much smaller due to flushed caches 00423 // of propagators 00424 Space* c = s->clone(); 00425 ds[l].space(c); 00426 stat.constrained(s,c); 00427 } else { 00428 s = s->clone(); 00429 } 00430 00431 if (d < a_d) { 00432 // No adaptive recomputation 00433 for (int i=l; i<n; i++) 00434 commit(s,i); 00435 } else { 00436 int m = l + static_cast<int>(d >> 1); // Middle between copy and top 00437 int i = l; // To iterate over all entries 00438 // Recompute up to middle 00439 for (; i<m; i++ ) 00440 commit(s,i); 00441 // Skip over all rightmost branches 00442 for (; (i<n) && ds[i].rightmost(); i++) 00443 commit(s,i); 00444 // Is there any point to make a copy? 00445 if (i<n-1) { 00446 // Propagate to fixpoint 00447 SpaceStatus ss = s->status(stat); 00448 /* 00449 * Again, the space might already propagate to failure 00450 * 00451 * This can be for two reasons: 00452 * - constrain is true, so we fail 00453 * - the space has weakly monotonic propagators 00454 */ 00455 if (ss == SS_FAILED) { 00456 // s must be deleted as it is not on the stack 00457 delete s; 00458 stat.fail++; 00459 unwind(i); 00460 return NULL; 00461 } 00462 ds[i].space(s->clone()); 00463 stat.adapt(ds[i].space()); 00464 d = static_cast<unsigned int>(n-i); 00465 } 00466 // Finally do the remaining commits 00467 for (; i<n; i++) 00468 commit(s,i); 00469 } 00470 return s; 00471 } 00472 00473 }}} 00474 00475 #endif 00476 00477 // STATISTICS: search-parallel