Generated on for Gecode by doxygen 1.17.0
engine.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 /*
42 * Basic access routines
43 */
44 template<class Tracer>
47 return _engine;
48 }
49 template<class Tracer>
50 forceinline const Options&
51 Engine<Tracer>::opt(void) const {
52 return _opt;
53 }
54 template<class Tracer>
55 forceinline unsigned int
57 return static_cast<unsigned int>(opt().threads);
58 }
59 template<class Tracer>
60 forceinline bool
62 return has_stopped.load(std::memory_order_acquire);
63 }
64
65
66
67 /*
68 * Engine: command and wait handling
69 */
70 template<class Tracer>
72 Engine<Tracer>::cmd(void) const {
73 return _cmd.load(std::memory_order_acquire);
74 }
75 template<class Tracer>
76 forceinline void
78 _cmd.store(C_WAIT, std::memory_order_release);
80 }
81 template<class Tracer>
82 forceinline void
84 _cmd.store(c, std::memory_order_release);
85 if (scheduler_enabled && ((c == C_WORK) || (c == C_RESET) ||
86 (c == C_TERMINATE)))
89 }
90 template<class Tracer>
91 forceinline void
93 _m_wait.acquire(); _m_wait.release();
94 }
95
96
97 /*
98 * Engine: initialization
99 */
100 template<class Tracer>
103 : tracer(e.opt().tracer), _engine(e),
104 path(s == nullptr ? 0 : e.opt().nogoods_limit), d(0),
105 idle(false) {
106 tracer.worker();
107 if (s != nullptr) {
108 if (s->status(*this) == SS_FAILED) {
109 fail++;
110 cur = nullptr;
111 if (!engine().opt().clone)
112 delete s;
113 } else {
114 cur = snapshot(s,engine().opt());
115 }
116 } else {
117 cur = nullptr;
118 }
119 }
120
121 template<class Tracer>
124 : Search::Engine(o,static_cast<unsigned int>(o.threads)),
125 _opt(o), scheduler_enabled(false),
126 scheduler_fast_admit(nullptr),
130 // Initialize termination information
133 // Initialize search information
134 n_busy = workers();
135 has_stopped.store(false, std::memory_order_release);
136 n_runs.store(0ULL, std::memory_order_release);
137 // Initialize reset information
139 }
140
141 template<class Tracer>
142 unsigned int
144 unsigned int exclude) const {
145 for (unsigned int offset=0U; offset<workers(); offset++) {
146 unsigned int i = (scheduler_cursor + offset) % workers();
147 if ((i != exclude) && !scheduler_worker[i].lease &&
148 scheduler_worker[i].parked &&
149 (scheduler_worker[i].logical == logical))
150 return i;
151 }
152 return workers();
153 }
154
155 template<class Tracer>
156 bool
158 bool wake = false;
161 if (i == workers())
163 if (i == workers())
165 if (i == workers()) {
166 for (i=0U; i<workers(); i++)
167 if (!scheduler_worker[i].lease)
168 break;
169 }
170 if (i == workers())
171 break;
172 scheduler_worker[i].lease = true;
173 scheduler_worker[i].parked = false;
175 scheduler_cursor = (i+1U) % workers();
176 wake = true;
177 }
178 return wake;
179 }
180
181 template<class Tracer>
182 void
184 if (!worker_control.engaged())
185 return;
188 scheduler_worker = static_cast<SchedulerWorker*>
189 (heap.ralloc(workers() * sizeof(SchedulerWorker)));
190 unsigned long long int generation;
194 for (unsigned int i=0U; i<workers(); i++) {
196 scheduler_worker[i].parked = false;
197 scheduler_worker[i].logical =
198 ((i == 0U) && root_owner) ?
200 }
201 scheduler_generation.store(generation,std::memory_order_release);
202 scheduler_enabled = true;
203 }
204
205 template<class Tracer>
206 void
209 return;
210 unsigned int requested;
211 unsigned long long int generation;
212 WorkerControlAccess::snapshot(worker_control,requested,generation);
213 scheduler_mutex.acquire();
214 scheduler_requested = requested;
216 scheduler_cursor = 0U;
217 for (unsigned int i=0U; i<workers(); i++) {
219 scheduler_worker[i].parked = false;
220 scheduler_worker[i].logical =
221 ((i == 0U) && root_owner) ?
223 }
224 scheduler_generation.store(generation,std::memory_order_release);
225 scheduler_mutex.release();
226 }
227
228 template<class Tracer>
229 bool
230 Engine<Tracer>::scheduler_admit(unsigned int worker) {
232 return true;
233 if (scheduler_fast_admit->load(std::memory_order_acquire))
234 return true;
235 if (cmd() == C_WORK) {
236 unsigned long long int generation =
238 if ((generation ==
239 scheduler_generation.load(std::memory_order_acquire)) &&
241 return true;
242
243 bool wake;
244 bool admitted;
245 unsigned int requested;
246 WorkerControlAccess::snapshot(worker_control,requested,generation);
247 scheduler_mutex.acquire();
248 if (generation >
249 scheduler_generation.load(std::memory_order_relaxed)) {
250 scheduler_requested = requested;
251 scheduler_generation.store(generation,std::memory_order_release);
252 }
253 wake = scheduler_grow();
254 if (scheduler_worker[worker].lease &&
256 scheduler_worker[worker].lease = false;
258 }
259 admitted = scheduler_worker[worker].lease;
260 scheduler_worker[worker].parked = !admitted;
261 scheduler_mutex.release();
262
263 if (requested == workers())
265 if (wake)
267 if (admitted)
268 return true;
270 // Re-enter the worker loop to observe a stop or command change.
271 return false;
272 }
273 return false;
274 }
275
276 template<class Tracer>
277 forceinline bool
282
283 template<class Tracer>
284 void
285 Engine<Tracer>::scheduler_owner(unsigned int worker) {
287 return;
288 scheduler_mutex.acquire();
290 scheduler_mutex.release();
291 }
292
293 template<class Tracer>
294 void
295 Engine<Tracer>::scheduler_idle(unsigned int worker) {
297 return;
298 scheduler_mutex.acquire();
300 scheduler_mutex.release();
301 }
302
303 template<class Tracer>
304 void
306 bool work_remains) {
308 return;
309 unsigned int target = workers();
310 scheduler_mutex.acquire();
311 if (scheduler_worker[worker].lease) {
313 scheduler_worker[worker].lease = false;
314 scheduler_worker[worker].parked = true;
316 } else if (work_remains) {
318 if (target == workers())
320 if (target != workers()) {
321 scheduler_worker[worker].lease = false;
322 scheduler_worker[worker].parked = true;
323 scheduler_worker[target].lease = true;
324 scheduler_worker[target].parked = false;
325 scheduler_cursor = (target+1U) % workers();
326 }
327 }
328 }
329 scheduler_mutex.release();
330 if (target != workers())
332 }
333
334 /*
335 * Statistics
336 */
337 template<class Tracer>
340 m.acquire();
341 Statistics s = *this;
342 m.release();
343 return s;
344 }
345
346
347 /*
348 * Engine: search control
349 */
350 template<class Tracer>
351 forceinline bool
353 return solutions.empty() && (n_busy > 0) &&
354 !has_stopped.load(std::memory_order_acquire);
355 }
356 template<class Tracer>
357 forceinline void
359 m_search.acquire();
360 bool bs = signal();
361 n_busy--;
362 if (bs && (n_busy == 0))
363 e_search.signal();
364 m_search.release();
365 }
366
367 template<class Tracer>
368 forceinline void
370 m_search.acquire();
371 assert(n_busy > 0);
372 n_busy++;
373 m_search.release();
374 }
375
376 template<class Tracer>
377 forceinline unsigned long long int
379 return n_runs.load(std::memory_order_acquire);
380 }
381
382 template<class Tracer>
383 forceinline void
384 Engine<Tracer>::stop(unsigned long long int r) {
385 m_search.acquire();
386 // A worker can decide to stop during one call of next() and report it
387 // during a later one, for example after a portfolio cleared its stop.
388 if (r != n_runs.load(std::memory_order_relaxed)) {
389 m_search.release();
390 return;
391 }
392 bool bs = signal();
393 has_stopped.store(true, std::memory_order_release);
394 if (bs)
395 e_search.signal();
396 m_search.release();
397 }
398
399 template<class Tracer>
400 forceinline bool
402 m_search.acquire();
403 bool remains = n_busy > 0;
404 m_search.release();
405 return remains;
406 }
407
408
409 /*
410 * Engine: termination control
411 */
412 template<class Tracer>
413 forceinline void
415 unsigned int n;
416 _m_term.acquire();
417 n = --_n_not_terminated;
418 _m_term.release();
419 // The signal must be outside of the look, otherwise a thread might be
420 // terminated that still holds a mutex.
421 if (n == 0)
422 _e_terminate.signal();
423 }
424
425 template<class Tracer>
426 forceinline void
428 _m_term.acquire();
429 if (--_n_term_not_ack == 0)
430 _e_term_ack.signal();
431 _m_term.release();
432 }
433
434 template<class Tracer>
435 forceinline void
437 _m_wait_terminate.acquire();
438 _m_wait_terminate.release();
439 }
440
441 template<class Tracer>
442 forceinline void
444 // Grab the wait mutex for termination
445 _m_wait_terminate.acquire();
446 // Release all threads
448 // Wait until all threads have acknowledged termination request
449 _e_term_ack.wait();
450 // Release waiting threads
451 _m_wait_terminate.release();
452 // Wait until all threads have in fact terminated
453 _e_terminate.wait();
454 // Now all threads are terminated!
455 }
456
457 /*
458 * Engine: reset control
459 */
460 template<class Tracer>
461 forceinline void
463 _m_reset.acquire();
464 if (--_n_reset_not_ack == 0)
465 e_reset_ack_start.signal();
466 _m_reset.release();
467 }
468
469 template<class Tracer>
470 forceinline void
472 _m_reset.acquire();
473 if (++_n_reset_not_ack == workers())
474 e_reset_ack_stop.signal();
475 _m_reset.release();
476 }
477
478 template<class Tracer>
479 forceinline void
481 m_wait_reset.acquire();
482 m_wait_reset.release();
483 }
484
485
486
487 /*
488 * Worker: finding and stealing working
489 */
490 template<class Tracer>
492 Engine<Tracer>::Worker::steal(unsigned long int& d,
493 Tracer& myt, Tracer& ot) {
494 /*
495 * Make a quick check whether the worker might have work
496 *
497 * If that is not true any longer, the worker will be asked
498 * again eventually.
499 */
500 m.acquire();
501 Space* s = path.steal() ? path.steal(*this,d,myt,ot) : nullptr;
502 m.release();
503 // Tell that there will be one more busy worker
504 if (s != nullptr)
505 engine().busy();
506 return s;
507 }
508
509 /*
510 * Return No-Goods
511 */
512 template<class Tracer>
515 return path;
516 }
517
518 /*
519 * Engine: search control
520 */
521 template<class Tracer>
522 Space*
524 // Invariant: the worker holds the wait mutex
525 m_search.acquire();
526 if (!solutions.empty()) {
527 // No search needs to be done, take leftover solution
528 Space* s = solutions.pop();
529 m_search.release();
530 return s;
531 }
532 // We ignore stopped (it will be reported again if needed)
533 has_stopped.store(false, std::memory_order_release);
534 // No more solutions?
535 if (n_busy == 0) {
536 m_search.release();
537 return nullptr;
538 }
539 n_runs.fetch_add(1ULL, std::memory_order_acq_rel);
540 m_search.release();
541 // Okay, now search has to continue, make the guys work
543
544 /*
545 * Wait until a search related event has happened. It might be that
546 * the event has already been signalled in the last run, but the
547 * solution has been removed. So we have to try until there has
548 * something new happened.
549 */
550 while (true) {
551 e_search.wait();
552 m_search.acquire();
553 if (!solutions.empty()) {
554 // Report solution
555 Space* s = solutions.pop();
556 m_search.release();
557 // Make workers wait again
558 block();
559 return s;
560 }
561 // No more solutions or stopped?
562 if ((n_busy == 0) || has_stopped.load(std::memory_order_acquire)) {
563 m_search.release();
564 // Make workers wait again
565 block();
566 return nullptr;
567 }
568 m_search.release();
569 }
571 return nullptr;
572 }
573
574 template<class Tracer>
577 return &_engine;
578 }
579
580 /*
581 * Termination and deletion
582 */
583 template<class Tracer>
585 delete cur;
586 path.reset(0);
587 tracer.done();
588 }
589
590 /*
591 * Destructor
592 */
593 template<class Tracer>
595 while (!solutions.empty())
596 delete solutions.pop();
597 if (scheduler_worker != nullptr)
598 heap.rfree(scheduler_worker);
599 }
600
601}}}
602
603// STATISTICS: search-par
No-goods recorded from restarts.
Definition core.hpp:1606
Engine(void)
Construct a meta engine without worker control.
Definition engine.cpp:39
WorkerControl worker_control
Control retained for the lifetime of a leaf engine.
Definition search.hh:1066
Search engine options
Definition search.hh:848
double threads
Number of threads to use.
Definition search.hh:853
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
virtual ~Worker(void)
Destructor.
Definition engine.hpp:584
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
virtual Support::Terminator * terminator(void) const
Terminator (engine).
Definition engine.hpp:576
Engine & engine(void) const
Provide access to engine.
Definition engine.hpp:46
Parallel depth-first search engine
Definition engine.hh:52
void idle(void)
Report that worker is idle.
Definition engine.hpp:358
void wait(void)
Ensure that worker waits.
Definition engine.hpp:92
Support::Event _e_terminate
Event for termination (all threads have terminated).
Definition engine.hh:198
std::atomic< unsigned long long int > n_runs
Number of calls to next() that have started search.
Definition engine.hh:246
void ack_reset_stop(void)
For worker to acknowledge stop of reset cycle.
Definition engine.hpp:471
const Options & opt(void) const
Provide access to search options.
Definition engine.hpp:51
void scheduler_idle(unsigned int worker)
Record that worker worker is idle.
Definition engine.hpp:295
Support::Mutex _m_wait_terminate
Mutex for waiting for termination.
Definition engine.hh:194
Support::Event e_reset_ack_stop
Event for reset acknowledgment stopped.
Definition engine.hh:220
Support::Mutex _m_wait
Mutex for forcing workers to wait.
Definition engine.hh:172
bool scheduler_grow(void)
Grant leases up to the current request (scheduler_mutex held).
Definition engine.hpp:157
Support::Event e_search
Event for search (solution found, no more solutions, search stopped).
Definition engine.hh:238
SchedulerLogical
Logical worker state used by adjustable parallel admission.
Definition engine.hh:96
@ IDLE
Has reported idle and owns no local search.
Definition engine.hh:102
@ PENDING
Has not yet reported its initial idle state.
Definition engine.hh:100
@ OWNER
Owns local search or has not yet reported its exhaustion.
Definition engine.hh:98
virtual Space * next(void)
Return next solution (nullptr, if none exists or search has been stopped).
Definition engine.hpp:523
Support::Event _e_term_ack
Event for termination acknowledgment.
Definition engine.hh:192
Support::DynamicQueue< Space *, Heap > solutions
Queue of solutions.
Definition engine.hh:240
SchedulerWorker * scheduler_worker
Per-worker adjustable parallel admission state.
Definition engine.hh:125
virtual bool stopped(void) const
Check whether engine has been stopped.
Definition engine.hpp:61
std::atomic< unsigned long long int > scheduler_generation
Last request generation reconciled by the scheduler.
Definition engine.hh:133
unsigned int scheduler_select(SchedulerLogical logical, unsigned int exclude) const
Select a no-lease worker by logical state (scheduler_mutex held).
Definition engine.hpp:143
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
bool scheduler_enabled
Whether adjustable parallel admission is enabled.
Definition engine.hh:113
Support::Event e_reset_ack_start
Event for reset acknowledgment started.
Definition engine.hh:218
Support::Mutex _m_term
Mutex for access to termination information.
Definition engine.hh:188
std::atomic< bool > has_stopped
Whether a worker had been stopped.
Definition engine.hh:244
Cmd cmd(void) const
Return current command.
Definition engine.hpp:72
Support::Mutex scheduler_mutex
Mutex for adjustable parallel admission.
Definition engine.hh:123
void scheduler_owner(unsigned int worker)
Record that worker worker owns search.
Definition engine.hpp:285
unsigned long long int run(void) const
Return the current call of next().
Definition engine.hpp:378
virtual ~Engine(void)
Destructor.
Definition engine.hpp:594
Engine(const Options &o)
Initialize with options o.
Definition engine.hpp:123
Options _opt
Search options.
Definition engine.hh:89
void busy(void)
Report that worker is busy.
Definition engine.hpp:369
volatile unsigned int _n_reset_not_ack
Number of workers that have not yet acknowledged reset.
Definition engine.hh:216
unsigned int scheduler_leases
Current lease count.
Definition engine.hh:129
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 ack_reset_start(void)
For worker to acknowledge start of reset cycle.
Definition engine.hpp:462
volatile unsigned int _n_term_not_ack
Number of workers that have not yet acknowledged termination.
Definition engine.hh:190
void wait_reset(void)
For worker to wait for all workers to reset.
Definition engine.hpp:480
volatile unsigned int _n_not_terminated
Number of not yet terminated workers.
Definition engine.hh:196
virtual void terminated(void)
For worker to register termination.
Definition engine.hpp:414
void scheduler_handoff(unsigned int worker, bool work_remains)
Hand worker worker's lease to a parked logical worker.
Definition engine.hpp:305
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
std::atomic< Cmd > _cmd
The current command.
Definition engine.hh:170
Support::Mutex _m_reset
Mutex for access to reset information.
Definition engine.hh:214
volatile unsigned int n_busy
Number of busy workers.
Definition engine.hh:242
unsigned int scheduler_requested
Current requested lease count.
Definition engine.hh:127
void wait_terminate(void)
For worker to wait until termination is legal.
Definition engine.hpp:436
unsigned int workers(void) const
Return number of workers.
Definition engine.hpp:56
Cmd
Commands from engine to workers.
Definition engine.hh:162
@ 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
unsigned int scheduler_cursor
Round-robin cursor for lease handoff.
Definition engine.hh:131
const std::atomic< bool > * scheduler_fast_admit
Unchanged-capacity admission fast path.
Definition engine.hh:115
void ack_terminate(void)
For worker to acknowledge termination command.
Definition engine.hpp:427
bool work_remains(void)
Whether logical search work remains.
Definition engine.hpp:401
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
static void signal(WorkerControl &control, unsigned int worker)
Signal the event belonging to worker worker.
static void signal_all(WorkerControl &control)
Signal every worker event.
static unsigned long long int generation(const WorkerControl &control)
Return the request generation.
static void snapshot(const WorkerControl &control, unsigned int &requested, unsigned long long int &generation)
Return a consistent request and generation snapshot.
static void wait(WorkerControl &control, unsigned int worker)
Wait for the event belonging to worker worker.
static const std::atomic< bool > * fast_admission(const WorkerControl &control)
Return the unchanged-capacity fast-admission flag.
static unsigned int requested(const WorkerControl &control)
Return the current request.
Worker(void)
Initialize.
Definition worker.hh:72
Computation spaces.
Definition core.hpp:1787
An interface for objects that can be called after a thread has terminated (after running the thread's...
Definition thread.hpp:168
static void releaseGlobalMutex(Mutex *m)
release globally acquired mutex m
Definition thread.cpp:159
static void acquireGlobalMutex(Mutex *m)
acquire mutex m globally and possibly lock
Definition thread.cpp:154
Heap heap
The single global heap.
Definition heap.cpp:44
SpaceStatus status(StatusStatistics &stat)
Query space status.
Definition core.cpp:281
@ SS_FAILED
Space is failed
Definition core.hpp:1727
Search engines
Space * snapshot(Space *s, const Options &o)
Clone space s depending on options o.
Definition support.hh:71
Gecode toplevel namespace
Per-worker adjustable parallel admission state.
Definition engine.hh:105
#define forceinline
Definition config.hpp:144
#define GECODE_NEVER
Assert that this command is never executed.
Definition macros.hpp:56