this repo has no description
dekker.one
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>
40#include <gecode/search/par/path.hh>
41
42namespace Gecode { namespace Search { namespace Par {
43
44 /// %Parallel depth-first search engine
45 template<class Tracer>
46 class Engine : public Search::Engine, public Support::Terminator {
47 protected:
48 /// %Parallel depth-first search worker
49 class Worker : public Search::Worker, public Support::Runnable {
50 public:
51 /// Search tracer
52 Tracer tracer;
53 protected:
54 /// Reference to engine
55 Engine& _engine;
56 /// Mutex for access to worker
57 Support::Mutex m;
58 /// Current path ins search tree
59 Path<Tracer> path;
60 /// Current space being explored
61 Space* cur;
62 /// Distance until next clone
63 unsigned int d;
64 /// Whether the worker is idle
65 bool idle;
66 public:
67 /// Initialize for space \a s with engine \a e
68 Worker(Space* s, Engine& e);
69 /// Hand over some work (nullptr if no work available)
70 Space* steal(unsigned long int& d, Tracer& myt, Tracer& ot);
71 /// Return statistics
72 Statistics statistics(void);
73 /// Provide access to engine
74 Engine& engine(void) const;
75 /// Return no-goods
76 NoGoods& nogoods(void);
77 /// Destructor
78 virtual ~Worker(void);
79 /// Terminator (engine)
80 virtual Support::Terminator* terminator(void) const;
81 };
82 /// Search options
83 Options _opt;
84 public:
85 /// Provide access to search options
86 const Options& opt(void) const;
87 /// Return number of workers
88 unsigned int workers(void) const;
89
90 /// \name Commands from engine to workers and wait management
91 //@{
92 /// Commands from engine to workers
93 enum Cmd {
94 C_WORK, ///< Perform work
95 C_WAIT, ///< Run into wait lock
96 C_RESET, ///< Perform reset operation
97 C_TERMINATE ///< Terminate
98 };
99 protected:
100 /// The current command
101 volatile Cmd _cmd;
102 /// Mutex for forcing workers to wait
103 Support::Mutex _m_wait;
104 public:
105 /// Return current command
106 Cmd cmd(void) const;
107 /// Block all workers
108 void block(void);
109 /// Release all workers
110 void release(Cmd c);
111 /// Ensure that worker waits
112 void wait(void);
113 //@}
114
115 /// \name Termination control
116 //@{
117 protected:
118 /// Mutex for access to termination information
119 Support::Mutex _m_term;
120 /// Number of workers that have not yet acknowledged termination
121 volatile unsigned int _n_term_not_ack;
122 /// Event for termination acknowledgment
123 Support::Event _e_term_ack;
124 /// Mutex for waiting for termination
125 Support::Mutex _m_wait_terminate;
126 /// Number of not yet terminated workers
127 volatile unsigned int _n_not_terminated;
128 /// Event for termination (all threads have terminated)
129 Support::Event _e_terminate;
130 public:
131 /// For worker to acknowledge termination command
132 void ack_terminate(void);
133 /// For worker to register termination
134 virtual void terminated(void);
135 /// For worker to wait until termination is legal
136 void wait_terminate(void);
137 /// For engine to peform thread termination
138 void terminate(void);
139 //@}
140
141 /// \name Reset control
142 //@{
143 protected:
144 /// Mutex for access to reset information
145 Support::Mutex _m_reset;
146 /// Number of workers that have not yet acknowledged reset
147 volatile unsigned int _n_reset_not_ack;
148 /// Event for reset acknowledgment started
149 Support::Event e_reset_ack_start;
150 /// Event for reset acknowledgment stopped
151 Support::Event e_reset_ack_stop;
152 /// Mutex for waiting for reset
153 Support::Mutex m_wait_reset;
154 public:
155 /// For worker to acknowledge start of reset cycle
156 void ack_reset_start(void);
157 /// For worker to acknowledge stop of reset cycle
158 void ack_reset_stop(void);
159 /// For worker to wait for all workers to reset
160 void wait_reset(void);
161 //@}
162
163 /// \name Search control
164 //@{
165 protected:
166 /// Mutex for search
167 Support::Mutex m_search;
168 /// Event for search (solution found, no more solutions, search stopped)
169 Support::Event e_search;
170 /// Queue of solutions
171 Support::DynamicQueue<Space*,Heap> solutions;
172 /// Number of busy workers
173 volatile unsigned int n_busy;
174 /// Whether a worker had been stopped
175 volatile bool has_stopped;
176 /// Whether search state changed such that signal is needed
177 bool signal(void) const;
178 public:
179 /// Report that worker is idle
180 void idle(void);
181 /// Report that worker is busy
182 void busy(void);
183 /// Report that worker has been stopped
184 void stop(void);
185 //@}
186
187 /// \name Engine interface
188 //@{
189 /// Initialize with options \a o
190 Engine(const Options& o);
191 /// Return next solution (nullptr, if none exists or search has been stopped)
192 virtual Space* next(void);
193 /// Check whether engine has been stopped
194 virtual bool stopped(void) const;
195 //@}
196 };
197
198}}}
199
200#include <gecode/search/par/engine.hpp>
201
202#endif
203
204// STATISTICS: search-par