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, size_t sz, Engine& e);
00070 Space* steal(unsigned long int& d);
00072 Statistics statistics(void);
00074 Engine& engine(void) const;
00076 virtual ~Worker(void);
00077 };
00079 const Options _opt;
00080 public:
00082 const Options& opt(void) const;
00084 unsigned int workers(void) const;
00085
00087
00088
00089 enum Cmd {
00090 C_WORK,
00091 C_WAIT,
00092 C_RESET,
00093 C_TERMINATE
00094 };
00095 protected:
00097 volatile Cmd _cmd;
00099 Support::Mutex _m_wait;
00100 public:
00102 Cmd cmd(void) const;
00104 void block(void);
00106 void release(Cmd c);
00108 void wait(void);
00110
00112
00113 protected:
00115 Support::Mutex _m_term;
00117 volatile unsigned int _n_term_not_ack;
00119 Support::Event _e_term_ack;
00121 Support::Mutex _m_wait_terminate;
00123 volatile unsigned int _n_not_terminated;
00125 Support::Event _e_terminate;
00126 public:
00128 void ack_terminate(void);
00130 void terminated(void);
00132 void wait_terminate(void);
00134 void terminate(void);
00136
00138
00139 protected:
00141 Support::Mutex _m_reset;
00143 volatile unsigned int _n_reset_not_ack;
00145 Support::Event e_reset_ack_start;
00147 Support::Event e_reset_ack_stop;
00149 Support::Mutex m_wait_reset;
00150 public:
00152 void ack_reset_start(void);
00154 void ack_reset_stop(void);
00156 void wait_reset(void);
00158
00160
00161 protected:
00163 Support::Mutex m_search;
00165 Support::Event e_search;
00167 Support::DynamicQueue<Space*,Heap> solutions;
00169 volatile unsigned int n_busy;
00171 volatile bool has_stopped;
00173 bool signal(void) const;
00174 public:
00176 void idle(void);
00178 void busy(void);
00180 void stop(void);
00182
00184
00185
00186 Engine(const Options& o);
00188 virtual Space* next(void);
00190 virtual bool stopped(void) const;
00192 };
00193
00194
00195
00196
00197
00198 forceinline Engine&
00199 Engine::Worker::engine(void) const {
00200 return _engine;
00201 }
00202 forceinline const Options&
00203 Engine::opt(void) const {
00204 return _opt;
00205 }
00206 forceinline unsigned int
00207 Engine::workers(void) const {
00208 return static_cast<unsigned int>(opt().threads);
00209 }
00210
00211
00212
00213
00214
00215 forceinline Engine::Cmd
00216 Engine::cmd(void) const {
00217 return _cmd;
00218 }
00219 forceinline void
00220 Engine::block(void) {
00221 _cmd = C_WAIT;
00222 _m_wait.acquire();
00223 }
00224 forceinline void
00225 Engine::release(Cmd c) {
00226 _cmd = c;
00227 _m_wait.release();
00228 }
00229 forceinline void
00230 Engine::wait(void) {
00231 _m_wait.acquire(); _m_wait.release();
00232 }
00233
00234
00235
00236
00237
00238 forceinline
00239 Engine::Worker::Worker(Space* s, size_t sz, Engine& e)
00240 : Search::Worker(sz), _engine(e), d(0), idle(false) {
00241 current(s);
00242 if (s != NULL) {
00243 if (s->status(*this) == SS_FAILED) {
00244 fail++;
00245 cur = NULL;
00246 if (!engine().opt().clone)
00247 delete s;
00248 } else {
00249 cur = snapshot(s,engine().opt(),false);
00250 }
00251 } else {
00252 cur = NULL;
00253 }
00254 current(NULL);
00255 current(cur);
00256 }
00257
00258 forceinline
00259 Engine::Engine(const Options& o)
00260 : _opt(o), solutions(heap) {
00261
00262 _n_term_not_ack = workers();
00263 _n_not_terminated = workers();
00264
00265 n_busy = workers();
00266 has_stopped = false;
00267
00268 _n_reset_not_ack = workers();
00269 }
00270
00271
00272
00273
00274
00275 forceinline Statistics
00276 Engine::Worker::statistics(void) {
00277 m.acquire();
00278 Statistics s = *this;
00279 s.memory += path.size();
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 #endif
00417
00418