Changeset 5cefa43 for doc/user/user.tex

Timestamp:

Feb 22, 2022, 2:44:52 PM (2 years ago)

Author:

Peter A. Buhr <pabuhr@…>

Branches:

ADT, ast-experimental, enum, master, pthread-emulation, qualifiedEnum

Children:

f53afafb

Parents:

1eec0b0

Message:

update PRNG documentation

File:

• doc/user/user.tex (modified) (7 diffs)

doc/user/user.tex

@@ -11 +11 @@
 %% 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
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 
@@ -8223 +8223 @@
 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:
@@ -8249 +8249 @@
 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}$
@@ -8264 +8264 @@
 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.
 
@@ -8307 +8308 @@
 \end{tabular}
 \end{cquote}
-\vspace{-10pt}
 \caption{Sequential PRNG}
 \label{f:SequentialPRNG}
@@ -8313 +8313 @@
 
 \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}$
@@ -8337 +8326 @@
 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.