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