Generated on for Gecode by doxygen 1.17.0
frontier.cpp
Go to the documentation of this file.
1/* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
2/*
3 * Main authors:
4 * Mikael Zayenz Lagerkvist <lagerkvist@gecode.dev>
5 *
6 * Copyright:
7 * Mikael Zayenz Lagerkvist, 2026
8 *
9 * This file is part of Gecode, the generic constraint
10 * development environment:
11 * http://www.gecode.dev
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
36
37#if defined(GECODE_HAS_EXPERIMENTAL) && defined(GECODE_HAS_THREADS)
38namespace Gecode { namespace Search { namespace Par {
39
41 : Support::Runnable(false), engine(e), id(i) {}
42
43 void
45 engine.work(id);
46 }
47
50 return const_cast<Runner*>(this);
51 }
52
53 void
55 done.signal();
56 }
57
59 : Search::Engine(o,static_cast<unsigned int>(o.threads)), opt(o),
60 guidance(*o.guidance), best(guidance.sense), order(0),
61 pending(heap), n_pending(0), runners(nullptr), active(0),
62 running(false), shutdown(false), _stopped(false), _limited(false),
63 batch(1), keyed(false) {}
64
65 void
67
68 void
70 pending.push(t); n_pending++;
71 }
72
73 void
74 Frontier::initialize(Space* s, bool clone) {
75 if (s == nullptr) {
76 stat.fail++;
77 return;
78 }
79 if (s->status(stat) == SS_FAILED) {
80 stat.fail++;
81 if (!clone)
82 delete s;
83 return;
84 }
85 started(*s);
86 std::unique_ptr<Task> t(new Task);
87 t->expansion.select(std::unique_ptr<Space>(clone ? s->clone() : s));
88 push(t.release());
89 }
90
91 void
93 if (runners != nullptr)
94 return;
95 unsigned int n = static_cast<unsigned int>(opt.threads);
96 runners = heap.alloc<Runner*>(n);
97 for (unsigned int i=0; i<n; i++)
98 runners[i] = new Runner(*this,i);
99 unsigned int started = 0;
100 try {
101 for (; started<n; started++)
103 } catch (...) {
104 { Support::Lock lock(mutex); shutdown = true; }
105 wake();
106 for (unsigned int i=0; i<started; i++)
107 runners[i]->done.wait();
108 for (unsigned int i=0; i<n; i++)
109 delete runners[i];
110 heap.free<Runner*>(runners,n);
111 runners = nullptr;
112 // All started runners have terminated, so there are no concurrent readers.
113 shutdown = false;
114 throw;
115 }
116 }
117
118 void
120 if (worker_control.engaged()) {
122 } else if (runners != nullptr) {
123 for (unsigned int i=0; i<static_cast<unsigned int>(opt.threads); i++)
124 runners[i]->wake.signal();
125 }
126 }
127
128 bool
129 Frontier::enabled(unsigned int id) {
130 return !worker_control.engaged() ||
132 }
133
134 void
136 if (runners == nullptr)
137 return;
138 { Support::Lock lock(mutex); shutdown = true; running = false; }
139 wake();
140 unsigned int n = static_cast<unsigned int>(opt.threads);
141 for (unsigned int i=0; i<n; i++)
142 runners[i]->done.wait();
143 for (unsigned int i=0; i<n; i++)
144 delete runners[i];
145 heap.free<Runner*>(runners,n);
146 runners = nullptr;
147 }
148
150 terminate();
151 while (n_pending > 0) {
152 delete pending.pop(); n_pending--;
153 }
154 }
155
156 void
157 Frontier::publish(Space* s, std::int64_t b) {
158 if (!best.improves(b)) {
159 delete s;
160 return;
161 }
162 std::unique_ptr<Space> incumbent(s);
163 solution.reset(s->clone());
164 best.update(incumbent.release(),b);
165 running = false;
166 }
167
168 void
169 Frontier::work(unsigned int id) {
170 // The leased task and the incumbent used for constraining its children
171 Task* task = nullptr;
172 std::unique_ptr<Space> incumbent;
173 unsigned long long int revision = 0;
174 std::optional<std::int64_t> cutoff;
175 Worker local;
176 // Children and solution found since the last submission
177 Entry children[max_batch];
178 unsigned int n_children = 0, submitted = 0;
179 std::unique_ptr<Space> solved;
180 std::int64_t solved_bound = 0;
181 while (true) {
182 try {
183 bool notify = false;
184 {
185 Support::Lock lock(mutex);
186 bool idle = (n_pending == 0) && !open();
187 bool enabled = this->enabled(id);
188 if (task != nullptr) {
189 stat += local;
190 local.reset();
191 for (submitted=0; submitted<n_children; submitted++)
192 submit(children[submitted],static_cast<bool>(task->expansion));
193 n_children = submitted = 0;
194 if (solved)
195 publish(solved.release(),solved_bound);
196 }
197 if (running && (opt.stop != nullptr) && opt.stop->stop(stat,opt)) {
198 _stopped = true; running = false;
199 }
200 if (task != nullptr) {
201 if (!task->expansion || !running || !enabled || shutdown) {
202 if (task->expansion)
203 push(task);
204 else
205 delete task;
206 task = nullptr;
207 active--;
208 // An enabled worker must check for termination
209 notify = (active == 0) && running && !enabled;
210 }
211 }
212 if (shutdown) {
213 incumbent.reset();
214 return;
215 }
216 while (running && enabled && (task == nullptr)) {
217 if ((n_pending == 0) && !open() && (active == 0) && !advance())
218 running = false;
219 if (!running || ((n_pending == 0) && !open()))
220 break;
221 if (n_pending > 0) {
222 task = pending.pop(); n_pending--;
223 } else {
224 Entry e = select();
225 std::unique_ptr<Space> s(e.space);
226 if (!best.improves(e.bound)) {
227 stat.fail++;
228 if ((opt.stop != nullptr) && opt.stop->stop(stat,opt)) {
229 _stopped = true; running = false;
230 }
231 continue;
232 }
233 task = new Task;
234 task->expansion.select(std::move(s));
235 task->depth = e.depth;
236 task->revision = e.revision;
237 task->counted = true;
238 }
239 active++;
240 }
241 if (task != nullptr) {
242 if (revision != best.revision)
243 incumbent.reset();
244 if (best.space && (task->revision != best.revision) && !incumbent)
245 incumbent.reset(best.space->clone());
246 revision = best.revision;
247 cutoff.reset();
248 if (best.space)
249 cutoff = best.bound;
250 } else {
251 incumbent.reset();
252 revision = 0;
253 }
254 notify = notify || (idle && ((n_pending > 0) || open()));
255 if (!running && (active == 0))
256 changed.signal();
257 }
258 if (notify)
259 wake();
260 if (task == nullptr) {
261 if (worker_control.engaged())
263 else
264 runners[id]->wake.wait();
265 continue;
266 }
267 if (!task->counted) {
268 local.node++;
269 local.stack_depth(task->depth);
270 task->counted = true;
271 }
272 // Limit the work between stop checks
273 for (unsigned int i=0; (i<32) && task->expansion; i++) {
274 Seq::ExpansionStep step =
275 task->expansion.next(local,task->depth+1,task->revision,
276 incumbent.get(),revision);
277 if (step.state == Seq::ExpansionStep::EXHAUSTED)
278 break;
279 if (step.status != SS_FAILED) {
280 if (step.status == SS_SOLVED)
281 (void) step.space->choice();
282 std::int64_t b = guidance.bound(*step.space);
283 if (step.status == SS_SOLVED) {
284 if (!cutoff || better(guidance.sense,b,*cutoff)) {
285 solved = std::move(step.space);
286 solved_bound = b;
287 break;
288 }
289 continue;
290 }
291 if ((step.status == SS_BRANCH) &&
292 (!cutoff || better(guidance.sense,b,*cutoff))) {
293 std::int64_t r = guidance.rank ? guidance.rank(*step.space) : 0;
294 std::size_t k = keyed ? guidance.dominance_key(*step.space) : 0;
295 children[n_children++] =
296 {step.space.release(),b,r,k,task->depth+1,0,revision};
297 if (n_children == batch)
298 break;
299 continue;
300 }
301 }
302 local.fail++;
303 if (!enabled(id))
304 break;
305 }
306 } catch (...) {
307 Support::Lock lock(mutex);
308 for (unsigned int i=submitted; i<n_children; i++)
309 delete children[i].space;
310 n_children = 0; submitted = 0;
311 solved.reset();
312 if (task != nullptr) {
313 delete task;
314 task = nullptr;
315 active--;
316 stat += local;
317 }
318 local.reset();
319 incumbent.reset();
320 revision = 0;
321 if (!error)
322 error = std::current_exception();
323 running = false;
324 if (active == 0)
325 changed.signal();
326 }
327 }
328 }
329
330 Space*
332 launch();
333 {
334 Support::Lock lock(mutex);
335 if (error)
336 std::rethrow_exception(error);
337 if (_limited) {
338 _stopped = true;
339 return nullptr;
340 }
341 _stopped = false;
342 running = true;
343 }
344 wake();
345 while (true) {
346 changed.wait();
347 Support::Lock lock(mutex);
348 if (running || (active > 0))
349 continue;
350 if (error)
351 std::rethrow_exception(error);
352 return solution.release();
353 }
354 }
355
358 Support::Lock lock(mutex);
359 return stat;
360 }
361
362 bool
363 Frontier::stopped(void) const {
364 Support::Lock lock(mutex);
365 return _stopped;
366 }
367
368 bool
369 Frontier::limited(void) const {
370 Support::Lock lock(mutex);
371 return _limited;
372 }
373
374 void
376 std::int64_t b = guidance.bound(s);
377 Support::Lock lock(mutex);
378 if (best.improves(b)) {
379 best.update(s.clone(),b);
380 solution.reset();
381 }
382 }
383
384 void
386 std::unique_ptr<Space> replacement(s);
387 Support::Lock lock(mutex);
388 while (n_pending > 0) {
389 delete pending.pop(); n_pending--;
390 }
391 clear();
392 best.reset();
393 solution.reset();
394 order = 0;
395 _stopped = _limited = false;
396 error = nullptr;
397 stat.reset();
398 initialize(s,false);
399 // The root is owned by the engine after initialize returns
400 (void) replacement.release();
401 }
402
403}}}
404#endif
405
406// STATISTICS: search-par
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
Open node of a heuristic search engine.
Definition heuristic.hh:53
Space * space
The stable space (owned by the container holding the entry).
Definition heuristic.hh:56
unsigned long long int revision
Incumbent revision the space has been constrained with.
Definition heuristic.hh:66
unsigned long int depth
Depth of the node.
Definition heuristic.hh:62
std::int64_t bound
Bound and rank of the space.
Definition heuristic.hh:58
Search engine options
Definition search.hh:848
Thread running a worker.
Definition frontier.hh:70
Support::Terminator * terminator(void) const override
Return terminator.
Definition frontier.cpp:49
void terminated(void) override
Signal termination.
Definition frontier.cpp:54
void run(void) override
Run worker.
Definition frontier.cpp:44
Runner(Frontier &e, unsigned int i)
Initialize.
Definition frontier.cpp:40
Node leased by a worker, or partially expanded node.
Definition frontier.hh:56
unsigned long int depth
Depth of the node.
Definition frontier.hh:61
unsigned long long int revision
Incumbent revision the node is constrained with.
Definition frontier.hh:63
bool counted
Whether the node has been counted.
Definition frontier.hh:65
Seq::ChoiceExpansion expansion
The node with its remaining alternatives.
Definition frontier.hh:59
bool stopped(void) const override
Whether search has been stopped.
Definition frontier.cpp:363
~Frontier(void) override
Destructor.
Definition frontier.cpp:149
std::exception_ptr error
First exception thrown by a worker.
Definition frontier.hh:114
void reset(Space *s) override
Reset engine to restart at space s.
Definition frontier.cpp:385
void wake(void)
Wake up all workers.
Definition frontier.cpp:119
virtual Entry select(void)=0
Remove and return the next open node.
void work(unsigned int id)
Run worker id.
Definition frontier.cpp:169
Support::Event changed
Signalled when search is idle.
Definition frontier.hh:106
unsigned long long int order
Number of created entries.
Definition frontier.hh:96
Space * next(void) override
Return next better solution (nullptr if none or stopped).
Definition frontier.cpp:331
void constrain(const Space &s) override
Constrain future solutions to be better than s.
Definition frontier.cpp:375
void publish(Space *s, std::int64_t b)
Make s with bound b the incumbent, if it improves.
Definition frontier.cpp:157
Search::Statistics stat
Statistics.
Definition frontier.hh:108
Options opt
Search options.
Definition frontier.hh:88
virtual void started(const Space &r)
Called with the root r when search starts.
Definition frontier.cpp:66
std::unique_ptr< Space > solution
Solution to be returned by next().
Definition frontier.hh:94
Support::Mutex mutex
Mutex protecting all data.
Definition frontier.hh:104
void terminate(void)
Stop all workers (must be called by subclass destructors).
Definition frontier.cpp:135
bool enabled(unsigned int id)
Whether worker id is currently enabled.
Definition frontier.cpp:129
bool keyed
Whether to compute dominance keys.
Definition frontier.hh:136
Runner ** runners
The threads (allocated on first next()).
Definition frontier.hh:102
HeuristicGuidance guidance
Guidance.
Definition frontier.hh:90
virtual bool open(void) const =0
Whether there are open nodes.
void initialize(Space *s, bool clone)
Start search from root s.
Definition frontier.cpp:74
Support::DynamicQueue< Task *, Heap > pending
Partially expanded nodes.
Definition frontier.hh:98
virtual void clear(void)=0
Delete all open nodes.
unsigned int batch
Number of children a worker collects before submitting.
Definition frontier.hh:134
void push(Task *t)
Add pending task t.
Definition frontier.cpp:69
void launch(void)
Start the threads.
Definition frontier.cpp:92
virtual bool advance(void)=0
Called when all work is done, return whether there is new work.
Search::Statistics statistics(void) const override
Return statistics.
Definition frontier.cpp:357
virtual void submit(const Entry &e, bool leased)=0
Add child e, or delete it; leased tells whether its parent is still leased.
bool limited(void) const override
Whether search stopped at the width or frontier limit.
Definition frontier.cpp:369
bool running
Whether search is running, being shut down, stopped, or limited.
Definition frontier.hh:112
unsigned int n_pending
Number of partially expanded nodes.
Definition frontier.hh:100
unsigned int active
Number of workers holding a task.
Definition frontier.hh:110
Incumbent best
Best solution so far.
Definition frontier.hh:92
static const unsigned int max_batch
Maximal number of children a worker collects before submitting.
Definition frontier.hh:132
Frontier(const Options &o)
Initialize with options o.
Definition frontier.cpp:58
ExpansionStep next(Worker &worker, unsigned long int depth, unsigned long long int node_revision, const Space *incumbent, unsigned long long int revision)
Commit and propagate the next alternative.
void select(std::unique_ptr< Space > s)
Take stable node s.
Result of expanding one alternative.
@ EXHAUSTED
Nothing, all alternatives have been expanded.
Search engine statistics
Definition search.hh:155
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
static void signal_all(WorkerControl &control)
Signal every worker event.
static void wait(WorkerControl &control, unsigned int worker)
Wait for the event belonging to worker worker.
static unsigned int requested(const WorkerControl &control)
Return the current request.
Search worker statistics
Definition worker.hh:44
void reset(unsigned long int d=0)
Reset statistics with root depth d.
Definition worker.hh:106
void stack_depth(unsigned long int d)
Record stack depth d.
Definition worker.hh:114
Computation spaces.
Definition core.hpp:1787
A lock as a scoped frontend for a mutex.
Definition thread.hpp:114
Runnable(bool d=true)
Initialize, d defines whether object is deleted when terminated.
Definition thread.hpp:40
An interface for objects that can be called after a thread has terminated (after running the thread's...
Definition thread.hpp:168
static void run(Runnable *r)
Construct a new thread and run r.
Definition thread.hpp:177
Heap heap
The single global heap.
Definition heap.cpp:44
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
Search engines
bool better(HeuristicGuidance::Sense s, std::int64_t a, std::int64_t b)
Whether bound a is better than bound b for objective direction s.
Definition heuristic.hh:48
Support algorithms and datastructures
Gecode toplevel namespace