bab.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_BAB_HH__
00039 #define __GECODE_SEARCH_PARALLEL_BAB_HH__
00040
00041 #include <gecode/search/parallel/engine.hh>
00042
00043 namespace Gecode { namespace Search { namespace Parallel {
00044
00046 class BAB : public Engine {
00047 protected:
00049 class Worker : public Engine::Worker {
00050 protected:
00052 int mark;
00054 Space* best;
00055 public:
00057 Worker(Space* s, BAB& e);
00059 BAB& engine(void) const;
00061 virtual void run(void);
00063 void better(Space* b);
00065 void find(void);
00067 void reset(Space* s, unsigned int ngdl);
00069 virtual ~Worker(void);
00070 };
00072 Worker** _worker;
00074 Space* best;
00075 public:
00077 Worker* worker(unsigned int i) const;
00078
00080
00081
00082 void solution(Space* s);
00084
00086
00087
00088 BAB(Space* s, const Options& o);
00090 virtual Statistics statistics(void) const;
00092 virtual void reset(Space* s);
00094 virtual NoGoods& nogoods(void);
00096 virtual ~BAB(void);
00098 };
00099
00100
00101
00102
00103
00104
00105 forceinline BAB&
00106 BAB::Worker::engine(void) const {
00107 return static_cast<BAB&>(_engine);
00108 }
00109 forceinline BAB::Worker*
00110 BAB::worker(unsigned int i) const {
00111 return _worker[i];
00112 }
00113
00114 forceinline void
00115 BAB::Worker::reset(Space* s, unsigned int ngdl) {
00116 delete cur;
00117 delete best;
00118 best = NULL;
00119 path.reset((s == NULL) ? 0 : ngdl);
00120 d = 0;
00121 mark = 0;
00122 idle = false;
00123 if ((s == NULL) || (s->status(*this) == SS_FAILED)) {
00124 delete s;
00125 cur = NULL;
00126 } else {
00127 cur = s;
00128 }
00129 Search::Worker::reset();
00130 }
00131
00132
00133
00134
00135
00136 forceinline
00137 BAB::Worker::Worker(Space* s, BAB& e)
00138 : Engine::Worker(s,e), mark(0), best(NULL) {}
00139
00140 forceinline
00141 BAB::BAB(Space* s, const Options& o)
00142 : Engine(o), best(NULL) {
00143
00144 _worker = static_cast<Worker**>
00145 (heap.ralloc(workers() * sizeof(Worker*)));
00146
00147 _worker[0] = new Worker(s,*this);
00148
00149 for (unsigned int i=1; i<workers(); i++)
00150 _worker[i] = new Worker(NULL,*this);
00151
00152 block();
00153
00154 for (unsigned int i=0; i<workers(); i++)
00155 Support::Thread::run(_worker[i]);
00156 }
00157
00158
00159
00160
00161
00162 forceinline void
00163 BAB::Worker::better(Space* b) {
00164 m.acquire();
00165 delete best;
00166 best = b->clone(false);
00167 mark = path.entries();
00168 if (cur != NULL)
00169 cur->constrain(*best);
00170 m.release();
00171 }
00172 forceinline void
00173 BAB::solution(Space* s) {
00174 m_search.acquire();
00175 if (best != NULL) {
00176 s->constrain(*best);
00177 if (s->status() == SS_FAILED) {
00178 delete s;
00179 m_search.release();
00180 return;
00181 } else {
00182 delete best;
00183 best = s->clone();
00184 }
00185 } else {
00186 best = s->clone();
00187 }
00188
00189 for (unsigned int i=0; i<workers(); i++)
00190 worker(i)->better(best);
00191 bool bs = signal();
00192 solutions.push(s);
00193 if (bs)
00194 e_search.signal();
00195 m_search.release();
00196 }
00197
00198
00199
00200
00201
00202 forceinline void
00203 BAB::Worker::find(void) {
00204
00205 for (unsigned int i=0; i<engine().workers(); i++) {
00206 unsigned long int r_d = 0ul;
00207 if (Space* s = engine().worker(i)->steal(r_d)) {
00208
00209 m.acquire();
00210 idle = false;
00211
00212 path.ngdl(0);
00213 d = 0;
00214 cur = s;
00215 mark = 0;
00216 if (best != NULL)
00217 cur->constrain(*best);
00218 Search::Worker::reset(r_d);
00219 m.release();
00220 return;
00221 }
00222 }
00223 }
00224
00225 }}}
00226
00227 #endif
00228
00229