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