Generated on for Gecode by doxygen 1.17.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.dev>
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.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
34namespace Gecode { namespace Search { namespace Par {
35
36 /*
37 * Basic access routines
38 */
39 template<class 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>
56 DFS<Tracer>::Worker::Worker(Space* s, DFS& e, unsigned int index0)
57 : Engine<Tracer>::Worker(s,e), index(index0) {}
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,0U);
69 // All other workers start with no work
70 for (unsigned int i=1; i<workers(); i++)
71 _worker[i] = new Worker(nullptr,*this,i);
72 this->scheduler_enable(_worker[0]->owns_work());
73 // Block all workers
74 block();
75 // Create and start threads
76 for (unsigned int i=0U; i<workers(); i++)
78 }
79
80
81 /*
82 * Reset
83 */
84 template<class Tracer>
85 forceinline void
86 DFS<Tracer>::Worker::reset(Space* s, unsigned int ngdl) {
87 delete cur;
88 tracer.round();
89 path.reset((s != nullptr) ? ngdl : 0);
90 d = 0;
91 idle = false;
92 // Reset the statistics first, so that a failed root is counted
94 if (s == nullptr) {
95 cur = nullptr;
96 } else if (s->status(*this) == SS_FAILED) {
97 fail++;
98 delete s;
99 cur = nullptr;
100 } else {
101 cur = s;
102 }
103 }
104
105 template<class Tracer>
106 forceinline bool
108 return (cur != nullptr) || !path.empty();
109 }
110
111
112 /*
113 * Engine: search control
114 */
115 template<class Tracer>
116 forceinline void
118 m_search.acquire();
119 bool bs = signal();
120 solutions.push(s);
121 if (bs)
122 e_search.signal();
123 m_search.release();
124 }
125
126
127
128 /*
129 * Worker: finding and stealing working
130 */
131 template<class Tracer>
132 forceinline bool
134 // Try to find new work (even if there is none)
135 for (unsigned int i=0U; i<engine().workers(); i++) {
136 unsigned long int r_d = 0ul;
137 typename Engine<Tracer>::Worker* wi = engine().worker(i);
138 if (Space* s = wi->steal(r_d,wi->tracer,tracer)) {
139 // Reset this guy
140 m.acquire();
141 idle = false;
142 // Not idle but also does not have the root of the tree
143 path.ngdl(0);
144 d = 0;
145 cur = s;
146 Statistics t = *this;
148 (*this) += t;
149 m.release();
150 engine().scheduler_owner(index);
151 return true;
152 }
153 }
154 return false;
155 }
156
157 /*
158 * Statistics
159 */
160 template<class Tracer>
163 Statistics s;
164 for (unsigned int i=0U; i<workers(); i++)
165 s += worker(i)->statistics();
166 return s;
167 }
168
169
170 /*
171 * Engine: search control
172 */
173 template<class Tracer>
174 void
176 /*
177 * The engine maintains the following invariant:
178 * - If the current space (cur) is not nullptr, the path always points
179 * to exactly that space.
180 * - If the current space (cur) is nullptr, the path always points
181 * to the next space (if there is any).
182 *
183 * This invariant is needed so that no-goods can be extracted properly
184 * when the engine is stopped or has found a solution.
185 *
186 */
187 // Perform initial delay, if not first worker
188 if (this != engine().worker(0))
190 // Okay, we are in business, start working
191 while (true) {
192 switch (engine().cmd()) {
193 case C_WAIT:
194 // Wait
195 engine().wait();
196 break;
197 case C_TERMINATE:
198 // Acknowledge termination request
199 engine().ack_terminate();
200 // Wait until termination can proceed
201 engine().wait_terminate();
202 // Thread will be terminated by returning from run
203 return;
204 case C_RESET:
205 // Acknowledge reset request
206 engine().ack_reset_start();
207 // Wait until reset has been performed
208 engine().wait_reset();
209 // Acknowledge that reset cycle is over
210 engine().ack_reset_stop();
211 break;
212 case C_WORK:
213 // Perform exploration work
214 {
215 const unsigned long long int run = engine().run();
216 if (engine().scheduler_paused()) {
217 start();
218 if (stop(engine().opt())) {
219 engine().stop(run);
220 break;
221 }
222 }
224 break;
225 m.acquire();
226 if (idle) {
227 m.release();
228 // Try to find new work
229 if (!find()) {
230 engine().scheduler_handoff(index,engine().work_remains());
231 }
232 } else if (cur != nullptr) {
233 start();
234 if (stop(engine().opt())) {
235 // Report stop
236 m.release();
237 engine().stop(run);
238 } else {
239 node++;
241 if (tracer) {
242 if (path.entries() > 0) {
243 typename Path<Tracer>::Edge& top = path.top();
244 ei.init(tracer.wid(), top.nid(), top.truealt(),
245 *cur, *top.choice());
246 } else if (*tracer.ei()) {
247 ei = *tracer.ei();
248 tracer.invalidate();
249 }
250 }
251 unsigned int nid = tracer.nid();
252 switch (cur->status(*this)) {
253 case SS_FAILED:
254 if (tracer) {
256 tracer.wid(), nid, *cur);
257 tracer.node(ei,ni);
258 }
259 fail++;
260 delete cur;
261 cur = nullptr;
262 path.next();
263 m.release();
264 break;
265 case SS_SOLVED:
266 {
267 if (tracer) {
269 tracer.wid(), nid, *cur);
270 tracer.node(ei,ni);
271 }
272 // Deletes all pending branchers
273 (void) cur->choice();
274 Space* s = cur->clone();
275 delete cur;
276 cur = nullptr;
277 path.next();
278 m.release();
279 engine().solution(s);
280 }
281 break;
282 case SS_BRANCH:
283 {
284 Space* c;
285 if ((d == 0) || (d >= engine().opt().c_d)) {
286 c = cur->clone();
287 d = 1;
288 } else {
289 c = nullptr;
290 d++;
291 }
292 const Choice* ch = path.push(*this,cur,c,nid);
293 if (tracer) {
295 tracer.wid(), nid, *cur, ch);
296 tracer.node(ei,ni);
297 }
298 cur->commit(*ch,0);
299 m.release();
300 }
301 break;
302 default:
304 }
305 }
306 } else if (!path.empty()) {
307 cur = path.recompute(d,engine().opt().a_d,*this,tracer);
308 if (cur == nullptr)
309 path.next();
310 m.release();
311 } else {
312 idle = true;
313 path.ngdl(0);
314 m.release();
315 // Report that worker is idle
316 engine().idle();
317 engine().scheduler_idle(index);
318 engine().scheduler_handoff(index,engine().work_remains());
319 }
320 }
321 break;
322 default:
324 }
325 }
326 }
327
328
329 /*
330 * Perform reset
331 *
332 */
333 template<class Tracer>
334 void
336 // Grab wait lock for reset
337 m_wait_reset.acquire();
338 // Release workers for reset
340 // Wait for reset cycle started
341 e_reset_ack_start.wait();
342 // All workers are marked as busy again
343 n_busy = workers();
344 for (unsigned int i=1U; i<workers(); i++)
345 worker(i)->reset(nullptr,0);
346 worker(0U)->reset(s,opt().nogoods_limit);
347 // Block workers again to ensure invariant
348 block();
349 // Release reset lock
350 m_wait_reset.release();
351 // Wait for reset cycle stopped
352 e_reset_ack_stop.wait();
353 this->scheduler_reset(worker(0U)->owns_work());
354 }
355
356
357
358 /*
359 * Create no-goods
360 *
361 */
362 template<class Tracer>
363 NoGoods&
365 NoGoods* ng;
366 // Grab wait lock for reset
367 m_wait_reset.acquire();
368 // Release workers for reset
370 // Wait for reset cycle started
371 e_reset_ack_start.wait();
372 ng = &worker(0)->nogoods();
373 // Block workers again to ensure invariant
374 block();
375 // Release reset lock
376 m_wait_reset.release();
377 // Wait for reset cycle stopped
378 e_reset_ack_stop.wait();
379 return *ng;
380 }
381
382
383 /*
384 * Termination and deletion
385 */
386 template<class Tracer>
388 terminate();
389 heap.rfree(_worker);
390 }
391
392}}}
393
394// STATISTICS: search-par
Choice for performing commit
Definition core.hpp:1430
No-goods recorded from restarts.
Definition core.hpp:1606
void init(unsigned int wid, unsigned int nid, unsigned int a)
Initialize.
Definition tracer.hpp:107
@ FAILED
A solution node.
Definition search.hh:286
@ BRANCH
A failed node.
Definition search.hh:287
@ DFS
Engine is a DFS engine.
Definition search.hh:202
Search engine options
Definition search.hh:848
SearchTracer * tracer
Tracer object for tracing search.
Definition search.hh:879
Parallel depth-first search worker
Definition dfs.hh:66
unsigned int index
Fixed worker index.
Definition dfs.hh:80
Worker(Space *s, DFS &e, unsigned int index)
Initialize for space s with engine e.
Definition dfs.hpp:56
bool owns_work(void) const
Whether this worker currently owns local search.
Definition dfs.hpp:107
void reset(Space *s, unsigned int ngdl)
Reset worker to restart at space s.
Definition dfs.hpp:86
bool find(void)
Try to find some work.
Definition dfs.hpp:133
DFS & engine(void) const
Provide access to engine.
Definition dfs.hpp:41
virtual void run(void)
Start execution of worker.
Definition dfs.hpp:175
Parallel depth-first search engine
Definition dfs.hh:43
virtual Statistics statistics(void) const
Return statistics.
Definition dfs.hpp:162
void solution(Space *s)
Report solution s.
Definition dfs.hpp:117
virtual void reset(Space *s)
Reset engine to restart at space s.
Definition dfs.hpp:335
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:95
virtual NoGoods & nogoods(void)
Return no-goods.
Definition dfs.hpp:364
virtual ~DFS(void)
Destructor.
Definition dfs.hpp:387
Parallel depth-first search worker
Definition engine.hh:55
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
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
const Options & opt(void) const
Provide access to search options.
Definition engine.hpp:51
Support::Event e_reset_ack_stop
Event for reset acknowledgment stopped.
Definition engine.hh:220
Support::Event e_search
Event for search (solution found, no more solutions, search stopped).
Definition engine.hh:238
Support::DynamicQueue< Space *, Heap > solutions
Queue of solutions.
Definition engine.hh:240
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
Support::Event e_reset_ack_start
Event for reset acknowledgment started.
Definition engine.hh:218
Cmd cmd(void) const
Return current command.
Definition engine.hpp:72
Engine(const Options &o)
Initialize with options o.
Definition engine.hpp:123
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 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
volatile unsigned int n_busy
Number of busy workers.
Definition engine.hh:242
unsigned int workers(void) const
Return number of workers.
Definition engine.hpp:56
@ 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
bool work_remains(void)
Whether logical search work remains.
Definition engine.hpp:401
Search tree edge for recomputation
Definition path.hh:70
unsigned int truealt(void) const
Return true number for alternatives (excluding lao optimization).
Definition path.hpp:80
unsigned int nid(void) const
Return node identifier.
Definition path.hpp:74
const Choice * choice(void) const
Return choice.
Definition path.hpp:112
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
unsigned long long int node
Number of nodes expanded.
Definition search.hh:160
void start(void)
Reset stop information.
Definition worker.hh:76
Worker(void)
Initialize.
Definition worker.hh:72
static void engine(SearchTracer *tracer, SearchTracer::EngineType t, unsigned int n)
Register engine.
Computation spaces.
Definition core.hpp:1787
void reset(void)
Reset information.
Definition core.hpp:4974
static void run(Runnable *r)
Construct a new thread and run r.
Definition thread.hpp:177
static void sleep(unsigned int ms)
Put current thread to sleep for ms milliseconds.
Definition thread.hpp:156
Heap heap
The single global heap.
Definition heap.cpp:44
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
const unsigned int initial_delay
Initial delay in milliseconds for all but first worker thread.
Definition search.hh:128
Search engines
Gecode toplevel namespace
#define forceinline
Definition config.hpp:144
#define GECODE_NEVER
Assert that this command is never executed.
Definition macros.hpp:56