Generated on Tue Feb 11 2025 17:33:26 for Gecode by doxygen 1.12.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.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 <algorithm>
35
36namespace Gecode { namespace Search { namespace Par {
37
38
41 : solutions(heap) {}
42 forceinline bool
44 solutions.push(s);
45 return true;
46 }
47 forceinline bool
49 (void) b;
50 return false;
51 }
52 forceinline bool
53 CollectAll::empty(void) const {
54 return solutions.empty();
55 }
58 return solutions.pop();
59 }
62 while (!solutions.empty())
63 delete solutions.pop();
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 }
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();
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();
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)),
158 n_slaves(n), n_active(n),
159 slave_stop(false), tostop(false), n_busy(0) {
160 // Initialize slaves
161 for (unsigned int i=0U; i<n_slaves; i++) {
162 slaves[i] = new Slave<Collect>(this,engines[i],stops[i]);
163 static_cast<PortfolioStop*>(stops[i])->share(&tostop);
164 }
165 }
166
167
168 template<class Collect>
169 forceinline bool
171 // If b is false the report should be repeated (solution was worse)
172 bool b = true;
173 m.acquire();
174 if (s != NULL) {
175 b = solutions.add(s,slave);
176 if (b)
177 tostop = true;
178 } else if (slave->stopped()) {
179 if (!tostop)
180 slave_stop = true;
181 } else {
182 // Move slave to inactive, as it has exhausted its engine
183 unsigned int i=0;
184 while (slaves[i] != slave)
185 i++;
186 assert(i < n_active);
187 assert(n_active > 0);
188 std::swap(slaves[i],slaves[--n_active]);
189 tostop = true;
190 }
191 if (b) {
192 if (--n_busy == 0)
193 idle.signal();
194 }
195 m.release();
196 return b;
197 }
198
199 template<class Collect>
200 void
202 Space* s;
203 do {
204 s = slave->next();
205 } while (!master->report(this,s));
206 }
207
208 template<class Collect>
209 Space*
211 m.acquire();
212 if (solutions.empty()) {
213 // Clear all
214 tostop = false;
215 slave_stop = false;
216
217 // Invariant: all slaves are idle!
218 assert(n_busy == 0);
219 assert(!tostop);
220
221 if (n_active > 0) {
222 // Run all active slaves
223 n_busy = n_active;
224 for (unsigned int i=0U; i<n_active; i++)
225 Support::Thread::run(slaves[i]);
226 m.release();
227 // Wait for all slaves to become idle
228 idle.wait();
229 m.acquire();
230 }
231 }
232
233 // Invariant all slaves are idle!
234 assert(n_busy == 0);
235
236 Space* s;
237
238 // Process solutions
239 if (solutions.empty()) {
240 s = NULL;
241 } else {
243 s = solutions.get(r);
244 if (Collect::best)
245 for (unsigned int i=0U; i<n_active; i++)
246 if (slaves[i] != r)
247 slaves[i]->constrain(*s);
248 }
249
250 m.release();
251 return s;
252 }
253
254 template<class Collect>
255 bool
257 return slave_stop;
258 }
259
260 template<class Collect>
263 assert(n_busy == 0);
264 Statistics s(stat);
265 for (unsigned int i=0U; i<n_slaves; i++)
266 s += slaves[i]->statistics();
267 return s;
268 }
269
270 template<class Collect>
271 void
273 assert(n_busy == 0);
274 if (!Collect::best)
275 throw NoBest("PBS::constrain");
276 if (solutions.constrain(b)) {
277 // The solution is better
278 for (unsigned int i=0U; i<n_active; i++)
279 slaves[i]->constrain(b);
280 }
281 }
282
283 template<class Collect>
285 assert(n_busy == 0);
286 heap.free<Slave<Collect>*>(slaves,n_slaves);
287 }
288
289}}}
290
291// STATISTICS: search-par
struct Gecode::@603::NNF::@65::@66 b
For binary nodes (and, or, eqv)
int n
Number of negative literals for node type.
void free(T *b, long unsigned int n)
Delete n objects starting at b.
Definition heap.hpp:457
Exception: Best solution search is not supported
Definition exception.hpp:60
Space * get(Slave< CollectAll > *&r)
Return solution reported by r.
Definition pbs.hpp:57
bool empty(void) const
Check whether there is any solution left.
Definition pbs.hpp:53
Support::DynamicQueue< Space *, Heap > solutions
Queue of solutions.
Definition pbs.hh:94
bool add(Space *s, Slave< CollectAll > *r)
Add a solution a reported by r and always return true.
Definition pbs.hpp:43
CollectAll(void)
Initialize.
Definition pbs.hpp:40
~CollectAll(void)
Destructor.
Definition pbs.hpp:61
bool constrain(const Space &b)
Dummy function.
Definition pbs.hpp:48
CollectBest(void)
Initialize.
Definition pbs.hpp:68
bool constrain(const Space &b)
Check whether b better and update accordingly.
Definition pbs.hpp:86
bool empty(void) const
Check whether there is any solution left.
Definition pbs.hpp:100
bool add(Space *s, Slave< CollectBest > *r)
Add a solution s by r and return whether is was better.
Definition pbs.hpp:71
Space * get(Slave< CollectBest > *&r)
Return solution reported by r (only if a better one was found)
Definition pbs.hpp:104
Slave< CollectBest > * reporter
Who has reported the best solution (NULL if solution has already been reported)
Definition pbs.hh:118
~CollectBest(void)
Destructor.
Definition pbs.hpp:111
Space * b
Currently best solution.
Definition pbs.hh:116
Parallel depth-first search engine
Definition engine.hh:46
Parallel portfolio engine implementation.
Definition pbs.hh:138
virtual bool stopped(void) const
Check whether engine has been stopped.
Definition pbs.hpp:256
virtual ~PBS(void)
Destructor.
Definition pbs.hpp:284
bool report(Slave< Collect > *slave, Space *s)
Process report from slave, return false if solution was ignored.
Definition pbs.hpp:170
friend class Slave< Collect >
Definition pbs.hh:139
Slave< Collect > ** slaves
Slave engines.
Definition pbs.hh:144
volatile bool tostop
Shared stop flag.
Definition pbs.hh:152
unsigned int n_slaves
Number of slave engines.
Definition pbs.hh:146
PBS(Engine **s, Stop **so, unsigned int n, const Statistics &stat)
Initialize.
Definition pbs.hpp:155
virtual void constrain(const Space &b)
Constrain future solutions to be better than b.
Definition pbs.hpp:272
virtual Space * next(void)
Return next solution (NULL, if none exists or search has been stopped)
Definition pbs.hpp:210
virtual Statistics statistics(void) const
Return statistics.
Definition pbs.hpp:262
Stop object used for controling slaves in a portfolio.
Definition pbs.hh:42
void share(volatile bool *ts)
Set pointer to shared tostop variable.
Definition pbs.hpp:121
PortfolioStop(Stop *so)
Initialize.
Definition pbs.hpp:117
Runnable slave of a portfolio master.
Definition pbs.hh:67
virtual void run(void)
Perform one run.
Definition pbs.hpp:201
bool stopped(void) const
Check whether slave has been stopped.
Definition pbs.hpp:137
virtual ~Slave(void)
Delete slave.
Definition pbs.hpp:146
Statistics statistics(void) const
Return statistics of slave.
Definition pbs.hpp:132
Slave(PBS< Collect > *m, Engine *s, Stop *so)
Initialize with master m, slave s, and its stop object so.
Definition pbs.hpp:128
void constrain(const Space &b)
Constrain with better solution b.
Definition pbs.hpp:142
Search engine statistics
Definition search.hh:147
Base-class for Stop-object.
Definition search.hh:799
Computation spaces.
Definition core.hpp:1742
static void run(Runnable *r)
Construct a new thread and run r.
Definition thread.hpp:115
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:841
SpaceStatus status(StatusStatistics &stat=unused_status)
Query space status.
Definition core.cpp:252
Space * clone(CloneStatistics &stat=unused_clone) const
Clone space.
Definition core.hpp:3224
@ SS_FAILED
Space is failed
Definition core.hpp:1682
Gecode toplevel namespace
Post propagator for SetVar SetOpType SetVar SetRelType r
Definition set.hh:767
#define forceinline
Definition config.hpp:187