Randomization
[Utilities]

Produce pseudo-randomness independently among the parXXL processes. More...

Collaboration diagram for Randomization:

Classes

class  par::step::extract_commat< T >
 Extraction class to identify the target process according to the position of the data. More...
class  par::cpp::primes
 Provides us with a large number of different prime numbers. More...

Defines

#define SIZE_CASE(...)

Functions

template<class T >
void par::mem::choose (sys::seed_t &seed, chunk< T > &arr, size_t amount)
 Randomly choose a sample of amount elements of a par::mem::chunk and move them in front.
size_t par::sys::cksum (char const *name)
 Compute a checksum of the string that name is pointing to.
template<>
size_t par::sys::cksum< char > (size_t size, char const *seed)
 Compute a checksum of the data that seed is pointing to.
double par::sys::drand (void)
 This one is slow since it uses a predefined seed. Don't use it often.
double par::sys::drand (seed_t &seed)
 Return a pseudo random double between 0.0 and 1.0.
double par::sys::drand (seed_t *seed)
 Return a pseudo random double between 0.0 and 1.0.
template<class T >
void par::sys::generate (T arrp[], size_t length)
 Generate an integer random permutation in place.
template<>
void par::step::generate (array< ulong > &C, par::sys::seed_t &seed, unsigned twist)
template<>
void par::step::generate (array< long > &C, par::sys::seed_t &seed, unsigned twist)
template<>
void par::step::generate (array< unsigned > &C, par::sys::seed_t &seed, unsigned twist)
template<>
void par::step::generate (array< signed > &C, par::sys::seed_t &seed, unsigned twist)
template<>
void par::step::generate (array< ushort > &C, par::sys::seed_t &seed, unsigned twist)
template<>
void par::step::generate (array< short > &C, par::sys::seed_t &seed, unsigned twist)
template<>
void par::step::generate (array< uchar > &C, par::sys::seed_t &seed, unsigned twist)
template<>
void par::step::generate (array< schar > &C, par::sys::seed_t &seed, unsigned twist)
template<class T >
void par::step::generate (array< T > &C, par::sys::seed_t &seed, unsigned twist)
template<class T >
void par::step::generate (array< T > &C, unsigned twist)
template<class T >
void par::step::generate (array< T > &C, par::sys::seed_t &seed)
template<class T >
void par::step::generate (array< T > &C)
 Generate an integer random permutation in place.
template<class T >
void par::mem::generate (chunk< T > &C)
 Generate an integer random permutation in place.
template<typename uT >
void par::sys::hypermat (size_t c, const uT C[], uT res[])
template<typename uT >
void par::sys::hypermat (size_t c, uT const C[], uT res[], seed_t &seed)
 Sample an nn permutation matrix.
template<typename uT >
void par::sys::hypermat (size_t c, const uT C[], size_t u, const uT U[], uT res[])
template<typename uT >
void par::sys::hypermat (size_t c, const uT C[], size_t u, const uT U[], uT res[], seed_t &seed)
 Sample an c u permutation matrix.
template<typename uT >
uT par::sys::hyperprox (par::sys::seed_t &seed, uT N1, uT N2, uT T)
 Similar to par::sys::randHypergeom.
void par::sys::init_rand (void)
 Initialize a hidden per parXXL-process seed to an un-guessable value.
void par::sys::init_rand (seed_t &seed)
 Initialize seed to an un-guessable value.
template<typename gT , typename lT >
lT par::mem::partGen (sys::seed_t &seed, chunk< gT > const &arr, typename sys::partition< 0, gT, lT >::states const &st, lT const *share, gT const *offset, FILE *deb=NULL)
 Generate a subinterval of a permutation.
template<typename gT , typename lT >
lT par::mem::partGen (chunk< gT > const &arr, typename sys::partition< 0, gT, lT >::states const &st, lT const *share, gT const *offset, FILE *deb=NULL)
 Generate a subinterval of a permutation.
template<class T >
void par::sys::permute (par::sys::seed_t &seed, T arrp[], size_t length)
 Perform an in place random permutation.
template<class T >
void par::step::permute (array< T > &A, par::sys::seed_t &seed)
template<class T >
void par::step::permute (array< T > &A)
 Randomly permute a par::step::array.
template<class T >
void par::mem::permute (sys::seed_t &seed, chunk< T > &arr)
 Randomly permute the elements of a par::mem::chunk.
size_t par::sys::rand (void)
 This one is slow since it uses a predefined seed. Don't use it often.
size_t par::sys::rand (seed_t &restrict seed)
 Return a pseudo random number with as many bits as size_t may hold.
size_t par::sys::rand (seed_t *restrict seed)
 Return a pseudo random number with as many bits as size_t may hold.
template<typename uT >
void par::sys::randHypergeom (par::sys::seed_t &seed, uT total, uT whites, size_t draws, uT *draw)
 Sample a variate hypergeometric distribution.
template<typename uT >
uT par::sys::randHypergeom (par::sys::seed_t &seed, uT total, uT whites, uT draw)
 Sample a hypergeometric distribution.
uint64_t par::sys::realrand (void)
 Provide 64 bits of real randomness, if available.
size_t par::sys::urand (size_t upperlimit)
 This one is slow since it uses a predefined seed. Don't use it often.
size_t par::sys::urand (seed_t &seed)
 Return a non-negative pseudo random number, smaller than par::sys::seed_t::urand_max.
size_t par::sys::urand (seed_t &seed, size_t upperlimit)
 Return a non-negative pseudo random number, smaller than upperlimit.
size_t par::sys::urand (seed_t *seed)
 Return a non-negative pseudo random number, smaller than par::sys::seed_t::urand_max.
size_t par::sys::urand (seed_t *seed, size_t upperlimit)
 Return a non-negative pseudo random number, smaller than upperlimit.

Detailed Description

Produce pseudo-randomness independently among the parXXL processes.

Generation of pseudo random numbers in sequential is already a non trivial task. In particular the standard interfaces rand() and rand_r() may already not be producing sufficiently many random bits on 64 bit machines. Our implementation tries to face this problem, cross fingers.

In a parallel or distributed setting this becomes even more challenging:

This also includes some functions for sampling random distribution of data, in particular a family of functions called `permute', par::sys::permute, par::mem::permute and par::step::permute.


Define Documentation

#define SIZE_CASE ( ...   ) 

Value:

{ \
 array< __VA_ARGS__ > iC(C.localSize()); \
 generate< __VA_ARGS__ >(iC, seed, twist); \
 size_t len = iC.localSize(); \
 mem::apointer< __VA_ARGS__ > aiC(iC); \
 mem::chunk< T > rC(len); \
 mem::apointer< T > arC(rC); \
 for (size_t i = 0; i < len; ++i) \
 arC[i] = static_cast< T >(aiC[i]); \
 C = rC; \
 }

Definition at line 234 of file par_step_perm.h.


Function Documentation

template<class T >
void par::mem::choose ( sys::seed_t &  seed,
chunk< T > &  arr,
size_t  amount 
) [inline]

Randomly choose a sample of amount elements of a par::mem::chunk and move them in front.

Definition at line 43 of file par_mem_permute.h.

size_t par::sys::cksum ( char const *  name  )  [inline]

Compute a checksum of the string that name is pointing to.

Compute a checksum of the data that name is pointing to.

Takes care of possible alignment issues.

Precondition:
Assumes that name points to a null-terminated string.

Definition at line 770 of file par_sys_rand.h.

template<>
size_t par::sys::cksum< char > ( size_t  size,
char const *  seed 
) [inline]

Compute a checksum of the data that seed is pointing to.

Takes care of possible alignment issues.

double par::sys::drand ( void   ) 

This one is slow since it uses a predefined seed. Don't use it often.

Definition at line 169 of file par_sys_rand.cc.

double par::sys::drand ( seed_t &  seed  )  [inline]

Return a pseudo random double between 0.0 and 1.0.

Definition at line 585 of file par_sys_rand.h.

double par::sys::drand ( seed_t *  seed  )  [inline]

Return a pseudo random double between 0.0 and 1.0.

Definition at line 581 of file par_sys_rand.h.

template<class T >
void par::sys::generate ( arrp[],
size_t  length 
) [inline]

Generate an integer random permutation in place.

This overwrites the data that might be present in arrp. length should be no more than the maximum value that is representable in type T.

Definition at line 176 of file par_sys_permute.h.

template<>
void par::step::generate ( array< ulong > &  C,
par::sys::seed_t seed,
unsigned  twist 
) [inline]

template<>
void par::step::generate ( array< long > &  C,
par::sys::seed_t seed,
unsigned  twist 
) [inline]

template<>
void par::step::generate ( array< unsigned > &  C,
par::sys::seed_t seed,
unsigned  twist 
) [inline]

template<>
void par::step::generate ( array< signed > &  C,
par::sys::seed_t seed,
unsigned  twist 
) [inline]

template<>
void par::step::generate ( array< ushort > &  C,
par::sys::seed_t seed,
unsigned  twist 
) [inline]

template<>
void par::step::generate ( array< short > &  C,
par::sys::seed_t seed,
unsigned  twist 
) [inline]

template<>
void par::step::generate ( array< uchar > &  C,
par::sys::seed_t seed,
unsigned  twist 
) [inline]

template<>
void par::step::generate ( array< schar > &  C,
par::sys::seed_t seed,
unsigned  twist 
) [inline]

template<class T >
void par::step::generate ( array< T > &  C,
par::sys::seed_t seed,
unsigned  twist 
) [inline]

Definition at line 250 of file par_step_perm.h.

template<class T >
void par::step::generate ( array< T > &  C,
unsigned  twist 
) [inline]

Definition at line 209 of file par_step_perm.h.

template<class T >
void par::step::generate ( array< T > &  C,
par::sys::seed_t seed 
) [inline]

Definition at line 195 of file par_step_perm.h.

template<class T >
void par::step::generate ( array< T > &  C  )  [inline]

Generate an integer random permutation in place.

This overwrites the data that might be present in C. C.length should be no more than the maximum value that is representable in type T.

Definition at line 202 of file par_step_perm.h.

template<class T >
void par::mem::generate ( chunk< T > &  C  )  [inline]

Generate an integer random permutation in place.

This overwrites the data that might be present in C. C.length should be no more than the maximum value that is representable in type T.

Definition at line 133 of file par_mem_permute.h.

template<typename uT >
void par::sys::hypermat ( size_t  c,
const uT  C[],
uT  res[] 
) [inline]

Definition at line 130 of file par_sys_hypergeom.h.

template<typename uT >
void par::sys::hypermat ( size_t  c,
uT const   C[],
uT  res[],
seed_t &  seed 
) [inline]

Sample an nn permutation matrix.

This generalizes the hypergeometric distribution to the case of n colors and n urns. m0[i] holds the size of the color classs i and urn i. res is an nn matrix. res[i][j] tells how many balls of color i will be found in urn j after a random mix of the balls.

Definition at line 117 of file par_sys_hypergeom.h.

template<typename uT >
void par::sys::hypermat ( size_t  c,
const uT  C[],
size_t  u,
const uT  U[],
uT  res[] 
) [inline]

Definition at line 91 of file par_sys_hypergeom.h.

template<typename uT >
void par::sys::hypermat ( size_t  c,
const uT  C[],
size_t  u,
const uT  U[],
uT  res[],
seed_t &  seed 
) [inline]

Sample an c u permutation matrix.

This generalizes the hypergeometric distribution to the case of c colors and u urns. C[i] holds the size of the color class i and U[i] of urn i. res is an c u matrix. res[i][j] tells how many balls of color i will be found in urn j after a random mix of the balls.

template<typename uT >
uT par::sys::hyperprox ( par::sys::seed_t seed,
uT  N1,
uT  N2,
uT  T 
) [inline]

Similar to par::sys::randHypergeom.

The difference is that N1 is the number of blacks and N2 the number of whites.

Definition at line 64 of file par_sys_hypergeom.h.

void par::sys::init_rand ( void   ) 

Initialize a hidden per parXXL-process seed to an un-guessable value.

This initialization is done differently on all parXXL processes such that hopefully the numbers that are produced are all independent.

void par::sys::init_rand ( seed_t seed  ) 

Initialize seed to an un-guessable value.

This initialization is done differently on all parXXL processes such that hopefully the numbers that are produced are all independent.

Definition at line 178 of file par_sys_rand.cc.

template<typename gT , typename lT >
lT par::mem::partGen ( sys::seed_t &  seed,
chunk< gT > const &  arr,
typename sys::partition< 0, gT, lT >::states const &  st,
lT const *  share,
gT const *  offset,
FILE *  deb = NULL 
) [inline]

Generate a subinterval of a permutation.

Analogous to par::sys::partition< 0 >::states::generate.

Definition at line 77 of file par_mem_permute.h.

template<typename gT , typename lT >
lT par::mem::partGen ( chunk< gT > const &  arr,
typename sys::partition< 0, gT, lT >::states const &  st,
lT const *  share,
gT const *  offset,
FILE *  deb = NULL 
) [inline]

Generate a subinterval of a permutation.

Analogous to par::sys::partition< T, 0 >::states::generate.

Definition at line 59 of file par_mem_permute.h.

template<class T >
void par::sys::permute ( par::sys::seed_t seed,
arrp[],
size_t  length 
) [inline]

Perform an in place random permutation.

Definition at line 31 of file par_sys_permute.h.

template<class T >
void par::step::permute ( array< T > &  A,
par::sys::seed_t seed 
) [inline]

Definition at line 113 of file par_step_perm.h.

template<class T >
void par::step::permute ( array< T > &  A  )  [inline]

Randomly permute a par::step::array.

Uses a constant number of supersteps and a linear amount of communication. This version must be able to hold a matrix of size $ p^2 $ on one parXXL process, so in total it is restricted to $ p < \sqrt[3]{n} $.

See also:
Randomization

Definition at line 169 of file par_step_perm.h.

template<class T >
void par::mem::permute ( sys::seed_t &  seed,
chunk< T > &  arr 
) [inline]

Randomly permute the elements of a par::mem::chunk.

Definition at line 31 of file par_mem_permute.h.

size_t par::sys::rand ( void   ) 

This one is slow since it uses a predefined seed. Don't use it often.

Still it guarantees the underlying par::sys::seed_t is different for each thread.

Definition at line 165 of file par_sys_rand.cc.

size_t par::sys::rand ( seed_t &restrict  seed  )  [inline]

Return a pseudo random number with as many bits as size_t may hold.

Definition at line 566 of file par_sys_rand.h.

size_t par::sys::rand ( seed_t *restrict  seed  )  [inline]

Return a pseudo random number with as many bits as size_t may hold.

Definition at line 559 of file par_sys_rand.h.

template<typename uT >
void par::sys::randHypergeom ( par::sys::seed_t seed,
uT  total,
uT  whites,
size_t  draws,
uT *  draw 
) [inline]

Sample a variate hypergeometric distribution.

This generalizes the simple hypergeometric distribution to multiple succesive draws that depend on each other.

template<typename uT >
uT par::sys::randHypergeom ( par::sys::seed_t seed,
uT  total,
uT  whites,
uT  draw 
) [inline]

Sample a hypergeometric distribution.

This is distribution of an urn experiment with total balls (black or white) and amoung them whites white balls. If we draw draw balls from such an urn, how many white balls will we have in this draw?

uint64_t par::sys::realrand ( void   ) 

Provide 64 bits of real randomness, if available.

This is a time consuming and blocking source of real randomness wherever the system provides such a thing.

Usually access to this is buffered so it should not do much harm to your execution times if used once in a while. But it will slow down your program considerably if used abundantly. Use it with caution.

Uses PAR_RANDOM_DEV as the source of randomness.

size_t par::sys::urand ( size_t  upperlimit  ) 

This one is slow since it uses a predefined seed. Don't use it often.

Definition at line 173 of file par_sys_rand.cc.

size_t par::sys::urand ( seed_t &  seed  )  [inline]

Return a non-negative pseudo random number, smaller than par::sys::seed_t::urand_max.

Definition at line 615 of file par_sys_rand.h.

size_t par::sys::urand ( seed_t &  seed,
size_t  upperlimit 
) [inline]

Return a non-negative pseudo random number, smaller than upperlimit.

Definition at line 608 of file par_sys_rand.h.

size_t par::sys::urand ( seed_t *  seed  )  [inline]

Return a non-negative pseudo random number, smaller than par::sys::seed_t::urand_max.

Definition at line 601 of file par_sys_rand.h.

size_t par::sys::urand ( seed_t *  seed,
size_t  upperlimit 
) [inline]

Return a non-negative pseudo random number, smaller than upperlimit.

Definition at line 594 of file par_sys_rand.h.


Generated on Tue Oct 13 22:03:50 2009 for parXXL by  doxygen 1.5.8