dfs.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_DFS_HH__ 00039 #define __GECODE_SEARCH_PARALLEL_DFS_HH__ 00040 00041 #include <gecode/search/parallel/engine.hh> 00042 00043 namespace Gecode { namespace Search { namespace Parallel { 00044 00046 class DFS : public Engine { 00047 protected: 00049 class Worker : public Engine::Worker { 00050 public: 00052 Worker(Space* s, size_t sz, DFS& e); 00054 DFS& engine(void) const; 00056 virtual void run(void); 00058 void find(void); 00060 Space* reset(Space* s); 00061 }; 00063 Worker** _worker; 00064 public: 00066 Worker* worker(unsigned int i) const; 00067 00069 00070 00071 void solution(Space* s); 00073 Space* reset(Space* s); 00075 00077 00078 00079 DFS(Space* s, size_t sz, const Options& o); 00081 virtual Statistics statistics(void) const; 00083 virtual ~DFS(void); 00085 }; 00086 00087 00088 /* 00089 * Basic access routines 00090 */ 00091 forceinline DFS& 00092 DFS::Worker::engine(void) const { 00093 return static_cast<DFS&>(_engine); 00094 } 00095 forceinline DFS::Worker* 00096 DFS::worker(unsigned int i) const { 00097 return _worker[i]; 00098 } 00099 00100 00101 /* 00102 * Engine: initialization 00103 */ 00104 forceinline 00105 DFS::Worker::Worker(Space* s, size_t sz, DFS& e) 00106 : Engine::Worker(s,sz,e) {} 00107 forceinline 00108 DFS::DFS(Space* s, size_t sz, const Options& o) 00109 : Engine(o) { 00110 // Create workers 00111 _worker = static_cast<Worker**> 00112 (heap.ralloc(workers() * sizeof(Worker*))); 00113 // The first worker gets the entire search tree 00114 _worker[0] = new Worker(s,sz,*this); 00115 // All other workers start with no work 00116 for (unsigned int i=1; i<workers(); i++) 00117 _worker[i] = new Worker(NULL,sz,*this); 00118 // Block all workers 00119 block(); 00120 // Create and start threads 00121 for (unsigned int i=0; i<workers(); i++) 00122 Support::Thread::run(_worker[i]); 00123 } 00124 00125 /* 00126 * Statistics 00127 */ 00128 forceinline Space* 00129 DFS::Worker::reset(Space* s) { 00130 delete cur; 00131 path.reset(); 00132 d = 0; 00133 idle = false; 00134 if ((s == NULL) || (s->status(*this) == SS_FAILED)) { 00135 delete s; 00136 cur = NULL; 00137 Search::Worker::reset(); 00138 return NULL; 00139 } else { 00140 cur = s; 00141 Search::Worker::reset(cur); 00142 return s->clone(false); 00143 } 00144 } 00145 forceinline Space* 00146 DFS::reset(Space* s) { 00147 // All workers are marked as busy again 00148 n_busy = workers(); 00149 for (unsigned int i=1; i<workers(); i++) 00150 (void) worker(i)->reset(NULL); 00151 return worker(0)->reset(s); 00152 } 00153 00154 /* 00155 * Engine: search control 00156 */ 00157 forceinline void 00158 DFS::solution(Space* s) { 00159 m_search.acquire(); 00160 bool bs = signal(); 00161 solutions.push(s); 00162 if (bs) 00163 e_search.signal(); 00164 m_search.release(); 00165 } 00166 00167 00168 00169 00170 /* 00171 * Worker: finding and stealing working 00172 */ 00173 forceinline void 00174 DFS::Worker::find(void) { 00175 // Try to find new work (even if there is none) 00176 for (unsigned int i=0; i<engine().workers(); i++) { 00177 unsigned long int r_d; 00178 if (Space* s = engine().worker(i)->steal(r_d)) { 00179 // Reset this guy 00180 m.acquire(); 00181 idle = false; 00182 d = 0; 00183 cur = s; 00184 Search::Worker::reset(cur,r_d); 00185 m.release(); 00186 return; 00187 } 00188 } 00189 } 00190 00191 }}} 00192 00193 #endif 00194 00195 // STATISTICS: search-parallel