Generated on Thu Mar 16 2017 03:24:22 for Gecode by doxygen 1.8.13
gpi.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, 2009
8  *
9  * Last modified:
10  * $Date: 2016-05-23 22:18:23 +0200 (Mon, 23 May 2016) $ by $Author: schulte $
11  * $Revision: 15073 $
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 <cmath>
39 
40 namespace Gecode {
41 
43  class GPI {
44  public:
46  class Info {
47  public:
49  unsigned int pid;
51  unsigned int gid;
53 
54  double c;
57  unsigned long int t;
59  void init(unsigned int pid, unsigned int gid);
61  };
62  private:
64  class Block {
65  public:
67  Block* next;
69  Info c[1];
71  static Block* allocate(unsigned int n, Block* p=NULL);
72  };
74  class Manager : public HeapAllocated {
75  protected:
77  unsigned next;
79  double d;
81  static const unsigned int n_dpow = 8U;
83  double dpow[n_dpow];
85  unsigned long int t;
87  void decay(Info& c);
88  public:
90  Manager(void);
92  unsigned int pid(void);
94  void decay(double d);
96  double decay(void) const;
98  void inc(Info& c);
100  void set(Info& c, double a);
102  double val(Info& c);
103  };
105  static const unsigned int size_min = 32;
107  static const unsigned int size_max = 32 * 1024;
109  class Object : public HeapAllocated {
110  public:
112  Support::FastMutex* mutex;
114  Manager* manager;
116  Object* parent;
118  unsigned int use_cnt;
120  unsigned int size;
122  unsigned int free;
124  Block* cur;
126  Object(Support::FastMutex* m, Object* p=NULL);
127  };
129  void* mo;
131  Object* object(void) const;
133  bool local(void) const;
135  void local(Object* o);
137  void global(void* mo);
139  void dispose(void);
140  public:
142  GPI(void);
144  GPI(const GPI& ga);
146  ~GPI(void);
148  void decay(double d);
150  double decay(void) const;
152  void fail(Info& c);
154  void set(Info& c, double a);
156  double afc(Info& c);
158  Info* allocate(unsigned int gid);
159  };
160 
161 
162 
163  forceinline void
164  GPI::Info::init(unsigned int pid0, unsigned int gid0) {
165  pid=pid0; gid=gid0; c=1.0; t=0UL;
166  }
167 
168  forceinline void
169  GPI::Manager::decay(double d0) {
170  d = d0;
171  if (d != 1.0) {
172  double p = d;
173  unsigned int i=0;
174  do {
175  dpow[i++]=p; p*=d;
176  } while (i<n_dpow);
177  }
178  }
180  GPI::Manager::Manager(void)
181  : next(0), d(1.0), t(0UL) {}
182 
183  forceinline unsigned int
184  GPI::Manager::pid(void) {
185  return next++;
186  }
187  forceinline double
188  GPI::Manager::decay(void) const {
189  return d;
190  }
191  forceinline void
192  GPI::Manager::decay(Info& c) {
193  assert((t >= c.t) && (d != 1.0));
194  unsigned int n = t - c.t;
195  if (n > 0) {
196  if (n <= n_dpow) {
197  c.c *= dpow[n-1];
198  } else {
199  c.c *= pow(d,static_cast<double>(n));
200  }
201  c.t = t;
202  }
203  }
204  forceinline void
205  GPI::Manager::inc(Info& c) {
206  if (d == 1.0) {
207  c.c += 1.0;
208  } else {
209  decay(c);
210  c.c += 1.0; c.t = ++t;
211  }
212  }
213  forceinline double
214  GPI::Manager::val(Info& c) {
215  if (d != 1.0)
216  decay(c);
217  return c.c;
218  }
219  forceinline void
220  GPI::Manager::set(Info& c, double a) {
221  c.c = a;
222  }
223 
224 
225  /*
226  * Global AFC information
227  *
228  */
229  forceinline GPI::Block*
230  GPI::Block::allocate(unsigned int n, GPI::Block* p) {
231  Block* b = static_cast<Block*>(heap.ralloc(sizeof(Block)+
232  (n-1)*sizeof(Info)));
233  b->next = p;
234  return b;
235  }
236 
238  GPI::Object::Object(Support::FastMutex* m, Object* p)
239  : mutex(m), parent(p), use_cnt(1), size(size_min), free(size_min),
240  cur(Block::allocate(size)) {
241  if (parent == NULL) {
242  manager = new Manager;
243  } else {
244  manager = parent->manager;
245  }
246  }
247 
248  forceinline GPI::Object*
249  GPI::object(void) const {
250  return static_cast<Object*>(Support::funmark(mo));
251  }
252  forceinline bool
253  GPI::local(void) const {
254  return !Support::marked(mo);
255  }
256  forceinline void
257  GPI::local(Object* o) {
258  assert(!Support::marked(o));
259  mo = o;
260  }
261  forceinline void
262  GPI::global(void* o) {
263  mo = Support::fmark(o);
264  }
265 
267  GPI::GPI(void) {
268  // No synchronization needed as single thread is creating this object
269  local(new Object(new Support::FastMutex));
270  }
271 
273  GPI::GPI(const GPI& gpi) {
274  global(gpi.mo);
275  Object* o = object();
276  o->mutex->acquire();
277  o->use_cnt++;
278  o->mutex->release();
279  }
280 
281  forceinline void
282  GPI::dispose(void) {
283  Support::FastMutex* m = object()->mutex;
284  m->acquire();
285  Object* c = object();
286  Manager* manager = c->manager;
287  while ((c != NULL) && (--c->use_cnt == 0)) {
288  // Delete all blocks for c
289  Block* b = c->cur;
290  while (b != NULL) {
291  Block* d = b; b=b->next;
292  heap.rfree(d);
293  }
294  // Delete object
295  Object* d = c; c = c->parent;
296  delete d;
297  }
298  m->release();
299  // All objects are deleted, so also delete mutex and manager
300  if (c == NULL) {
301  delete manager;
302  delete m;
303  }
304  }
305 
307  GPI::~GPI(void) {
308  dispose();
309  }
310 
311  forceinline void
313  Support::FastMutex& m = *object()->mutex;
314  m.acquire();
315  object()->manager->inc(c);
316  m.release();
317  }
318 
319  forceinline void
320  GPI::set(Info& c, double a) {
321  Support::FastMutex& m = *object()->mutex;
322  m.acquire();
323  object()->manager->set(c,a);
324  m.release();
325  }
326 
327  forceinline double
329  Support::FastMutex& m = *object()->mutex;
330  double d;
331  m.acquire();
332  d = object()->manager->val(c);
333  m.release();
334  return d;
335  }
336 
337  forceinline double
338  GPI::decay(void) const {
339  Support::FastMutex& m = *object()->mutex;
340  double d;
341  m.acquire();
342  d = object()->manager->decay();
343  m.release();
344  return d;
345  }
346 
347  forceinline void
348  GPI::decay(double d) {
349  Support::FastMutex& m = *object()->mutex;
350  m.acquire();
351  object()->manager->decay(d);
352  m.release();
353  }
354 
356  GPI::allocate(unsigned int gid) {
357  /*
358  * If there is no local object, create one.
359  *
360  * There is no synchronization needed as only ONE space has access
361  * to the marked pointer AND the local object.
362  */
363  if (!local())
364  local(new Object(object()->mutex,object()));
365 
366  assert(local());
367 
368  Object* o = object();
369 
370  if (o->free == 0) {
371  if (2*o->size <= size_max)
372  o->size *= 2;
373  o->free = o->size;
374  o->cur = Block::allocate(o->size,o->cur);
375  }
376 
377  Info* c = &o->cur->c[--o->free];
378  c->init(o->manager->pid(),gid);
379 
380  return c;
381  }
382 
383 }
384 
385 // STATISTICS: kernel-prop
bool marked(void *p)
Check whether p is marked.
void rfree(void *p)
Free memory block starting at p.
Definition: heap.hpp:375
void pow(Home home, FloatVar x0, int n, FloatVar x1)
Post propagator for for $n 0$.
Definition: arithmetic.cpp:117
void acquire(void)
Acquire the mutex and possibly block.
Definition: none.hpp:46
void * ralloc(size_t s)
Allocate s bytes from heap.
Definition: heap.hpp:361
A mutex for mutual exclausion among several threads.
Definition: thread.hpp:99
Gecode::IntSet d(v, 7)
void * funmark(void *p)
Return unmarked pointer for a possibly marked pointer p.
void release(void)
Release the mutex.
Definition: none.hpp:52
struct Gecode::@554::NNF::@60::@62 a
For atomic nodes.
int p
Number of positive literals for node type.
Definition: bool-expr.cpp:236
~GPI(void)
Destructor.
Definition: gpi.hpp:307
Gecode::IntArgs i(4, 1, 2, 3, 4)
int n
Number of negative literals for node type.
Definition: bool-expr.cpp:238
Global propagator information.
Definition: gpi.hpp:43
unsigned int pid
Propagator identifier.
Definition: gpi.hpp:49
Info * allocate(unsigned int gid)
Allocate new actor info.
Definition: gpi.hpp:356
unsigned int size(I &i)
Size of all ranges of range iterator i.
void set(Info &c, double a)
Set failure count to a.
Definition: gpi.hpp:320
double afc(Info &c)
Return failure count.
Definition: gpi.hpp:328
double c
The counter value.
Definition: gpi.hpp:55
double decay(void) const
Return decay factor.
Definition: gpi.hpp:338
unsigned int gid
Group identifier.
Definition: gpi.hpp:51
void init(unsigned int pid, unsigned int gid)
Initialize.
Definition: gpi.hpp:164
Heap heap
The single global heap.
Definition: heap.cpp:48
#define forceinline
Definition: config.hpp:173
void fail(Info &c)
Increment failure count.
Definition: gpi.hpp:312
void * fmark(void *p)
Return marked pointer for p (possibly already marked)
Gecode toplevel namespace
Class for storing timed-decay value.
Definition: gpi.hpp:46
GPI(void)
Initialize.
Definition: gpi.hpp:267
struct Gecode::@554::NNF::@60::@61 b
For binary nodes (and, or, eqv)
unsigned long int t
The time-stamp.
Definition: gpi.hpp:57
Base class for heap allocated objects.
Definition: heap.hpp:344