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 #ifndef GECODE_SEARCH_PAR_PBS_HH 35 #define GECODE_SEARCH_PAR_PBS_HH 36 37 #include <gecode/search.hh> 38 39 namespace Gecode { namespace Search { namespace Par { 40 41 /// Stop object used for controling slaves in a portfolio 42 class GECODE_SEARCH_EXPORT PortfolioStop : public Stop { 43 private: 44 /// The stop object for the slaves 45 Stop* so; 46 /// Whether search must be stopped 47 volatile bool* tostop; 48 public: 49 /// Initialize 50 PortfolioStop(Stop* so); 51 /// Set pointer to shared \a tostop variable 52 void share(volatile bool* ts); 53 /// Return true if portfolio engine must be stopped 54 virtual bool stop(const Statistics& s, const Options& o); 55 /// Signal whether search must be stopped 56 void stop(bool s); 57 /// Whether search must be stopped 58 bool stop(void) const; 59 }; 60 61 // Forward declaration 62 template<class Collect> 63 class PBS; 64 65 /// Runnable slave of a portfolio master 66 template<class Collect> 67 class GECODE_SEARCH_EXPORT Slave : public Support::Runnable { 68 protected: 69 /// The master engine 70 PBS<Collect>* master; 71 /// The slave engine 72 Engine* slave; 73 /// Stop object 74 Stop* stop; 75 public: 76 /// Initialize with master \a m, slave \a s, and its stop object \a so 77 Slave(PBS<Collect>* m, Engine* s, Stop* so); 78 /// Return statistics of slave 79 Statistics statistics(void) const; 80 /// Check whether slave has been stopped 81 bool stopped(void) const; 82 /// Constrain with better solution \a b 83 void constrain(const Space& b); 84 /// Perform one run 85 virtual void run(void); 86 /// Delete slave 87 virtual ~Slave(void); 88 }; 89 90 /// Collect all solutions 91 class CollectAll { 92 protected: 93 /// Queue of solutions 94 Support::DynamicQueue<Space*,Heap> solutions; 95 public: 96 /// Whether it collects best solutions 97 static const bool best = false; 98 /// Initialize 99 CollectAll(void); 100 /// Add a solution \a a reported by \a r and always return true 101 bool add(Space* s, Slave<CollectAll>* r); 102 /// Dummy function 103 bool constrain(const Space& b); 104 /// Check whether there is any solution left 105 bool empty(void) const; 106 /// Return solution reported by \a r 107 Space* get(Slave<CollectAll>*& r); 108 /// Destructor 109 ~CollectAll(void); 110 }; 111 112 /// Collect best solutions 113 class CollectBest { 114 protected: 115 /// Currently best solution 116 Space* b; 117 /// Who has reported the best solution (nullptr if solution has already been reported) 118 Slave<CollectBest>* reporter; 119 public: 120 /// Whether it collects best solutions 121 static const bool best = true; 122 /// Initialize 123 CollectBest(void); 124 /// Add a solution \a s by \a r and return whether is was better 125 bool add(Space* s, Slave<CollectBest>* r); 126 /// Check whether \a b better and update accordingly 127 bool constrain(const Space& b); 128 /// Check whether there is any solution left 129 bool empty(void) const; 130 /// Return solution reported by \a r (only if a better one was found) 131 Space* get(Slave<CollectBest>*& r); 132 /// Destructor 133 ~CollectBest(void); 134 }; 135 136 /// Parallel portfolio engine implementation 137 template<class Collect> 138 class GECODE_SEARCH_EXPORT PBS : public Engine { 139 friend class Slave<Collect>; 140 protected: 141 /// Master statistics 142 Statistics stat; 143 /// Slave engines 144 Slave<Collect>** slaves; 145 /// Number of slave engines 146 unsigned int n_slaves; 147 /// Number of active slave engines 148 unsigned int n_active; 149 /// Whether a slave has been stopped 150 bool slave_stop; 151 /// Shared stop flag 152 volatile bool tostop; 153 /// Collect solutions in this 154 Collect solutions; 155 /// Mutex for synchronization 156 Support::Mutex m; 157 /// Number of busy slaves 158 unsigned int n_busy; 159 /// Signal that number of busy slaves becomes zero 160 Support::Event idle; 161 /// Process report from slave, return false if solution was ignored 162 bool report(Slave<Collect>* slave, Space* s); 163 /** 164 * The key invariant of the engine is as follows: 165 * - n_busy is always zero outside the next() function. 166 * - that entails, that locking is only needed insided next(). 167 * - the slaves 0..n_active-1 still might not have exausted their 168 * search space. 169 * - the slaves n_active..n_slaves-1 have exhausted their search space. 170 */ 171 public: 172 /// Initialize 173 PBS(Engine** s, Stop** so, unsigned int n, const Statistics& stat); 174 /// Return next solution (nullptr, if none exists or search has been stopped) 175 virtual Space* next(void); 176 /// Return statistics 177 virtual Statistics statistics(void) const; 178 /// Check whether engine has been stopped 179 virtual bool stopped(void) const; 180 /// Constrain future solutions to be better than \a b 181 virtual void constrain(const Space& b); 182 /// Destructor 183 virtual ~PBS(void); 184 }; 185 186 }}} 187 188 #include <gecode/search/par/pbs.hpp> 189 190 #endif 191 192 // STATISTICS: search-par 193