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, 2009 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_ENGINE_HH 35 #define GECODE_SEARCH_PAR_ENGINE_HH 36 37 #include <gecode/search.hh> 38 #include <gecode/search/support.hh> 39 #include <gecode/search/worker.hh> 40 #include <gecode/search/par/path.hh> 41 42 namespace Gecode { namespace Search { namespace Par { 43 44 /// %Parallel depth-first search engine 45 template<class Tracer> 46 class Engine : public Search::Engine, public Support::Terminator { 47 protected: 48 /// %Parallel depth-first search worker 49 class Worker : public Search::Worker, public Support::Runnable { 50 public: 51 /// Search tracer 52 Tracer tracer; 53 protected: 54 /// Reference to engine 55 Engine& _engine; 56 /// Mutex for access to worker 57 Support::Mutex m; 58 /// Current path ins search tree 59 Path<Tracer> path; 60 /// Current space being explored 61 Space* cur; 62 /// Distance until next clone 63 unsigned int d; 64 /// Whether the worker is idle 65 bool idle; 66 public: 67 /// Initialize for space \a s with engine \a e 68 Worker(Space* s, Engine& e); 69 /// Hand over some work (nullptr if no work available) 70 Space* steal(unsigned long int& d, Tracer& myt, Tracer& ot); 71 /// Return statistics 72 Statistics statistics(void); 73 /// Provide access to engine 74 Engine& engine(void) const; 75 /// Return no-goods 76 NoGoods& nogoods(void); 77 /// Destructor 78 virtual ~Worker(void); 79 /// Terminator (engine) 80 virtual Support::Terminator* terminator(void) const; 81 }; 82 /// Search options 83 Options _opt; 84 public: 85 /// Provide access to search options 86 const Options& opt(void) const; 87 /// Return number of workers 88 unsigned int workers(void) const; 89 90 /// \name Commands from engine to workers and wait management 91 //@{ 92 /// Commands from engine to workers 93 enum Cmd { 94 C_WORK, ///< Perform work 95 C_WAIT, ///< Run into wait lock 96 C_RESET, ///< Perform reset operation 97 C_TERMINATE ///< Terminate 98 }; 99 protected: 100 /// The current command 101 volatile Cmd _cmd; 102 /// Mutex for forcing workers to wait 103 Support::Mutex _m_wait; 104 public: 105 /// Return current command 106 Cmd cmd(void) const; 107 /// Block all workers 108 void block(void); 109 /// Release all workers 110 void release(Cmd c); 111 /// Ensure that worker waits 112 void wait(void); 113 //@} 114 115 /// \name Termination control 116 //@{ 117 protected: 118 /// Mutex for access to termination information 119 Support::Mutex _m_term; 120 /// Number of workers that have not yet acknowledged termination 121 volatile unsigned int _n_term_not_ack; 122 /// Event for termination acknowledgment 123 Support::Event _e_term_ack; 124 /// Mutex for waiting for termination 125 Support::Mutex _m_wait_terminate; 126 /// Number of not yet terminated workers 127 volatile unsigned int _n_not_terminated; 128 /// Event for termination (all threads have terminated) 129 Support::Event _e_terminate; 130 public: 131 /// For worker to acknowledge termination command 132 void ack_terminate(void); 133 /// For worker to register termination 134 virtual void terminated(void); 135 /// For worker to wait until termination is legal 136 void wait_terminate(void); 137 /// For engine to peform thread termination 138 void terminate(void); 139 //@} 140 141 /// \name Reset control 142 //@{ 143 protected: 144 /// Mutex for access to reset information 145 Support::Mutex _m_reset; 146 /// Number of workers that have not yet acknowledged reset 147 volatile unsigned int _n_reset_not_ack; 148 /// Event for reset acknowledgment started 149 Support::Event e_reset_ack_start; 150 /// Event for reset acknowledgment stopped 151 Support::Event e_reset_ack_stop; 152 /// Mutex for waiting for reset 153 Support::Mutex m_wait_reset; 154 public: 155 /// For worker to acknowledge start of reset cycle 156 void ack_reset_start(void); 157 /// For worker to acknowledge stop of reset cycle 158 void ack_reset_stop(void); 159 /// For worker to wait for all workers to reset 160 void wait_reset(void); 161 //@} 162 163 /// \name Search control 164 //@{ 165 protected: 166 /// Mutex for search 167 Support::Mutex m_search; 168 /// Event for search (solution found, no more solutions, search stopped) 169 Support::Event e_search; 170 /// Queue of solutions 171 Support::DynamicQueue<Space*,Heap> solutions; 172 /// Number of busy workers 173 volatile unsigned int n_busy; 174 /// Whether a worker had been stopped 175 volatile bool has_stopped; 176 /// Whether search state changed such that signal is needed 177 bool signal(void) const; 178 public: 179 /// Report that worker is idle 180 void idle(void); 181 /// Report that worker is busy 182 void busy(void); 183 /// Report that worker has been stopped 184 void stop(void); 185 //@} 186 187 /// \name Engine interface 188 //@{ 189 /// Initialize with options \a o 190 Engine(const Options& o); 191 /// Return next solution (nullptr, if none exists or search has been stopped) 192 virtual Space* next(void); 193 /// Check whether engine has been stopped 194 virtual bool stopped(void) const; 195 //@} 196 }; 197 198 }}} 199 200 #include <gecode/search/par/engine.hpp> 201 202 #endif 203 204 // STATISTICS: search-par 205