Generated on Thu Apr 5 2018 19:44:19 for Gecode by doxygen 1.8.13
tracer.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.org>
5  *
6  * Copyright:
7  * Christian Schulte, 2017
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 #include <climits>
39 
40 namespace Gecode {
41 
42  /*
43  * Engine information
44  *
45  */
48 
51  unsigned int fst, unsigned int lst)
52  : _type(et), _fst(fst), _lst(lst) {}
53 
56  return _type;
57  }
58 
59  forceinline bool
61  return (type() == EngineType::RBS) || (type() == EngineType::PBS);
62  }
63 
64  forceinline unsigned int
66  assert((type() == EngineType::DFS) || (type() == EngineType::BAB) ||
67  (type() == EngineType::LDS) || (type() == EngineType::AOE));
68  return _fst;
69  }
70 
71  forceinline unsigned int
73  assert((type() == EngineType::DFS) || (type() == EngineType::BAB) ||
74  (type() == EngineType::LDS) || (type() == EngineType::AOE));
75  return _lst;
76  }
77 
78  forceinline unsigned int
80  return wlst() - wfst();
81  }
82 
83  forceinline unsigned int
85  assert((type() == EngineType::RBS) || (type() == EngineType::PBS));
86  return _fst;
87  }
88 
89  forceinline unsigned int
91  assert((type() == EngineType::RBS) || (type() == EngineType::PBS));
92  return _lst;
93  }
94 
96  unsigned int SearchTracer::EngineInfo::engines(void) const {
97  return elst() - efst();
98  }
99 
100 
101  /*
102  * Edge information
103  *
104  */
105  forceinline void
107  _wid=UINT_MAX; _s.clear();
108  }
109 
110  forceinline void
111  SearchTracer::EdgeInfo::init(unsigned int wid, unsigned int nid,
112  unsigned int a) {
113  _wid=wid; _nid=nid; _a=a; _s="";
114  }
115 
116  forceinline void
117  SearchTracer::EdgeInfo::init(unsigned int wid, unsigned int nid,
118  unsigned int a,
119  const Space& s, const Choice& c) {
120  _wid=wid; _nid=nid; _a=a;
121  std::ostringstream os;
122  s.print(c, a, os); _s = os.str();
123  }
124 
126  SearchTracer::EdgeInfo::EdgeInfo(unsigned int wid, unsigned int nid,
127  unsigned int a)
128  : _wid(wid), _nid(nid), _a(a) {}
129 
132  : _wid(UINT_MAX) {}
133 
135  SearchTracer::EdgeInfo::operator bool(void) const {
136  return _wid != UINT_MAX;
137  }
138 
139  forceinline unsigned int
141  assert(*this);
142  return _wid;
143  }
144 
145  forceinline unsigned int
147  assert(*this);
148  return _nid;
149  }
150 
151  forceinline unsigned int
153  assert(*this);
154  return _a;
155  }
156 
157  forceinline std::string
159  assert(*this);
160  return _s;
161  }
162 
163 
164  /*
165  * Node information
166  *
167  */
170  unsigned int wid, unsigned int nid,
171  const Space& s, const Choice* c)
172  : _nt(nt), _wid(wid), _nid(nid), _s(s), _c(c) {}
173 
176  return _nt;
177  }
178 
179  forceinline unsigned int
181  return _wid;
182  }
183 
184  forceinline unsigned int
186  return _nid;
187  }
188 
189  forceinline const Space&
191  return _s;
192  }
193 
194  forceinline const Choice&
196  assert(_nt == NodeType::BRANCH);
197  return *_c;
198  }
199 
200 
201  /*
202  * The actual tracer
203  *
204  */
205  forceinline void
206  SearchTracer::_round(unsigned int eid) {
207  m.acquire();
208  round(eid);
209  m.release();
210  }
211 
212  forceinline void
213  SearchTracer::_skip(const EdgeInfo& ei) {
214  m.acquire();
215  skip(ei);
216  m.release();
217  }
218 
219  forceinline void
220  SearchTracer::_node(const EdgeInfo& ei, const NodeInfo& ni) {
221  m.acquire();
222  node(ei,ni);
223  m.release();
224  }
225 
228  : pending(1U), n_e(0U), n_w(0U), es(heap), w2e(heap) {}
229 
230  forceinline void
231  SearchTracer::engine(EngineType t, unsigned int n) {
232  assert(pending > 0);
233  pending += n-1;
234  switch (t) {
235  case EngineType::PBS: case EngineType::RBS:
236  es[n_e]=EngineInfo(t,n_e+1,n_e+1+n);
237  break;
238  case EngineType::DFS: case EngineType::BAB:
239  case EngineType::LDS: case EngineType::AOE:
240  es[n_e]=EngineInfo(t,n_w,n_w+n);
241  break;
242  default: GECODE_NEVER;
243  }
244  n_e++;
245  assert(pending > 0);
246  }
247 
248  forceinline void
249  SearchTracer::worker(unsigned int& wid, unsigned int& eid) {
250  assert(pending > 0);
251  pending--;
252  w2e[n_w]=eid=n_e-1;
253  wid=n_w++;
254  if (pending == 0) {
255  n_active = n_w;
256  init();
257  }
258  }
259 
260  forceinline void
261  SearchTracer::worker(void) {
262  m.acquire();
263  if (--n_active == 0U) {
264  done();
265  }
266  m.release();
267  }
268 
269  forceinline unsigned int
270  SearchTracer::workers(void) const {
271  return n_w;
272  }
273 
274  forceinline unsigned int
275  SearchTracer::engines(void) const {
276  return n_e;
277  }
278 
280  SearchTracer::engine(unsigned int eid) const {
281  assert(eid < n_e);
282  return es[eid];
283  }
284 
285 
286  forceinline unsigned int
287  SearchTracer::eid(unsigned int wid) const {
288  assert(wid < n_w);
289  return w2e[wid];
290  }
291 
294 
295 }
296 
297 // STATISTICS: search-trace
Edge information.
Definition: search.hh:244
unsigned int elst(void) const
Return id of last engine.
Definition: tracer.hpp:90
const Space & _s
The corresponding space.
Definition: search.hh:293
const Choice * _c
The corresponding choice (nullptr if type is not BRANCH)
Definition: search.hh:295
unsigned int nid(void) const
Return node id.
Definition: tracer.hpp:185
NodeType t
Type of node.
Definition: bool-expr.cpp:234
virtual void node(const EdgeInfo &ei, const NodeInfo &ni)=0
The engine creates a new node with information ei and ni.
unsigned int eid(unsigned int wid) const
Return the engine id of a worker with id wid.
Definition: tracer.hpp:287
EdgeInfo(void)
Initialize as non existing.
Definition: tracer.hpp:131
Node representing a branch.
Definition: spacenode.hh:51
EngineType type(void) const
Return engine type.
Definition: tracer.hpp:55
unsigned int engines(void) const
Return number of engines.
Definition: tracer.hpp:96
unsigned int _nid
The parent node id.
Definition: search.hh:249
std::string _s
String corresponding to alternative.
Definition: search.hh:253
bool meta(void) const
Return whether engine is a meta engine.
Definition: tracer.hpp:60
const Choice & choice(void) const
Return corresponding choice.
Definition: tracer.hpp:195
void acquire(void)
Acquire the mutex and possibly block.
Definition: none.hpp:46
unsigned int wid(void) const
Return parent worker id.
Definition: tracer.hpp:140
Multi _c(Gecode::IntArgs(3, 1, 2, 3))
unsigned int wlst(void) const
Return id of last worker plus one.
Definition: tracer.hpp:72
unsigned int engines(void) const
Return number of engines.
Definition: tracer.hpp:275
virtual void skip(const EdgeInfo &ei)=0
The engine skips an edge.
#define forceinline
Definition: config.hpp:182
EngineType
Which type of engine.
Definition: search.hh:195
Computation spaces.
Definition: core.hpp:1668
std::string string(void) const
Return string for alternative.
Definition: tracer.hpp:158
void release(void)
Release the mutex.
Definition: none.hpp:52
Gecode::FloatVal c(-8, 8)
Single _a(2, 3)
void print(const Choice &c, unsigned int a, std::ostream &o) const
Print branch for choice c and alternative a.
Definition: core.cpp:624
void init(unsigned int wid, unsigned int nid, unsigned int a)
Initialize.
Definition: tracer.hpp:111
int n
Number of negative literals for node type.
Definition: bool-expr.cpp:238
unsigned int efst(void) const
Return id of first engine.
Definition: tracer.hpp:84
EngineType _type
The engine type.
Definition: search.hh:207
NodeType type(void) const
Return node type.
Definition: tracer.hpp:175
unsigned int _a
Number of alternative.
Definition: search.hh:251
unsigned int nid(void) const
Return parent node id.
Definition: tracer.hpp:146
SearchTracer(void)
Initialize.
Definition: tracer.hpp:227
virtual void init(void)=0
The search engine initializes.
unsigned int _lst
Last worker or engine.
Definition: search.hh:211
NodeInfo(NodeType nt, unsigned int wid, unsigned int nid, const Space &s, const Choice *c=nullptr)
Initialize node info.
Definition: tracer.hpp:169
EngineInfo(void)
Do not initialize.
Definition: tracer.hpp:47
virtual ~SearchTracer(void)
Delete.
Definition: tracer.hpp:293
virtual void round(unsigned int eid)=0
The engine with id eid goes to a next round (restart or next iteration in LDS)
struct Gecode::@585::NNF::@62::@64 a
For atomic nodes.
Choice for performing commit
Definition: core.hpp:1338
unsigned int alternative(void) const
Return number of alternative.
Definition: tracer.hpp:152
unsigned int workers(void) const
Return number of workers.
Definition: tracer.hpp:79
unsigned int workers(void) const
Return number of workers.
Definition: tracer.hpp:270
unsigned int wid(void) const
Return worker id.
Definition: tracer.hpp:180
Heap heap
The single global heap.
Definition: heap.cpp:48
virtual void done(void)=0
All workers are done.
unsigned int _wid
The worker id.
Definition: search.hh:289
Node information.
Definition: search.hh:284
NodeType
Node type.
Definition: search.hh:278
unsigned int _nid
The node id.
Definition: search.hh:291
unsigned int wfst(void) const
Return id of first worker.
Definition: tracer.hpp:65
Gecode toplevel namespace
Information about an engine.
Definition: search.hh:204
void invalidate(void)
Invalidate edge information (for stealing)
Definition: tracer.hpp:106
unsigned int _wid
The parent worker id (edge does not exist if UINT_MAX)
Definition: search.hh:247
NodeType _nt
The node type.
Definition: search.hh:287
#define GECODE_NEVER
Assert that this command is never executed.
Definition: macros.hpp:60
unsigned int _fst
First worker or engine.
Definition: search.hh:209
const Space & space(void) const
Return corresponding space.
Definition: tracer.hpp:190