Generated on Thu Apr 11 13:59:18 2019 for Gecode by doxygen 1.6.3

pbs.hpp

Go to the documentation of this file.
00001 /* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
00002 /*
00003  *  Main authors:
00004  *     Christian Schulte <schulte@gecode.org>
00005  *
00006  *  Copyright:
00007  *     Christian Schulte, 2015
00008  *
00009  *  This file is part of Gecode, the generic constraint
00010  *  development environment:
00011  *     http://www.gecode.org
00012  *
00013  *  Permission is hereby granted, free of charge, to any person obtaining
00014  *  a copy of this software and associated documentation files (the
00015  *  "Software"), to deal in the Software without restriction, including
00016  *  without limitation the rights to use, copy, modify, merge, publish,
00017  *  distribute, sublicense, and/or sell copies of the Software, and to
00018  *  permit persons to whom the Software is furnished to do so, subject to
00019  *  the following conditions:
00020  *
00021  *  The above copyright notice and this permission notice shall be
00022  *  included in all copies or substantial portions of the Software.
00023  *
00024  *  THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
00025  *  EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
00026  *  MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
00027  *  NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
00028  *  LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
00029  *  OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
00030  *  WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
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     // Initialize slaves
00161     for (unsigned int i=0U; 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     // If b is false the report should be repeated (solution was worse)
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       // Move slave to inactive, as it has exhausted its engine
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       // Clear all
00214       tostop = false;
00215       slave_stop = false;
00216 
00217       // Invariant: all slaves are idle!
00218       assert(n_busy == 0);
00219       assert(!tostop);
00220 
00221       if (n_active > 0) {
00222         // Run all active slaves
00223         n_busy = n_active;
00224         for (unsigned int i=0U; i<n_active; i++)
00225           Support::Thread::run(slaves[i]);
00226         m.release();
00227         // Wait for all slaves to become idle
00228         idle.wait();
00229         m.acquire();
00230       }
00231     }
00232 
00233     // Invariant all slaves are idle!
00234     assert(n_busy == 0);
00235 
00236     Space* s;
00237 
00238     // Process solutions
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=0U; 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=0U; 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       // The solution is better
00278       for (unsigned int i=0U; 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 // STATISTICS: search-par