Generated on Tue Mar 24 2020 14:04:04 for Gecode by doxygen 1.8.17
pbs.hpp
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, 2015
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 #include <algorithm>
35 
36 namespace Gecode { namespace Search { namespace Par {
37 
38 
41  : solutions(heap) {}
42  forceinline bool
44  solutions.push(s);
45  return true;
46  }
47  forceinline bool
49  (void) b;
50  return false;
51  }
52  forceinline bool
53  CollectAll::empty(void) const {
54  return solutions.empty();
55  }
58  return solutions.pop();
59  }
62  while (!solutions.empty())
63  delete solutions.pop();
64  }
65 
66 
69  : b(NULL), reporter(NULL) {}
70  forceinline bool
72  if (b != NULL) {
73  b->constrain(*s);
74  if (b->status() == SS_FAILED) {
75  delete b;
76  } else {
77  delete s;
78  return false;
79  }
80  }
81  b = s;
82  reporter = r;
83  return true;
84  }
85  forceinline bool
87  if (b != NULL) {
88  b->constrain(s);
89  if (b->status() == SS_FAILED) {
90  delete b;
91  } else {
92  return false;
93  }
94  }
95  b = s.clone();
96  reporter = NULL;
97  return true;
98  }
99  forceinline bool
100  CollectBest::empty(void) const {
101  return reporter == NULL;
102  }
105  assert(!empty());
106  r = reporter;
107  reporter = NULL;
108  return b->clone();
109  }
112  delete b;
113  }
114 
115 
118  : so(so0), tostop(NULL) {}
119 
120  forceinline void
121  PortfolioStop::share(volatile bool* ts) {
122  tostop = ts;
123  }
124 
125 
126  template<class Collect>
129  : Support::Runnable(false), master(m), slave(s), stop(so) {}
130  template<class Collect>
133  return slave->statistics();
134  }
135  template<class Collect>
136  forceinline bool
138  return slave->stopped();
139  }
140  template<class Collect>
141  forceinline void
143  slave->constrain(b);
144  }
145  template<class Collect>
147  delete slave;
148  delete stop;
149  }
150 
151 
152 
153  template<class Collect>
155  PBS<Collect>::PBS(Engine** engines, Stop** stops, unsigned int n,
156  const Statistics& stat0)
157  : stat(stat0), slaves(heap.alloc<Slave<Collect>*>(n)),
158  n_slaves(n), n_active(n),
159  slave_stop(false), tostop(false), n_busy(0) {
160  // Initialize slaves
161  for (unsigned int i=0U; i<n_slaves; i++) {
162  slaves[i] = new Slave<Collect>(this,engines[i],stops[i]);
163  static_cast<PortfolioStop*>(stops[i])->share(&tostop);
164  }
165  }
166 
167 
168  template<class Collect>
169  forceinline bool
171  // If b is false the report should be repeated (solution was worse)
172  bool b = true;
173  m.acquire();
174  if (s != NULL) {
175  b = solutions.add(s,slave);
176  if (b)
177  tostop = true;
178  } else if (slave->stopped()) {
179  if (!tostop)
180  slave_stop = true;
181  } else {
182  // Move slave to inactive, as it has exhausted its engine
183  unsigned int i=0;
184  while (slaves[i] != slave)
185  i++;
186  assert(i < n_active);
187  assert(n_active > 0);
188  std::swap(slaves[i],slaves[--n_active]);
189  tostop = true;
190  }
191  if (b) {
192  if (--n_busy == 0)
193  idle.signal();
194  }
195  m.release();
196  return b;
197  }
198 
199  template<class Collect>
200  void
202  Space* s;
203  do {
204  s = slave->next();
205  } while (!master->report(this,s));
206  }
207 
208  template<class Collect>
209  Space*
211  m.acquire();
212  if (solutions.empty()) {
213  // Clear all
214  tostop = false;
215  slave_stop = false;
216 
217  // Invariant: all slaves are idle!
218  assert(n_busy == 0);
219  assert(!tostop);
220 
221  if (n_active > 0) {
222  // Run all active slaves
223  n_busy = n_active;
224  for (unsigned int i=0U; i<n_active; i++)
225  Support::Thread::run(slaves[i]);
226  m.release();
227  // Wait for all slaves to become idle
228  idle.wait();
229  m.acquire();
230  }
231  }
232 
233  // Invariant all slaves are idle!
234  assert(n_busy == 0);
235 
236  Space* s;
237 
238  // Process solutions
239  if (solutions.empty()) {
240  s = NULL;
241  } else {
242  Slave<Collect>* r;
243  s = solutions.get(r);
244  if (Collect::best)
245  for (unsigned int i=0U; i<n_active; i++)
246  if (slaves[i] != r)
247  slaves[i]->constrain(*s);
248  }
249 
250  m.release();
251  return s;
252  }
253 
254  template<class Collect>
255  bool
256  PBS<Collect>::stopped(void) const {
257  return slave_stop;
258  }
259 
260  template<class Collect>
261  Statistics
263  assert(n_busy == 0);
264  Statistics s(stat);
265  for (unsigned int i=0U; i<n_slaves; i++)
266  s += slaves[i]->statistics();
267  return s;
268  }
269 
270  template<class Collect>
271  void
273  assert(n_busy == 0);
274  if (!Collect::best)
275  throw NoBest("PBS::constrain");
276  if (solutions.constrain(b)) {
277  // The solution is better
278  for (unsigned int i=0U; i<n_active; i++)
279  slaves[i]->constrain(b);
280  }
281  }
282 
283  template<class Collect>
285  assert(n_busy == 0);
286  heap.free<Slave<Collect>*>(slaves,n_slaves);
287  }
288 
289 }}}
290 
291 // STATISTICS: search-par
bool add(Space *s, Slave< CollectAll > *r)
Add a solution a reported by r and always return true.
Definition: pbs.hpp:43
CollectAll(void)
Initialize.
Definition: pbs.hpp:40
PortfolioStop(Stop *so)
Initialize.
Definition: pbs.hpp:117
bool empty(void) const
Check whether there is any solution left.
Definition: pbs.hpp:100
virtual void constrain(const Space &best)
Constrain function for best solution search.
Definition: core.cpp:841
Base-class for Stop-object.
Definition: search.hh:799
int solutions(TestSpace *c, Gecode::Search::Options &o, int maxNbSol=-1)
Find number of solutions.
Definition: branch.cpp:412
bool stopped(void) const
Check whether slave has been stopped.
Definition: pbs.hpp:137
Runnable slave of a portfolio master.
Definition: pbs.hh:67
Computation spaces.
Definition: core.hpp:1742
Support::DynamicQueue< Space *, Heap > solutions
Queue of solutions.
Definition: pbs.hh:94
Exception: Best solution search is not supported
Definition: exception.hpp:60
bool add(Space *s, Slave< CollectBest > *r)
Add a solution s by r and return whether is was better.
Definition: pbs.hpp:71
CollectBest(void)
Initialize.
Definition: pbs.hpp:68
Gecode toplevel namespace
Space * clone(CloneStatistics &stat=unused_clone) const
Clone space.
Definition: core.hpp:3224
Parallel portfolio engine implementation.
Definition: pbs.hh:63
Space * get(Slave< CollectAll > *&r)
Return solution reported by r.
Definition: pbs.hpp:57
Parallel depth-first search engine
Definition: engine.hh:46
void stop(Support::Timer &timer, std::ostream &os)
Get time since start of timer and print user friendly time information.
Definition: script.cpp:42
Space * get(Slave< CollectBest > *&r)
Return solution reported by r (only if a better one was found)
Definition: pbs.hpp:104
Post propagator for SetVar SetOpType SetVar SetRelType r
Definition: set.hh:767
~CollectBest(void)
Destructor.
Definition: pbs.hpp:111
~CollectAll(void)
Destructor.
Definition: pbs.hpp:61
IntRelType swap(IntRelType irt)
Return swapped relation type of irt.
Definition: irt.hpp:37
Slave(PBS< Collect > *m, Engine *s, Stop *so)
Initialize with master m, slave s, and its stop object so.
Definition: pbs.hpp:128
Space * b
Currently best solution.
Definition: pbs.hh:116
struct Gecode::@602::NNF::@65::@66 b
For binary nodes (and, or, eqv)
void share(volatile bool *ts)
Set pointer to shared tostop variable.
Definition: pbs.hpp:121
SpaceStatus status(StatusStatistics &stat=unused_status)
Query space status.
Definition: core.cpp:252
Heap heap
The single global heap.
Definition: heap.cpp:44
Slave< CollectBest > * reporter
Who has reported the best solution (NULL if solution has already been reported)
Definition: pbs.hh:118
void free(T *b, long unsigned int n)
Delete n objects starting at b.
Definition: heap.hpp:457
bool empty(void) const
Check whether there is any solution left.
Definition: pbs.hpp:53
bool constrain(const Space &b)
Dummy function.
Definition: pbs.hpp:48
NNF * r
Right subtree.
Definition: bool-expr.cpp:242
#define forceinline
Definition: config.hpp:185
void constrain(const Space &b)
Constrain with better solution b.
Definition: pbs.hpp:142
bool constrain(const Space &b)
Check whether b better and update accordingly.
Definition: pbs.hpp:86
Statistics statistics(void) const
Return statistics of slave.
Definition: pbs.hpp:132
int n
Number of negative literals for node type.
Definition: bool-expr.cpp:234
Gecode::IntArgs i({1, 2, 3, 4})
Search engine statistics
Definition: search.hh:147
@ SS_FAILED
Space is failed
Definition: core.hpp:1682
Stop object used for controling slaves in a portfolio.
Definition: pbs.hh:42