Generated on for Gecode by doxygen 1.17.0
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.dev>
5 *
6 * Contributing authors:
7 * Mikael Zayenz Lagerkvist <lagerkvist@gecode.dev>
8 *
9 * Copyright:
10 * Christian Schulte, 2015
11 * Mikael Zayenz Lagerkvist, 2026
12 *
13 * This file is part of Gecode, the generic constraint
14 * development environment:
15 * http://www.gecode.dev
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 <algorithm>
39
40namespace Gecode { namespace Search { namespace Par {
41
42 template<class Collect>
45 // A slave has not been submitted yet. This initial signal lets the
46 // first submission use the same consume-before-reuse handshake as all
47 // subsequent submissions.
48 done.signal();
49 }
50
51 template<class Collect>
52 forceinline void
56
57 template<class Collect>
58 forceinline void
60 done.wait();
61 }
62
63
67 forceinline bool
69 solutions.push(s);
70 return true;
71 }
72 forceinline bool
74 (void) b;
75 return false;
76 }
77 forceinline bool
78 CollectAll::empty(void) const {
79 return solutions.empty();
80 }
83 return solutions.pop();
84 }
87 while (!solutions.empty())
88 delete solutions.pop();
89 }
90
94 : b(nullptr), reporter(nullptr) {}
95 forceinline bool
97 if (b != nullptr) {
98 b->constrain(*s);
99 if (b->status() == SS_FAILED) {
100 delete b;
101 } else {
102 delete s;
103 return false;
104 }
106 b = s;
108 return true;
110 forceinline bool
112 if (b != nullptr) {
114 if (b->status() == SS_FAILED) {
115 delete b;
116 } else {
117 return false;
118 }
120 b = s.clone();
121 reporter = nullptr;
122 return true;
123 }
124 forceinline bool
125 CollectBest::empty(void) const {
126 return reporter == nullptr;
127 }
130 assert(!empty());
131 r = reporter;
132 reporter = nullptr;
133 return b->clone();
134 }
137 delete b;
138 }
139
140
143 const WorkerControl& control)
144 : so(so0), po(po0), worker_control(control), tostop(nullptr) {}
145
146 forceinline void
147 PortfolioStop::share(std::atomic<bool>* ts) {
148 tostop = ts;
149 }
150
151
152 template<class Collect>
155 : Support::Runnable(false), master(m), slave(s), stop(so) {}
156 template<class Collect>
159 return slave->statistics();
160 }
161 template<class Collect>
162 forceinline bool
164 return slave->stopped();
165 }
166 template<class Collect>
167 forceinline bool
169#ifdef GECODE_HAS_EXPERIMENTAL
170 return slave->limited();
171#else
172 return false;
173#endif
174 }
175 template<class Collect>
178 return const_cast<Completion*>(&completion);
179 }
180 template<class Collect>
181 forceinline void
183 completion.wait();
184 }
185 template<class Collect>
186 forceinline void
188 static_cast<PortfolioStop*>(stop)->wake();
189 }
190 template<class Collect>
191 forceinline void
193 slave->constrain(b);
194 }
195 template<class Collect>
197 delete slave;
198 delete stop;
199 }
200
201
202
203 template<class Collect>
205 PBS<Collect>::PBS(Engine** engines, Stop** stops, unsigned int n,
206 const Statistics& stat0)
207 : stat(stat0), slaves(heap.alloc<Slave<Collect>*>(n)),
208 n_slaves(n), n_active(n),
209 slave_stop(false), incomplete(false), tostop(false), n_busy(0) {
210 // Initialize slaves
211 for (unsigned int i=0U; i<n_slaves; i++) {
212 slaves[i] = new Slave<Collect>(this,engines[i],stops[i]);
213 static_cast<PortfolioStop*>(stops[i])->share(&tostop);
214 }
216
218 template<class Collect>
219 forceinline bool
221 // If b is false the report should be repeated (solution was worse)
222 bool b = true;
223 bool wake = false;
224 m.acquire();
225 if (s != nullptr) {
226 b = solutions.add(s,slave);
227 if (b) {
228 tostop.store(true, std::memory_order_release);
229 wake = true;
230 }
231 } else if (slave->stopped() && !slave->limited()) {
232 if (!tostop.load(std::memory_order_acquire)) {
233 slave_stop.store(true, std::memory_order_release);
234 tostop.store(true, std::memory_order_release);
235 wake = true;
236 }
237 } else {
238 // The slave is done or stopped at a local limit (then search is incomplete)
239 if (slave->limited())
240 incomplete = true;
241 // Move slave to inactive
242 unsigned int i=0;
243 while (slaves[i] != slave)
244 i++;
245 assert(i < n_active);
246 assert(n_active > 0);
247 std::swap(slaves[i],slaves[--n_active]);
248 tostop.store(true, std::memory_order_release);
249 wake = true;
250 }
251 if (wake)
252 for (unsigned int i=0U; i<n_active; i++)
253 slaves[i]->wake();
254 if (b) {
255 if (--n_busy == 0)
256 idle.signal();
257 }
258 m.release();
259 return b;
260 }
261
262 template<class Collect>
263 void
265 Space* s;
266 do {
267 s = slave->next();
268 } while (!master->report(this,s));
269 }
270
271 template<class Collect>
272 Space*
274 m.acquire();
275 if (solutions.empty())
276 slave_stop.store(false, std::memory_order_release);
277 while (solutions.empty() && (n_active > 0) &&
278 !slave_stop.load(std::memory_order_acquire)) {
279 // Clear the internal stop used to interrupt sibling slaves
280 tostop.store(false, std::memory_order_release);
281
282 // Invariant: all slaves are idle!
283 assert(n_busy == 0);
284 assert(!tostop.load(std::memory_order_acquire));
285
286 // Run all active slaves
288 for (unsigned int i=0U; i<n_active; i++) {
289 // Consume the previous completion before reusing this slave. The
290 // initial signal handles the first submission.
291 slaves[i]->wait();
293 }
294 m.release();
295 // Wait for all slaves to become idle
296 idle.wait();
297 m.acquire();
298 }
299
300 // Invariant all slaves are idle!
301 assert(n_busy == 0);
302
303 if (solutions.empty() && (n_active == 0) && incomplete)
304 slave_stop.store(true, std::memory_order_release);
305
306 Space* s;
307
308 // Process solutions
309 if (solutions.empty()) {
310 s = nullptr;
311 } else {
313 s = solutions.get(r);
314 if (Collect::best)
315 for (unsigned int i=0U; i<n_active; i++)
316 if (slaves[i] != r)
317 slaves[i]->constrain(*s);
318 }
319
320 m.release();
321 return s;
322 }
323
324 template<class Collect>
325 bool
327 return slave_stop.load(std::memory_order_acquire);
328 }
329
330 template<class Collect>
333 assert(n_busy == 0);
334 Statistics s(stat);
335 for (unsigned int i=0U; i<n_slaves; i++)
336 s += slaves[i]->statistics();
337 return s;
338 }
339
340 template<class Collect>
341 void
343 assert(n_busy == 0);
344 if (!Collect::best)
345 throw NoBest("PBS::constrain");
346 if (solutions.constrain(b)) {
347 // The solution is better
348 for (unsigned int i=0U; i<n_active; i++)
349 slaves[i]->constrain(b);
350 }
351 }
352
353 template<class Collect>
355 // A report can make n_busy zero before Slave::run and Thread::Run::exec
356 // have returned. Wait for the completion handshake before deleting the
357 // PBS-owned slaves.
358 for (unsigned int i=0U; i<n_slaves; i++)
359 slaves[i]->wait();
360 assert(n_busy == 0);
361 for (unsigned int i=0U; i<n_slaves; i++)
362 delete slaves[i];
364 }
365
366}}}
367
368// STATISTICS: search-par
Exception: Best solution search is not supported
Definition exception.hpp:60
Space * get(Slave< CollectAll > *&r)
Return solution reported by r.
Definition pbs.hpp:82
bool empty(void) const
Check whether there is any solution left.
Definition pbs.hpp:78
Support::DynamicQueue< Space *, Heap > solutions
Queue of solutions.
Definition pbs.hh:126
bool add(Space *s, Slave< CollectAll > *r)
Add a solution a reported by r and always return true.
Definition pbs.hpp:68
CollectAll(void)
Initialize.
Definition pbs.hpp:65
~CollectAll(void)
Destructor.
Definition pbs.hpp:86
bool constrain(const Space &b)
Dummy function.
Definition pbs.hpp:73
CollectBest(void)
Initialize.
Definition pbs.hpp:93
bool constrain(const Space &b)
Check whether b better and update accordingly.
Definition pbs.hpp:111
bool empty(void) const
Check whether there is any solution left.
Definition pbs.hpp:125
bool add(Space *s, Slave< CollectBest > *r)
Add a solution s by r and return whether is was better.
Definition pbs.hpp:96
Space * get(Slave< CollectBest > *&r)
Return solution reported by r (only if a better one was found).
Definition pbs.hpp:129
Slave< CollectBest > * reporter
Who has reported the best solution (nullptr if solution has already been reported).
Definition pbs.hh:150
~CollectBest(void)
Destructor.
Definition pbs.hpp:136
Space * b
Currently best solution.
Definition pbs.hh:148
Parallel depth-first search engine
Definition engine.hh:52
Engine(const Options &o)
Initialize with options o.
Definition engine.hpp:123
void stop(unsigned long long int r)
Report that a worker was stopped during call r of next().
Definition engine.hpp:384
Parallel portfolio engine implementation.
Definition pbs.hh:170
virtual bool stopped(void) const
Check whether engine has been stopped.
Definition pbs.hpp:326
virtual ~PBS(void)
Destructor.
Definition pbs.hpp:354
Support::Event idle
Signal that number of busy slaves becomes zero.
Definition pbs.hh:194
bool report(Slave< Collect > *slave, Space *s)
Process report from slave, return false if solution was ignored.
Definition pbs.hpp:220
Collect solutions
Collect solutions in this.
Definition pbs.hh:188
Support::Mutex m
Mutex for synchronization.
Definition pbs.hh:190
Slave< Gecode::Search::Par::CollectBest > ** slaves
Definition pbs.hh:176
PBS(Engine **s, Stop **so, unsigned int n, const Statistics &stat)
Initialize.
Definition pbs.hpp:205
virtual void constrain(const Space &b)
Constrain future solutions to be better than b.
Definition pbs.hpp:342
virtual Space * next(void)
Return next solution (nullptr, if none exists or search has been stopped).
Definition pbs.hpp:273
virtual Statistics statistics(void) const
Return statistics.
Definition pbs.hpp:332
Stop object used for controlling slaves in a portfolio.
Definition pbs.hh:47
void share(std::atomic< bool > *ts)
Set pointer to shared tostop variable.
Definition pbs.hpp:147
PortfolioStop(Stop *so, Stop *po, const WorkerControl &control)
Initialize with slave stop so, portfolio stop po, and control.
Definition pbs.hpp:142
Completion event for the current run.
Definition pbs.hh:81
virtual void terminated(void)
Signal completion.
Definition pbs.hpp:53
void wait(void)
Wait for completion and consume the signal.
Definition pbs.hpp:59
Completion(void)
Initialize as completed.
Definition pbs.hpp:44
Support::Event done
The completion event.
Definition pbs.hh:84
Runnable slave of a portfolio master.
Definition pbs.hh:78
Engine * slave
The slave engine.
Definition pbs.hh:96
PBS< Collect > * master
The master engine.
Definition pbs.hh:94
void wait(void)
Wait for the slave to complete its current run.
Definition pbs.hpp:182
virtual Support::Terminator * terminator(void) const
Return the completion terminator.
Definition pbs.hpp:177
virtual void run(void)
Perform one run.
Definition pbs.hpp:264
bool stopped(void) const
Check whether slave has been stopped.
Definition pbs.hpp:163
virtual ~Slave(void)
Delete slave.
Definition pbs.hpp:196
Statistics statistics(void) const
Return statistics of slave.
Definition pbs.hpp:158
Slave(PBS< Collect > *m, Engine *s, Stop *so)
Initialize with master m, slave s, and its stop object so.
Definition pbs.hpp:154
Gecode::Search::Par::Slave::Completion completion
void wake(void)
Wake a paused slave so that it can observe the portfolio stop.
Definition pbs.hpp:187
void constrain(const Space &b)
Constrain with better solution b.
Definition pbs.hpp:192
Stop * stop
Stop object.
Definition pbs.hh:98
bool limited(void) const
Check whether slave stopped at a local limit.
Definition pbs.hpp:168
Search engine statistics
Definition search.hh:155
Base-class for Stop-object.
Definition search.hh:919
Stop(void)
Default constructor.
Definition stop.hpp:45
External control for the requested number of search workers.
Definition search.hh:773
Computation spaces.
Definition core.hpp:1787
Runnable(bool d=true)
Initialize, d defines whether object is deleted when terminated.
Definition thread.hpp:40
An interface for objects that can be called after a thread has terminated (after running the thread's...
Definition thread.hpp:168
static void run(Runnable *r)
Construct a new thread and run r.
Definition thread.hpp:177
Heap heap
The single global heap.
Definition heap.cpp:44
virtual void constrain(const Space &best)
Constrain function for best solution search.
Definition core.cpp:896
Space * clone(void) const
Clone space.
Definition core.hpp:3384
SpaceStatus status(StatusStatistics &stat)
Query space status.
Definition core.cpp:281
@ SS_FAILED
Space is failed
Definition core.hpp:1727
Search engines
Support algorithms and datastructures
Gecode toplevel namespace
void wait(Home home, FloatVar x, std::function< void(Space &home)> c)
Execute c when x becomes assigned.
Definition exec.cpp:39
#define forceinline
Definition config.hpp:144