Generated on Sat Jan 12 2019 20:58:51 for Gecode by doxygen 1.8.13
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>
38 #include <gecode/search/support.hh>
39 #include <gecode/search/worker.hh>
41 
42 namespace 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);
72  Statistics statistics(void);
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  enum Cmd {
98  };
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  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
virtual Space * next(void)
Return next solution (NULL, if none exists or search has been stopped)
Definition: engine.hpp:298
Statistics statistics(void)
Return statistics.
Definition: engine.hpp:134
Support::Event e_reset_ack_stop
Event for reset acknowledgment stopped.
Definition: engine.hh:151
Worker(void)
Initialize.
Definition: worker.hh:70
virtual ~Worker(void)
Destructor.
Definition: engine.hpp:358
void ack_terminate(void)
For worker to acknowledge termination command.
Definition: engine.hpp:200
Search engine implementation interface
Definition: search.hh:899
Path< Tracer > path
Current path ins search tree.
Definition: engine.hh:59
unsigned int workers(void) const
Return number of workers.
Definition: engine.hpp:52
Search engine statistics
Definition: search.hh:147
Support::Event e_reset_ack_start
Event for reset acknowledgment started.
Definition: engine.hh:149
void terminate(void)
For engine to peform thread termination.
Definition: engine.hpp:216
Search engine options
Definition: search.hh:746
An interface for objects that can be run by a thread.
Definition: thread.hpp:264
volatile bool has_stopped
Whether a worker had been stopped.
Definition: engine.hh:175
void wait_terminate(void)
For worker to wait until termination is legal.
Definition: engine.hpp:209
bool signal(void) const
Whether search state changed such that signal is needed.
Definition: engine.hpp:147
Engine & _engine
Reference to engine.
Definition: engine.hh:55
Support::Mutex _m_term
Mutex for access to termination information.
Definition: engine.hh:119
Support::Mutex m_search
Mutex for search.
Definition: engine.hh:167
void ack_reset_stop(void)
For worker to acknowledge stop of reset cycle.
Definition: engine.hpp:244
bool stopped(void) const
Check whether engine has been stopped.
Definition: worker.hh:87
Parallel depth-first search engine
Definition: engine.hh:46
volatile unsigned int _n_reset_not_ack
Number of workers that have not yet acknowledged reset.
Definition: engine.hh:147
Perform reset operation.
Definition: engine.hh:96
Computation spaces.
Definition: core.hpp:1701
A mutex for mutual exclausion among several threads.
Definition: thread.hpp:96
Cmd
Commands from engine to workers.
Definition: engine.hh:93
Gecode::FloatVal c(-8, 8)
An event for synchronization.
Definition: thread.hpp:215
Space * cur
Current space being explored.
Definition: engine.hh:61
Engine(const Options &o)
Initialize with options o.
Definition: engine.hpp:116
Cmd cmd(void) const
Return current command.
Definition: engine.hpp:68
Support::Mutex m
Mutex for access to worker.
Definition: engine.hh:57
Options _opt
Search options.
Definition: engine.hh:83
void wait(void)
Ensure that worker waits.
Definition: engine.hpp:85
volatile unsigned int _n_term_not_ack
Number of workers that have not yet acknowledged termination.
Definition: engine.hh:121
Run into wait lock.
Definition: engine.hh:95
Support::Mutex m_wait_reset
Mutex for waiting for reset.
Definition: engine.hh:153
void release(Cmd c)
Release all workers.
Definition: engine.hpp:79
bool idle
Whether the worker is idle.
Definition: engine.hh:65
Space * steal(unsigned long int &d, Tracer &myt, Tracer &ot)
Hand over some work (NULL if no work available)
Definition: engine.hpp:265
Support::Mutex _m_reset
Mutex for access to reset information.
Definition: engine.hh:145
void busy(void)
Report that worker is busy.
Definition: engine.hpp:163
Search worker statistics
Definition: worker.hh:44
const Options & opt(void) const
Provide access to search options.
Definition: engine.hpp:47
unsigned int d
Distance until next clone.
Definition: engine.hh:63
Queue with arbitrary number of elements.
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
Support::Mutex _m_wait_terminate
Mutex for waiting for termination.
Definition: engine.hh:125
No-goods recorded from restarts.
Definition: core.hpp:1547
Engine & engine(void) const
Provide access to engine.
Definition: engine.hpp:42
void wait_reset(void)
For worker to wait for all workers to reset.
Definition: engine.hpp:253
Tracer.
Definition: tracer.hpp:149
volatile Cmd _cmd
The current command.
Definition: engine.hh:101
NoGoods & nogoods(void)
Return no-goods.
Definition: engine.hpp:289
void ack_reset_start(void)
For worker to acknowledge start of reset cycle.
Definition: engine.hpp:235
An interface for objects that can be called after a thread has terminated (after running the thread&#39;s...
Definition: thread.hpp:251
Support::Event _e_terminate
Event for termination (all threads have terminated)
Definition: engine.hh:129
Gecode toplevel namespace
virtual void terminated(void)
For worker to register termination.
Definition: engine.hpp:187
volatile unsigned int n_busy
Number of busy workers.
Definition: engine.hh:173
volatile unsigned int _n_not_terminated
Number of not yet terminated workers.
Definition: engine.hh:127
virtual Support::Terminator * terminator(void) const
Terminator (engine)
Definition: engine.hpp:350
void block(void)
Block all workers.
Definition: engine.hpp:73
Tracer tracer
Search tracer.
Definition: engine.hh:52
Support::Mutex _m_wait
Mutex for forcing workers to wait.
Definition: engine.hh:103
Depth-first path (stack of edges) supporting recomputation.
Definition: path.hh:60
Support::Event _e_term_ack
Event for termination acknowledgment.
Definition: engine.hh:123
bool stop(const Options &o)
Check whether engine must be stopped.
Definition: worker.hh:79
Parallel depth-first search worker
Definition: engine.hh:49