engine.hh
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_ENGINE_HH__
00039 #define __GECODE_SEARCH_PARALLEL_ENGINE_HH__
00040
00041 #include <gecode/search.hh>
00042 #include <gecode/search/support.hh>
00043 #include <gecode/search/worker.hh>
00044 #include <gecode/search/parallel/path.hh>
00045
00046 namespace Gecode { namespace Search { namespace Parallel {
00047
00049 class Engine : public Search::Engine {
00050 protected:
00052 class Worker : public Search::Worker, public Support::Runnable {
00053 protected:
00055 Engine& _engine;
00057 Support::Mutex m;
00059 Path path;
00061 Space* cur;
00063 unsigned int d;
00065 bool idle;
00066 public:
00068 Worker(Space* s, Engine& e);
00070 Space* steal(unsigned long int& d);
00072 Statistics statistics(void);
00074 Engine& engine(void) const;
00076 NoGoods& nogoods(void);
00078 virtual ~Worker(void);
00079 };
00081 const Options _opt;
00082 public:
00084 const Options& opt(void) const;
00086 unsigned int workers(void) const;
00087
00089
00090
00091 enum Cmd {
00092 C_WORK,
00093 C_WAIT,
00094 C_RESET,
00095 C_TERMINATE
00096 };
00097 protected:
00099 volatile Cmd _cmd;
00101 Support::Mutex _m_wait;
00102 public:
00104 Cmd cmd(void) const;
00106 void block(void);
00108 void release(Cmd c);
00110 void wait(void);
00112
00114
00115 protected:
00117 Support::Mutex _m_term;
00119 volatile unsigned int _n_term_not_ack;
00121 Support::Event _e_term_ack;
00123 Support::Mutex _m_wait_terminate;
00125 volatile unsigned int _n_not_terminated;
00127 Support::Event _e_terminate;
00128 public:
00130 void ack_terminate(void);
00132 void terminated(void);
00134 void wait_terminate(void);
00136 void terminate(void);
00138
00140
00141 protected:
00143 Support::Mutex _m_reset;
00145 volatile unsigned int _n_reset_not_ack;
00147 Support::Event e_reset_ack_start;
00149 Support::Event e_reset_ack_stop;
00151 Support::Mutex m_wait_reset;
00152 public:
00154 void ack_reset_start(void);
00156 void ack_reset_stop(void);
00158 void wait_reset(void);
00160
00162
00163 protected:
00165 Support::Mutex m_search;
00167 Support::Event e_search;
00169 Support::DynamicQueue<Space*,Heap> solutions;
00171 volatile unsigned int n_busy;
00173 volatile bool has_stopped;
00175 bool signal(void) const;
00176 public:
00178 void idle(void);
00180 void busy(void);
00182 void stop(void);
00184
00186
00187
00188 Engine(const Options& o);
00190 virtual Space* next(void);
00192 virtual bool stopped(void) const;
00194 };
00195
00196
00197
00198
00199
00200 forceinline Engine&
00201 Engine::Worker::engine(void) const {
00202 return _engine;
00203 }
00204 forceinline const Options&
00205 Engine::opt(void) const {
00206 return _opt;
00207 }
00208 forceinline unsigned int
00209 Engine::workers(void) const {
00210 return static_cast<unsigned int>(opt().threads);
00211 }
00212
00213
00214
00215
00216
00217 forceinline Engine::Cmd
00218 Engine::cmd(void) const {
00219 return _cmd;
00220 }
00221 forceinline void
00222 Engine::block(void) {
00223 _cmd = C_WAIT;
00224 _m_wait.acquire();
00225 }
00226 forceinline void
00227 Engine::release(Cmd c) {
00228 _cmd = c;
00229 _m_wait.release();
00230 }
00231 forceinline void
00232 Engine::wait(void) {
00233 _m_wait.acquire(); _m_wait.release();
00234 }
00235
00236
00237
00238
00239
00240 forceinline
00241 Engine::Worker::Worker(Space* s, Engine& e)
00242 : _engine(e),
00243 path(s == NULL ? 0 : e.opt().nogoods_limit), d(0),
00244 idle(false) {
00245 if (s != NULL) {
00246 if (s->status(*this) == SS_FAILED) {
00247 fail++;
00248 cur = NULL;
00249 if (!engine().opt().clone)
00250 delete s;
00251 } else {
00252 cur = snapshot(s,engine().opt(),false);
00253 }
00254 } else {
00255 cur = NULL;
00256 }
00257 }
00258
00259 forceinline
00260 Engine::Engine(const Options& o)
00261 : _opt(o), solutions(heap) {
00262
00263 _n_term_not_ack = workers();
00264 _n_not_terminated = workers();
00265
00266 n_busy = workers();
00267 has_stopped = false;
00268
00269 _n_reset_not_ack = workers();
00270 }
00271
00272
00273
00274
00275
00276 forceinline Statistics
00277 Engine::Worker::statistics(void) {
00278 m.acquire();
00279 Statistics s = *this;
00280 m.release();
00281 return s;
00282 }
00283
00284
00285
00286
00287
00288 forceinline bool
00289 Engine::signal(void) const {
00290 return solutions.empty() && (n_busy > 0) && !has_stopped;
00291 }
00292 forceinline void
00293 Engine::idle(void) {
00294 m_search.acquire();
00295 bool bs = signal();
00296 n_busy--;
00297 if (bs && (n_busy == 0))
00298 e_search.signal();
00299 m_search.release();
00300 }
00301 forceinline void
00302 Engine::busy(void) {
00303 m_search.acquire();
00304 assert(n_busy > 0);
00305 n_busy++;
00306 m_search.release();
00307 }
00308 forceinline void
00309 Engine::stop(void) {
00310 m_search.acquire();
00311 bool bs = signal();
00312 has_stopped = true;
00313 if (bs)
00314 e_search.signal();
00315 m_search.release();
00316 }
00317
00318
00319
00320
00321
00322 forceinline void
00323 Engine::terminated(void) {
00324 unsigned int n;
00325 _m_term.acquire();
00326 n = --_n_not_terminated;
00327 _m_term.release();
00328
00329
00330 if (n == 0)
00331 _e_terminate.signal();
00332 }
00333
00334 forceinline void
00335 Engine::ack_terminate(void) {
00336 _m_term.acquire();
00337 if (--_n_term_not_ack == 0)
00338 _e_term_ack.signal();
00339 _m_term.release();
00340 }
00341
00342 forceinline void
00343 Engine::wait_terminate(void) {
00344 _m_wait_terminate.acquire();
00345 _m_wait_terminate.release();
00346 }
00347
00348 forceinline void
00349 Engine::terminate(void) {
00350
00351 _m_wait_terminate.acquire();
00352
00353 release(C_TERMINATE);
00354
00355 _e_term_ack.wait();
00356
00357 _m_wait_terminate.release();
00358
00359 _e_terminate.wait();
00360
00361 }
00362
00363
00364
00365
00366
00367
00368 forceinline void
00369 Engine::ack_reset_start(void) {
00370 _m_reset.acquire();
00371 if (--_n_reset_not_ack == 0)
00372 e_reset_ack_start.signal();
00373 _m_reset.release();
00374 }
00375
00376 forceinline void
00377 Engine::ack_reset_stop(void) {
00378 _m_reset.acquire();
00379 if (++_n_reset_not_ack == workers())
00380 e_reset_ack_stop.signal();
00381 _m_reset.release();
00382 }
00383
00384 forceinline void
00385 Engine::wait_reset(void) {
00386 m_wait_reset.acquire();
00387 m_wait_reset.release();
00388 }
00389
00390
00391
00392
00393
00394
00395 forceinline Space*
00396 Engine::Worker::steal(unsigned long int& d) {
00397
00398
00399
00400
00401
00402
00403 if (!path.steal())
00404 return NULL;
00405 m.acquire();
00406 Space* s = path.steal(*this,d);
00407 m.release();
00408
00409 if (s != NULL)
00410 engine().busy();
00411 return s;
00412 }
00413
00414
00415
00416
00417 forceinline NoGoods&
00418 Engine::Worker::nogoods(void) {
00419 return path;
00420 }
00421
00422 }}}
00423
00424 #endif
00425
00426