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 void constrain(const Space& b);
00097 virtual NoGoods& nogoods(void);
00099 virtual ~BAB(void);
00101 };
00102
00103
00104
00105
00106
00107
00108 forceinline BAB&
00109 BAB::Worker::engine(void) const {
00110 return static_cast<BAB&>(_engine);
00111 }
00112 forceinline BAB::Worker*
00113 BAB::worker(unsigned int i) const {
00114 return _worker[i];
00115 }
00116
00117 forceinline void
00118 BAB::Worker::reset(Space* s, unsigned int ngdl) {
00119 delete cur;
00120 delete best;
00121 best = NULL;
00122 path.reset((s == NULL) ? 0 : ngdl);
00123 d = 0;
00124 mark = 0;
00125 idle = false;
00126 if ((s == NULL) || (s->status(*this) == SS_FAILED)) {
00127 delete s;
00128 cur = NULL;
00129 } else {
00130 cur = s;
00131 }
00132 Search::Worker::reset();
00133 }
00134
00135
00136
00137
00138
00139 forceinline
00140 BAB::Worker::Worker(Space* s, BAB& e)
00141 : Engine::Worker(s,e), mark(0), best(NULL) {}
00142
00143 forceinline
00144 BAB::BAB(Space* s, const Options& o)
00145 : Engine(o), best(NULL) {
00146
00147 _worker = static_cast<Worker**>
00148 (heap.ralloc(workers() * sizeof(Worker*)));
00149
00150 _worker[0] = new Worker(s,*this);
00151
00152 for (unsigned int i=1; i<workers(); i++)
00153 _worker[i] = new Worker(NULL,*this);
00154
00155 block();
00156
00157 for (unsigned int i=0; i<workers(); i++)
00158 Support::Thread::run(_worker[i]);
00159 }
00160
00161
00162
00163
00164
00165 forceinline void
00166 BAB::Worker::better(Space* b) {
00167 m.acquire();
00168 delete best;
00169 best = b->clone(false);
00170 mark = path.entries();
00171 if (cur != NULL)
00172 cur->constrain(*best);
00173 m.release();
00174 }
00175 forceinline void
00176 BAB::solution(Space* s) {
00177 m_search.acquire();
00178 if (best != NULL) {
00179 s->constrain(*best);
00180 if (s->status() == SS_FAILED) {
00181 delete s;
00182 m_search.release();
00183 return;
00184 } else {
00185 delete best;
00186 best = s->clone();
00187 }
00188 } else {
00189 best = s->clone();
00190 }
00191
00192 for (unsigned int i=0; i<workers(); i++)
00193 worker(i)->better(best);
00194 bool bs = signal();
00195 solutions.push(s);
00196 if (bs)
00197 e_search.signal();
00198 m_search.release();
00199 }
00200
00201
00202
00203
00204
00205 forceinline void
00206 BAB::Worker::find(void) {
00207
00208 for (unsigned int i=0; i<engine().workers(); i++) {
00209 unsigned long int r_d = 0ul;
00210 if (Space* s = engine().worker(i)->steal(r_d)) {
00211
00212 m.acquire();
00213 idle = false;
00214
00215 path.ngdl(0);
00216 d = 0;
00217 cur = s;
00218 mark = 0;
00219 if (best != NULL)
00220 cur->constrain(*best);
00221 Search::Worker::reset(r_d);
00222 m.release();
00223 return;
00224 }
00225 }
00226 }
00227
00228 }}}
00229
00230 #endif
00231
00232