pbs.hpp
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 #include <algorithm>
00035
00036 namespace Gecode { namespace Search { namespace Par {
00037
00038
00039 forceinline
00040 CollectAll::CollectAll(void)
00041 : solutions(heap) {}
00042 forceinline bool
00043 CollectAll::add(Space* s, Slave<CollectAll>*) {
00044 solutions.push(s);
00045 return true;
00046 }
00047 forceinline bool
00048 CollectAll::constrain(const Space& b) {
00049 (void) b;
00050 return false;
00051 }
00052 forceinline bool
00053 CollectAll::empty(void) const {
00054 return solutions.empty();
00055 }
00056 forceinline Space*
00057 CollectAll::get(Slave<CollectAll>*&) {
00058 return solutions.pop();
00059 }
00060 forceinline
00061 CollectAll::~CollectAll(void) {
00062 while (!solutions.empty())
00063 delete solutions.pop();
00064 }
00065
00066
00067 forceinline
00068 CollectBest::CollectBest(void)
00069 : b(NULL), reporter(NULL) {}
00070 forceinline bool
00071 CollectBest::add(Space* s, Slave<CollectBest>* r) {
00072 if (b != NULL) {
00073 b->constrain(*s);
00074 if (b->status() == SS_FAILED) {
00075 delete b;
00076 } else {
00077 delete s;
00078 return false;
00079 }
00080 }
00081 b = s;
00082 reporter = r;
00083 return true;
00084 }
00085 forceinline bool
00086 CollectBest::constrain(const Space& s) {
00087 if (b != NULL) {
00088 b->constrain(s);
00089 if (b->status() == SS_FAILED) {
00090 delete b;
00091 } else {
00092 return false;
00093 }
00094 }
00095 b = s.clone();
00096 reporter = NULL;
00097 return true;
00098 }
00099 forceinline bool
00100 CollectBest::empty(void) const {
00101 return reporter == NULL;
00102 }
00103 forceinline Space*
00104 CollectBest::get(Slave<CollectBest>*& r) {
00105 assert(!empty());
00106 r = reporter;
00107 reporter = NULL;
00108 return b->clone();
00109 }
00110 forceinline
00111 CollectBest::~CollectBest(void) {
00112 delete b;
00113 }
00114
00115
00116 forceinline
00117 PortfolioStop::PortfolioStop(Stop* so0)
00118 : so(so0), tostop(NULL) {}
00119
00120 forceinline void
00121 PortfolioStop::share(volatile bool* ts) {
00122 tostop = ts;
00123 }
00124
00125
00126 template<class Collect>
00127 forceinline
00128 Slave<Collect>::Slave(PBS<Collect>* m, Engine* s, Stop* so)
00129 : Support::Runnable(false), master(m), slave(s), stop(so) {}
00130 template<class Collect>
00131 forceinline Statistics
00132 Slave<Collect>::statistics(void) const {
00133 return slave->statistics();
00134 }
00135 template<class Collect>
00136 forceinline bool
00137 Slave<Collect>::stopped(void) const {
00138 return slave->stopped();
00139 }
00140 template<class Collect>
00141 forceinline void
00142 Slave<Collect>::constrain(const Space& b) {
00143 slave->constrain(b);
00144 }
00145 template<class Collect>
00146 Slave<Collect>::~Slave(void) {
00147 delete slave;
00148 delete stop;
00149 }
00150
00151
00152
00153 template<class Collect>
00154 forceinline
00155 PBS<Collect>::PBS(Engine** engines, Stop** stops, unsigned int n,
00156 const Statistics& stat0)
00157 : stat(stat0), slaves(heap.alloc<Slave<Collect>*>(n)),
00158 n_slaves(n), n_active(n),
00159 slave_stop(false), tostop(false), n_busy(0) {
00160
00161 for (unsigned int i=n_slaves; i--; ) {
00162 slaves[i] = new Slave<Collect>(this,engines[i],stops[i]);
00163 static_cast<PortfolioStop*>(stops[i])->share(&tostop);
00164 }
00165 }
00166
00167
00168 template<class Collect>
00169 forceinline bool
00170 PBS<Collect>::report(Slave<Collect>* slave, Space* s) {
00171
00172 bool b = true;
00173 m.acquire();
00174 if (s != NULL) {
00175 b = solutions.add(s,slave);
00176 if (b)
00177 tostop = true;
00178 } else if (slave->stopped()) {
00179 if (!tostop)
00180 slave_stop = true;
00181 } else {
00182
00183 unsigned int i=0;
00184 while (slaves[i] != slave)
00185 i++;
00186 assert(i < n_active);
00187 assert(n_active > 0);
00188 std::swap(slaves[i],slaves[--n_active]);
00189 tostop = true;
00190 }
00191 if (b) {
00192 if (--n_busy == 0)
00193 idle.signal();
00194 }
00195 m.release();
00196 return b;
00197 }
00198
00199 template<class Collect>
00200 void
00201 Slave<Collect>::run(void) {
00202 Space* s;
00203 do {
00204 s = slave->next();
00205 } while (!master->report(this,s));
00206 }
00207
00208 template<class Collect>
00209 Space*
00210 PBS<Collect>::next(void) {
00211 m.acquire();
00212 if (solutions.empty()) {
00213
00214 tostop = false;
00215 slave_stop = false;
00216
00217
00218 assert(n_busy == 0);
00219 assert(!tostop);
00220
00221 if (n_active > 0) {
00222
00223 n_busy = n_active;
00224 for (unsigned int i=n_active; i--; )
00225 Support::Thread::run(slaves[i]);
00226 m.release();
00227
00228 idle.wait();
00229 m.acquire();
00230 }
00231 }
00232
00233
00234 assert(n_busy == 0);
00235
00236 Space* s;
00237
00238
00239 if (solutions.empty()) {
00240 s = NULL;
00241 } else {
00242 Slave<Collect>* r;
00243 s = solutions.get(r);
00244 if (Collect::best)
00245 for (unsigned int i=n_active; i--; )
00246 if (slaves[i] != r)
00247 slaves[i]->constrain(*s);
00248 }
00249
00250 m.release();
00251 return s;
00252 }
00253
00254 template<class Collect>
00255 bool
00256 PBS<Collect>::stopped(void) const {
00257 return slave_stop;
00258 }
00259
00260 template<class Collect>
00261 Statistics
00262 PBS<Collect>::statistics(void) const {
00263 assert(n_busy == 0);
00264 Statistics s(stat);
00265 for (unsigned int i=n_slaves; i--; )
00266 s += slaves[i]->statistics();
00267 return s;
00268 }
00269
00270 template<class Collect>
00271 void
00272 PBS<Collect>::constrain(const Space& b) {
00273 assert(n_busy == 0);
00274 if (!Collect::best)
00275 throw NoBest("PBS::constrain");
00276 if (solutions.constrain(b)) {
00277
00278 for (unsigned int i=n_active; i--; )
00279 slaves[i]->constrain(b);
00280 }
00281 }
00282
00283 template<class Collect>
00284 PBS<Collect>::~PBS(void) {
00285 assert(n_busy == 0);
00286 heap.free<Slave<Collect>*>(slaves,n_slaves);
00287 }
00288
00289 }}}
00290
00291