Generated on Sat Jul 28 2018 17:18:34 for Gecode by doxygen 1.8.14
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 #include <cmath>
39 #include <algorithm>
40 
41 namespace Gecode { namespace Search {
42 
44  template<class T, template<class> class E>
45  class PbsBuilder : public Builder {
46  using Builder::opt;
47  public:
49  PbsBuilder(const Options& opt);
51  virtual Engine* operator() (Space* s) const;
52  };
53 
54  template<class T, template<class> class E>
55  inline
57  : Builder(opt,E<T>::best) {}
58 
59  template<class T, template<class> class E>
60  Engine*
62  return build<T,PBS<T,E> >(s,opt);
63  }
64 
65 }}
66 
68 
69 namespace Gecode { namespace Search { namespace Meta { namespace Sequential {
70 
73  stop(Stop* so);
74 
76  GECODE_SEARCH_EXPORT Engine*
77  engine(Engine** slaves, Stop** stops, unsigned int n_slaves,
78  const Statistics& stat, const Search::Options& opt, bool best);
79 
80 }}}}
81 
82 namespace Gecode { namespace Search { namespace Meta { namespace Parallel {
83 
86  stop(Stop* so);
87 
89  GECODE_SEARCH_EXPORT Engine*
90  engine(Engine** slaves, Stop** stops, unsigned int n_slaves,
91  const Statistics& stat, bool best);
92 
93 }}}}
94 
95 namespace Gecode { namespace Search { namespace Meta {
96 
97  template<class T, template<class> class E>
98  Engine*
99  sequential(T* master, const Search::Statistics& stat, Options& opt) {
100  Stop* stop = opt.stop;
101  Region r(*master);
102 
103  // In case there are more threads than assets requested
104  opt.threads = std::max(floor(opt.threads /
105  static_cast<double>(opt.assets)),1.0);
106 
107  unsigned int n_slaves = opt.assets;
108  Engine** slaves = r.alloc<Engine*>(n_slaves);
109  Stop** stops = r.alloc<Stop*>(n_slaves);
110 
111  for (unsigned int i=0; i<n_slaves; i++) {
112  opt.stop = stops[i] = Sequential::stop(stop);
113  Space* slave = (i == n_slaves-1) ?
114  master : master->clone(opt.threads <= 1.0,opt.share_pbs);
115  (void) slave->slave(i);
116  slaves[i] = build<T,E>(slave,opt);
117  }
118 
119  return Sequential::engine(slaves,stops,n_slaves,stat,opt,E<T>::best);
120  }
121 
122  template<class T, template<class> class E>
123  Engine*
124  sequential(T* master, SEBs& sebs,
125  const Search::Statistics& stat, Options& opt, bool best) {
126  Region r(*master);
127 
128  int n_slaves = sebs.size();
129  Engine** slaves = r.alloc<Engine*>(n_slaves);
130  Stop** stops = r.alloc<Stop*>(n_slaves);
131 
132  for (int i=0; i<n_slaves; i++) {
133  // Re-configure slave options
134  stops[i] = Sequential::stop(sebs[i]->options().stop);
135  sebs[i]->options().stop = stops[i];
136  sebs[i]->options().clone = false;
137  Space* slave = (i == n_slaves-1) ?
138  master : master->clone(sebs[i]->options().threads <= 1.0,
139  sebs[i]->options().share_pbs);
140  (void) slave->slave(i);
141  slaves[i] = (*sebs[i])(slave);
142  delete sebs[i];
143  }
144 
145  return Sequential::engine(slaves,stops,n_slaves,stat,opt,best);
146  }
147 
148 #ifdef GECODE_HAS_THREADS
149 
150  template<class T, template<class> class E>
151  Engine*
152  parallel(T* master, const Search::Statistics& stat, Options& opt) {
153  Stop* stop = opt.stop;
154  Region r(*master);
155 
156  // Limit the number of slaves to the number of threads
157  unsigned int n_slaves = std::min(static_cast<unsigned int>(opt.threads),
158  opt.assets);
159  // Redistribute additional threads to slaves
160  opt.threads = floor(opt.threads / static_cast<double>(n_slaves));
161 
162  Engine** slaves = r.alloc<Engine*>(n_slaves);
163  Stop** stops = r.alloc<Stop*>(n_slaves);
164 
165  for (unsigned int i=0; i<n_slaves; i++) {
166  opt.stop = stops[i] = Parallel::stop(stop);
167  Space* slave = (i == n_slaves-1) ?
168  master : master->clone(false,opt.share_pbs);
169  (void) slave->slave(i);
170  slaves[i] = build<T,E>(slave,opt);
171  }
172 
173  return Parallel::engine(slaves,stops,n_slaves,stat,E<T>::best);
174  }
175 
176  template<class T, template<class> class E>
177  Engine*
178  parallel(T* master, SEBs& sebs,
179  const Search::Statistics& stat, Options& opt, bool best) {
180  Region r(*master);
181 
182  // Limit the number of slaves to the number of threads
183  int n_slaves = std::min(static_cast<int>(opt.threads),
184  sebs.size());
185  Engine** slaves = r.alloc<Engine*>(n_slaves);
186  Stop** stops = r.alloc<Stop*>(n_slaves);
187 
188  for (int i=0; i<n_slaves; i++) {
189  // Re-configure slave options
190  stops[i] = Parallel::stop(sebs[i]->options().stop);
191  sebs[i]->options().stop = stops[i];
192  sebs[i]->options().clone = false;
193  Space* slave = (i == n_slaves-1) ?
194  master : master->clone(false,sebs[i]->options().share_pbs);
195  (void) slave->slave(i);
196  slaves[i] = (*sebs[i])(slave);
197  delete sebs[i];
198  }
199  // Delete excess builders
200  for (int i=n_slaves; i<sebs.size(); i++)
201  delete sebs[i];
202 
203  return Parallel::engine(slaves,stops,n_slaves,stat,best);
204  }
205 
206 #endif
207 
208 }}}
209 
210 namespace Gecode {
211 
212  template<class T, template<class> class E>
213  PBS<T,E>::PBS(T* s, const Search::Options& o) {
215 
216  if (opt.assets == 0)
217  throw Search::NoAssets("PBS::PBS");
218 
219  Search::Statistics stat;
220 
221  if (s->status(stat) == SS_FAILED) {
222  stat.fail++;
223  if (!opt.clone)
224  delete s;
225  e = new Search::Meta::Dead(stat);
226  return;
227  }
228 
229  // Check whether a clone must be used
230  T* master = opt.clone ?
231  dynamic_cast<T*>(s->clone(opt.threads <= 1.0,opt.share_pbs)) : s;
232  opt.clone = false;
233 
234  // Always execute master function
235  (void) master->master(0);
236 
237  // No need to create a portfolio engine but must run slave function
238  if (o.assets == 1) {
239  (void) master->slave(0);
240  e = Search::build<T,E>(master,opt);
241  return;
242  }
243 
244 #ifdef GECODE_HAS_THREADS
245  if (opt.threads > 1.0)
246  e = Search::Meta::parallel<T,E>(master,stat,opt);
247  else
248 #endif
249  e = Search::Meta::sequential<T,E>(master,stat,opt);
250  }
251 
252  template<class T, template<class> class E>
253  void
254  PBS<T,E>::build(T* s, SEBs& sebs, const Search::Options& o) {
255  // Check whether all sebs do either best solution search or not
256  bool best;
257  {
258  int b = 0;
259  for (int i=sebs.size(); i--; )
260  b += sebs[i]->best() ? 1 : 0;
261  if ((b > 0) && (b < sebs.size()))
262  throw Search::MixedBest("PBS::PBS");
263  best = (b == sebs.size());
264  }
265 
267  Search::Statistics stat;
268 
269  if (s->status(stat) == SS_FAILED) {
270  stat.fail++;
271  if (!opt.clone)
272  delete s;
273  e = new Search::Meta::Dead(stat);
274  return;
275  }
276 
277  // Check whether a clone must be used
278  T* master = opt.clone ?
279  dynamic_cast<T*>(s->clone(opt.threads <= 1.0,opt.share_pbs)) : s;
280  opt.clone = false;
281 
282  // Always execute master function
283  (void) master->master(0);
284 
285 #ifdef GECODE_HAS_THREADS
286  if (opt.threads > 1.0)
287  e = Search::Meta::parallel<T,E>(master,sebs,stat,opt,best);
288  else
289 #endif
290  e = Search::Meta::sequential<T,E>(master,sebs,stat,opt,best);
291  }
292 
293  template<class T, template<class> class E>
294  inline
295  PBS<T,E>::PBS(T* s, SEBs& sebs, const Search::Options& o) {
296  build(s,sebs,o);
297  }
298  template<class T, template<class> class E>
299  inline
300  PBS<T,E>::PBS(T* s, SEB seb0, SEB seb1,
301  const Search::Options& o) {
302  SEBs sebs(2, seb0, seb1);
303  build(s,sebs,o);
304  }
305  template<class T, template<class> class E>
306  inline
307  PBS<T,E>::PBS(T* s, SEB seb0, SEB seb1, SEB seb2,
308  const Search::Options& o) {
309  SEBs sebs(3, seb0, seb1, seb2);
310  build(s,sebs,o);
311  }
312  template<class T, template<class> class E>
313  inline
314  PBS<T,E>::PBS(T* s, SEB seb0, SEB seb1, SEB seb2, SEB seb3,
315  const Search::Options& o) {
316  SEBs sebs(4, seb0, seb1, seb2, seb3);
317  build(s,sebs,o);
318  }
319 
320  template<class T, template<class> class E>
321  inline T*
322  pbs(T* s, const Search::Options& o) {
323  PBS<T,E> r(s,o);
324  return r.next();
325  }
326 
327  template<class T, template<class> class E>
328  inline SEB
329  pbs(const Search::Options& o) {
330  return new Search::PbsBuilder<T,E>(o);
331  }
332 
333 }
334 
335 // STATISTICS: search-meta
void build(T *s, SEBs &sebs, const Search::Options &o)
The actual build function.
Definition: pbs.hpp:254
Search engine implementation interface
Definition: search.hh:601
A PBS engine builder.
Definition: pbs.hpp:45
int size(void) const
Return size of array (number of elements)
Definition: array.hpp:1669
Search engine statistics
Definition: search.hh:140
const FloatNum max
Largest allowed float value.
Definition: float.hh:848
Meta engine using a portfolio of search engines.
Definition: search.hh:939
#define GECODE_SEARCH_EXPORT
Definition: search.hh:63
virtual Engine * operator()(Space *s) const
The actual build function.
Definition: pbs.hpp:61
Search engine options
Definition: search.hh:446
A class for building search engines.
Definition: search.hh:667
Stop * stop(Stop *so)
Create stop object.
Definition: pbs.cpp:65
Exception: No assets requested for portfolio-based search
Definition: exception.hpp:52
Options opt
Stored and already expanded options.
Definition: search.hh:670
Engine * build(Space *s, const Options &opt)
Build an engine of type E for a script T.
Definition: build.hpp:62
unsigned long int fail
Number of failed nodes in search tree.
Definition: search.hh:143
Space * clone(bool share_data=true, bool share_info=true, CloneStatistics &stat=unused_clone) const
Clone space.
Definition: core.hpp:3326
Handle to region.
Definition: region.hpp:61
Engine * engine(Engine **slaves, Stop **stops, unsigned int n_slaves, const Statistics &stat, const Search::Options &opt, bool best)
Create sequential portfolio engine.
Definition: pbs.cpp:48
Computation spaces.
Definition: core.hpp:1748
Options expand(void) const
Expand with real number of threads.
Definition: options.cpp:47
Engine * engine(Engine **slaves, Stop **stops, unsigned int n_slaves, const Statistics &stat, bool best)
Create parallel portfolio engine.
Definition: pbs.cpp:70
const FloatNum min
Smallest allowed float value.
Definition: float.hh:850
Gecode::IntArgs i(4, 1, 2, 3, 4)
Options opt
The options.
Definition: test.cpp:101
Engine * sequential(T *master, const Search::Statistics &stat, Options &opt)
Build a sequential engine.
Definition: pbs.hpp:99
A dead engine (failed root)
Definition: dead.hh:44
struct Gecode::@579::NNF::@61::@62 b
For binary nodes (and, or, eqv)
virtual bool slave(const MetaInfo &mi)
Slave configuration function for meta search engines.
Definition: core.cpp:841
Search::Builder * SEB
Type for a search engine builder.
Definition: search.hh:695
Stop * stop(Stop *so)
Create stop object.
Definition: pbs.cpp:43
Exception: Mixed non-best and best solution search requested
Definition: exception.hpp:58
unsigned int assets
Number of assets (engines) in a portfolio.
Definition: search.hh:463
T * pbs(T *s, const Search::Options &o)
Run a portfolio of search engines.
Definition: pbs.hpp:322
Post propagator for SetVar SetOpType SetVar SetRelType r
Definition: set.hh:784
void assets(unsigned int n)
Set default number of assets in a portfolio.
Definition: options.hpp:359
Engine * parallel(T *master, const Search::Statistics &stat, Options &opt)
Build a parallel engine.
Definition: pbs.hpp:152
PbsBuilder(const Options &opt)
The constructor.
Definition: pbs.hpp:56
Passing search engine builder arguments.
Definition: search.hh:704
void threads(double n)
Set number of parallel threads.
Definition: options.hpp:296
Gecode toplevel namespace
Space is failed
Definition: core.hpp:1689
Base-class for Stop-object.
Definition: search.hh:501
PBS(T *s, const Search::Options &o=Search::Options::def)
Initialize with engines running copies of s with options o.
Definition: pbs.hpp:213
bool stop
Whether to stop on an error.
Definition: test.hh:93
Stop * stop(Stop *stop)
Create stop object.
Definition: rbs.cpp:43