Generated on for Gecode by doxygen 1.17.0
engine.hh
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
38#ifndef GECODE_SEARCH_PAR_ENGINE_HH
39#define GECODE_SEARCH_PAR_ENGINE_HH
40
41#include <gecode/search.hh>
46#include <atomic>
47
48namespace Gecode { namespace Search { namespace Par {
49
51 template<class Tracer>
52 class Engine : public Search::Engine, public Support::Terminator {
53 protected:
55 class Worker : public Search::Worker, public Support::Runnable {
56 public:
59 protected:
69 unsigned int d;
71 bool idle;
72 public:
74 Worker(Space* s, Engine& e);
76 Space* steal(unsigned long int& d, Tracer& myt, Tracer& ot);
80 Engine& engine(void) const;
82 NoGoods& nogoods(void);
84 virtual ~Worker(void);
86 virtual Support::Terminator* terminator(void) const;
87 };
88
104
112
115 const std::atomic<bool>* scheduler_fast_admit;
129 unsigned int scheduler_leases;
131 unsigned int scheduler_cursor;
133 std::atomic<unsigned long long int> scheduler_generation;
135 unsigned int scheduler_select(SchedulerLogical logical,
136 unsigned int exclude) const;
138 bool scheduler_grow(void);
139 public:
141 const Options& opt(void) const;
143 unsigned int workers(void) const;
145 void scheduler_enable(bool root_owner);
147 void scheduler_reset(bool root_owner);
149 bool scheduler_admit(unsigned int worker);
151 bool scheduler_paused(void) const;
153 void scheduler_owner(unsigned int worker);
155 void scheduler_idle(unsigned int worker);
157 void scheduler_handoff(unsigned int worker, bool work_remains);
158
160
161
168 protected:
170 std::atomic<Cmd> _cmd;
173 public:
175 Cmd cmd(void) const;
177 void block(void);
179 void release(Cmd c);
181 void wait(void);
183
185
186 protected:
190 volatile unsigned int _n_term_not_ack;
196 volatile unsigned int _n_not_terminated;
199 public:
201 void ack_terminate(void);
203 virtual void terminated(void);
205 void wait_terminate(void);
207 void terminate(void);
209
211
212 protected:
216 volatile unsigned int _n_reset_not_ack;
223 public:
225 void ack_reset_start(void);
227 void ack_reset_stop(void);
229 void wait_reset(void);
231
233
234 protected:
242 volatile unsigned int n_busy;
244 std::atomic<bool> has_stopped;
246 std::atomic<unsigned long long int> n_runs;
248 bool signal(void) const;
249 public:
251 void idle(void);
253 void busy(void);
255 unsigned long long int run(void) const;
257 void stop(unsigned long long int r);
259 bool work_remains(void);
261
263
264
265 Engine(const Options& o);
267 virtual Space* next(void);
269 virtual bool stopped(void) const;
271
273 virtual ~Engine(void);
274 };
275
276}}}
277
279
280#endif
281
282// STATISTICS: search-par
No-goods recorded from restarts.
Definition core.hpp:1606
Search engine implementation interface
Definition search.hh:1063
Engine(void)
Construct a meta engine without worker control.
Definition engine.cpp:39
Search engine options
Definition search.hh:848
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
Worker(Space *s, Engine &e)
Initialize for space s with engine e.
Definition engine.hpp:102
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
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
Depth-first path (stack of edges) supporting recomputation.
Definition path.hh:64
Statistics(void)
Initialize.
Search worker statistics
Definition worker.hh:44
Worker(void)
Initialize.
Definition worker.hh:72
Computation spaces.
Definition core.hpp:1787
Queue with arbitrary number of elements.
An event for synchronization.
Definition thread.hpp:138
A mutex for mutual exclausion among several threads.
Definition thread.hpp:78
An interface for objects that can be run by a thread.
Definition thread.hpp:181
An interface for objects that can be called after a thread has terminated (after running the thread's...
Definition thread.hpp:168
Search engines
Gecode toplevel namespace
Per-worker adjustable parallel admission state.
Definition engine.hh:105
bool lease
Permission to execute exploration actions.
Definition engine.hh:107
bool parked
Waiting or due to wait for admission.
Definition engine.hh:109