bab.hpp
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 namespace Gecode { namespace Search { namespace Par {
00035
00036
00037
00038
00039 template<class Tracer>
00040 forceinline BAB<Tracer>&
00041 BAB<Tracer>::Worker::engine(void) const {
00042 return static_cast<BAB&>(_engine);
00043 }
00044 template<class Tracer>
00045 forceinline typename BAB<Tracer>::Worker*
00046 BAB<Tracer>::worker(unsigned int i) const {
00047 return _worker[i];
00048 }
00049
00050 template<class Tracer>
00051 forceinline void
00052 BAB<Tracer>::Worker::reset(Space* s, unsigned int ngdl) {
00053 tracer.round();
00054 delete cur;
00055 delete best;
00056 best = NULL;
00057 path.reset((s == NULL) ? 0 : ngdl);
00058 d = 0;
00059 mark = 0;
00060 idle = false;
00061 if ((s == NULL) || (s->status(*this) == SS_FAILED)) {
00062 delete s;
00063 cur = NULL;
00064 } else {
00065 cur = s;
00066 }
00067 Search::Worker::reset();
00068 }
00069
00070
00071
00072
00073
00074 template<class Tracer>
00075 forceinline
00076 BAB<Tracer>::Worker::Worker(Space* s, BAB& e)
00077 : Engine<Tracer>::Worker(s,e), mark(0), best(NULL) {}
00078
00079 template<class Tracer>
00080 forceinline
00081 BAB<Tracer>::BAB(Space* s, const Options& o)
00082 : Engine<Tracer>(o), best(NULL) {
00083 WrapTraceRecorder::engine(o.tracer, SearchTracer::EngineType::DFS,
00084 workers());
00085
00086 _worker = static_cast<Worker**>
00087 (heap.ralloc(workers() * sizeof(Worker*)));
00088
00089 _worker[0] = new Worker(s,*this);
00090
00091 for (unsigned int i=1U; i<workers(); i++)
00092 _worker[i] = new Worker(NULL,*this);
00093
00094 block();
00095
00096 for (unsigned int i=0U; i<workers(); i++)
00097 Support::Thread::run(_worker[i]);
00098 }
00099
00100
00101
00102
00103
00104 template<class Tracer>
00105 forceinline void
00106 BAB<Tracer>::Worker::better(Space* b) {
00107 m.acquire();
00108 delete best;
00109 best = b->clone();
00110 mark = path.entries();
00111 if (cur != NULL)
00112 cur->constrain(*best);
00113 m.release();
00114 }
00115 template<class Tracer>
00116 forceinline void
00117 BAB<Tracer>::solution(Space* s) {
00118 m_search.acquire();
00119 if (best != NULL) {
00120 s->constrain(*best);
00121 if (s->status() == SS_FAILED) {
00122 delete s;
00123 m_search.release();
00124 return;
00125 } else {
00126 delete best;
00127 best = s->clone();
00128 }
00129 } else {
00130 best = s->clone();
00131 }
00132
00133 for (unsigned int i=0U; i<workers(); i++)
00134 worker(i)->better(best);
00135 bool bs = signal();
00136 solutions.push(s);
00137 if (bs)
00138 e_search.signal();
00139 m_search.release();
00140 }
00141
00142
00143
00144
00145
00146 template<class Tracer>
00147 forceinline void
00148 BAB<Tracer>::Worker::find(void) {
00149
00150 for (unsigned int i=0U; i<engine().workers(); i++) {
00151 unsigned long int r_d = 0ul;
00152 typename Engine<Tracer>::Worker* wi = engine().worker(i);
00153 if (Space* s = wi->steal(r_d,wi->tracer,tracer)) {
00154
00155 m.acquire();
00156 idle = false;
00157
00158 path.ngdl(0);
00159 d = 0;
00160 cur = s;
00161 mark = 0;
00162 if (best != NULL)
00163 cur->constrain(*best);
00164 Statistics t = *this;
00165 Search::Worker::reset(r_d);
00166 (*this) += t;
00167 m.release();
00168 return;
00169 }
00170 }
00171 }
00172
00173
00174
00175
00176 template<class Tracer>
00177 Statistics
00178 BAB<Tracer>::statistics(void) const {
00179 Statistics s;
00180 for (unsigned int i=0U; i<workers(); i++)
00181 s += worker(i)->statistics();
00182 return s;
00183 }
00184
00185 template<class Tracer>
00186 void
00187 BAB<Tracer>::constrain(const Space& b) {
00188 m_search.acquire();
00189 if (best != NULL) {
00190 best->constrain(b);
00191 if (best->status() != SS_FAILED) {
00192 m_search.release();
00193 return;
00194 }
00195 delete best;
00196 }
00197 best = b.clone();
00198
00199 for (unsigned int i=0U; i<workers(); i++)
00200 worker(i)->better(best);
00201 m_search.release();
00202 }
00203
00204
00205
00206
00207 template<class Tracer>
00208 void
00209 BAB<Tracer>::Worker::run(void) {
00210
00211
00212
00213
00214
00215
00216
00217
00218
00219
00220
00221
00222
00223
00224
00225
00226
00227 if (this != engine().worker(0))
00228 Support::Thread::sleep(Config::initial_delay);
00229
00230 while (true) {
00231 switch (engine().cmd()) {
00232 case C_WAIT:
00233
00234 engine().wait();
00235 break;
00236 case C_TERMINATE:
00237
00238 engine().ack_terminate();
00239
00240 engine().wait_terminate();
00241
00242 return;
00243 case C_RESET:
00244
00245 engine().ack_reset_start();
00246
00247 engine().wait_reset();
00248
00249 engine().ack_reset_stop();
00250 break;
00251 case C_WORK:
00252
00253 {
00254 m.acquire();
00255 if (idle) {
00256 m.release();
00257
00258 find();
00259 } else if (cur != NULL) {
00260 start();
00261 if (stop(engine().opt())) {
00262
00263 m.release();
00264 engine().stop();
00265 } else {
00266 node++;
00267 SearchTracer::EdgeInfo ei;
00268 if (tracer) {
00269 if (path.entries() > 0) {
00270 typename Path<Tracer>::Edge& top = path.top();
00271 ei.init(tracer.wid(), top.nid(), top.truealt(),
00272 *cur, *top.choice());
00273 } else if (*tracer.ei()) {
00274 ei = *tracer.ei();
00275 tracer.invalidate();
00276 }
00277 }
00278 unsigned int nid = tracer.nid();
00279 switch (cur->status(*this)) {
00280 case SS_FAILED:
00281 if (tracer) {
00282 SearchTracer::NodeInfo ni(SearchTracer::NodeType::FAILED,
00283 tracer.wid(), nid, *cur);
00284 tracer.node(ei,ni);
00285 }
00286 fail++;
00287 delete cur;
00288 cur = NULL;
00289 path.next();
00290 m.release();
00291 break;
00292 case SS_SOLVED:
00293 {
00294 if (tracer) {
00295 SearchTracer::NodeInfo ni(SearchTracer::NodeType::SOLVED,
00296 tracer.wid(), nid, *cur);
00297 tracer.node(ei,ni);
00298 }
00299
00300 (void) cur->choice();
00301 Space* s = cur->clone();
00302 delete cur;
00303 cur = NULL;
00304 path.next();
00305 m.release();
00306 engine().solution(s);
00307 }
00308 break;
00309 case SS_BRANCH:
00310 {
00311 Space* c;
00312 if ((d == 0) || (d >= engine().opt().c_d)) {
00313 c = cur->clone();
00314 d = 1;
00315 } else {
00316 c = NULL;
00317 d++;
00318 }
00319 const Choice* ch = path.push(*this,cur,c,nid);
00320 if (tracer) {
00321 SearchTracer::NodeInfo ni(SearchTracer::NodeType::BRANCH,
00322 tracer.wid(), nid, *cur, ch);
00323 tracer.node(ei,ni);
00324 }
00325 cur->commit(*ch,0);
00326 m.release();
00327 }
00328 break;
00329 default:
00330 GECODE_NEVER;
00331 }
00332 }
00333 } else if (!path.empty()) {
00334 cur = path.recompute(d,engine().opt().a_d,*this,*best,mark,tracer);
00335 if (cur == NULL)
00336 path.next();
00337 m.release();
00338 } else {
00339 idle = true;
00340 path.ngdl(0);
00341 m.release();
00342
00343 engine().idle();
00344 }
00345 }
00346 break;
00347 default:
00348 GECODE_NEVER;
00349 }
00350 }
00351 }
00352
00353
00354
00355
00356
00357
00358 template<class Tracer>
00359 void
00360 BAB<Tracer>::reset(Space* s) {
00361
00362 m_wait_reset.acquire();
00363
00364 release(C_RESET);
00365
00366 e_reset_ack_start.wait();
00367
00368 delete best;
00369 best = NULL;
00370 n_busy = workers();
00371 for (unsigned int i=1U; i<workers(); i++)
00372 worker(i)->reset(NULL,0);
00373 worker(0)->reset(s,opt().nogoods_limit);
00374
00375 block();
00376
00377 m_wait_reset.release();
00378
00379 e_reset_ack_stop.wait();
00380 }
00381
00382
00383
00384
00385
00386
00387 template<class Tracer>
00388 NoGoods&
00389 BAB<Tracer>::nogoods(void) {
00390 NoGoods* ng;
00391
00392 m_wait_reset.acquire();
00393
00394 release(C_RESET);
00395
00396 e_reset_ack_start.wait();
00397 ng = &worker(0)->nogoods();
00398
00399 block();
00400
00401 m_wait_reset.release();
00402
00403 e_reset_ack_stop.wait();
00404 return *ng;
00405 }
00406
00407
00408
00409
00410 template<class Tracer>
00411 BAB<Tracer>::Worker::~Worker(void) {
00412 delete best;
00413 }
00414
00415 template<class Tracer>
00416 BAB<Tracer>::~BAB(void) {
00417 terminate();
00418 delete best;
00419 heap.rfree(_worker);
00420 }
00421
00422 }}}
00423
00424