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 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 forceinline bool
00213 Engine::stopped(void) const {
00214 return has_stopped;
00215 }
00216
00217
00218
00219
00220
00221
00222 forceinline Engine::Cmd
00223 Engine::cmd(void) const {
00224 return _cmd;
00225 }
00226 forceinline void
00227 Engine::block(void) {
00228 _cmd = C_WAIT;
00229 _m_wait.acquire();
00230 }
00231 forceinline void
00232 Engine::release(Cmd c) {
00233 _cmd = c;
00234 _m_wait.release();
00235 }
00236 forceinline void
00237 Engine::wait(void) {
00238 _m_wait.acquire(); _m_wait.release();
00239 }
00240
00241
00242
00243
00244
00245 forceinline
00246 Engine::Worker::Worker(Space* s, Engine& e)
00247 : _engine(e),
00248 path(s == NULL ? 0 : e.opt().nogoods_limit), d(0),
00249 idle(false) {
00250 if (s != NULL) {
00251 if (s->status(*this) == SS_FAILED) {
00252 fail++;
00253 cur = NULL;
00254 if (!engine().opt().clone)
00255 delete s;
00256 } else {
00257 cur = snapshot(s,engine().opt(),false);
00258 }
00259 } else {
00260 cur = NULL;
00261 }
00262 }
00263
00264 forceinline
00265 Engine::Engine(const Options& o)
00266 : _opt(o), solutions(heap) {
00267
00268 _n_term_not_ack = workers();
00269 _n_not_terminated = workers();
00270
00271 n_busy = workers();
00272 has_stopped = false;
00273
00274 _n_reset_not_ack = workers();
00275 }
00276
00277
00278
00279
00280
00281 forceinline Statistics
00282 Engine::Worker::statistics(void) {
00283 m.acquire();
00284 Statistics s = *this;
00285 m.release();
00286 return s;
00287 }
00288
00289
00290
00291
00292
00293 forceinline bool
00294 Engine::signal(void) const {
00295 return solutions.empty() && (n_busy > 0) && !has_stopped;
00296 }
00297 forceinline void
00298 Engine::idle(void) {
00299 m_search.acquire();
00300 bool bs = signal();
00301 n_busy--;
00302 if (bs && (n_busy == 0))
00303 e_search.signal();
00304 m_search.release();
00305 }
00306 forceinline void
00307 Engine::busy(void) {
00308 m_search.acquire();
00309 assert(n_busy > 0);
00310 n_busy++;
00311 m_search.release();
00312 }
00313 forceinline void
00314 Engine::stop(void) {
00315 m_search.acquire();
00316 bool bs = signal();
00317 has_stopped = true;
00318 if (bs)
00319 e_search.signal();
00320 m_search.release();
00321 }
00322
00323
00324
00325
00326
00327 forceinline void
00328 Engine::terminated(void) {
00329 unsigned int n;
00330 _m_term.acquire();
00331 n = --_n_not_terminated;
00332 _m_term.release();
00333
00334
00335 if (n == 0)
00336 _e_terminate.signal();
00337 }
00338
00339 forceinline void
00340 Engine::ack_terminate(void) {
00341 _m_term.acquire();
00342 if (--_n_term_not_ack == 0)
00343 _e_term_ack.signal();
00344 _m_term.release();
00345 }
00346
00347 forceinline void
00348 Engine::wait_terminate(void) {
00349 _m_wait_terminate.acquire();
00350 _m_wait_terminate.release();
00351 }
00352
00353 forceinline void
00354 Engine::terminate(void) {
00355
00356 _m_wait_terminate.acquire();
00357
00358 release(C_TERMINATE);
00359
00360 _e_term_ack.wait();
00361
00362 _m_wait_terminate.release();
00363
00364 _e_terminate.wait();
00365
00366 }
00367
00368
00369
00370
00371
00372
00373 forceinline void
00374 Engine::ack_reset_start(void) {
00375 _m_reset.acquire();
00376 if (--_n_reset_not_ack == 0)
00377 e_reset_ack_start.signal();
00378 _m_reset.release();
00379 }
00380
00381 forceinline void
00382 Engine::ack_reset_stop(void) {
00383 _m_reset.acquire();
00384 if (++_n_reset_not_ack == workers())
00385 e_reset_ack_stop.signal();
00386 _m_reset.release();
00387 }
00388
00389 forceinline void
00390 Engine::wait_reset(void) {
00391 m_wait_reset.acquire();
00392 m_wait_reset.release();
00393 }
00394
00395
00396
00397
00398
00399
00400 forceinline Space*
00401 Engine::Worker::steal(unsigned long int& d) {
00402
00403
00404
00405
00406
00407
00408 if (!path.steal())
00409 return NULL;
00410 m.acquire();
00411 Space* s = path.steal(*this,d);
00412 m.release();
00413
00414 if (s != NULL)
00415 engine().busy();
00416 return s;
00417 }
00418
00419
00420
00421
00422 forceinline NoGoods&
00423 Engine::Worker::nogoods(void) {
00424 return path;
00425 }
00426
00427 }}}
00428
00429 #endif
00430
00431