Generated on for Gecode by doxygen 1.17.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.dev>
5 *
6 * Contributing authors:
7 * Mikael Zayenz Lagerkvist <lagerkvist@gecode.dev>
8 *
9 * Copyright:
10 * Christian Schulte, 2009
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
38namespace Gecode { namespace Search { namespace Par {
39
40 /*
41 * Engine: basic access routines
42 */
43 template<class Tracer>
46 return static_cast<BAB&>(_engine);
47 }
48 template<class Tracer>
50 BAB<Tracer>::worker(unsigned int i) const {
51 return _worker[i];
52 }
53
54 template<class Tracer>
55 forceinline void
56 BAB<Tracer>::Worker::reset(Space* s, unsigned int ngdl) {
57 tracer.round();
58 delete cur;
59 delete best;
60 best = nullptr;
61 path.reset((s == nullptr) ? 0 : ngdl);
62 d = 0;
63 mark = 0;
64 idle = false;
65 // Reset the statistics first, so that a failed root is counted
67 if (s == nullptr) {
68 cur = nullptr;
69 } else if (s->status(*this) == SS_FAILED) {
70 fail++;
71 delete s;
72 cur = nullptr;
73 } else {
74 cur = s;
75 }
76 }
77
78 template<class Tracer>
79 forceinline bool
81 return (cur != nullptr) || !path.empty();
82 }
83
84
85 /*
86 * Engine: initialization
87 */
88 template<class Tracer>
90 BAB<Tracer>::Worker::Worker(Space* s, BAB& e, unsigned int index0)
91 : Engine<Tracer>::Worker(s,e), mark(0), best(nullptr), index(index0) {}
92
93 template<class Tracer>
96 : Engine<Tracer>(o), best(nullptr) {
98 workers());
99 // Create workers
100 _worker = static_cast<Worker**>
101 (heap.ralloc(workers() * sizeof(Worker*)));
102 // The first worker gets the entire search tree
103 _worker[0] = new Worker(s,*this,0U);
104 // All other workers start with no work
105 for (unsigned int i=1U; i<workers(); i++)
106 _worker[i] = new Worker(nullptr,*this,i);
107 this->scheduler_enable(_worker[0]->owns_work());
108 // Block all workers
109 block();
110 // Create and start threads
111 for (unsigned int i=0U; i<workers(); i++)
113 }
114
115
116 /*
117 * Engine: search control
118 */
119 template<class Tracer>
120 forceinline void
122 m.acquire();
123 delete best;
124 best = b->clone();
125 mark = path.entries();
126 if (cur != nullptr)
127 cur->constrain(*best);
128 m.release();
129 }
130 template<class Tracer>
131 forceinline void
133 m_search.acquire();
134 if (best != nullptr) {
135 s->constrain(*best);
136 if (s->status() == SS_FAILED) {
137 delete s;
138 m_search.release();
139 return;
140 } else {
141 delete best;
142 best = s->clone();
143 }
144 } else {
145 best = s->clone();
146 }
147 // Announce better solutions
148 for (unsigned int i=0U; i<workers(); i++)
149 worker(i)->better(best);
150 bool bs = signal();
151 solutions.push(s);
152 if (bs)
153 e_search.signal();
154 m_search.release();
155 }
156
157
158 /*
159 * Worker: finding and stealing working
160 */
161 template<class Tracer>
162 forceinline bool
164 // Try to find new work (even if there is none)
165 for (unsigned int i=0U; i<engine().workers(); i++) {
166 unsigned long int r_d = 0ul;
167 typename Engine<Tracer>::Worker* wi = engine().worker(i);
168 if (Space* s = wi->steal(r_d,wi->tracer,tracer)) {
169 // Reset this guy
170 m.acquire();
171 idle = false;
172 // Not idle but also does not have the root of the tree
173 path.ngdl(0);
174 d = 0;
175 cur = s;
176 mark = 0;
177 if (best != nullptr)
178 cur->constrain(*best);
179 Statistics t = *this;
181 (*this) += t;
182 m.release();
183 engine().scheduler_owner(index);
184 return true;
185 }
186 }
187 return false;
188 }
189
190 /*
191 * Statistics
192 */
193 template<class Tracer>
196 Statistics s;
197 for (unsigned int i=0U; i<workers(); i++)
198 s += worker(i)->statistics();
199 return s;
200 }
201
202 template<class Tracer>
203 void
205 m_search.acquire();
206 if (best != nullptr) {
207 best->constrain(b);
208 if (best->status() != SS_FAILED) {
209 m_search.release();
210 return;
211 }
212 delete best;
213 }
214 best = b.clone();
215 // Announce better solutions
216 for (unsigned int i=0U; i<workers(); i++)
217 worker(i)->better(best);
218 m_search.release();
219 }
220
221 /*
222 * Actual work
223 */
224 template<class Tracer>
225 void
227 /*
228 * The engine maintains the following invariant:
229 * - If the current space (cur) is not nullptr, the path always points
230 * to exactly that space.
231 * - If the current space (cur) is nullptr, the path always points
232 * to the next space (if there is any).
233 *
234 * This invariant is needed so that no-goods can be extracted properly
235 * when the engine is stopped or has found a solution.
236 *
237 * An additional invariant maintained by the engine is:
238 * For all nodes stored at a depth less than mark, there
239 * is no guarantee of betterness. For those above the mark,
240 * betterness is guaranteed.
241 *
242 */
243 // Perform initial delay, if not first worker
244 if (this != engine().worker(0))
246 // Okay, we are in business, start working
247 while (true) {
248 switch (engine().cmd()) {
249 case C_WAIT:
250 // Wait
251 engine().wait();
252 break;
253 case C_TERMINATE:
254 // Acknowledge termination request
255 engine().ack_terminate();
256 // Wait until termination can proceed
257 engine().wait_terminate();
258 // Thread will be terminated by returning from run
259 return;
260 case C_RESET:
261 // Acknowledge reset request
262 engine().ack_reset_start();
263 // Wait until reset has been performed
264 engine().wait_reset();
265 // Acknowledge that reset cycle is over
266 engine().ack_reset_stop();
267 break;
268 case C_WORK:
269 // Perform exploration work
270 {
271 const unsigned long long int run = engine().run();
272 if (engine().scheduler_paused()) {
273 start();
274 if (stop(engine().opt())) {
275 engine().stop(run);
276 break;
277 }
278 }
280 break;
281 m.acquire();
282 if (idle) {
283 m.release();
284 // Try to find new work
285 if (!find()) {
286 engine().scheduler_handoff(index,engine().work_remains());
287 }
288 } else if (cur != nullptr) {
289 start();
290 if (stop(engine().opt())) {
291 // Report stop
292 m.release();
293 engine().stop(run);
294 } else {
295 node++;
297 if (tracer) {
298 if (path.entries() > 0) {
299 typename Path<Tracer>::Edge& top = path.top();
300 ei.init(tracer.wid(), top.nid(), top.truealt(),
301 *cur, *top.choice());
302 } else if (*tracer.ei()) {
303 ei = *tracer.ei();
304 tracer.invalidate();
305 }
306 }
307 unsigned int nid = tracer.nid();
308 switch (cur->status(*this)) {
309 case SS_FAILED:
310 if (tracer) {
312 tracer.wid(), nid, *cur);
313 tracer.node(ei,ni);
314 }
315 fail++;
316 delete cur;
317 cur = nullptr;
318 path.next();
319 m.release();
320 break;
321 case SS_SOLVED:
322 {
323 if (tracer) {
325 tracer.wid(), nid, *cur);
326 tracer.node(ei,ni);
327 }
328 // Deletes all pending branchers
329 (void) cur->choice();
330 Space* s = cur->clone();
331 delete cur;
332 cur = nullptr;
333 path.next();
334 m.release();
335 engine().solution(s);
336 }
337 break;
338 case SS_BRANCH:
339 {
340 Space* c;
341 if ((d == 0) || (d >= engine().opt().c_d)) {
342 c = cur->clone();
343 d = 1;
344 } else {
345 c = nullptr;
346 d++;
347 }
348 const Choice* ch = path.push(*this,cur,c,nid);
349 if (tracer) {
351 tracer.wid(), nid, *cur, ch);
352 tracer.node(ei,ni);
353 }
354 cur->commit(*ch,0);
355 m.release();
356 }
357 break;
358 default:
360 }
361 }
362 } else if (!path.empty()) {
363 cur = path.recompute(d,engine().opt().a_d,*this,best,mark,tracer);
364 if (cur == nullptr)
365 path.next();
366 m.release();
367 } else {
368 idle = true;
369 path.ngdl(0);
370 m.release();
371 // Report that worker is idle
372 engine().idle();
373 engine().scheduler_idle(index);
374 engine().scheduler_handoff(index,engine().work_remains());
375 }
376 }
377 break;
378 default:
380 }
381 }
382 }
383
384
385 /*
386 * Perform reset
387 *
388 */
389 template<class Tracer>
390 void
392 // Grab wait lock for reset
393 m_wait_reset.acquire();
394 // Release workers for reset
396 // Wait for reset cycle started
397 e_reset_ack_start.wait();
398 // All workers are marked as busy again
399 delete best;
400 best = nullptr;
401 n_busy = workers();
402 for (unsigned int i=1U; i<workers(); i++)
403 worker(i)->reset(nullptr,0);
404 worker(0)->reset(s,opt().nogoods_limit);
405 // Block workers again to ensure invariant
406 block();
407 // Release reset lock
408 m_wait_reset.release();
409 // Wait for reset cycle stopped
410 e_reset_ack_stop.wait();
411 this->scheduler_reset(worker(0U)->owns_work());
412 }
413
414
415 /*
416 * Create no-goods
417 *
418 */
419 template<class Tracer>
420 NoGoods&
422 NoGoods* ng;
423 // Grab wait lock for reset
424 m_wait_reset.acquire();
425 // Release workers for reset
427 // Wait for reset cycle started
428 e_reset_ack_start.wait();
429 ng = &worker(0)->nogoods();
430 // Block workers again to ensure invariant
431 block();
432 // Release reset lock
433 m_wait_reset.release();
434 // Wait for reset cycle stopped
435 e_reset_ack_stop.wait();
436 return *ng;
437 }
438
439 /*
440 * Termination and deletion
441 */
442 template<class Tracer>
444 delete best;
445 }
446
447 template<class Tracer>
449 terminate();
450 delete best;
451 heap.rfree(_worker);
452 }
453
454}}}
455
456// STATISTICS: search-par
Choice for performing commit
Definition core.hpp:1430
No-goods recorded from restarts.
Definition core.hpp:1606
void init(unsigned int wid, unsigned int nid, unsigned int a)
Initialize.
Definition tracer.hpp:107
@ FAILED
A solution node.
Definition search.hh:286
@ BRANCH
A failed node.
Definition search.hh:287
@ DFS
Engine is a DFS engine.
Definition search.hh:202
Search engine options
Definition search.hh:848
SearchTracer * tracer
Tracer object for tracing search.
Definition search.hh:879
Parallel branch-and-bound search worker
Definition bab.hh:66
bool find(void)
Try to find some work.
Definition bab.hpp:163
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
Worker(Space *s, BAB &e, unsigned int index)
Initialize for space s with engine e.
Definition bab.hpp:90
void better(Space *b)
Accept better solution b.
Definition bab.hpp:121
BAB & engine(void) const
Provide access to engine.
Definition bab.hpp:45
bool owns_work(void) const
Whether this worker currently owns local search.
Definition bab.hpp:80
virtual ~Worker(void)
Destructor.
Definition bab.hpp:443
virtual void run(void)
Start execution of worker.
Definition bab.hpp:226
unsigned int index
Fixed worker index.
Definition bab.hh:84
void reset(Space *s, unsigned int ngdl)
Reset engine to restart at space s.
Definition bab.hpp:56
Parallel branch-and-bound engine
Definition bab.hh:43
Worker ** _worker
Array of worker references.
Definition bab.hh:104
void solution(Space *s)
Report solution s.
Definition bab.hpp:132
Worker * worker(unsigned int i) const
Provide access to worker i.
Definition bab.hpp:50
virtual void constrain(const Space &b)
Constrain future solutions to be better than b.
Definition bab.hpp:204
virtual void reset(Space *s)
Reset engine to restart at space s.
Definition bab.hpp:391
virtual ~BAB(void)
Destructor.
Definition bab.hpp:448
Space * best
Best solution so far.
Definition bab.hh:106
BAB(Space *s, const Options &o)
Initialize for space s with options o.
Definition bab.hpp:95
virtual Statistics statistics(void) const
Return statistics.
Definition bab.hpp:195
virtual NoGoods & nogoods(void)
Constrain Return no-goods.
Definition bab.hpp:421
Parallel depth-first search worker
Definition engine.hh:55
Support::Mutex m
Mutex for access to worker.
Definition engine.hh:63
Engine & _engine
Reference to engine.
Definition engine.hh:61
NoGoods & nogoods(void)
Return no-goods.
Definition engine.hpp:514
Statistics statistics(void)
Return statistics.
Definition engine.hpp:339
Space * cur
Current space being explored.
Definition engine.hh:67
Tracer tracer
Search tracer.
Definition engine.hh:58
Space * steal(unsigned long int &d, Tracer &myt, Tracer &ot)
Hand over some work (nullptr if no work available).
Definition engine.hpp:492
unsigned int d
Distance until next clone.
Definition engine.hh:69
bool idle
Whether the worker is idle.
Definition engine.hh:71
Path< Tracer > path
Current path ins search tree.
Definition engine.hh:65
const Options & opt(void) const
Provide access to search options.
Definition engine.hpp:51
Support::Event e_reset_ack_stop
Event for reset acknowledgment stopped.
Definition engine.hh:220
Support::Event e_search
Event for search (solution found, no more solutions, search stopped).
Definition engine.hh:238
Support::DynamicQueue< Space *, Heap > solutions
Queue of solutions.
Definition engine.hh:240
void block(void)
Block all workers.
Definition engine.hpp:77
Support::Mutex m_wait_reset
Mutex for waiting for reset.
Definition engine.hh:222
void scheduler_enable(bool root_owner)
Enable adjustable parallel admission.
Definition engine.hpp:183
Support::Mutex m_search
Mutex for search.
Definition engine.hh:236
Support::Event e_reset_ack_start
Event for reset acknowledgment started.
Definition engine.hh:218
Cmd cmd(void) const
Return current command.
Definition engine.hpp:72
Engine(const Options &o)
Initialize with options o.
Definition engine.hpp:123
bool scheduler_admit(unsigned int worker)
Admit worker worker for one exploration action.
Definition engine.hpp:230
void release(Cmd c)
Release all workers.
Definition engine.hpp:83
bool signal(void) const
Whether search state changed such that signal is needed.
Definition engine.hpp:352
void stop(unsigned long long int r)
Report that a worker was stopped during call r of next().
Definition engine.hpp:384
void scheduler_reset(bool root_owner)
Reset adjustable parallel state while all workers are blocked.
Definition engine.hpp:207
bool scheduler_paused(void) const
Whether the external worker request currently pauses the engine.
Definition engine.hpp:278
void terminate(void)
For engine to perform thread termination.
Definition engine.hpp:443
volatile unsigned int n_busy
Number of busy workers.
Definition engine.hh:242
unsigned int workers(void) const
Return number of workers.
Definition engine.hpp:56
@ C_WORK
Perform work.
Definition engine.hh:163
@ C_RESET
Perform reset operation.
Definition engine.hh:165
@ C_WAIT
Run into wait lock.
Definition engine.hh:164
bool work_remains(void)
Whether logical search work remains.
Definition engine.hpp:401
Search tree edge for recomputation
Definition path.hh:70
unsigned int truealt(void) const
Return true number for alternatives (excluding lao optimization).
Definition path.hpp:80
unsigned int nid(void) const
Return node identifier.
Definition path.hpp:74
const Choice * choice(void) const
Return choice.
Definition path.hpp:112
Search engine statistics
Definition search.hh:155
Statistics(void)
Initialize.
unsigned long long int fail
Number of failed nodes in search tree.
Definition search.hh:158
unsigned long long int node
Number of nodes expanded.
Definition search.hh:160
void start(void)
Reset stop information.
Definition worker.hh:76
Worker(void)
Initialize.
Definition worker.hh:72
static void engine(SearchTracer *tracer, SearchTracer::EngineType t, unsigned int n)
Register engine.
Computation spaces.
Definition core.hpp:1787
void reset(void)
Reset information.
Definition core.hpp:4974
static void run(Runnable *r)
Construct a new thread and run r.
Definition thread.hpp:177
static void sleep(unsigned int ms)
Put current thread to sleep for ms milliseconds.
Definition thread.hpp:156
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_BRANCH
Space must be branched (at least one brancher left)
Definition core.hpp:1729
@ SS_SOLVED
Space is solved (no brancher left)
Definition core.hpp:1728
@ SS_FAILED
Space is failed
Definition core.hpp:1727
const unsigned int initial_delay
Initial delay in milliseconds for all but first worker thread.
Definition search.hh:128
Search engines
Gecode toplevel namespace
#define forceinline
Definition config.hpp:144
#define GECODE_NEVER
Assert that this command is never executed.
Definition macros.hpp:56