Go to the documentation of this file.00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025
00026
00027
00028
00029
00030
00031
00032
00033
00034
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
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
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
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
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
00332 int l=n;
00333
00334 while (ds[l].space() == NULL)
00335 l--;
00336 Space* c = ds[l].space()->clone(false);
00337
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
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
00357
00358
00359
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
00366 if (ds.entries() > ngdl())
00367 ds.top().next();
00368 d = 0;
00369 return s;
00370 }
00371
00372 int l = lc();
00373 int n = ds.entries();
00374
00375 d = static_cast<unsigned int>(n - l);
00376
00377 Space* s = ds[l].space()->clone();
00378
00379 if (d < a_d) {
00380
00381 for (int i=l; i<n; i++)
00382 commit(s,i);
00383 } else {
00384 int m = l + static_cast<int>(d >> 1);
00385 int i = l;
00386
00387 for (; i<m; i++ )
00388 commit(s,i);
00389
00390 for (; (i<n) && ds[i].rightmost(); i++)
00391 commit(s,i);
00392
00393 if (i<n-1) {
00394
00395 SpaceStatus ss = s->status(stat);
00396
00397
00398
00399
00400 if (ss == SS_FAILED) {
00401
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
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
00422
00423
00424
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
00435 if (ds.entries() > ngdl())
00436 ds.top().next();
00437 d = 0;
00438 return s;
00439 }
00440
00441 int l = lc();
00442 int n = ds.entries();
00443
00444 d = static_cast<unsigned int>(n - l);
00445
00446 Space* s = ds[l].space();
00447
00448 if (l < mark) {
00449 mark = l;
00450 s->constrain(*best);
00451
00452
00453 if (s->status(stat) == SS_FAILED) {
00454
00455 stat.fail++;
00456 unwind(l);
00457 return NULL;
00458 }
00459
00460
00461
00462 Space* c = s->clone();
00463 ds[l].space(c);
00464 } else {
00465 s = s->clone();
00466 }
00467
00468 if (d < a_d) {
00469
00470 for (int i=l; i<n; i++)
00471 commit(s,i);
00472 } else {
00473 int m = l + static_cast<int>(d >> 1);
00474 int i = l;
00475
00476 for (; i<m; i++ )
00477 commit(s,i);
00478
00479 for (; (i<n) && ds[i].rightmost(); i++)
00480 commit(s,i);
00481
00482 if (i<n-1) {
00483
00484 SpaceStatus ss = s->status(stat);
00485
00486
00487
00488
00489
00490
00491
00492 if (ss == SS_FAILED) {
00493
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
00503 for (; i<n; i++)
00504 commit(s,i);
00505 }
00506 return s;
00507 }
00508
00509 }}}
00510
00511 #endif
00512
00513