Generated on for Gecode by doxygen 1.17.0
pbs.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, 2015
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_PBS_HH
39#define GECODE_SEARCH_PAR_PBS_HH
40
41#include <gecode/search.hh>
42#include <atomic>
43
44namespace Gecode { namespace Search { namespace Par {
45
48 private:
50 Stop* so;
52 Stop* po;
54 WorkerControl worker_control;
56 std::atomic<bool>* tostop;
57 public:
59 PortfolioStop(Stop* so, Stop* po, const WorkerControl& control);
61 void share(std::atomic<bool>* ts);
63 virtual bool stop(const Statistics& s, const Options& o);
65 void wake(void);
67 void stop(bool s);
69 bool stop(void) const;
70 };
71
72 // Forward declaration
73 template<class Collect>
74 class PBS;
75
77 template<class Collect>
79 protected:
82 protected:
85 public:
87 Completion(void);
89 virtual void terminated(void);
91 void wait(void);
92 } completion;
99 public:
101 Slave(PBS<Collect>* m, Engine* s, Stop* so);
103 Statistics statistics(void) const;
105 bool stopped(void) const;
107 bool limited(void) const;
109 virtual Support::Terminator* terminator(void) const;
111 void wait(void);
113 void wake(void);
115 void constrain(const Space& b);
117 virtual void run(void);
119 virtual ~Slave(void);
120 };
121
124 protected:
127 public:
129 static const bool best = false;
131 CollectAll(void);
133 bool add(Space* s, Slave<CollectAll>* r);
135 bool constrain(const Space& b);
137 bool empty(void) const;
141 ~CollectAll(void);
142 };
143
146 protected:
151 public:
153 static const bool best = true;
155 CollectBest(void);
157 bool add(Space* s, Slave<CollectBest>* r);
159 bool constrain(const Space& b);
161 bool empty(void) const;
166 };
167
169 template<class Collect>
171 friend class Slave<Collect>;
172 protected:
178 unsigned int n_slaves;
180 unsigned int n_active;
182 std::atomic<bool> slave_stop;
186 std::atomic<bool> tostop;
188 Collect solutions;
192 unsigned int n_busy;
196 bool report(Slave<Collect>* slave, Space* s);
205 public:
207 PBS(Engine** s, Stop** so, unsigned int n, const Statistics& stat);
209 virtual Space* next(void);
211 virtual Statistics statistics(void) const;
213 virtual bool stopped(void) const;
215 virtual void constrain(const Space& b);
217 virtual ~PBS(void);
218 };
219
220}}}
221
223
224#endif
225
226// STATISTICS: search-par
Search engine options
Definition search.hh:848
Space * get(Slave< CollectAll > *&r)
Return solution reported by r.
Definition pbs.hpp:82
bool empty(void) const
Check whether there is any solution left.
Definition pbs.hpp:78
Support::DynamicQueue< Space *, Heap > solutions
Queue of solutions.
Definition pbs.hh:126
bool add(Space *s, Slave< CollectAll > *r)
Add a solution a reported by r and always return true.
Definition pbs.hpp:68
CollectAll(void)
Initialize.
Definition pbs.hpp:65
~CollectAll(void)
Destructor.
Definition pbs.hpp:86
static const bool best
Whether it collects best solutions.
Definition pbs.hh:129
bool constrain(const Space &b)
Dummy function.
Definition pbs.hpp:73
CollectBest(void)
Initialize.
Definition pbs.hpp:93
static const bool best
Whether it collects best solutions.
Definition pbs.hh:153
bool constrain(const Space &b)
Check whether b better and update accordingly.
Definition pbs.hpp:111
bool empty(void) const
Check whether there is any solution left.
Definition pbs.hpp:125
bool add(Space *s, Slave< CollectBest > *r)
Add a solution s by r and return whether is was better.
Definition pbs.hpp:96
Space * get(Slave< CollectBest > *&r)
Return solution reported by r (only if a better one was found).
Definition pbs.hpp:129
Slave< CollectBest > * reporter
Who has reported the best solution (nullptr if solution has already been reported).
Definition pbs.hh:150
~CollectBest(void)
Destructor.
Definition pbs.hpp:136
Space * b
Currently best solution.
Definition pbs.hh:148
Parallel depth-first search engine
Definition engine.hh:52
Engine(const Options &o)
Initialize with options o.
Definition engine.hpp:123
Parallel portfolio engine implementation.
Definition pbs.hh:170
virtual bool stopped(void) const
Check whether engine has been stopped.
Definition pbs.hpp:326
Support::Event idle
Signal that number of busy slaves becomes zero.
Definition pbs.hh:194
bool report(Slave< Collect > *slave, Space *s)
Process report from slave, return false if solution was ignored.
Definition pbs.hpp:220
bool incomplete
Whether a slave stopped at a local limit.
Definition pbs.hh:184
Collect solutions
Collect solutions in this.
Definition pbs.hh:188
Support::Mutex m
Mutex for synchronization.
Definition pbs.hh:190
Slave< Collect > ** slaves
Slave engines.
Definition pbs.hh:176
std::atomic< bool > tostop
Shared stop flag.
Definition pbs.hh:186
unsigned int n_active
Number of active slave engines.
Definition pbs.hh:180
unsigned int n_slaves
Number of slave engines.
Definition pbs.hh:178
Statistics stat
Master statistics.
Definition pbs.hh:174
PBS(Engine **s, Stop **so, unsigned int n, const Statistics &stat)
Initialize.
Definition pbs.hpp:205
virtual void constrain(const Space &b)
Constrain future solutions to be better than b.
Definition pbs.hpp:342
std::atomic< bool > slave_stop
Whether a slave has been stopped.
Definition pbs.hh:182
virtual Space * next(void)
Return next solution (nullptr, if none exists or search has been stopped).
Definition pbs.hpp:273
virtual Statistics statistics(void) const
Return statistics.
Definition pbs.hpp:332
unsigned int n_busy
Number of busy slaves.
Definition pbs.hh:192
void wake(void)
Wake workers so that a paused asset can observe the portfolio stop.
Definition pbs.cpp:51
void share(std::atomic< bool > *ts)
Set pointer to shared tostop variable.
Definition pbs.hpp:147
virtual bool stop(const Statistics &s, const Options &o)
Return true if portfolio engine must be stopped.
Definition pbs.cpp:44
void stop(bool s)
Signal whether search must be stopped.
PortfolioStop(Stop *so, Stop *po, const WorkerControl &control)
Initialize with slave stop so, portfolio stop po, and control.
Definition pbs.hpp:142
bool stop(void) const
Whether search must be stopped.
virtual void terminated(void)
Signal completion.
Definition pbs.hpp:53
void wait(void)
Wait for completion and consume the signal.
Definition pbs.hpp:59
Completion(void)
Initialize as completed.
Definition pbs.hpp:44
Support::Event done
The completion event.
Definition pbs.hh:84
Runnable slave of a portfolio master.
Definition pbs.hh:78
Engine * slave
The slave engine.
Definition pbs.hh:96
PBS< Collect > * master
The master engine.
Definition pbs.hh:94
void wait(void)
Wait for the slave to complete its current run.
Definition pbs.hpp:182
virtual Support::Terminator * terminator(void) const
Return the completion terminator.
Definition pbs.hpp:177
virtual void run(void)
Perform one run.
Definition pbs.hpp:264
bool stopped(void) const
Check whether slave has been stopped.
Definition pbs.hpp:163
Statistics statistics(void) const
Return statistics of slave.
Definition pbs.hpp:158
Slave(PBS< Collect > *m, Engine *s, Stop *so)
Initialize with master m, slave s, and its stop object so.
Definition pbs.hpp:154
void wake(void)
Wake a paused slave so that it can observe the portfolio stop.
Definition pbs.hpp:187
void constrain(const Space &b)
Constrain with better solution b.
Definition pbs.hpp:192
Stop * stop
Stop object.
Definition pbs.hh:98
bool limited(void) const
Check whether slave stopped at a local limit.
Definition pbs.hpp:168
Search engine statistics
Definition search.hh:155
Base-class for Stop-object.
Definition search.hh:919
Stop(void)
Default constructor.
Definition stop.hpp:45
External control for the requested number of search workers.
Definition search.hh:773
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
#define GECODE_SEARCH_EXPORT
Definition search.hh:75