this repo has no description
dekker.one
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
37namespace 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
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*
57 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
65namespace 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
78namespace 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
91namespace Gecode { namespace Search {
92
93 template<class T, template<class> class E>
94 Engine*
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*
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*
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*
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
222namespace Gecode {
223
224 template<class T, template<class> class E>
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
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
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*
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
320 pbs(const Search::Options& o) {
321 return new Search::PbsBuilder<T,E>(o);
322 }
323
324}
325
326// STATISTICS: search-other