GraphLab: Distributed Graph-Parallel API  2.1
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Macros Groups Pages
random.cpp
1 /**
2  * Copyright (c) 2009 Carnegie Mellon University.
3  * All rights reserved.
4  *
5  * Licensed under the Apache License, Version 2.0 (the "License");
6  * you may not use this file except in compliance with the License.
7  * You may obtain a copy of the License at
8  *
9  * http://www.apache.org/licenses/LICENSE-2.0
10  *
11  * Unless required by applicable law or agreed to in writing,
12  * software distributed under the License is distributed on an "AS
13  * IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either
14  * express or implied. See the License for the specific language
15  * governing permissions and limitations under the License.
16  *
17  * For more about this software visit:
18  *
19  * http://www.graphlab.ml.cmu.edu
20  *
21  */
22 
23 
24 #include <pthread.h>
25 
26 #include <set>
27 #include <iostream>
28 #include <fstream>
29 
30 #include <boost/random.hpp>
31 #include <boost/integer_traits.hpp>
32 
33 #include <graphlab/parallel/pthread_tools.hpp>
34 #include <graphlab/logger/assertions.hpp>
35 #include <graphlab/util/timer.hpp>
36 
37 #include <graphlab/util/random.hpp>
38 
39 
40 
41 
42 #include <graphlab/macros_def.hpp>
43 namespace graphlab {
44  namespace random {
45 
46  /**
47  * A truely nondeterministic generator
48  */
49  class nondet_generator {
50  public:
51  static nondet_generator& global() {
52  static nondet_generator global_gen;
53  return global_gen;
54  }
55 
56  typedef size_t result_type;
57  BOOST_STATIC_CONSTANT(result_type, min_value =
58  boost::integer_traits<result_type>::const_min);
59  BOOST_STATIC_CONSTANT(result_type, max_value =
60  boost::integer_traits<result_type>::const_max);
61  result_type min BOOST_PREVENT_MACRO_SUBSTITUTION () const { return min_value; }
62  result_type max BOOST_PREVENT_MACRO_SUBSTITUTION () const { return max_value; }
63 
64  nondet_generator() {
65  rnd_dev.open("/dev/urandom", std::ios::binary | std::ios::in);
66  ASSERT_TRUE(rnd_dev.good());
67  }
68  // Close the random number generator
69  ~nondet_generator() { rnd_dev.close(); }
70  // read a size_t from the source
71  result_type operator()() {
72  // read a machine word into result
73  result_type result(0);
74  mut.lock();
75  ASSERT_TRUE(rnd_dev.good());
76  rnd_dev.read(reinterpret_cast<char*>(&result), sizeof(result_type));
77  ASSERT_TRUE(rnd_dev.good());
78  mut.unlock();
79  // std::cout << result << std::endl;
80  return result;
81  }
82  private:
83  std::ifstream rnd_dev;
84  mutex mut;
85  };
86  //nondet_generator global_nondet_rng;
87 
88 
89 
90 
91 
92 
93  /**
94  * This class represents a master registery of all active random
95  * number generators
96  */
97  struct source_registry {
98  std::set<generator*> generators;
99  generator master;
100  mutex mut;
101 
102  static source_registry& global() {
103  static source_registry registry;
104  return registry;
105  }
106  /**
107  * Seed all threads using the default seed
108  */
109  void seed() {
110  mut.lock();
111  master.seed();
112  foreach(generator* generator, generators) {
113  ASSERT_TRUE(generator != NULL);
114  generator->seed(master);
115  }
116  mut.unlock();
117  }
118 
119  /**
120  * Seed all threads using the default seed
121  */
122  void nondet_seed() {
123  mut.lock();
124  master.nondet_seed();
125  foreach(generator* generator, generators) {
126  ASSERT_TRUE(generator != NULL);
127  generator->seed(master);
128  }
129  mut.unlock();
130  }
131 
132 
133  /**
134  * Seed all threads using the default seed
135  */
136  void time_seed() {
137  mut.lock();
138  master.time_seed();
139  foreach(generator* generator, generators) {
140  ASSERT_TRUE(generator != NULL);
141  generator->seed(master);
142  }
143  mut.unlock();
144  }
145 
146 
147  /**
148  * Seed all threads with a fixed number
149  */
150  void seed(const size_t number) {
151  mut.lock();
152  master.seed(number);
153  foreach(generator* generator, generators) {
154  ASSERT_TRUE(generator != NULL);
155  generator->seed(master);
156  }
157  mut.unlock();
158  }
159 
160  /**
161  * Register a source with the registry and seed it based on the
162  * master.
163  */
164  void register_generator(generator* tls_ptr) {
165  ASSERT_TRUE(tls_ptr != NULL);
166  mut.lock();
167  generators.insert(tls_ptr);
168  tls_ptr->seed(master);
169  // std::cout << "Generator created" << std::endl;
170  // __print_back_trace();
171  mut.unlock();
172  }
173 
174  /**
175  * Unregister a source from the registry
176  */
177  void unregister_source(generator* tls_ptr) {
178  mut.lock();
179  generators.erase(tls_ptr);
180  mut.unlock();
181  }
182  };
183  // source_registry registry;
184 
185 
186 
187 
188 
189 
190 
191 
192  //////////////////////////////////////////////////////////////
193  /// Pthread TLS code
194 
195  /**
196  * this function is responsible for destroying the random number
197  * generators
198  */
199  void destroy_tls_data(void* ptr) {
200  generator* tls_rnd_ptr =
201  reinterpret_cast<generator*>(ptr);
202  if(tls_rnd_ptr != NULL) {
203  source_registry::global().unregister_source(tls_rnd_ptr);
204  delete tls_rnd_ptr;
205  }
206  }
207 
208 
209  /**
210  * Simple struct used to construct the thread local storage at
211  * startup.
212  */
213  struct tls_key_creator {
214  pthread_key_t TLS_RANDOM_SOURCE_KEY;
215  tls_key_creator() : TLS_RANDOM_SOURCE_KEY(0) {
216  pthread_key_create(&TLS_RANDOM_SOURCE_KEY,
218  }
219  };
220  // This function is to be called prior to any access to the random
221  // source
222  static pthread_key_t get_random_source_key() {
223  static const tls_key_creator key;
224  return key.TLS_RANDOM_SOURCE_KEY;
225  }
226  // This forces __init_keys__ to be called prior to main.
227  static pthread_key_t __unused_init_keys__(get_random_source_key());
228 
229  // the combination of the two mechanisms above will force the
230  // thread local store to be initialized
231  // 1: before main
232  // 2: before any use of random by global variables.
233  // KNOWN_ISSUE: if a global variable (initialized before main)
234  // spawns threads which then call random. Things explode.
235 
236 
237  /////////////////////////////////////////////////////////////
238  //// Implementation of header functions
239 
240 
241 
243  // get the thread local storage
244  generator* tls_rnd_ptr =
245  reinterpret_cast<generator*>
246  (pthread_getspecific(get_random_source_key()));
247  // Create a tls_random_source if none was provided
248  if(tls_rnd_ptr == NULL) {
249  tls_rnd_ptr = new generator();
250  assert(tls_rnd_ptr != NULL);
251  // This will seed it with the master rng
252  source_registry::global().register_generator(tls_rnd_ptr);
253  pthread_setspecific(get_random_source_key(),
254  tls_rnd_ptr);
255  }
256  // assert(tls_rnd_ptr != NULL);
257  return *tls_rnd_ptr;
258  } // end of get local random source
259 
260 
261 
262  void seed() { source_registry::global().seed(); }
263 
264  void nondet_seed() { source_registry::global().nondet_seed(); }
265 
266  void time_seed() { source_registry::global().time_seed(); }
267 
268  void seed(const size_t seed_value) {
269  source_registry::global().seed(seed_value);
270  }
271 
272 
274  // Get the global nondeterministic random number generator.
275  nondet_generator& nondet_rnd(nondet_generator::global());
276  mut.lock();
277  // std::cout << "initializing real rng" << std::endl;
278  real_rng.seed(nondet_rnd());
279  // std::cout << "initializing discrete rng" << std::endl;
280  discrete_rng.seed(nondet_rnd());
281  // std::cout << "initializing fast discrete rng" << std::endl;
282  fast_discrete_rng.seed(nondet_rnd());
283  mut.unlock();
284  }
285 
286 
287  void pdf2cdf(std::vector<double>& pdf) {
288  double Z = 0;
289  for(size_t i = 0; i < pdf.size(); ++i) Z += pdf[i];
290  for(size_t i = 0; i < pdf.size(); ++i)
291  pdf[i] = pdf[i]/Z + ((i>0)? pdf[i-1] : 0);
292  } // end of pdf2cdf
293 
294 
295 
296 
297  }; // end of namespace random
298 
299 };// end of namespace graphlab
300