Generated on Thu Apr 5 2018 19:44:19 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  * Last modified:
10  * $Date$ by $Author$
11  * $Revision$
12  *
13  * This file is part of Gecode, the generic constraint
14  * development environment:
15  * http://www.gecode.org
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_ENGINE_HH__
39 #define __GECODE_SEARCH_PAR_ENGINE_HH__
40 
41 #include <gecode/search.hh>
42 #include <gecode/search/support.hh>
43 #include <gecode/search/worker.hh>
45 
46 namespace Gecode { namespace Search { namespace Par {
47 
49  template<class Tracer>
50  class Engine : public Search::Engine, public Support::Terminator {
51  protected:
53  class Worker : public Search::Worker, public Support::Runnable {
54  public:
57  protected:
67  unsigned int d;
69  bool idle;
70  public:
72  Worker(Space* s, Engine& e);
74  Space* steal(unsigned long int& d, Tracer& myt, Tracer& ot);
76  Statistics statistics(void);
78  Engine& engine(void) const;
80  NoGoods& nogoods(void);
82  virtual ~Worker(void);
84  virtual Support::Terminator* terminator(void) const;
85  };
88  public:
90  const Options& opt(void) const;
92  unsigned int workers(void) const;
93 
95 
96  enum Cmd {
102  };
103  protected:
105  volatile Cmd _cmd;
108  public:
110  Cmd cmd(void) const;
112  void block(void);
114  void release(Cmd c);
116  void wait(void);
118 
120 
121  protected:
125  volatile unsigned int _n_term_not_ack;
131  volatile unsigned int _n_not_terminated;
134  public:
136  void ack_terminate(void);
138  virtual void terminated(void);
140  void wait_terminate(void);
142  void terminate(void);
144 
146 
147  protected:
151  volatile unsigned int _n_reset_not_ack;
158  public:
160  void ack_reset_start(void);
162  void ack_reset_stop(void);
164  void wait_reset(void);
166 
168 
169  protected:
177  volatile unsigned int n_busy;
179  volatile bool has_stopped;
181  bool signal(void) const;
182  public:
184  void idle(void);
186  void busy(void);
188  void stop(void);
190 
192 
193  Engine(const Options& o);
196  virtual Space* next(void);
198  virtual bool stopped(void) const;
200  };
201 
202 }}}
203 
205 
206 #endif
207 
208 // STATISTICS: search-par
virtual Space * next(void)
Return next solution (NULL, if none exists or search has been stopped)
Definition: engine.hpp:302
Statistics statistics(void)
Return statistics.
Definition: engine.hpp:138
Support::Event e_reset_ack_stop
Event for reset acknowledgment stopped.
Definition: engine.hh:155
Worker(void)
Initialize.
Definition: worker.hh:74
virtual ~Worker(void)
Destructor.
Definition: engine.hpp:362
void ack_terminate(void)
For worker to acknowledge termination command.
Definition: engine.hpp:204
Search engine implementation interface
Definition: search.hh:901
Path< Tracer > path
Current path ins search tree.
Definition: engine.hh:63
unsigned int workers(void) const
Return number of workers.
Definition: engine.hpp:56
Search engine statistics
Definition: search.hh:149
Support::Event e_reset_ack_start
Event for reset acknowledgment started.
Definition: engine.hh:153
void terminate(void)
For engine to peform thread termination.
Definition: engine.hpp:220
Search engine options
Definition: search.hh:748
An interface for objects that can be run by a thread.
Definition: thread.hpp:267
volatile bool has_stopped
Whether a worker had been stopped.
Definition: engine.hh:179
void wait_terminate(void)
For worker to wait until termination is legal.
Definition: engine.hpp:213
bool signal(void) const
Whether search state changed such that signal is needed.
Definition: engine.hpp:151
Engine & _engine
Reference to engine.
Definition: engine.hh:59
Support::Mutex _m_term
Mutex for access to termination information.
Definition: engine.hh:123
Support::Mutex m_search
Mutex for search.
Definition: engine.hh:171
void ack_reset_stop(void)
For worker to acknowledge stop of reset cycle.
Definition: engine.hpp:248
bool stopped(void) const
Check whether engine has been stopped.
Definition: worker.hh:91
Parallel depth-first search engine
Definition: engine.hh:50
volatile unsigned int _n_reset_not_ack
Number of workers that have not yet acknowledged reset.
Definition: engine.hh:151
Perform reset operation.
Definition: engine.hh:100
Computation spaces.
Definition: core.hpp:1668
A mutex for mutual exclausion among several threads.
Definition: thread.hpp:105
Cmd
Commands from engine to workers.
Definition: engine.hh:97
Gecode::FloatVal c(-8, 8)
An event for synchronization.
Definition: thread.hpp:218
Space * cur
Current space being explored.
Definition: engine.hh:65
Engine(const Options &o)
Initialize with options o.
Definition: engine.hpp:120
Cmd cmd(void) const
Return current command.
Definition: engine.hpp:72
Support::Mutex m
Mutex for access to worker.
Definition: engine.hh:61
Options _opt
Search options.
Definition: engine.hh:87
void wait(void)
Ensure that worker waits.
Definition: engine.hpp:89
volatile unsigned int _n_term_not_ack
Number of workers that have not yet acknowledged termination.
Definition: engine.hh:125
Run into wait lock.
Definition: engine.hh:99
Support::Mutex m_wait_reset
Mutex for waiting for reset.
Definition: engine.hh:157
void release(Cmd c)
Release all workers.
Definition: engine.hpp:83
bool idle
Whether the worker is idle.
Definition: engine.hh:69
Space * steal(unsigned long int &d, Tracer &myt, Tracer &ot)
Hand over some work (NULL if no work available)
Definition: engine.hpp:269
Support::Mutex _m_reset
Mutex for access to reset information.
Definition: engine.hh:149
void busy(void)
Report that worker is busy.
Definition: engine.hpp:167
Search worker statistics
Definition: worker.hh:48
const Options & opt(void) const
Provide access to search options.
Definition: engine.hpp:51
unsigned int d
Distance until next clone.
Definition: engine.hh:67
Queue with arbitrary number of elements.
Support::Event e_search
Event for search (solution found, no more solutions, search stopped)
Definition: engine.hh:173
Support::DynamicQueue< Space *, Heap > solutions
Queue of solutions.
Definition: engine.hh:175
Support::Mutex _m_wait_terminate
Mutex for waiting for termination.
Definition: engine.hh:129
No-goods recorded from restarts.
Definition: core.hpp:1514
Engine & engine(void) const
Provide access to engine.
Definition: engine.hpp:46
void wait_reset(void)
For worker to wait for all workers to reset.
Definition: engine.hpp:257
Tracer.
Definition: tracer.hpp:153
volatile Cmd _cmd
The current command.
Definition: engine.hh:105
NoGoods & nogoods(void)
Return no-goods.
Definition: engine.hpp:293
void ack_reset_start(void)
For worker to acknowledge start of reset cycle.
Definition: engine.hpp:239
An interface for objects that can be called after a thread has terminated (after running the thread&#39;s...
Definition: thread.hpp:254
Support::Event _e_terminate
Event for termination (all threads have terminated)
Definition: engine.hh:133
Gecode toplevel namespace
virtual void terminated(void)
For worker to register termination.
Definition: engine.hpp:191
volatile unsigned int n_busy
Number of busy workers.
Definition: engine.hh:177
volatile unsigned int _n_not_terminated
Number of not yet terminated workers.
Definition: engine.hh:131
virtual Support::Terminator * terminator(void) const
Terminator (engine)
Definition: engine.hpp:354
void block(void)
Block all workers.
Definition: engine.hpp:77
Tracer tracer
Search tracer.
Definition: engine.hh:56
Support::Mutex _m_wait
Mutex for forcing workers to wait.
Definition: engine.hh:107
Depth-first path (stack of edges) supporting recomputation.
Definition: path.hh:64
Support::Event _e_term_ack
Event for termination acknowledgment.
Definition: engine.hh:127
bool stop(const Options &o)
Check whether engine must be stopped.
Definition: worker.hh:83
Parallel depth-first search worker
Definition: engine.hh:53