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 #include <cmath>
00039 #include <algorithm>
00040
00041 namespace Gecode { namespace Search {
00042
00044 template<class T, template<class> class E>
00045 class PbsBuilder : public Builder {
00046 using Builder::opt;
00047 public:
00049 PbsBuilder(const Options& opt);
00051 virtual Engine* operator() (Space* s) const;
00052 };
00053
00054 template<class T, template<class> class E>
00055 inline
00056 PbsBuilder<T,E>::PbsBuilder(const Options& opt)
00057 : Builder(opt,E<T>::best) {}
00058
00059 template<class T, template<class> class E>
00060 Engine*
00061 PbsBuilder<T,E>::operator() (Space* s) const {
00062 return build<T,PBS<T,E> >(s,opt);
00063 }
00064
00065 }}
00066
00067 #include <gecode/search/meta/dead.hh>
00068
00069 namespace Gecode { namespace Search { namespace Meta { namespace Sequential {
00070
00072 GECODE_SEARCH_EXPORT Stop*
00073 stop(Stop* so);
00074
00076 GECODE_SEARCH_EXPORT Engine*
00077 engine(Engine** slaves, Stop** stops, unsigned int n_slaves,
00078 const Statistics& stat, const Search::Options& opt, bool best);
00079
00080 }}}}
00081
00082 namespace Gecode { namespace Search { namespace Meta { namespace Parallel {
00083
00085 GECODE_SEARCH_EXPORT Stop*
00086 stop(Stop* so);
00087
00089 GECODE_SEARCH_EXPORT Engine*
00090 engine(Engine** slaves, Stop** stops, unsigned int n_slaves,
00091 const Statistics& stat, bool best);
00092
00093 }}}}
00094
00095 namespace Gecode { namespace Search { namespace Meta {
00096
00097 template<class T, template<class> class E>
00098 Engine*
00099 sequential(T* master, const Search::Statistics& stat, Options& opt) {
00100 Stop* stop = opt.stop;
00101 Region r(*master);
00102
00103
00104 opt.threads = std::max(floor(opt.threads /
00105 static_cast<double>(opt.assets)),1.0);
00106
00107 unsigned int n_slaves = opt.assets;
00108 Engine** slaves = r.alloc<Engine*>(n_slaves);
00109 Stop** stops = r.alloc<Stop*>(n_slaves);
00110
00111 for (unsigned int i=0; i<n_slaves; i++) {
00112 opt.stop = stops[i] = Sequential::stop(stop);
00113 Space* slave = (i == n_slaves-1) ?
00114 master : master->clone(opt.threads <= 1.0,opt.share_pbs);
00115 (void) slave->slave(i);
00116 slaves[i] = build<T,E>(slave,opt);
00117 }
00118
00119 return Sequential::engine(slaves,stops,n_slaves,stat,opt,E<T>::best);
00120 }
00121
00122 template<class T, template<class> class E>
00123 Engine*
00124 sequential(T* master, SEBs& sebs,
00125 const Search::Statistics& stat, Options& opt, bool best) {
00126 Region r(*master);
00127
00128 int n_slaves = sebs.size();
00129 Engine** slaves = r.alloc<Engine*>(n_slaves);
00130 Stop** stops = r.alloc<Stop*>(n_slaves);
00131
00132 for (int i=0; i<n_slaves; i++) {
00133
00134 stops[i] = Sequential::stop(sebs[i]->options().stop);
00135 sebs[i]->options().stop = stops[i];
00136 sebs[i]->options().clone = false;
00137 Space* slave = (i == n_slaves-1) ?
00138 master : master->clone(sebs[i]->options().threads <= 1.0,
00139 sebs[i]->options().share_pbs);
00140 (void) slave->slave(i);
00141 slaves[i] = (*sebs[i])(slave);
00142 delete sebs[i];
00143 }
00144
00145 return Sequential::engine(slaves,stops,n_slaves,stat,opt,best);
00146 }
00147
00148 #ifdef GECODE_HAS_THREADS
00149
00150 template<class T, template<class> class E>
00151 Engine*
00152 parallel(T* master, const Search::Statistics& stat, Options& opt) {
00153 Stop* stop = opt.stop;
00154 Region r(*master);
00155
00156
00157 unsigned int n_slaves = std::min(static_cast<unsigned int>(opt.threads),
00158 opt.assets);
00159
00160 opt.threads = floor(opt.threads / static_cast<double>(n_slaves));
00161
00162 Engine** slaves = r.alloc<Engine*>(n_slaves);
00163 Stop** stops = r.alloc<Stop*>(n_slaves);
00164
00165 for (unsigned int i=0; i<n_slaves; i++) {
00166 opt.stop = stops[i] = Parallel::stop(stop);
00167 Space* slave = (i == n_slaves-1) ?
00168 master : master->clone(false,opt.share_pbs);
00169 (void) slave->slave(i);
00170 slaves[i] = build<T,E>(slave,opt);
00171 }
00172
00173 return Parallel::engine(slaves,stops,n_slaves,stat,E<T>::best);
00174 }
00175
00176 template<class T, template<class> class E>
00177 Engine*
00178 parallel(T* master, SEBs& sebs,
00179 const Search::Statistics& stat, Options& opt, bool best) {
00180 Region r(*master);
00181
00182
00183 int n_slaves = std::min(static_cast<int>(opt.threads),
00184 sebs.size());
00185 Engine** slaves = r.alloc<Engine*>(n_slaves);
00186 Stop** stops = r.alloc<Stop*>(n_slaves);
00187
00188 for (int i=0; i<n_slaves; i++) {
00189
00190 stops[i] = Parallel::stop(sebs[i]->options().stop);
00191 sebs[i]->options().stop = stops[i];
00192 sebs[i]->options().clone = false;
00193 Space* slave = (i == n_slaves-1) ?
00194 master : master->clone(false,sebs[i]->options().share_pbs);
00195 (void) slave->slave(i);
00196 slaves[i] = (*sebs[i])(slave);
00197 delete sebs[i];
00198 }
00199
00200 for (int i=n_slaves; i<sebs.size(); i++)
00201 delete sebs[i];
00202
00203 return Parallel::engine(slaves,stops,n_slaves,stat,best);
00204 }
00205
00206 #endif
00207
00208 }}}
00209
00210 namespace Gecode {
00211
00212 template<class T, template<class> class E>
00213 PBS<T,E>::PBS(T* s, const Search::Options& o) {
00214 Search::Options opt(o.expand());
00215
00216 if (opt.assets == 0)
00217 throw Search::NoAssets("PBS::PBS");
00218
00219 Search::Statistics stat;
00220
00221 if (s->status(stat) == SS_FAILED) {
00222 stat.fail++;
00223 if (!opt.clone)
00224 delete s;
00225 e = new Search::Meta::Dead(stat);
00226 return;
00227 }
00228
00229
00230 T* master = opt.clone ?
00231 dynamic_cast<T*>(s->clone(opt.threads <= 1.0,opt.share_pbs)) : s;
00232 opt.clone = false;
00233
00234
00235 (void) master->master(0);
00236
00237
00238 if (o.assets == 1) {
00239 (void) master->slave(0);
00240 e = Search::build<T,E>(master,opt);
00241 return;
00242 }
00243
00244 #ifdef GECODE_HAS_THREADS
00245 if (opt.threads > 1.0)
00246 e = Search::Meta::parallel<T,E>(master,stat,opt);
00247 else
00248 #endif
00249 e = Search::Meta::sequential<T,E>(master,stat,opt);
00250 }
00251
00252 template<class T, template<class> class E>
00253 void
00254 PBS<T,E>::build(T* s, SEBs& sebs, const Search::Options& o) {
00255
00256 bool best;
00257 {
00258 int b = 0;
00259 for (int i=sebs.size(); i--; )
00260 b += sebs[i]->best() ? 1 : 0;
00261 if ((b > 0) && (b < sebs.size()))
00262 throw Search::MixedBest("PBS::PBS");
00263 best = (b == sebs.size());
00264 }
00265
00266 Search::Options opt(o.expand());
00267 Search::Statistics stat;
00268
00269 if (s->status(stat) == SS_FAILED) {
00270 stat.fail++;
00271 if (!opt.clone)
00272 delete s;
00273 e = new Search::Meta::Dead(stat);
00274 return;
00275 }
00276
00277
00278 T* master = opt.clone ?
00279 dynamic_cast<T*>(s->clone(opt.threads <= 1.0,opt.share_pbs)) : s;
00280 opt.clone = false;
00281
00282
00283 (void) master->master(0);
00284
00285 #ifdef GECODE_HAS_THREADS
00286 if (opt.threads > 1.0)
00287 e = Search::Meta::parallel<T,E>(master,sebs,stat,opt,best);
00288 else
00289 #endif
00290 e = Search::Meta::sequential<T,E>(master,sebs,stat,opt,best);
00291 }
00292
00293 template<class T, template<class> class E>
00294 inline
00295 PBS<T,E>::PBS(T* s, SEBs& sebs, const Search::Options& o) {
00296 build(s,sebs,o);
00297 }
00298 template<class T, template<class> class E>
00299 inline
00300 PBS<T,E>::PBS(T* s, SEB seb0, SEB seb1,
00301 const Search::Options& o) {
00302 SEBs sebs(2, seb0, seb1);
00303 build(s,sebs,o);
00304 }
00305 template<class T, template<class> class E>
00306 inline
00307 PBS<T,E>::PBS(T* s, SEB seb0, SEB seb1, SEB seb2,
00308 const Search::Options& o) {
00309 SEBs sebs(3, seb0, seb1, seb2);
00310 build(s,sebs,o);
00311 }
00312 template<class T, template<class> class E>
00313 inline
00314 PBS<T,E>::PBS(T* s, SEB seb0, SEB seb1, SEB seb2, SEB seb3,
00315 const Search::Options& o) {
00316 SEBs sebs(4, seb0, seb1, seb2, seb3);
00317 build(s,sebs,o);
00318 }
00319
00320 template<class T, template<class> class E>
00321 inline T*
00322 pbs(T* s, const Search::Options& o) {
00323 PBS<T,E> r(s,o);
00324 return r.next();
00325 }
00326
00327 template<class T, template<class> class E>
00328 inline SEB
00329 pbs(const Search::Options& o) {
00330 return new Search::PbsBuilder<T,E>(o);
00331 }
00332
00333 }
00334
00335