bab.hh
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, 2009 00008 * 00009 * Last modified: 00010 * $Date: 2010-04-08 12:35:31 +0200 (Thu, 08 Apr 2010) $ by $Author: schulte $ 00011 * $Revision: 10684 $ 00012 * 00013 * This file is part of Gecode, the generic constraint 00014 * development environment: 00015 * http://www.gecode.org 00016 * 00017 * Permission is hereby granted, free of charge, to any person obtaining 00018 * a copy of this software and associated documentation files (the 00019 * "Software"), to deal in the Software without restriction, including 00020 * without limitation the rights to use, copy, modify, merge, publish, 00021 * distribute, sublicense, and/or sell copies of the Software, and to 00022 * permit persons to whom the Software is furnished to do so, subject to 00023 * the following conditions: 00024 * 00025 * The above copyright notice and this permission notice shall be 00026 * included in all copies or substantial portions of the Software. 00027 * 00028 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, 00029 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF 00030 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND 00031 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE 00032 * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION 00033 * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION 00034 * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. 00035 * 00036 */ 00037 00038 #ifndef __GECODE_SEARCH_PARALLEL_BAB_HH__ 00039 #define __GECODE_SEARCH_PARALLEL_BAB_HH__ 00040 00041 #include <gecode/search/parallel/engine.hh> 00042 00043 namespace Gecode { namespace Search { namespace Parallel { 00044 00046 class BAB : public Engine { 00047 protected: 00049 class Worker : public Engine::Worker { 00050 protected: 00052 int mark; 00054 Space* best; 00055 public: 00057 Worker(Space* s, size_t sz, BAB& e); 00059 BAB& engine(void) const; 00061 virtual void run(void); 00063 void better(Space* b); 00065 void find(void); 00067 virtual ~Worker(void); 00068 }; 00070 Worker** _worker; 00072 Space* best; 00073 public: 00075 Worker* worker(unsigned int i) const; 00076 00078 00079 00080 void solution(Space* s); 00082 00084 00085 00086 BAB(Space* s, size_t sz, const Options& o); 00088 virtual Statistics statistics(void) const; 00090 virtual ~BAB(void); 00092 }; 00093 00094 00095 00096 /* 00097 * Engine: basic access routines 00098 */ 00099 forceinline BAB& 00100 BAB::Worker::engine(void) const { 00101 return static_cast<BAB&>(_engine); 00102 } 00103 forceinline BAB::Worker* 00104 BAB::worker(unsigned int i) const { 00105 return _worker[i]; 00106 } 00107 00108 00109 /* 00110 * Engine: initialization 00111 */ 00112 forceinline 00113 BAB::Worker::Worker(Space* s, size_t sz, BAB& e) 00114 : Engine::Worker(s,sz,e), mark(0), best(NULL) {} 00115 00116 forceinline 00117 BAB::BAB(Space* s, size_t sz, const Options& o) 00118 : Engine(o), best(NULL) { 00119 // Create workers 00120 _worker = static_cast<Worker**> 00121 (heap.ralloc(workers() * sizeof(Worker*))); 00122 // The first worker gets the entire search tree 00123 _worker[0] = new Worker(s,sz,*this); 00124 // All other workers start with no work 00125 for (unsigned int i=1; i<workers(); i++) 00126 _worker[i] = new Worker(NULL,sz,*this); 00127 // Block all workers 00128 block(); 00129 // Create and start threads 00130 for (unsigned int i=0; i<workers(); i++) 00131 Support::Thread::run(_worker[i]); 00132 } 00133 00134 00135 /* 00136 * Engine: search control 00137 */ 00138 forceinline void 00139 BAB::Worker::better(Space* b) { 00140 m.acquire(); 00141 delete best; 00142 best = b->clone(false); 00143 mark = path.entries(); 00144 if (cur != NULL) 00145 cur->constrain(*best); 00146 m.release(); 00147 } 00148 forceinline void 00149 BAB::solution(Space* s) { 00150 m_search.acquire(); 00151 if (best != NULL) { 00152 s->constrain(*best); 00153 if (s->status() == SS_FAILED) { 00154 delete s; 00155 m_search.release(); 00156 return; 00157 } else { 00158 delete best; 00159 best = s->clone(); 00160 } 00161 } else { 00162 best = s->clone(); 00163 } 00164 // Announce better solutions 00165 for (unsigned int i=0; i<workers(); i++) 00166 worker(i)->better(best); 00167 bool bs = signal(); 00168 solutions.push(s); 00169 if (bs) 00170 e_search.signal(); 00171 m_search.release(); 00172 } 00173 00174 00175 /* 00176 * Worker: finding and stealing working 00177 */ 00178 forceinline void 00179 BAB::Worker::find(void) { 00180 // Try to find new work (even if there is none) 00181 for (unsigned int i=0; i<engine().workers(); i++) { 00182 unsigned long int r_d; 00183 if (Space* s = engine().worker(i)->steal(r_d)) { 00184 // Reset this guy 00185 m.acquire(); 00186 idle = false; 00187 d = 0; 00188 cur = s; 00189 mark = 0; 00190 if (best != NULL) 00191 cur->constrain(*best); 00192 Search::Worker::reset(cur,r_d); 00193 m.release(); 00194 return; 00195 } 00196 } 00197 } 00198 00199 }}} 00200 00201 #endif 00202 00203 // STATISTICS: search-parallel