Generated on Tue Feb 11 2025 17:33:26 for Gecode by doxygen 1.12.0
dfs.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.org>
5 *
6 * Copyright:
7 * Christian Schulte, 2009
8 *
9 * This file is part of Gecode, the generic constraint
10 * development environment:
11 * http://www.gecode.org
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
34namespace Gecode { namespace Search { namespace Par {
35
36 /*
37 * Basic access routines
38 */
39 template<class Tracer>
40 forceinline DFS<Tracer>&
42 return static_cast<DFS<Tracer>&>(_engine);
43 }
44 template<class Tracer>
46 DFS<Tracer>::worker(unsigned int i) const {
47 return _worker[i];
48 }
49
50
51 /*
52 * Engine: initialization
53 */
54 template<class Tracer>
58 template<class Tracer>
61 : Engine<Tracer>(o) {
63 workers());
64 // Create workers
65 _worker = static_cast<Worker**>
66 (heap.ralloc(workers() * sizeof(Worker*)));
67 // The first worker gets the entire search tree
68 _worker[0] = new Worker(s,*this);
69 // All other workers start with no work
70 for (unsigned int i=1; i<workers(); i++)
71 _worker[i] = new Worker(NULL,*this);
72 // Block all workers
73 block();
74 // Create and start threads
75 for (unsigned int i=0U; i<workers(); i++)
77 }
78
79
80 /*
81 * Reset
82 */
83 template<class Tracer>
84 forceinline void
85 DFS<Tracer>::Worker::reset(Space* s, unsigned int ngdl) {
86 delete cur;
87 tracer.round();
88 path.reset((s != NULL) ? ngdl : 0);
89 d = 0;
90 idle = false;
91 if ((s == NULL) || (s->status(*this) == SS_FAILED)) {
92 delete s;
93 cur = NULL;
94 } else {
95 cur = s;
96 }
98 }
99
100
101 /*
102 * Engine: search control
103 */
104 template<class Tracer>
105 forceinline void
108 bool bs = signal();
109 solutions.push(s);
110 if (bs)
113 }
114
115
116
117 /*
118 * Worker: finding and stealing working
119 */
120 template<class Tracer>
121 forceinline void
123 // Try to find new work (even if there is none)
124 for (unsigned int i=0U; i<engine().workers(); i++) {
125 unsigned long int r_d = 0ul;
126 typename Engine<Tracer>::Worker* wi = engine().worker(i);
127 if (Space* s = wi->steal(r_d,wi->tracer,tracer)) {
128 // Reset this guy
129 m.acquire();
130 idle = false;
131 // Not idle but also does not have the root of the tree
132 path.ngdl(0);
133 d = 0;
134 cur = s;
135 Statistics t = *this;
137 (*this) += t;
138 m.release();
139 return;
140 }
141 }
142 }
143
144 /*
145 * Statistics
146 */
147 template<class Tracer>
150 Statistics s;
151 for (unsigned int i=0U; i<workers(); i++)
152 s += worker(i)->statistics();
153 return s;
154 }
155
156
157 /*
158 * Engine: search control
159 */
160 template<class Tracer>
161 void
163 /*
164 * The engine maintains the following invariant:
165 * - If the current space (cur) is not NULL, the path always points
166 * to exactly that space.
167 * - If the current space (cur) is NULL, the path always points
168 * to the next space (if there is any).
169 *
170 * This invariant is needed so that no-goods can be extracted properly
171 * when the engine is stopped or has found a solution.
172 *
173 */
174 // Peform initial delay, if not first worker
175 if (this != engine().worker(0))
177 // Okay, we are in business, start working
178 while (true) {
179 switch (engine().cmd()) {
180 case C_WAIT:
181 // Wait
182 engine().wait();
183 break;
184 case C_TERMINATE:
185 // Acknowledge termination request
186 engine().ack_terminate();
187 // Wait until termination can proceed
188 engine().wait_terminate();
189 // Thread will be terminated by returning from run
190 return;
191 case C_RESET:
192 // Acknowledge reset request
193 engine().ack_reset_start();
194 // Wait until reset has been performed
195 engine().wait_reset();
196 // Acknowledge that reset cycle is over
197 engine().ack_reset_stop();
198 break;
199 case C_WORK:
200 // Perform exploration work
201 {
202 m.acquire();
203 if (idle) {
204 m.release();
205 // Try to find new work
206 find();
207 } else if (cur != NULL) {
208 start();
209 if (stop(engine().opt())) {
210 // Report stop
211 m.release();
212 engine().stop();
213 } else {
214 node++;
216 if (tracer) {
217 if (path.entries() > 0) {
218 typename Path<Tracer>::Edge& top = path.top();
219 ei.init(tracer.wid(), top.nid(), top.truealt(),
220 *cur, *top.choice());
221 } else if (*tracer.ei()) {
222 ei = *tracer.ei();
223 tracer.invalidate();
224 }
225 }
226 unsigned int nid = tracer.nid();
227 switch (cur->status(*this)) {
228 case SS_FAILED:
229 if (tracer) {
231 tracer.wid(), nid, *cur);
232 tracer.node(ei,ni);
233 }
234 fail++;
235 delete cur;
236 cur = NULL;
237 path.next();
238 m.release();
239 break;
240 case SS_SOLVED:
241 {
242 if (tracer) {
244 tracer.wid(), nid, *cur);
245 tracer.node(ei,ni);
246 }
247 // Deletes all pending branchers
248 (void) cur->choice();
249 Space* s = cur->clone();
250 delete cur;
251 cur = NULL;
252 path.next();
253 m.release();
254 engine().solution(s);
255 }
256 break;
257 case SS_BRANCH:
258 {
259 Space* c;
260 if ((d == 0) || (d >= engine().opt().c_d)) {
261 c = cur->clone();
262 d = 1;
263 } else {
264 c = NULL;
265 d++;
266 }
267 const Choice* ch = path.push(*this,cur,c,nid);
268 if (tracer) {
270 tracer.wid(), nid, *cur, ch);
271 tracer.node(ei,ni);
272 }
273 cur->commit(*ch,0);
274 m.release();
275 }
276 break;
277 default:
279 }
280 }
281 } else if (!path.empty()) {
282 cur = path.recompute(d,engine().opt().a_d,*this,tracer);
283 if (cur == NULL)
284 path.next();
285 m.release();
286 } else {
287 idle = true;
288 path.ngdl(0);
289 m.release();
290 // Report that worker is idle
291 engine().idle();
292 }
293 }
294 break;
295 default:
297 }
298 }
299 }
300
301
302 /*
303 * Perform reset
304 *
305 */
306 template<class Tracer>
307 void
309 // Grab wait lock for reset
311 // Release workers for reset
313 // Wait for reset cycle started
315 // All workers are marked as busy again
316 n_busy = workers();
317 for (unsigned int i=1U; i<workers(); i++)
318 worker(i)->reset(NULL,0);
319 worker(0U)->reset(s,opt().nogoods_limit);
320 // Block workers again to ensure invariant
321 block();
322 // Release reset lock
324 // Wait for reset cycle stopped
326 }
327
328
329
330 /*
331 * Create no-goods
332 *
333 */
334 template<class Tracer>
335 NoGoods&
337 NoGoods* ng;
338 // Grab wait lock for reset
340 // Release workers for reset
342 // Wait for reset cycle started
344 ng = &worker(0)->nogoods();
345 // Block workers again to ensure invariant
346 block();
347 // Release reset lock
349 // Wait for reset cycle stopped
351 return *ng;
352 }
353
354
355 /*
356 * Termination and deletion
357 */
358 template<class Tracer>
360 terminate();
362 }
363
364}}}
365
366// STATISTICS: search-par
NodeType t
Type of node.
Choice for performing commit
Definition core.hpp:1412
void rfree(void *p)
Free memory block starting at p.
Definition heap.hpp:371
void * ralloc(size_t s)
Allocate s bytes from heap.
Definition heap.hpp:357
No-goods recorded from restarts.
Definition core.hpp:1588
void invalidate(void)
Invalidate edge information (for stealing)
Definition tracer.hpp:102
void init(unsigned int wid, unsigned int nid, unsigned int a)
Initialize.
Definition tracer.hpp:107
unsigned int nid(void) const
Return parent node id.
Definition tracer.hpp:142
@ FAILED
A solution node.
Definition search.hh:278
@ BRANCH
A failed node.
Definition search.hh:279
@ DFS
Engine is a DFS engine.
Definition search.hh:194
Search engine options
Definition search.hh:746
SearchTracer * tracer
Tracer object for tracing search.
Definition search.hh:769
Parallel depth-first search worker
Definition dfs.hh:66
void find(void)
Try to find some work.
Definition dfs.hpp:122
void reset(Space *s, unsigned int ngdl)
Reset worker to restart at space s.
Definition dfs.hpp:85
DFS & engine(void) const
Provide access to engine.
Definition dfs.hpp:41
virtual void run(void)
Start execution of worker.
Definition dfs.hpp:162
Parallel depth-first search engine
Definition dfs.hh:43
virtual Statistics statistics(void) const
Return statistics.
Definition dfs.hpp:149
void solution(Space *s)
Report solution s.
Definition dfs.hpp:106
virtual void reset(Space *s)
Reset engine to restart at space s.
Definition dfs.hpp:308
DFS(Space *s, const Options &o)
Initialize for space s with options o.
Definition dfs.hpp:60
Worker * worker(unsigned int i) const
Provide access to worker i.
Definition dfs.hpp:46
Worker ** _worker
Array of worker references.
Definition dfs.hh:91
virtual NoGoods & nogoods(void)
Return no-goods.
Definition dfs.hpp:336
virtual ~DFS(void)
Destructor.
Definition dfs.hpp:359
Parallel depth-first search worker
Definition engine.hh:49
Engine & _engine
Reference to engine.
Definition engine.hh:55
NoGoods & nogoods(void)
Return no-goods.
Definition engine.hpp:289
Statistics statistics(void)
Return statistics.
Definition engine.hpp:134
Space * cur
Current space being explored.
Definition engine.hh:61
Tracer tracer
Search tracer.
Definition engine.hh:52
Space * steal(unsigned long int &d, Tracer &myt, Tracer &ot)
Hand over some work (NULL if no work available)
Definition engine.hpp:265
unsigned int d
Distance until next clone.
Definition engine.hh:63
bool idle
Whether the worker is idle.
Definition engine.hh:65
Path< Tracer > path
Current path ins search tree.
Definition engine.hh:59
Parallel depth-first search engine
Definition engine.hh:46
void idle(void)
Report that worker is idle.
Definition engine.hpp:152
const Options & opt(void) const
Provide access to search options.
Definition engine.hpp:47
Support::Event e_reset_ack_stop
Event for reset acknowledgment stopped.
Definition engine.hh:151
Support::Event e_search
Event for search (solution found, no more solutions, search stopped)
Definition engine.hh:169
Support::DynamicQueue< Space *, Heap > solutions
Queue of solutions.
Definition engine.hh:171
void stop(void)
Report that worker has been stopped.
Definition engine.hpp:172
void block(void)
Block all workers.
Definition engine.hpp:73
Support::Mutex m_wait_reset
Mutex for waiting for reset.
Definition engine.hh:153
Support::Mutex m_search
Mutex for search.
Definition engine.hh:167
Support::Event e_reset_ack_start
Event for reset acknowledgment started.
Definition engine.hh:149
Cmd cmd(void) const
Return current command.
Definition engine.hpp:68
void release(Cmd c)
Release all workers.
Definition engine.hpp:79
bool signal(void) const
Whether search state changed such that signal is needed.
Definition engine.hpp:147
void terminate(void)
For engine to peform thread termination.
Definition engine.hpp:216
volatile unsigned int n_busy
Number of busy workers.
Definition engine.hh:173
unsigned int workers(void) const
Return number of workers.
Definition engine.hpp:52
@ C_WORK
Perform work.
Definition engine.hh:94
@ C_RESET
Perform reset operation.
Definition engine.hh:96
@ C_WAIT
Run into wait lock.
Definition engine.hh:95
Search tree edge for recomputation
Definition path.hh:66
unsigned int truealt(void) const
Return true number for alternatives (excluding lao optimization)
Definition path.hpp:76
unsigned int nid(void) const
Return node identifier.
Definition path.hpp:70
const Choice * choice(void) const
Return choice.
Definition path.hpp:108
Search engine statistics
Definition search.hh:147
Worker(void)
Initialize.
Definition worker.hh:70
static void engine(SearchTracer *tracer, SearchTracer::EngineType t, unsigned int n)
Register engine.
Computation spaces.
Definition core.hpp:1742
void reset(void)
Reset information.
Definition core.hpp:4690
void wait(void)
Wait until the event becomes signalled.
Definition none.hpp:61
void signal(void)
Signal the event.
Definition none.hpp:59
void release(void)
Release the mutex.
Definition none.hpp:48
void acquire(void)
Acquire the mutex and possibly block.
Definition none.hpp:42
static void run(Runnable *r)
Construct a new thread and run r.
Definition thread.hpp:115
static void sleep(unsigned int ms)
Put current thread to sleep for ms milliseconds.
Definition none.hpp:74
Heap heap
The single global heap.
Definition heap.cpp:44
SpaceStatus status(StatusStatistics &stat=unused_status)
Query space status.
Definition core.cpp:252
Space * clone(CloneStatistics &stat=unused_clone) const
Clone space.
Definition core.hpp:3224
@ SS_BRANCH
Space must be branched (at least one brancher left)
Definition core.hpp:1684
@ SS_SOLVED
Space is solved (no brancher left)
Definition core.hpp:1683
@ SS_FAILED
Space is failed
Definition core.hpp:1682
const unsigned int initial_delay
Initial delay in milliseconds for all but first worker thread.
Definition search.hh:120
Gecode toplevel namespace
void path(Home home, const IntVarArgs &x, IntVar s, IntVar e, IntPropLevel ipl=IPL_DEF)
Post propagator such that x forms a Hamiltonian path.
Definition circuit.cpp:169
#define forceinline
Definition config.hpp:187
#define GECODE_NEVER
Assert that this command is never executed.
Definition macros.hpp:56