Generated on Sat Feb 7 2015 02:01:28 for Gecode by doxygen 1.8.9.1
global-afc.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: 2013-07-01 06:38:48 +0200 (Mon, 01 Jul 2013) $ by $Author: tack $
11  * $Revision: 13740 $
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 GlobalAFC {
44  public:
46  class Counter {
47  public:
49  double c;
51  unsigned long int t;
53  void init(void);
54  };
55  private:
57  class Block {
58  public:
60  Block* next;
62  Counter c[1];
64  static Block* allocate(unsigned int n, Block* p=NULL);
65  };
67  class DecayManager {
68  protected:
70  double d;
72  static const unsigned int n_dpow = 8U;
74  double dpow[n_dpow];
76  unsigned long int t;
78  void decay(Counter& c);
79  public:
81  DecayManager(void);
83  void decay(double d);
85  double decay(void) const;
87  void inc(Counter& c);
89  void set(Counter& c, double a);
91  double val(Counter& c);
93  static void* operator new(size_t s);
95  static void operator delete(void* p);
96  };
98  static const unsigned int size_min = 32;
100  static const unsigned int size_max = 32 * 1024;
102  class Object {
103  public:
105  Support::FastMutex* mutex;
107  DecayManager* decay;
109  Object* parent;
111  unsigned int use_cnt;
113  unsigned int size;
115  unsigned int free;
117  Block* cur;
119  Object(Support::FastMutex* m, Object* p=NULL);
121  static void* operator new(size_t s);
123  static void operator delete(void* p);
124  };
126  void* mo;
128  Object* object(void) const;
130  bool local(void) const;
132  void local(Object* o);
134  void global(void* mo);
135  public:
137  GlobalAFC(void);
139  GlobalAFC(const GlobalAFC& ga);
141  ~GlobalAFC(void);
143  void decay(double d);
145  double decay(void) const;
147  void fail(Counter& c);
149  void set(Counter& c, double a);
151  double afc(Counter& c);
153  Counter& allocate(void);
154  };
155 
156 
157 
158  forceinline void
160  c=1.0; t=0UL;
161  }
162 
163  forceinline void
164  GlobalAFC::DecayManager::decay(double d0) {
165  d = d0;
166  if (d != 1.0) {
167  double p = d;
168  unsigned int i=0;
169  do {
170  dpow[i++]=p; p*=d;
171  } while (i<n_dpow);
172  }
173  }
175  GlobalAFC::DecayManager::DecayManager(void)
176  : d(1.0), t(0UL) {}
177 
178  forceinline double
179  GlobalAFC::DecayManager::decay(void) const {
180  return d;
181  }
182  forceinline void
183  GlobalAFC::DecayManager::decay(Counter& c) {
184  assert((t >= c.t) && (d != 1.0));
185  unsigned int n = t - c.t;
186  if (n > 0) {
187  if (n <= n_dpow) {
188  c.c *= dpow[n-1];
189  } else {
190  c.c *= pow(d,static_cast<double>(n));
191  }
192  c.t = t;
193  }
194  }
195  forceinline void
196  GlobalAFC::DecayManager::inc(Counter& c) {
197  if (d == 1.0) {
198  c.c += 1.0;
199  } else {
200  decay(c);
201  c.c += 1.0; c.t = ++t;
202  }
203  }
204  forceinline double
205  GlobalAFC::DecayManager::val(Counter& c) {
206  if (d != 1.0)
207  decay(c);
208  return c.c;
209  }
210  forceinline void
211  GlobalAFC::DecayManager::set(Counter& c, double a) {
212  c.c = a;
213  }
214  forceinline void*
215  GlobalAFC::DecayManager::operator new(size_t s) {
216  return Gecode::heap.ralloc(s);
217  }
218  forceinline void
219  GlobalAFC::DecayManager::operator delete(void* p) {
221  }
222 
223 
224  /*
225  * Global AFC information
226  *
227  */
228 
229  forceinline void*
230  GlobalAFC::Object::operator new(size_t s) {
231  return Gecode::heap.ralloc(s);
232  }
233 
234  forceinline void
235  GlobalAFC::Object::operator delete(void* p) {
237  }
238 
239  forceinline GlobalAFC::Block*
240  GlobalAFC::Block::allocate(unsigned int n, GlobalAFC::Block* p) {
241  Block* b = static_cast<Block*>(heap.ralloc(sizeof(Block)+
242  (n-1)*sizeof(Counter)));
243  b->next = p;
244  return b;
245  }
246 
248  GlobalAFC::Object::Object(Support::FastMutex* m, Object* p)
249  : mutex(m), parent(p), use_cnt(1), size(size_min), free(size_min),
250  cur(Block::allocate(size)) {
251  if (parent == NULL) {
252  decay = new DecayManager;
253  } else {
254  decay = parent->decay;
255  }
256  }
257 
258  forceinline GlobalAFC::Object*
259  GlobalAFC::object(void) const {
260  return static_cast<Object*>(Support::funmark(mo));
261  }
262  forceinline bool
263  GlobalAFC::local(void) const {
264  return !Support::marked(mo);
265  }
266  forceinline void
267  GlobalAFC::local(Object* o) {
268  assert(!Support::marked(o));
269  mo = o;
270  }
271  forceinline void
272  GlobalAFC::global(void* o) {
273  mo = Support::fmark(o);
274  }
275 
278  // No synchronization needed as single thread is creating this object
279  local(new Object(new Support::FastMutex));
280  }
281 
284  global(gpi.mo);
285  Object* o = object();
286  o->mutex->acquire();
287  o->use_cnt++;
288  o->mutex->release();
289  }
290 
293  Support::FastMutex* m = object()->mutex;
294  m->acquire();
295  Object* c = object();
296  DecayManager* decay = c->decay;
297  while ((c != NULL) && (--c->use_cnt == 0)) {
298  // Delete all blocks for c
299  Block* b = c->cur;
300  while (b != NULL) {
301  Block* d = b; b=b->next;
302  heap.rfree(d);
303  }
304  // Delete object
305  Object* d = c; c = c->parent;
306  delete d;
307  }
308  m->release();
309  // All objects are deleted, so also delete mutex and decya info
310  if (c == NULL) {
311  delete decay;
312  delete m;
313  }
314  }
315 
316  forceinline void
318  Support::FastMutex& m = *object()->mutex;
319  m.acquire();
320  object()->decay->inc(c);
321  m.release();
322  }
323 
324  forceinline void
325  GlobalAFC::set(Counter& c, double a) {
326  Support::FastMutex& m = *object()->mutex;
327  m.acquire();
328  object()->decay->set(c,a);
329  m.release();
330  }
331 
332  forceinline double
334  Support::FastMutex& m = *object()->mutex;
335  double d;
336  m.acquire();
337  d = object()->decay->val(c);
338  m.release();
339  return d;
340  }
341 
342  forceinline double
343  GlobalAFC::decay(void) const {
344  Support::FastMutex& m = *object()->mutex;
345  double d;
346  m.acquire();
347  d = object()->decay->decay();
348  m.release();
349  return d;
350  }
351 
352  forceinline void
353  GlobalAFC::decay(double d) {
354  Support::FastMutex& m = *object()->mutex;
355  m.acquire();
356  object()->decay->decay(d);
357  m.release();
358  }
359 
362  /*
363  * If there is no local object, create one.
364  *
365  * There is no synchronization needed as only ONE space has access
366  * to the marked pointer AND the local object.
367  */
368  if (!local())
369  local(new Object(object()->mutex,object()));
370 
371  assert(local());
372 
373  Object* o = object();
374 
375  if (o->free == 0) {
376  if (2*o->size <= size_max)
377  o->size *= 2;
378  o->free = o->size;
379  o->cur = Block::allocate(o->size,o->cur);
380  }
381 
382  Counter* c = &o->cur->c[--o->free];
383  c->init();
384 
385  return *c;
386  }
387 
388 }
389 
390 // STATISTICS: kernel-prop
bool marked(void *p)
Check whether p is marked.
NodeType t
Type of node.
Definition: bool-expr.cpp:234
double c
The counter value.
Definition: global-afc.hpp:49
void rfree(void *p)
Free memory block starting at p.
Definition: heap.hpp:355
~GlobalAFC(void)
Destructor.
Definition: global-afc.hpp:292
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:341
GlobalAFC(void)
Initialize.
Definition: global-afc.hpp:277
Heap heap
The single global heap.
Definition: heap.cpp:49
A mutex for mutual exclausion among several threads.
Definition: thread.hpp:99
void fail(Counter &c)
Increment failure count.
Definition: global-afc.hpp:317
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
Gecode::FloatVal c(-8, 8)
int p
Number of positive literals for node type.
Definition: bool-expr.cpp:236
Gecode::IntArgs i(4, 1, 2, 3, 4)
int n
Number of negative literals for node type.
Definition: bool-expr.cpp:238
unsigned int size(I &i)
Size of all ranges of range iterator i.
void init(void)
Initialize.
Definition: global-afc.hpp:159
double decay(void) const
Return decay factor.
Definition: global-afc.hpp:343
Class for storing timed-decay value.
Definition: global-afc.hpp:46
Globally shared object for propagator information.
Definition: global-afc.hpp:43
double afc(Counter &c)
Return failure count.
Definition: global-afc.hpp:333
Counter & allocate(void)
Allocate new propagator info.
Definition: global-afc.hpp:361
Mutex FastMutex
Definition: thread.hpp:188
#define forceinline
Definition: config.hpp:132
void * fmark(void *p)
Return marked pointer for p (possibly already marked)
void set(Counter &c, double a)
Set failure count to a.
Definition: global-afc.hpp:325
struct Gecode::@518::NNF::@57::@58 b
For binary nodes (and, or, eqv)
Gecode toplevel namespace
unsigned long int t
The time-stamp.
Definition: global-afc.hpp:51
struct Gecode::@518::NNF::@57::@59 a
For atomic nodes.