Generated on Tue Feb 11 2025 17:33:26 for Gecode by doxygen 1.12.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.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
34#ifndef __GECODE_SEARCH_PAR_ENGINE_HH__
35#define __GECODE_SEARCH_PAR_ENGINE_HH__
36
37#include <gecode/search.hh>
41
42namespace Gecode { namespace Search { namespace Par {
43
45 template<class Tracer>
46 class Engine : public Search::Engine, public Support::Terminator {
47 protected:
49 class Worker : public Search::Worker, public Support::Runnable {
50 public:
53 protected:
63 unsigned int d;
65 bool idle;
66 public:
68 Worker(Space* s, Engine& e);
70 Space* steal(unsigned long int& d, Tracer& myt, Tracer& ot);
74 Engine& engine(void) const;
76 NoGoods& nogoods(void);
78 virtual ~Worker(void);
80 virtual Support::Terminator* terminator(void) const;
81 };
84 public:
86 const Options& opt(void) const;
88 unsigned int workers(void) const;
89
91
92
99 protected:
101 volatile Cmd _cmd;
104 public:
106 Cmd cmd(void) const;
108 void block(void);
110 void release(Cmd c);
112 void wait(void);
114
116
117 protected:
121 volatile unsigned int _n_term_not_ack;
127 volatile unsigned int _n_not_terminated;
130 public:
132 void ack_terminate(void);
134 virtual void terminated(void);
136 void wait_terminate(void);
138 void terminate(void);
140
142
143 protected:
147 volatile unsigned int _n_reset_not_ack;
154 public:
156 void ack_reset_start(void);
158 void ack_reset_stop(void);
160 void wait_reset(void);
162
164
165 protected:
173 volatile unsigned int n_busy;
175 volatile bool has_stopped;
177 bool signal(void) const;
178 public:
180 void idle(void);
182 void busy(void);
184 void stop(void);
186
188
189
190 Engine(const Options& o);
192 virtual Space* next(void);
194 virtual bool stopped(void) const;
196 };
197
198}}}
199
201
202#endif
203
204// STATISTICS: search-par
No-goods recorded from restarts.
Definition core.hpp:1588
Search engine implementation interface
Definition search.hh:899
Search engine options
Definition search.hh:746
Parallel depth-first search worker
Definition engine.hh:49
Support::Mutex m
Mutex for access to worker.
Definition engine.hh:57
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
virtual ~Worker(void)
Destructor.
Definition engine.hpp:358
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
virtual Support::Terminator * terminator(void) const
Terminator (engine)
Definition engine.hpp:350
Engine & engine(void) const
Provide access to engine.
Definition engine.hpp:42
Parallel depth-first search engine
Definition engine.hh:46
void idle(void)
Report that worker is idle.
Definition engine.hpp:152
void wait(void)
Ensure that worker waits.
Definition engine.hpp:85
Support::Event _e_terminate
Event for termination (all threads have terminated)
Definition engine.hh:129
void ack_reset_stop(void)
For worker to acknowledge stop of reset cycle.
Definition engine.hpp:244
const Options & opt(void) const
Provide access to search options.
Definition engine.hpp:47
Support::Mutex _m_wait_terminate
Mutex for waiting for termination.
Definition engine.hh:125
Support::Event e_reset_ack_stop
Event for reset acknowledgment stopped.
Definition engine.hh:151
Support::Mutex _m_wait
Mutex for forcing workers to wait.
Definition engine.hh:103
Support::Event e_search
Event for search (solution found, no more solutions, search stopped)
Definition engine.hh:169
volatile bool has_stopped
Whether a worker had been stopped.
Definition engine.hh:175
virtual Space * next(void)
Return next solution (NULL, if none exists or search has been stopped)
Definition engine.hpp:298
Support::Event _e_term_ack
Event for termination acknowledgment.
Definition engine.hh:123
Support::DynamicQueue< Space *, Heap > solutions
Queue of solutions.
Definition engine.hh:171
virtual bool stopped(void) const
Check whether engine has been stopped.
Definition engine.hpp:57
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
Support::Mutex _m_term
Mutex for access to termination information.
Definition engine.hh:119
Cmd cmd(void) const
Return current command.
Definition engine.hpp:68
Engine(const Options &o)
Initialize with options o.
Definition engine.hpp:116
Options _opt
Search options.
Definition engine.hh:83
void busy(void)
Report that worker is busy.
Definition engine.hpp:163
volatile Cmd _cmd
The current command.
Definition engine.hh:101
volatile unsigned int _n_reset_not_ack
Number of workers that have not yet acknowledged reset.
Definition engine.hh:147
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 ack_reset_start(void)
For worker to acknowledge start of reset cycle.
Definition engine.hpp:235
volatile unsigned int _n_term_not_ack
Number of workers that have not yet acknowledged termination.
Definition engine.hh:121
void wait_reset(void)
For worker to wait for all workers to reset.
Definition engine.hpp:253
volatile unsigned int _n_not_terminated
Number of not yet terminated workers.
Definition engine.hh:127
virtual void terminated(void)
For worker to register termination.
Definition engine.hpp:187
void terminate(void)
For engine to peform thread termination.
Definition engine.hpp:216
Support::Mutex _m_reset
Mutex for access to reset information.
Definition engine.hh:145
volatile unsigned int n_busy
Number of busy workers.
Definition engine.hh:173
void wait_terminate(void)
For worker to wait until termination is legal.
Definition engine.hpp:209
unsigned int workers(void) const
Return number of workers.
Definition engine.hpp:52
Cmd
Commands from engine to workers.
Definition engine.hh:93
@ 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
void ack_terminate(void)
For worker to acknowledge termination command.
Definition engine.hpp:200
Depth-first path (stack of edges) supporting recomputation.
Definition path.hh:60
Search engine statistics
Definition search.hh:147
Search worker statistics
Definition worker.hh:44
Worker(void)
Initialize.
Definition worker.hh:70
Computation spaces.
Definition core.hpp:1742
Queue with arbitrary number of elements.
An event for synchronization.
Definition thread.hpp:215
A mutex for mutual exclausion among several threads.
Definition thread.hpp:96
An interface for objects that can be run by a thread.
Definition thread.hpp:264
An interface for objects that can be called after a thread has terminated (after running the thread's...
Definition thread.hpp:251
Gecode toplevel namespace