Generated on Tue Feb 11 2025 17:33:26 for Gecode by doxygen 1.12.0
bab.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, 2009
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
34namespace Gecode { namespace Search { namespace Par {
35
36 /*
37 * Engine: basic access routines
38 */
39 template<class Tracer>
40 forceinline BAB<Tracer>&
42 return static_cast<BAB&>(_engine);
43 }
44 template<class Tracer>
46 BAB<Tracer>::worker(unsigned int i) const {
47 return _worker[i];
48 }
49
50 template<class Tracer>
51 forceinline void
52 BAB<Tracer>::Worker::reset(Space* s, unsigned int ngdl) {
53 tracer.round();
54 delete cur;
55 delete best;
56 best = NULL;
57 path.reset((s == NULL) ? 0 : ngdl);
58 d = 0;
59 mark = 0;
60 idle = false;
61 if ((s == NULL) || (s->status(*this) == SS_FAILED)) {
62 delete s;
63 cur = NULL;
64 } else {
65 cur = s;
66 }
68 }
69
70
71 /*
72 * Engine: initialization
73 */
74 template<class Tracer>
77 : Engine<Tracer>::Worker(s,e), mark(0), best(NULL) {}
78
79 template<class Tracer>
82 : Engine<Tracer>(o), best(NULL) {
84 workers());
85 // Create workers
86 _worker = static_cast<Worker**>
87 (heap.ralloc(workers() * sizeof(Worker*)));
88 // The first worker gets the entire search tree
89 _worker[0] = new Worker(s,*this);
90 // All other workers start with no work
91 for (unsigned int i=1U; i<workers(); i++)
92 _worker[i] = new Worker(NULL,*this);
93 // Block all workers
94 block();
95 // Create and start threads
96 for (unsigned int i=0U; i<workers(); i++)
98 }
99
100
101 /*
102 * Engine: search control
103 */
104 template<class Tracer>
105 forceinline void
107 m.acquire();
108 delete best;
109 best = b->clone();
110 mark = path.entries();
111 if (cur != NULL)
112 cur->constrain(*best);
113 m.release();
114 }
115 template<class Tracer>
116 forceinline void
119 if (best != NULL) {
120 s->constrain(*best);
121 if (s->status() == SS_FAILED) {
122 delete s;
124 return;
125 } else {
126 delete best;
127 best = s->clone();
128 }
129 } else {
130 best = s->clone();
131 }
132 // Announce better solutions
133 for (unsigned int i=0U; i<workers(); i++)
134 worker(i)->better(best);
135 bool bs = signal();
136 solutions.push(s);
137 if (bs)
140 }
141
142
143 /*
144 * Worker: finding and stealing working
145 */
146 template<class Tracer>
147 forceinline void
149 // Try to find new work (even if there is none)
150 for (unsigned int i=0U; i<engine().workers(); i++) {
151 unsigned long int r_d = 0ul;
152 typename Engine<Tracer>::Worker* wi = engine().worker(i);
153 if (Space* s = wi->steal(r_d,wi->tracer,tracer)) {
154 // Reset this guy
155 m.acquire();
156 idle = false;
157 // Not idle but also does not have the root of the tree
158 path.ngdl(0);
159 d = 0;
160 cur = s;
161 mark = 0;
162 if (best != NULL)
163 cur->constrain(*best);
164 Statistics t = *this;
166 (*this) += t;
167 m.release();
168 return;
169 }
170 }
171 }
172
173 /*
174 * Statistics
175 */
176 template<class Tracer>
179 Statistics s;
180 for (unsigned int i=0U; i<workers(); i++)
181 s += worker(i)->statistics();
182 return s;
183 }
184
185 template<class Tracer>
186 void
189 if (best != NULL) {
190 best->constrain(b);
191 if (best->status() != SS_FAILED) {
193 return;
194 }
195 delete best;
196 }
197 best = b.clone();
198 // Announce better solutions
199 for (unsigned int i=0U; i<workers(); i++)
200 worker(i)->better(best);
202 }
203
204 /*
205 * Actual work
206 */
207 template<class Tracer>
208 void
210 /*
211 * The engine maintains the following invariant:
212 * - If the current space (cur) is not NULL, the path always points
213 * to exactly that space.
214 * - If the current space (cur) is NULL, the path always points
215 * to the next space (if there is any).
216 *
217 * This invariant is needed so that no-goods can be extracted properly
218 * when the engine is stopped or has found a solution.
219 *
220 * An additional invariant maintained by the engine is:
221 * For all nodes stored at a depth less than mark, there
222 * is no guarantee of betterness. For those above the mark,
223 * betterness is guaranteed.
224 *
225 */
226 // Peform initial delay, if not first worker
227 if (this != engine().worker(0))
229 // Okay, we are in business, start working
230 while (true) {
231 switch (engine().cmd()) {
232 case C_WAIT:
233 // Wait
234 engine().wait();
235 break;
236 case C_TERMINATE:
237 // Acknowledge termination request
238 engine().ack_terminate();
239 // Wait until termination can proceed
240 engine().wait_terminate();
241 // Thread will be terminated by returning from run
242 return;
243 case C_RESET:
244 // Acknowledge reset request
245 engine().ack_reset_start();
246 // Wait until reset has been performed
247 engine().wait_reset();
248 // Acknowledge that reset cycle is over
249 engine().ack_reset_stop();
250 break;
251 case C_WORK:
252 // Perform exploration work
253 {
254 m.acquire();
255 if (idle) {
256 m.release();
257 // Try to find new work
258 find();
259 } else if (cur != NULL) {
260 start();
261 if (stop(engine().opt())) {
262 // Report stop
263 m.release();
264 engine().stop();
265 } else {
266 node++;
268 if (tracer) {
269 if (path.entries() > 0) {
270 typename Path<Tracer>::Edge& top = path.top();
271 ei.init(tracer.wid(), top.nid(), top.truealt(),
272 *cur, *top.choice());
273 } else if (*tracer.ei()) {
274 ei = *tracer.ei();
275 tracer.invalidate();
276 }
277 }
278 unsigned int nid = tracer.nid();
279 switch (cur->status(*this)) {
280 case SS_FAILED:
281 if (tracer) {
283 tracer.wid(), nid, *cur);
284 tracer.node(ei,ni);
285 }
286 fail++;
287 delete cur;
288 cur = NULL;
289 path.next();
290 m.release();
291 break;
292 case SS_SOLVED:
293 {
294 if (tracer) {
296 tracer.wid(), nid, *cur);
297 tracer.node(ei,ni);
298 }
299 // Deletes all pending branchers
300 (void) cur->choice();
301 Space* s = cur->clone();
302 delete cur;
303 cur = NULL;
304 path.next();
305 m.release();
306 engine().solution(s);
307 }
308 break;
309 case SS_BRANCH:
310 {
311 Space* c;
312 if ((d == 0) || (d >= engine().opt().c_d)) {
313 c = cur->clone();
314 d = 1;
315 } else {
316 c = NULL;
317 d++;
318 }
319 const Choice* ch = path.push(*this,cur,c,nid);
320 if (tracer) {
322 tracer.wid(), nid, *cur, ch);
323 tracer.node(ei,ni);
324 }
325 cur->commit(*ch,0);
326 m.release();
327 }
328 break;
329 default:
331 }
332 }
333 } else if (!path.empty()) {
334 cur = path.recompute(d,engine().opt().a_d,*this,*best,mark,tracer);
335 if (cur == NULL)
336 path.next();
337 m.release();
338 } else {
339 idle = true;
340 path.ngdl(0);
341 m.release();
342 // Report that worker is idle
343 engine().idle();
344 }
345 }
346 break;
347 default:
349 }
350 }
351 }
352
353
354 /*
355 * Perform reset
356 *
357 */
358 template<class Tracer>
359 void
361 // Grab wait lock for reset
363 // Release workers for reset
365 // Wait for reset cycle started
367 // All workers are marked as busy again
368 delete best;
369 best = NULL;
370 n_busy = workers();
371 for (unsigned int i=1U; i<workers(); i++)
372 worker(i)->reset(NULL,0);
373 worker(0)->reset(s,opt().nogoods_limit);
374 // Block workers again to ensure invariant
375 block();
376 // Release reset lock
378 // Wait for reset cycle stopped
380 }
381
382
383 /*
384 * Create no-goods
385 *
386 */
387 template<class Tracer>
388 NoGoods&
390 NoGoods* ng;
391 // Grab wait lock for reset
393 // Release workers for reset
395 // Wait for reset cycle started
397 ng = &worker(0)->nogoods();
398 // Block workers again to ensure invariant
399 block();
400 // Release reset lock
402 // Wait for reset cycle stopped
404 return *ng;
405 }
406
407 /*
408 * Termination and deletion
409 */
410 template<class Tracer>
412 delete best;
413 }
414
415 template<class Tracer>
417 terminate();
418 delete best;
420 }
421
422}}}
423
424// STATISTICS: search-par
struct Gecode::@603::NNF::@65::@66 b
For binary nodes (and, or, eqv)
NodeType t
Type of node.
Choice for performing commit
Definition core.hpp:1412
void rfree(void *p)
Free memory block starting at p.
Definition heap.hpp:371
void * ralloc(size_t s)
Allocate s bytes from heap.
Definition heap.hpp:357
No-goods recorded from restarts.
Definition core.hpp:1588
void invalidate(void)
Invalidate edge information (for stealing)
Definition tracer.hpp:102
void init(unsigned int wid, unsigned int nid, unsigned int a)
Initialize.
Definition tracer.hpp:107
unsigned int nid(void) const
Return parent node id.
Definition tracer.hpp:142
@ FAILED
A solution node.
Definition search.hh:278
@ BRANCH
A failed node.
Definition search.hh:279
@ DFS
Engine is a DFS engine.
Definition search.hh:194
Search engine options
Definition search.hh:746
SearchTracer * tracer
Tracer object for tracing search.
Definition search.hh:769
Parallel branch-and-bound search worker
Definition bab.hh:66
void find(void)
Try to find some work.
Definition bab.hpp:148
Space * best
Best solution found so far.
Definition bab.hh:82
int mark
Number of entries not yet constrained to be better.
Definition bab.hh:80
void better(Space *b)
Accept better solution b.
Definition bab.hpp:106
BAB & engine(void) const
Provide access to engine.
Definition bab.hpp:41
virtual ~Worker(void)
Destructor.
Definition bab.hpp:411
virtual void run(void)
Start execution of worker.
Definition bab.hpp:209
void reset(Space *s, unsigned int ngdl)
Reset engine to restart at space s.
Definition bab.hpp:52
Parallel branch-and-bound engine
Definition bab.hh:43
Worker ** _worker
Array of worker references.
Definition bab.hh:100
void solution(Space *s)
Report solution s.
Definition bab.hpp:117
Worker * worker(unsigned int i) const
Provide access to worker i.
Definition bab.hpp:46
virtual void constrain(const Space &b)
Constrain future solutions to be better than b.
Definition bab.hpp:187
virtual void reset(Space *s)
Reset engine to restart at space s.
Definition bab.hpp:360
virtual ~BAB(void)
Destructor.
Definition bab.hpp:416
Space * best
Best solution so far.
Definition bab.hh:102
BAB(Space *s, const Options &o)
Initialize for space s with options o.
Definition bab.hpp:81
virtual Statistics statistics(void) const
Return statistics.
Definition bab.hpp:178
virtual NoGoods & nogoods(void)
Constrain Return no-goods.
Definition bab.hpp:389
Parallel depth-first search worker
Definition engine.hh:49
Support::Mutex m
Mutex for access to worker.
Definition engine.hh:57
Engine & _engine
Reference to engine.
Definition engine.hh:55
NoGoods & nogoods(void)
Return no-goods.
Definition engine.hpp:289
Statistics statistics(void)
Return statistics.
Definition engine.hpp:134
Space * cur
Current space being explored.
Definition engine.hh:61
Tracer tracer
Search tracer.
Definition engine.hh:52
Space * steal(unsigned long int &d, Tracer &myt, Tracer &ot)
Hand over some work (NULL if no work available)
Definition engine.hpp:265
Path< Tracer > path
Current path ins search tree.
Definition engine.hh:59
Parallel depth-first search engine
Definition engine.hh:46
void idle(void)
Report that worker is idle.
Definition engine.hpp:152
const Options & opt(void) const
Provide access to search options.
Definition engine.hpp:47
Support::Event e_reset_ack_stop
Event for reset acknowledgment stopped.
Definition engine.hh:151
Support::Event e_search
Event for search (solution found, no more solutions, search stopped)
Definition engine.hh:169
Support::DynamicQueue< Space *, Heap > solutions
Queue of solutions.
Definition engine.hh:171
void stop(void)
Report that worker has been stopped.
Definition engine.hpp:172
void block(void)
Block all workers.
Definition engine.hpp:73
Support::Mutex m_wait_reset
Mutex for waiting for reset.
Definition engine.hh:153
Support::Mutex m_search
Mutex for search.
Definition engine.hh:167
Support::Event e_reset_ack_start
Event for reset acknowledgment started.
Definition engine.hh:149
Cmd cmd(void) const
Return current command.
Definition engine.hpp:68
void release(Cmd c)
Release all workers.
Definition engine.hpp:79
bool signal(void) const
Whether search state changed such that signal is needed.
Definition engine.hpp:147
void terminate(void)
For engine to peform thread termination.
Definition engine.hpp:216
volatile unsigned int n_busy
Number of busy workers.
Definition engine.hh:173
unsigned int workers(void) const
Return number of workers.
Definition engine.hpp:52
@ C_WORK
Perform work.
Definition engine.hh:94
@ C_RESET
Perform reset operation.
Definition engine.hh:96
@ C_WAIT
Run into wait lock.
Definition engine.hh:95
Search tree edge for recomputation
Definition path.hh:66
unsigned int truealt(void) const
Return true number for alternatives (excluding lao optimization)
Definition path.hpp:76
unsigned int nid(void) const
Return node identifier.
Definition path.hpp:70
const Choice * choice(void) const
Return choice.
Definition path.hpp:108
Search engine statistics
Definition search.hh:147
Worker(void)
Initialize.
Definition worker.hh:70
static void engine(SearchTracer *tracer, SearchTracer::EngineType t, unsigned int n)
Register engine.
Computation spaces.
Definition core.hpp:1742
void reset(void)
Reset information.
Definition core.hpp:4690
void wait(void)
Wait until the event becomes signalled.
Definition none.hpp:61
void signal(void)
Signal the event.
Definition none.hpp:59
void release(void)
Release the mutex.
Definition none.hpp:48
void acquire(void)
Acquire the mutex and possibly block.
Definition none.hpp:42
static void run(Runnable *r)
Construct a new thread and run r.
Definition thread.hpp:115
static void sleep(unsigned int ms)
Put current thread to sleep for ms milliseconds.
Definition none.hpp:74
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_BRANCH
Space must be branched (at least one brancher left)
Definition core.hpp:1684
@ SS_SOLVED
Space is solved (no brancher left)
Definition core.hpp:1683
@ SS_FAILED
Space is failed
Definition core.hpp:1682
const unsigned int initial_delay
Initial delay in milliseconds for all but first worker thread.
Definition search.hh:120
Gecode toplevel namespace
void path(Home home, const IntVarArgs &x, IntVar s, IntVar e, IntPropLevel ipl=IPL_DEF)
Post propagator such that x forms a Hamiltonian path.
Definition circuit.cpp:169
#define forceinline
Definition config.hpp:187
#define GECODE_NEVER
Assert that this command is never executed.
Definition macros.hpp:56