Generated on Thu Mar 13 2014 04:39:35 for Gecode by doxygen 1.8.1.2
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: 2011-04-11 19:28:27 +1000 (Mon, 11 Apr 2011) $ by $Author: tack $
11  * $Revision: 11929 $
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  virtual ~Worker(void);
68  };
73  public:
75  Worker* worker(unsigned int i) const;
76 
78 
79 
80  void solution(Space* s);
82 
84 
85 
86  BAB(Space* s, size_t sz, const Options& o);
88  virtual Statistics statistics(void) const;
90  virtual ~BAB(void);
92  };
93 
94 
95 
96  /*
97  * Engine: basic access routines
98  */
100  BAB::Worker::engine(void) const {
101  return static_cast<BAB&>(_engine);
102  }
104  BAB::worker(unsigned int i) const {
105  return _worker[i];
106  }
107 
108 
109  /*
110  * Engine: initialization
111  */
113  BAB::Worker::Worker(Space* s, size_t sz, BAB& e)
114  : Engine::Worker(s,sz,e), mark(0), best(NULL) {}
115 
117  BAB::BAB(Space* s, size_t sz, const Options& o)
118  : Engine(o), best(NULL) {
119  // Create workers
120  _worker = static_cast<Worker**>
121  (heap.ralloc(workers() * sizeof(Worker*)));
122  // The first worker gets the entire search tree
123  _worker[0] = new Worker(s,sz,*this);
124  // All other workers start with no work
125  for (unsigned int i=1; i<workers(); i++)
126  _worker[i] = new Worker(NULL,sz,*this);
127  // Block all workers
128  block();
129  // Create and start threads
130  for (unsigned int i=0; i<workers(); i++)
132  }
133 
134 
135  /*
136  * Engine: search control
137  */
138  forceinline void
140  m.acquire();
141  delete best;
142  best = b->clone(false);
143  mark = path.entries();
144  if (cur != NULL)
145  cur->constrain(*best);
146  m.release();
147  }
148  forceinline void
150  m_search.acquire();
151  if (best != NULL) {
152  s->constrain(*best);
153  if (s->status() == SS_FAILED) {
154  delete s;
155  m_search.release();
156  return;
157  } else {
158  delete best;
159  best = s->clone();
160  }
161  } else {
162  best = s->clone();
163  }
164  // Announce better solutions
165  for (unsigned int i=0; i<workers(); i++)
166  worker(i)->better(best);
167  bool bs = signal();
168  solutions.push(s);
169  if (bs)
170  e_search.signal();
171  m_search.release();
172  }
173 
174 
175  /*
176  * Worker: finding and stealing working
177  */
178  forceinline void
180  // Try to find new work (even if there is none)
181  for (unsigned int i=0; i<engine().workers(); i++) {
182  unsigned long int r_d = 0ul;
183  if (Space* s = engine().worker(i)->steal(r_d)) {
184  // Reset this guy
185  m.acquire();
186  idle = false;
187  d = 0;
188  cur = s;
189  mark = 0;
190  if (best != NULL)
191  cur->constrain(*best);
192  Search::Worker::reset(cur,r_d);
193  m.release();
194  return;
195  }
196  }
197  }
198 
199 }}}
200 
201 #endif
202 
203 // STATISTICS: search-parallel