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 <cmath>
35 #include <algorithm>
36 
37 namespace Gecode { namespace Search {
38 
39   /// A PBS engine builder
40   template<class T, template<class> class E>
41   class PbsBuilder : public Builder {
42     using Builder::opt;
43   public:
44     /// The constructor
45     PbsBuilder(const Options& opt);
46     /// The actual build function
47     virtual Engine* operator() (Space* s) const;
48   };
49 
50   template<class T, template<class> class E>
51   inline
PbsBuilder(const Options & opt)52   PbsBuilder<T,E>::PbsBuilder(const Options& opt)
53     : Builder(opt,E<T>::best) {}
54 
55   template<class T, template<class> class E>
56   Engine*
operator ()(Space * s) const57   PbsBuilder<T,E>::operator() (Space* s) const {
58     return build<T,PBS<T,E> >(s,opt);
59   }
60 
61 }}
62 
63 #include <gecode/search/seq/dead.hh>
64 
65 namespace Gecode { namespace Search { namespace Seq {
66 
67   /// Create stop object
68   GECODE_SEARCH_EXPORT Stop*
69   pbsstop(Stop* so);
70 
71   /// Create sequential portfolio engine
72   GECODE_SEARCH_EXPORT Engine*
73   pbsengine(Engine** slaves, Stop** stops, unsigned int n_slaves,
74             const Statistics& stat, const Search::Options& opt, bool best);
75 
76 }}}
77 
78 namespace Gecode { namespace Search { namespace Par {
79 
80   /// Create stop object
81   GECODE_SEARCH_EXPORT Stop*
82   pbsstop(Stop* so);
83 
84   /// Create parallel portfolio engine
85   GECODE_SEARCH_EXPORT Engine*
86   pbsengine(Engine** slaves, Stop** stops, unsigned int n_slaves,
87             const Statistics& stat, bool best);
88 
89 }}}
90 
91 namespace Gecode { namespace Search {
92 
93   template<class T, template<class> class E>
94   Engine*
pbsseq(T * master,const Search::Statistics & stat,Options & opt)95   pbsseq(T* master, const Search::Statistics& stat, Options& opt) {
96     Stop* stop = opt.stop;
97     Region r;
98 
99     // In case there are more threads than assets requested
100     opt.threads = std::max(floor(opt.threads /
101                                  static_cast<double>(opt.assets)),1.0);
102 
103     unsigned int n_slaves = opt.assets;
104     Engine** slaves = r.alloc<Engine*>(n_slaves);
105     Stop** stops = r.alloc<Stop*>(n_slaves);
106 
107     WrapTraceRecorder::engine(opt.tracer,
108                               SearchTracer::EngineType::PBS, n_slaves);
109 
110     for (unsigned int i=0U; i<n_slaves; i++) {
111       opt.stop = stops[i] = Seq::pbsstop(stop);
112       Space* slave = (i == n_slaves-1) ?
113         master : master->clone();
114       (void) slave->slave(i);
115       slaves[i] = build<T,E>(slave,opt);
116     }
117 
118     return Seq::pbsengine(slaves,stops,n_slaves,stat,opt,E<T>::best);
119   }
120 
121   template<class T, template<class> class E>
122   Engine*
pbsseq(T * master,SEBs & sebs,const Search::Statistics & stat,Options & opt,bool best)123   pbsseq(T* master, SEBs& sebs,
124              const Search::Statistics& stat, Options& opt, bool best) {
125     Region r;
126 
127     int n_slaves = sebs.size();
128     Engine** slaves = r.alloc<Engine*>(n_slaves);
129     Stop** stops = r.alloc<Stop*>(n_slaves);
130 
131     WrapTraceRecorder::engine(opt.tracer,
132                               SearchTracer::EngineType::PBS,
133                               static_cast<unsigned int>(n_slaves));
134 
135     for (int i=0; i<n_slaves; i++) {
136       // Re-configure slave options
137       stops[i] = Seq::pbsstop(sebs[i]->options().stop);
138       sebs[i]->options().stop  = stops[i];
139       sebs[i]->options().clone = false;
140       Space* slave = (i == n_slaves-1) ?
141         master : master->clone();
142       (void) slave->slave(static_cast<unsigned int>(i));
143       slaves[i] = (*sebs[i])(slave);
144       delete sebs[i];
145     }
146 
147     return Seq::pbsengine(slaves,stops,static_cast<unsigned int>(n_slaves),
148                           stat,opt,best);
149   }
150 
151 #ifdef GECODE_HAS_THREADS
152 
153   template<class T, template<class> class E>
154   Engine*
pbspar(T * master,const Search::Statistics & stat,Options & opt)155   pbspar(T* master, const Search::Statistics& stat, Options& opt) {
156     Stop* stop = opt.stop;
157     Region r;
158 
159     // Limit the number of slaves to the number of threads
160     unsigned int n_slaves = std::min(static_cast<unsigned int>(opt.threads),
161                                      opt.assets);
162     // Redistribute additional threads to slaves
163     opt.threads = floor(opt.threads / static_cast<double>(n_slaves));
164 
165     WrapTraceRecorder::engine(opt.tracer,
166                               SearchTracer::EngineType::PBS, n_slaves);
167 
168     Engine** slaves = r.alloc<Engine*>(n_slaves);
169     Stop** stops = r.alloc<Stop*>(n_slaves);
170 
171     for (unsigned int i=0U; i<n_slaves; i++) {
172       opt.stop = stops[i] = Par::pbsstop(stop);
173       Space* slave = (i == n_slaves-1) ?
174         master : master->clone();
175       (void) slave->slave(static_cast<unsigned int>(i));
176       slaves[i] = build<T,E>(slave,opt);
177     }
178 
179     return Par::pbsengine(slaves,stops,n_slaves,stat,E<T>::best);
180   }
181 
182   template<class T, template<class> class E>
183   Engine*
pbspar(T * master,SEBs & sebs,const Search::Statistics & stat,Options & opt,bool best)184   pbspar(T* master, SEBs& sebs,
185          const Search::Statistics& stat, Options& opt, bool best) {
186     Region r;
187 
188     // Limit the number of slaves to the number of threads
189     int n_slaves = std::min(static_cast<int>(opt.threads),
190                             sebs.size());
191 
192     WrapTraceRecorder::engine(opt.tracer,
193                               SearchTracer::EngineType::PBS,
194                               static_cast<unsigned int>(n_slaves));
195 
196     Engine** slaves = r.alloc<Engine*>(n_slaves);
197     Stop** stops = r.alloc<Stop*>(n_slaves);
198 
199     for (int i=0; i<n_slaves; i++) {
200       // Re-configure slave options
201       stops[i] = Par::pbsstop(sebs[i]->options().stop);
202       sebs[i]->options().stop  = stops[i];
203       sebs[i]->options().clone = false;
204       Space* slave = (i == n_slaves-1) ?
205         master : master->clone();
206       (void) slave->slave(static_cast<unsigned int>(i));
207       slaves[i] = (*sebs[i])(slave);
208       delete sebs[i];
209     }
210     // Delete excess builders
211     for (int i=n_slaves; i<sebs.size(); i++)
212       delete sebs[i];
213 
214     return Par::pbsengine(slaves,stops,static_cast<unsigned int>(n_slaves),
215                           stat,best);
216   }
217 
218 #endif
219 
220 }}
221 
222 namespace Gecode {
223 
224   template<class T, template<class> class E>
PBS(T * s,const Search::Options & o)225   PBS<T,E>::PBS(T* s, const Search::Options& o) {
226     Search::Options opt(o.expand());
227 
228     if (opt.assets == 0)
229       throw Search::NoAssets("PBS::PBS");
230 
231     Search::Statistics stat;
232 
233     if (s->status(stat) == SS_FAILED) {
234       stat.fail++;
235       if (!opt.clone)
236         delete s;
237       e = Search::Seq::dead(opt,stat);
238       return;
239     }
240 
241     // Check whether a clone must be used
242     T* master = opt.clone ?
243       dynamic_cast<T*>(s->clone()) : s;
244     opt.clone = false;
245 
246     // Always execute master function
247     (void) master->master(0);
248 
249     // No need to create a portfolio engine but must run slave function
250     if (o.assets == 1) {
251       (void) master->slave(0);
252       e = Search::build<T,E>(master,opt);
253       return;
254     }
255 
256 #ifdef GECODE_HAS_THREADS
257     if (opt.threads > 1.0)
258       e = Search::pbspar<T,E>(master,stat,opt);
259     else
260 #endif
261       e = Search::pbsseq<T,E>(master,stat,opt);
262   }
263 
264   template<class T, template<class> class E>
265   void
build(T * s,SEBs & sebs,const Search::Options & o)266   PBS<T,E>::build(T* s, SEBs& sebs, const Search::Options& o) {
267     // Check whether all sebs do either best solution search or not
268     bool best;
269     {
270       int b = 0;
271       for (int i=0; i<sebs.size(); i++)
272         b += sebs[i]->best() ? 1 : 0;
273       if ((b > 0) && (b < sebs.size()))
274         throw Search::MixedBest("PBS::PBS");
275       best = (b == sebs.size());
276     }
277 
278     Search::Options opt(o.expand());
279     Search::Statistics stat;
280 
281     if (s->status(stat) == SS_FAILED) {
282       stat.fail++;
283       if (!opt.clone)
284         delete s;
285       e = Search::Seq::dead(opt,stat);
286       return;
287     }
288 
289     // Check whether a clone must be used
290     T* master = opt.clone ?
291       dynamic_cast<T*>(s->clone()) : s;
292     opt.clone = false;
293 
294     // Always execute master function
295     (void) master->master(0);
296 
297 #ifdef GECODE_HAS_THREADS
298     if (opt.threads > 1.0)
299       e = Search::pbspar<T,E>(master,sebs,stat,opt,best);
300     else
301 #endif
302       e = Search::pbsseq<T,E>(master,sebs,stat,opt,best);
303   }
304 
305   template<class T, template<class> class E>
306   inline
PBS(T * s,SEBs & sebs,const Search::Options & o)307   PBS<T,E>::PBS(T* s, SEBs& sebs, const Search::Options& o) {
308     build(s,sebs,o);
309   }
310 
311   template<class T, template<class> class E>
312   inline T*
pbs(T * s,const Search::Options & o)313   pbs(T* s, const Search::Options& o) {
314     PBS<T,E> r(s,o);
315     return r.next();
316   }
317 
318   template<class T, template<class> class E>
319   inline SEB
pbs(const Search::Options & o)320   pbs(const Search::Options& o) {
321     return new Search::PbsBuilder<T,E>(o);
322   }
323 
324 }
325 
326 // STATISTICS: search-other
327