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