Generated on Sat May 25 2013 18:00:40 for Gecode by doxygen 1.8.3.1
bab.hh
Go to the documentation of this file.
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  * Last modified:
10  * $Date: 2013-03-07 20:56:21 +0100 (Thu, 07 Mar 2013) $ by $Author: schulte $
11  * $Revision: 13463 $
12  *
13  * This file is part of Gecode, the generic constraint
14  * development environment:
15  * http://www.gecode.org
16  *
17  * Permission is hereby granted, free of charge, to any person obtaining
18  * a copy of this software and associated documentation files (the
19  * "Software"), to deal in the Software without restriction, including
20  * without limitation the rights to use, copy, modify, merge, publish,
21  * distribute, sublicense, and/or sell copies of the Software, and to
22  * permit persons to whom the Software is furnished to do so, subject to
23  * the following conditions:
24  *
25  * The above copyright notice and this permission notice shall be
26  * included in all copies or substantial portions of the Software.
27  *
28  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
29  * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
30  * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
31  * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
32  * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
33  * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
34  * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
35  *
36  */
37 
38 #ifndef __GECODE_SEARCH_PARALLEL_BAB_HH__
39 #define __GECODE_SEARCH_PARALLEL_BAB_HH__
40 
42 
43 namespace Gecode { namespace Search { namespace Parallel {
44 
46  class BAB : public Engine {
47  protected:
49  class Worker : public Engine::Worker {
50  protected:
52  int mark;
55  public:
57  Worker(Space* s, size_t sz, BAB& e);
59  BAB& engine(void) const;
61  virtual void run(void);
63  void better(Space* b);
65  void find(void);
67  void reset(Space* s);
69  virtual ~Worker(void);
70  };
75  public:
77  Worker* worker(unsigned int i) const;
78 
80 
81 
82  void solution(Space* s);
84 
86 
87 
88  BAB(Space* s, size_t sz, const Options& o);
90  virtual Statistics statistics(void) const;
92  virtual void reset(Space* s);
94  virtual ~BAB(void);
96  };
97 
98 
99 
100  /*
101  * Engine: basic access routines
102  */
104  BAB::Worker::engine(void) const {
105  return static_cast<BAB&>(_engine);
106  }
108  BAB::worker(unsigned int i) const {
109  return _worker[i];
110  }
111 
112  forceinline void
114  delete cur;
115  delete best;
116  best = NULL;
117  path.reset();
118  d = mark = 0;
119  idle = false;
120  if ((s == NULL) || (s->status(*this) == SS_FAILED)) {
121  delete s;
122  cur = NULL;
124  } else {
125  cur = s;
127  }
128  }
129 
130 
131  /*
132  * Engine: initialization
133  */
135  BAB::Worker::Worker(Space* s, size_t sz, BAB& e)
136  : Engine::Worker(s,sz,e), mark(0), best(NULL) {}
137 
139  BAB::BAB(Space* s, size_t sz, const Options& o)
140  : Engine(o), best(NULL) {
141  // Create workers
142  _worker = static_cast<Worker**>
143  (heap.ralloc(workers() * sizeof(Worker*)));
144  // The first worker gets the entire search tree
145  _worker[0] = new Worker(s,sz,*this);
146  // All other workers start with no work
147  for (unsigned int i=1; i<workers(); i++)
148  _worker[i] = new Worker(NULL,sz,*this);
149  // Block all workers
150  block();
151  // Create and start threads
152  for (unsigned int i=0; i<workers(); i++)
154  }
155 
156 
157  /*
158  * Engine: search control
159  */
160  forceinline void
162  m.acquire();
163  delete best;
164  best = b->clone(false);
165  mark = path.entries();
166  if (cur != NULL)
167  cur->constrain(*best);
168  m.release();
169  }
170  forceinline void
172  m_search.acquire();
173  if (best != NULL) {
174  s->constrain(*best);
175  if (s->status() == SS_FAILED) {
176  delete s;
177  m_search.release();
178  return;
179  } else {
180  delete best;
181  best = s->clone();
182  }
183  } else {
184  best = s->clone();
185  }
186  // Announce better solutions
187  for (unsigned int i=0; i<workers(); i++)
188  worker(i)->better(best);
189  bool bs = signal();
190  solutions.push(s);
191  if (bs)
192  e_search.signal();
193  m_search.release();
194  }
195 
196 
197  /*
198  * Worker: finding and stealing working
199  */
200  forceinline void
202  // Try to find new work (even if there is none)
203  for (unsigned int i=0; i<engine().workers(); i++) {
204  unsigned long int r_d = 0ul;
205  if (Space* s = engine().worker(i)->steal(r_d)) {
206  // Reset this guy
207  m.acquire();
208  idle = false;
209  d = 0;
210  cur = s;
211  mark = 0;
212  if (best != NULL)
213  cur->constrain(*best);
214  Search::Worker::reset(cur,r_d);
215  m.release();
216  return;
217  }
218  }
219  }
220 
221 }}}
222 
223 #endif
224 
225 // STATISTICS: search-parallel