1 /* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */ 2 /* 3 * Main authors: 4 * Christian Schulte <schulte@gecode.org> 5 * 6 * Copyright: 7 * Christian Schulte, 2015 8 * 9 * This file is part of Gecode, the generic constraint 10 * development environment: 11 * http://www.gecode.org 12 * 13 * Permission is hereby granted, free of charge, to any person obtaining 14 * a copy of this software and associated documentation files (the 15 * "Software"), to deal in the Software without restriction, including 16 * without limitation the rights to use, copy, modify, merge, publish, 17 * distribute, sublicense, and/or sell copies of the Software, and to 18 * permit persons to whom the Software is furnished to do so, subject to 19 * the following conditions: 20 * 21 * The above copyright notice and this permission notice shall be 22 * included in all copies or substantial portions of the Software. 23 * 24 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, 25 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF 26 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND 27 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE 28 * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION 29 * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION 30 * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. 31 * 32 */ 33 34 #include <cmath> 35 #include <algorithm> 36 37 namespace Gecode { namespace Search { 38 39 /// A PBS engine builder 40 template<class T, template<class> class E> 41 class PbsBuilder : public Builder { 42 using Builder::opt; 43 public: 44 /// The constructor 45 PbsBuilder(const Options& opt); 46 /// The actual build function 47 virtual Engine* operator() (Space* s) const; 48 }; 49 50 template<class T, template<class> class E> 51 inline PbsBuilder(const Options & opt)52 PbsBuilder<T,E>::PbsBuilder(const Options& opt) 53 : Builder(opt,E<T>::best) {} 54 55 template<class T, template<class> class E> 56 Engine* operator ()(Space * s) const57 PbsBuilder<T,E>::operator() (Space* s) const { 58 return build<T,PBS<T,E> >(s,opt); 59 } 60 61 }} 62 63 #include <gecode/search/seq/dead.hh> 64 65 namespace Gecode { namespace Search { namespace Seq { 66 67 /// Create stop object 68 GECODE_SEARCH_EXPORT Stop* 69 pbsstop(Stop* so); 70 71 /// Create sequential portfolio engine 72 GECODE_SEARCH_EXPORT Engine* 73 pbsengine(Engine** slaves, Stop** stops, unsigned int n_slaves, 74 const Statistics& stat, const Search::Options& opt, bool best); 75 76 }}} 77 78 namespace Gecode { namespace Search { namespace Par { 79 80 /// Create stop object 81 GECODE_SEARCH_EXPORT Stop* 82 pbsstop(Stop* so); 83 84 /// Create parallel portfolio engine 85 GECODE_SEARCH_EXPORT Engine* 86 pbsengine(Engine** slaves, Stop** stops, unsigned int n_slaves, 87 const Statistics& stat, bool best); 88 89 }}} 90 91 namespace Gecode { namespace Search { 92 93 template<class T, template<class> class E> 94 Engine* pbsseq(T * master,const Search::Statistics & stat,Options & opt)95 pbsseq(T* master, const Search::Statistics& stat, Options& opt) { 96 Stop* stop = opt.stop; 97 Region r; 98 99 // In case there are more threads than assets requested 100 opt.threads = std::max(floor(opt.threads / 101 static_cast<double>(opt.assets)),1.0); 102 103 unsigned int n_slaves = opt.assets; 104 Engine** slaves = r.alloc<Engine*>(n_slaves); 105 Stop** stops = r.alloc<Stop*>(n_slaves); 106 107 WrapTraceRecorder::engine(opt.tracer, 108 SearchTracer::EngineType::PBS, n_slaves); 109 110 for (unsigned int i=0U; i<n_slaves; i++) { 111 opt.stop = stops[i] = Seq::pbsstop(stop); 112 Space* slave = (i == n_slaves-1) ? 113 master : master->clone(); 114 (void) slave->slave(i); 115 slaves[i] = build<T,E>(slave,opt); 116 } 117 118 return Seq::pbsengine(slaves,stops,n_slaves,stat,opt,E<T>::best); 119 } 120 121 template<class T, template<class> class E> 122 Engine* pbsseq(T * master,SEBs & sebs,const Search::Statistics & stat,Options & opt,bool best)123 pbsseq(T* master, SEBs& sebs, 124 const Search::Statistics& stat, Options& opt, bool best) { 125 Region r; 126 127 int n_slaves = sebs.size(); 128 Engine** slaves = r.alloc<Engine*>(n_slaves); 129 Stop** stops = r.alloc<Stop*>(n_slaves); 130 131 WrapTraceRecorder::engine(opt.tracer, 132 SearchTracer::EngineType::PBS, 133 static_cast<unsigned int>(n_slaves)); 134 135 for (int i=0; i<n_slaves; i++) { 136 // Re-configure slave options 137 stops[i] = Seq::pbsstop(sebs[i]->options().stop); 138 sebs[i]->options().stop = stops[i]; 139 sebs[i]->options().clone = false; 140 Space* slave = (i == n_slaves-1) ? 141 master : master->clone(); 142 (void) slave->slave(static_cast<unsigned int>(i)); 143 slaves[i] = (*sebs[i])(slave); 144 delete sebs[i]; 145 } 146 147 return Seq::pbsengine(slaves,stops,static_cast<unsigned int>(n_slaves), 148 stat,opt,best); 149 } 150 151 #ifdef GECODE_HAS_THREADS 152 153 template<class T, template<class> class E> 154 Engine* pbspar(T * master,const Search::Statistics & stat,Options & opt)155 pbspar(T* master, const Search::Statistics& stat, Options& opt) { 156 Stop* stop = opt.stop; 157 Region r; 158 159 // Limit the number of slaves to the number of threads 160 unsigned int n_slaves = std::min(static_cast<unsigned int>(opt.threads), 161 opt.assets); 162 // Redistribute additional threads to slaves 163 opt.threads = floor(opt.threads / static_cast<double>(n_slaves)); 164 165 WrapTraceRecorder::engine(opt.tracer, 166 SearchTracer::EngineType::PBS, n_slaves); 167 168 Engine** slaves = r.alloc<Engine*>(n_slaves); 169 Stop** stops = r.alloc<Stop*>(n_slaves); 170 171 for (unsigned int i=0U; i<n_slaves; i++) { 172 opt.stop = stops[i] = Par::pbsstop(stop); 173 Space* slave = (i == n_slaves-1) ? 174 master : master->clone(); 175 (void) slave->slave(static_cast<unsigned int>(i)); 176 slaves[i] = build<T,E>(slave,opt); 177 } 178 179 return Par::pbsengine(slaves,stops,n_slaves,stat,E<T>::best); 180 } 181 182 template<class T, template<class> class E> 183 Engine* pbspar(T * master,SEBs & sebs,const Search::Statistics & stat,Options & opt,bool best)184 pbspar(T* master, SEBs& sebs, 185 const Search::Statistics& stat, Options& opt, bool best) { 186 Region r; 187 188 // Limit the number of slaves to the number of threads 189 int n_slaves = std::min(static_cast<int>(opt.threads), 190 sebs.size()); 191 192 WrapTraceRecorder::engine(opt.tracer, 193 SearchTracer::EngineType::PBS, 194 static_cast<unsigned int>(n_slaves)); 195 196 Engine** slaves = r.alloc<Engine*>(n_slaves); 197 Stop** stops = r.alloc<Stop*>(n_slaves); 198 199 for (int i=0; i<n_slaves; i++) { 200 // Re-configure slave options 201 stops[i] = Par::pbsstop(sebs[i]->options().stop); 202 sebs[i]->options().stop = stops[i]; 203 sebs[i]->options().clone = false; 204 Space* slave = (i == n_slaves-1) ? 205 master : master->clone(); 206 (void) slave->slave(static_cast<unsigned int>(i)); 207 slaves[i] = (*sebs[i])(slave); 208 delete sebs[i]; 209 } 210 // Delete excess builders 211 for (int i=n_slaves; i<sebs.size(); i++) 212 delete sebs[i]; 213 214 return Par::pbsengine(slaves,stops,static_cast<unsigned int>(n_slaves), 215 stat,best); 216 } 217 218 #endif 219 220 }} 221 222 namespace Gecode { 223 224 template<class T, template<class> class E> PBS(T * s,const Search::Options & o)225 PBS<T,E>::PBS(T* s, const Search::Options& o) { 226 Search::Options opt(o.expand()); 227 228 if (opt.assets == 0) 229 throw Search::NoAssets("PBS::PBS"); 230 231 Search::Statistics stat; 232 233 if (s->status(stat) == SS_FAILED) { 234 stat.fail++; 235 if (!opt.clone) 236 delete s; 237 e = Search::Seq::dead(opt,stat); 238 return; 239 } 240 241 // Check whether a clone must be used 242 T* master = opt.clone ? 243 dynamic_cast<T*>(s->clone()) : s; 244 opt.clone = false; 245 246 // Always execute master function 247 (void) master->master(0); 248 249 // No need to create a portfolio engine but must run slave function 250 if (o.assets == 1) { 251 (void) master->slave(0); 252 e = Search::build<T,E>(master,opt); 253 return; 254 } 255 256 #ifdef GECODE_HAS_THREADS 257 if (opt.threads > 1.0) 258 e = Search::pbspar<T,E>(master,stat,opt); 259 else 260 #endif 261 e = Search::pbsseq<T,E>(master,stat,opt); 262 } 263 264 template<class T, template<class> class E> 265 void build(T * s,SEBs & sebs,const Search::Options & o)266 PBS<T,E>::build(T* s, SEBs& sebs, const Search::Options& o) { 267 // Check whether all sebs do either best solution search or not 268 bool best; 269 { 270 int b = 0; 271 for (int i=0; i<sebs.size(); i++) 272 b += sebs[i]->best() ? 1 : 0; 273 if ((b > 0) && (b < sebs.size())) 274 throw Search::MixedBest("PBS::PBS"); 275 best = (b == sebs.size()); 276 } 277 278 Search::Options opt(o.expand()); 279 Search::Statistics stat; 280 281 if (s->status(stat) == SS_FAILED) { 282 stat.fail++; 283 if (!opt.clone) 284 delete s; 285 e = Search::Seq::dead(opt,stat); 286 return; 287 } 288 289 // Check whether a clone must be used 290 T* master = opt.clone ? 291 dynamic_cast<T*>(s->clone()) : s; 292 opt.clone = false; 293 294 // Always execute master function 295 (void) master->master(0); 296 297 #ifdef GECODE_HAS_THREADS 298 if (opt.threads > 1.0) 299 e = Search::pbspar<T,E>(master,sebs,stat,opt,best); 300 else 301 #endif 302 e = Search::pbsseq<T,E>(master,sebs,stat,opt,best); 303 } 304 305 template<class T, template<class> class E> 306 inline PBS(T * s,SEBs & sebs,const Search::Options & o)307 PBS<T,E>::PBS(T* s, SEBs& sebs, const Search::Options& o) { 308 build(s,sebs,o); 309 } 310 311 template<class T, template<class> class E> 312 inline T* pbs(T * s,const Search::Options & o)313 pbs(T* s, const Search::Options& o) { 314 PBS<T,E> r(s,o); 315 return r.next(); 316 } 317 318 template<class T, template<class> class E> 319 inline SEB pbs(const Search::Options & o)320 pbs(const Search::Options& o) { 321 return new Search::PbsBuilder<T,E>(o); 322 } 323 324 } 325 326 // STATISTICS: search-other 327