Changeset 5cefa43 for doc/user


Ignore:
Timestamp:
Feb 22, 2022, 2:44:52 PM (4 months ago)
Author:
Peter A. Buhr <pabuhr@…>
Branches:
enum, master
Children:
f53afafb
Parents:
1eec0b0
Message:

update PRNG documentation

File:
1 edited

Legend:

Unmodified
Added
Removed
  • doc/user/user.tex

    r1eec0b0 r5cefa43  
    1111%% Created On       : Wed Apr  6 14:53:29 2016
    1212%% Last Modified By : Peter A. Buhr
    13 %% Last Modified On : Sat Feb 12 17:04:03 2022
    14 %% Update Count     : 5376
     13%% Last Modified On : Mon Feb 14 17:20:39 2022
     14%% Update Count     : 5382
    1515%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
    1616
     
    82238223Random 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.
    82248224While a primary goal of programming is computing values that are \emph{not} random, random values are useful in simulation, cryptography, games, etc.
    8225 A random-number generator is an algorithm computing independent values.
    8226 If the algorithm uses deterministic computation (predictable sequence of values), it generates \emph{pseudo} random numbers versus \emph{true} random numbers.
     8225A random-number generator is an algorithm that computes independent values.
     8226If the algorithm uses deterministic computation (a predictable sequence of values), it generates \emph{pseudo} random numbers versus \emph{true} random numbers.
    82278227
    82288228All \newterm{pseudo random-number generators} (\newterm{PRNG}) involve some technique to scramble bits of a value, \eg multiplicative recurrence:
     
    82498249Finally, 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.
    82508250
    8251 \CFA provides a sequential and concurrent PRNGs.
     8251\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.
    82528252\begin{itemize}
    82538253\item
    8254 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.
     8254The ©PRNG© type is for sequential programs, like coroutining:
    82558255\begin{cfa}
    82568256struct PRNG { ... }; $\C[3.75in]{// opaque type}$
     
    82648264uint32_t calls( PRNG & prng ); $\C{// number of calls}\CRT$
    82658265\end{cfa}
    8266 Sequential execution is repeatable given the same starting seeds for all ©PRNG©s.
    8267 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.
     8266A ©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.
     8267In this scenario, it is useful to have multiple ©PRNG© objects, \eg one per player or object.
     8268However, sequential execution is still repeatable given the same starting seeds for all ©PRNG©s.
    82688269\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.
    82698270
     
    83078308\end{tabular}
    83088309\end{cquote}
    8309 \vspace{-10pt}
    83108310\caption{Sequential PRNG}
    83118311\label{f:SequentialPRNG}
     
    83138313
    83148314\item
    8315 For concurrent programs, it is important the PRNG is thread-safe and not a point of contention.
    8316 A PRNG in concurrent programs is often used to randomize execution in short-running programs, \eg ©yield( prng() % 5 )©.
    8317 
    8318 Because concurrent execution is non-deterministic, seeding the concurrent PRNG is less important, as repeatable execution is impossible.
    8319 Hence, there is one system-wide PRNG (global seed) but each \CFA thread has its own non-contended PRNG state.
    8320 If the global seed is set, threads start with this seed, until it is reset and than threads start with the reset seed.
    8321 Hence, these threads generate the same sequence of random numbers from their specific starting seed.
    8322 If the global seed is \emph{not} set, threads start with a random seed, until the global seed is set.
    8323 Hence, these threads generate different sequences of random numbers.
    8324 If each thread needs its own seed, use a sequential ©PRNG© in each thread.
    8325 
    8326 There are two versions of the PRNG functions to manipulate the thread-local PRNG-state, which are differentiated by performance.
     8315The PRNG global and companion thread functions are for concurrent programming, such as randomizing execution in short-running programs, \eg ©yield( prng() % 5 )©.
    83278316\begin{cfa}
    83288317void set_seed( uint32_t seed ); $\C[3.75in]{// set global seed}$
     
    83378326uint32_t prng( $thread\LstStringStyle{\textdollar}$ & th, uint32_t l, uint32_t u );     $\C{// [l,u]}\CRT$
    83388327\end{cfa}
    8339 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.
    8340 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.
     8328The only difference between the two sets of ©prng© routines is performance.
     8329
     8330Because concurrent execution is non-deterministic, seeding the concurrent PRNG is less important, as repeatable execution is impossible.
     8331Hence, there is one system-wide PRNG (global seed) but each \CFA thread has its own non-contended PRNG state.
     8332If the global seed is set, threads start with this seed, until it is reset and then threads start with the reset seed.
     8333Hence, these threads generate the same sequence of random numbers from their specific starting seed.
     8334If the global seed is \emph{not} set, threads start with a random seed, until the global seed is set.
     8335Hence, these threads generate different sequences of random numbers.
     8336If each thread needs its own seed, use a sequential ©PRNG© in each thread.
     8337The 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.
     8338If 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.
    83418339\VRef[Figure]{f:ConcurrentPRNG} shows an example using the slower/faster concurrent PRNG in the program main and a thread.
    83428340
Note: See TracChangeset for help on using the changeset viewer.