Changeset 5cefa43

Ignore:
Timestamp:
Feb 22, 2022, 2:44:52 PM (4 months ago)
Branches:
enum, master
Children:
f53afafb
Parents:
1eec0b0
Message:

update PRNG documentation

File:
1 edited

Legend:

Unmodified
 r1eec0b0 %% Created On       : Wed Apr  6 14:53:29 2016 %% Last Modified By : Peter A. Buhr %% Last Modified On : Sat Feb 12 17:04:03 2022 %% Update Count     : 5376 %% Last Modified On : Mon Feb 14 17:20:39 2022 %% Update Count     : 5382 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% Random numbers are values generated independently, i.e., new values do not depend on previous values (independent trials), \eg lottery numbers, shuffled cards, dice roll, coin flip. While a primary goal of programming is computing values that are \emph{not} random, random values are useful in simulation, cryptography, games, etc. A random-number generator is an algorithm computing independent values. If the algorithm uses deterministic computation (predictable sequence of values), it generates \emph{pseudo} random numbers versus \emph{true} random numbers. A random-number generator is an algorithm that computes independent values. If the algorithm uses deterministic computation (a predictable sequence of values), it generates \emph{pseudo} random numbers versus \emph{true} random numbers. All \newterm{pseudo random-number generators} (\newterm{PRNG}) involve some technique to scramble bits of a value, \eg multiplicative recurrence: Finally, a PRNG usually generates a range of large values, \eg ©[0, UINT_MAX]©, which are scaled using the modulus operator, \eg ©prng() % 5© produces random values in the range 0--4. \CFA provides a sequential and concurrent PRNGs. \CFA provides a sequential PRNG type only accessible by a single thread (not thread-safe) and a set of global and companion thread PRNG functions accessible by multiple threads without contention. \begin{itemize} \item For sequential programs, like coroutining, the PRNG is used to randomize behaviour or values during execution, \eg in games, a character makes a random move or an object takes on a random value. The ©PRNG© type is for sequential programs, like coroutining: \begin{cfa} struct PRNG { ... }; $\C[3.75in]{// opaque type}$ uint32_t calls( PRNG & prng ); $\C{// number of calls}\CRT$ \end{cfa} Sequential execution is repeatable given the same starting seeds for all ©PRNG©s. In this scenario, it is useful to have multiple ©PRNG©, \eg one per player or object so a type is provided to generate multiple instances. A ©PRNG© object is used to randomize behaviour or values during execution, \eg in games, a character makes a random move or an object takes on a random value. In this scenario, it is useful to have multiple ©PRNG© objects, \eg one per player or object. However, sequential execution is still repeatable given the same starting seeds for all ©PRNG©s. \VRef[Figure]{f:SequentialPRNG} shows an example that creates two sequential ©PRNG©s, sets both to the same seed (1009), and illustrates the three forms for generating random values, where both ©PRNG©s generate the same sequence of values. \end{tabular} \end{cquote} \vspace{-10pt} \caption{Sequential PRNG} \label{f:SequentialPRNG} \item For concurrent programs, it is important the PRNG is thread-safe and not a point of contention. A PRNG in concurrent programs is often used to randomize execution in short-running programs, \eg ©yield( prng() % 5 )©. Because concurrent execution is non-deterministic, seeding the concurrent PRNG is less important, as repeatable execution is impossible. Hence, there is one system-wide PRNG (global seed) but each \CFA thread has its own non-contended PRNG state. If the global seed is set, threads start with this seed, until it is reset and than threads start with the reset seed. Hence, these threads generate the same sequence of random numbers from their specific starting seed. If the global seed is \emph{not} set, threads start with a random seed, until the global seed is set. Hence, these threads generate different sequences of random numbers. If each thread needs its own seed, use a sequential ©PRNG© in each thread. There are two versions of the PRNG functions to manipulate the thread-local PRNG-state, which are differentiated by performance. The PRNG global and companion thread functions are for concurrent programming, such as randomizing execution in short-running programs, \eg ©yield( prng() % 5 )©. \begin{cfa} void set_seed( uint32_t seed ); $\C[3.75in]{// set global seed}$ uint32_t prng( $thread\LstStringStyle{\textdollar}$ & th, uint32_t l, uint32_t u );     $\C{// [l,u]}\CRT$ \end{cfa} The slower ©prng© functions call ©active_thread© internally to access the thread-local PRNG-state, while the faster ©prng© functions are passed a pointer to the active thread. If the thread pointer is known, \eg in a thread ©main©, eliminating the call to ©active_thread© significantly reduces the cost for accessing the thread's PRNG state. The only difference between the two sets of ©prng© routines is performance. Because concurrent execution is non-deterministic, seeding the concurrent PRNG is less important, as repeatable execution is impossible. Hence, there is one system-wide PRNG (global seed) but each \CFA thread has its own non-contended PRNG state. If the global seed is set, threads start with this seed, until it is reset and then threads start with the reset seed. Hence, these threads generate the same sequence of random numbers from their specific starting seed. If the global seed is \emph{not} set, threads start with a random seed, until the global seed is set. Hence, these threads generate different sequences of random numbers. If each thread needs its own seed, use a sequential ©PRNG© in each thread. The slower ©prng© functions \emph{without} a thread argument call ©active_thread© internally to indirectly access the current thread's PRNG state, while the faster ©prng© functions \emph{with} a thread argument directly access the thread through the thread parameter. If a thread pointer is available, \eg in thread main, eliminating the call to ©active_thread© significantly reduces the cost of accessing the thread's PRNG state. \VRef[Figure]{f:ConcurrentPRNG} shows an example using the slower/faster concurrent PRNG in the program main and a thread.