Generated on Tue Jul 18 2017 18:41:42 for Gecode by doxygen 1.8.13
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  * Last modified:
10  * $Date: 2016-04-19 17:19:45 +0200 (Tue, 19 Apr 2016) $ by $Author: schulte $
11  * $Revision: 14967 $
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 namespace Gecode { namespace Search { namespace Meta { namespace Parallel {
39 
40 
43  : solutions(heap) {}
44  forceinline bool
46  solutions.push(s);
47  return true;
48  }
49  forceinline bool
51  (void) b;
52  return false;
53  }
54  forceinline bool
55  CollectAll::empty(void) const {
56  return solutions.empty();
57  }
60  return solutions.pop();
61  }
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(false);
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(false);
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)), n_slaves(n),
158  slave_stop(false), tostop(false), n_busy(0) {
159  // Initialize slaves
160  for (unsigned int i=n_slaves; i--; ) {
161  slaves[i] = new Slave<Collect>(this,engines[i],stops[i]);
162  static_cast<PortfolioStop*>(stops[i])->share(&tostop);
163  }
164  }
165 
166  template<class Collect>
167  forceinline bool
169  // If b is false the report should be repeated (solution was worse)
170  bool b = true;
171  m.acquire();
172  if (s != NULL) {
173  b = solutions.add(s,slave);
174  if (b)
175  tostop = true;
176  } else if (slave->stopped()) {
177  if (!tostop)
178  slave_stop = true;
179  } else {
180  // Delete slave from slaves
181  stat += slave->statistics();
182  // Do not actually delete, the thread should do that upon termination
183  slave->todelete(true);
184  unsigned int i=0;
185  while (slaves[i] != slave)
186  i++;
187  assert(i < n_slaves);
188  slaves[i] = slaves[--n_slaves];
189  }
190  if (b) {
191  if (--n_busy == 0)
192  idle.signal();
193  }
194  m.release();
195  return b;
196  }
197 
198  template<class Collect>
199  void
201  Space* s;
202  do {
203  s = slave->next();
204  } while (!master->report(this,s));
205  }
206 
207  template<class Collect>
208  Space*
210  m.acquire();
211  if (solutions.empty()) {
212  // Clear all
213  tostop = false;
214  slave_stop = false;
215 
216  // Invariant: all slaves are idle!
217  assert(n_busy == 0);
218  assert(!tostop);
219 
220  if (n_slaves > 0) {
221  // Run all slaves
222  n_busy = n_slaves;
223  for (unsigned int i=n_slaves; i--; )
224  Support::Thread::run(slaves[i]);
225  m.release();
226  // Wait for all slaves to become idle
227  idle.wait();
228  m.acquire();
229  }
230  }
231 
232  // Invariant all slaves are idle!
233  assert(n_busy == 0);
234 
235  Space* s;
236 
237  // Process solutions
238  if (solutions.empty()) {
239  s = NULL;
240  } else {
241  Slave<Collect>* r;
242  s = solutions.get(r);
243  if (Collect::best)
244  for (unsigned int i=n_slaves; i--; )
245  if (slaves[i] != r)
246  slaves[i]->constrain(*s);
247  }
248 
249  m.release();
250  return s;
251  }
252 
253  template<class Collect>
254  bool
255  PBS<Collect>::stopped(void) const {
256  return slave_stop;
257  }
258 
259  template<class Collect>
260  Statistics
262  Statistics s(stat);
263  for (unsigned int i=n_slaves; i--; )
264  s += slaves[i]->statistics();
265  return s;
266  }
267 
268  template<class Collect>
269  void
271  if (!Collect::best)
272  throw NoBest("PBS::constrain");
273  if (solutions.constrain(b)) {
274  // The solution is better
275  for (unsigned int i=n_slaves; i--; )
276  slaves[i]->constrain(b);
277  }
278  }
279 
280  template<class Collect>
282  for (unsigned int i=n_slaves; i--; )
283  delete slaves[i];
284  // Note that n_slaves might be different now!
285  heap.rfree(slaves);
286  }
287 
288 }}}}
289 
290 // STATISTICS: search-meta
Slave(PBS< Collect > *m, Engine *s, Stop *so)
Initialize with master m, slave s, and its stop object so.
Definition: pbs.hpp:128
bool stopped(void) const
Check whether slave has been stopped.
Definition: pbs.hpp:137
Search engine implementation interface
Definition: search.hh:601
Search engine statistics
Definition: search.hh:140
void rfree(void *p)
Free memory block starting at p.
Definition: heap.hpp:375
Statistics statistics(void) const
Return statistics of slave.
Definition: pbs.hpp:132
void stop(Support::Timer &timer, std::ostream &os)
Get time since start of timer and print user friendly time information.
Definition: script.cpp:46
Space * b
Currently best solution.
Definition: pbs.hh:120
Support::DynamicQueue< Space *, Heap > solutions
Queue of solutions.
Definition: pbs.hh:98
Space * clone(bool share_data=true, bool share_info=true, CloneStatistics &stat=unused_clone) const
Clone space.
Definition: core.hpp:3326
Computation spaces.
Definition: core.hpp:1748
Gecode::IntArgs i(4, 1, 2, 3, 4)
int n
Number of negative literals for node type.
Definition: bool-expr.cpp:238
bool stop(void) const
Whether search must be stopped.
NNF * r
Right subtree.
Definition: bool-expr.cpp:246
Runnable slave of a portfolio master.
Definition: pbs.hh:71
Space * get(Slave< CollectBest > *&r)
Return solution reported by r (only if a better one was found)
Definition: pbs.hpp:104
virtual void constrain(const Space &best)
Constrain function for best solution search.
Definition: core.cpp:819
struct Gecode::@579::NNF::@61::@62 b
For binary nodes (and, or, eqv)
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
bool add(Space *s, Slave< CollectAll > *r)
Add a solution a reported by r and always return true.
Definition: pbs.hpp:45
Post propagator for SetVar SetOpType SetVar SetRelType r
Definition: set.hh:784
Stop object used for controling slaves in a portfolio.
Definition: pbs.hh:46
bool constrain(const Space &b)
Dummy function.
Definition: pbs.hpp:50
void share(volatile bool *ts)
Set pointer to shared tostop variable.
Definition: pbs.hpp:121
Heap heap
The single global heap.
Definition: heap.cpp:48
bool empty(void) const
Check whether there is any solution left.
Definition: pbs.hpp:55
#define forceinline
Definition: config.hpp:173
bool add(Space *s, Slave< CollectBest > *r)
Add a solution s by r and return whether is was better.
Definition: pbs.hpp:71
SpaceStatus status(StatusStatistics &stat=unused_status)
Query space status.
Definition: core.cpp:224
Exception: Best solution search is not supported
Definition: exception.hpp:64
bool empty(void) const
Check whether there is any solution left.
Definition: pbs.hpp:100
Gecode toplevel namespace
Space * get(Slave< CollectAll > *&r)
Return solution reported by r.
Definition: pbs.hpp:59
Space is failed
Definition: core.hpp:1689
Base-class for Stop-object.
Definition: search.hh:501
void todelete(bool d)
Set whether to delete upon termination.
Definition: thread.hpp:47
Parallel portfolio engine implementation.
Definition: pbs.hh:67
int solutions(TestSpace *c, Gecode::Search::Options &o, int maxNbSol=-1)
Find number of solutions.
Definition: branch.cpp:416
Slave< CollectBest > * reporter
Who has reported the best solution (NULL if solution has already been reported)
Definition: pbs.hh:122