Index: libcfa/src/concurrency/kernel/startup.cfa =================================================================== --- libcfa/src/concurrency/kernel/startup.cfa (revision a10f6b41699df79630c018e98b486d9ee3ecfd70) +++ libcfa/src/concurrency/kernel/startup.cfa (revision 1959528943f80644f53138c6bb1c3c33883c8ceb) @@ -101,4 +101,5 @@ extern void __wake_proc(processor *); extern int cfa_main_returned; // from interpose.cfa +extern uint32_t __global_random_seed; //----------------------------------------------------------------------------- @@ -489,4 +490,5 @@ preferred = ready_queue_new_preferred(); last_proc = 0p; + random_state = __global_random_seed; #if defined( __CFA_WITH_VERIFY__ ) canary = 0x0D15EA5E0D15EA5Ep; Index: libcfa/src/concurrency/thread.cfa =================================================================== --- libcfa/src/concurrency/thread.cfa (revision a10f6b41699df79630c018e98b486d9ee3ecfd70) +++ libcfa/src/concurrency/thread.cfa (revision 1959528943f80644f53138c6bb1c3c33883c8ceb) @@ -10,6 +10,6 @@ // Created On : Tue Jan 17 12:27:26 2017 // Last Modified By : Peter A. Buhr -// Last Modified On : Mon Jan 10 17:05:35 2022 -// Update Count : 28 +// Last Modified On : Wed Jan 12 18:28:18 2022 +// Update Count : 35 // @@ -27,5 +27,5 @@ uint64_t thread_rand(); -extern uint32_t __thread_seed; // global thread seed +extern uint32_t __global_random_seed; //----------------------------------------------------------------------------- @@ -41,5 +41,4 @@ self_mon.owner = &this; self_mon.recursion = 1; - random_state = __thread_seed; self_mon_p = &self_mon; curr_cluster = &cl; @@ -48,4 +47,5 @@ preferred = ready_queue_new_preferred(); last_proc = 0p; + random_state = __global_random_seed; #if defined( __CFA_WITH_VERIFY__ ) canary = 0x0D15EA5E0D15EA5Ep; @@ -180,19 +180,22 @@ return ret; } - + #define GENERATOR LCG -inline uint32_t MarsagliaXor( uint32_t & state ) { +static inline uint32_t MarsagliaXor( uint32_t & state ) { + uint32_t ret = state; state ^= state << 6; state ^= state >> 21; state ^= state << 7; - return state; + return ret; } // MarsagliaXor -inline uint32_t LCG( uint32_t & state ) { // linear congruential generator - return state = 36969 * (state & 65535) + (state >> 16); // 36969 is NOT prime! +static inline uint32_t LCG( uint32_t & state ) { // linear congruential generator + uint32_t ret = state; + state = 36969 * (state & 65535) + (state >> 16); // 36969 is NOT prime! No not change it! + return ret; } // LCG -void set_seed( uint32_t seed ) { active_thread()->random_state = seed; __thread_seed = seed; } +void set_seed( uint32_t seed ) { active_thread()->random_state = seed; __global_random_seed = seed; } uint32_t prng( void ) { return GENERATOR( active_thread()->random_state ); } // [0,UINT_MAX] Index: libcfa/src/startup.cfa =================================================================== --- libcfa/src/startup.cfa (revision a10f6b41699df79630c018e98b486d9ee3ecfd70) +++ libcfa/src/startup.cfa (revision 1959528943f80644f53138c6bb1c3c33883c8ceb) @@ -10,6 +10,6 @@ // Created On : Tue Jul 24 16:21:57 2018 // Last Modified By : Peter A. Buhr -// Last Modified On : Sat Jan 9 23:18:23 2021 -// Update Count : 34 +// Last Modified On : Wed Jan 12 16:25:37 2022 +// Update Count : 49 // @@ -18,4 +18,7 @@ #include // getenv #include "startup.hfa" +#include "bits/defs.hfa" + +extern uint32_t __global_random_seed; extern "C" { @@ -48,4 +51,5 @@ void __cfaabi_core_startup( void ) __attribute__(( constructor( STARTUP_PRIORITY_CORE ) )); void __cfaabi_core_startup( void ) { + __global_random_seed = rdtscl(); __cfaabi_interpose_startup(); __cfaabi_device_startup(); Index: libcfa/src/stdlib.cfa =================================================================== --- libcfa/src/stdlib.cfa (revision a10f6b41699df79630c018e98b486d9ee3ecfd70) +++ libcfa/src/stdlib.cfa (revision 1959528943f80644f53138c6bb1c3c33883c8ceb) @@ -10,6 +10,6 @@ // Created On : Thu Jan 28 17:10:29 2016 // Last Modified By : Peter A. Buhr -// Last Modified On : Mon Jan 10 17:07:21 2022 -// Update Count : 572 +// Last Modified On : Wed Jan 12 16:25:36 2022 +// Update Count : 578 // @@ -223,24 +223,34 @@ //--------------------------------------- +// Pipelined to allow OoO overlap with reduced dependencies. Critically, return the current value, and compute and store +// the next value. + #define GENERATOR LCG -inline uint32_t MarsagliaXor( uint32_t & state ) { +static inline uint32_t MarsagliaXor( uint32_t & state ) { + uint32_t ret = state; state ^= state << 6; state ^= state >> 21; state ^= state << 7; - return state; + return ret; } // MarsagliaXor -inline uint32_t LCG( uint32_t & state ) { // linear congruential generator - return state = 36969 * (state & 65535) + (state >> 16); // 36969 is NOT prime! +static inline uint32_t LCG( uint32_t & state ) { // linear congruential generator + uint32_t ret = state; + state = 36969 * (state & 65535) + (state >> 16); // 36969 is NOT prime! No not change it! + return ret; } // LCG -uint32_t __thread_seed = rdtscl(); // global thread seed - -void set_seed( uint32_t seed ) { __thread_seed = seed; } -uint32_t get_seed() { return __thread_seed; } +uint32_t __global_random_seed; + +void set_seed( PRNG & prng, uint32_t seed_ ) with( prng ) { state = seed = seed_; GENERATOR( state ); } // set seed uint32_t prng( PRNG & prng ) with( prng ) { callcnt += 1; return GENERATOR( state ); } -uint32_t prng( void ) { return GENERATOR( __thread_seed ); } // [0,UINT_MAX] +void set_seed( uint32_t seed ) { + active_thread()->random_state = __global_random_seed = seed; + GENERATOR( active_thread()->random_state ); +} // set_seed +uint32_t get_seed() { return __global_random_seed; } +uint32_t prng( void ) { return GENERATOR( active_thread()->random_state ); } // [0,UINT_MAX] //--------------------------------------- Index: libcfa/src/stdlib.hfa =================================================================== --- libcfa/src/stdlib.hfa (revision a10f6b41699df79630c018e98b486d9ee3ecfd70) +++ libcfa/src/stdlib.hfa (revision 1959528943f80644f53138c6bb1c3c33883c8ceb) @@ -10,6 +10,6 @@ // Created On : Thu Jan 28 17:12:35 2016 // Last Modified By : Peter A. Buhr -// Last Modified On : Mon Jan 10 17:03:18 2022 -// Update Count : 619 +// Last Modified On : Wed Jan 12 09:09:48 2022 +// Update Count : 620 // @@ -386,4 +386,23 @@ //--------------------------------------- +// Sequential Pseudo Random-Number Generator : generate repeatable sequence of values that appear random. +// +// Declaration : +// PRNG sprng = { 1009 } - set starting seed versus random seed +// +// Interface : +// set_seed( sprng, 1009 ) - set starting seed for ALL kernel threads versus random seed +// get_seed( sprng ) - read seed +// prng( sprng ) - generate random value in range [0,UINT_MAX] +// prng( sprng, u ) - generate random value in range [0,u) +// prng( sprng, l, u ) - generate random value in range [l,u] +// calls( sprng ) - number of generated random value so far +// +// Examples : generate random number between 5-21 +// prng( sprng ) % 17 + 5; values 0-16 + 5 = 5-21 +// prng( sprng, 16 + 1 ) + 5; +// prng( sprng, 5, 21 ); +// calls( sprng ); + struct PRNG { uint32_t callcnt; // call count @@ -392,7 +411,7 @@ }; // PRNG +void set_seed( PRNG & prng, uint32_t seed_ ); uint32_t prng( PRNG & prng ) __attribute__(( warn_unused_result )); // [0,UINT_MAX] static inline { - void set_seed( PRNG & prng, uint32_t seed_ ) with( prng ) { state = seed = seed_; } // set seed void ?{}( PRNG & prng ) { set_seed( prng, rdtscl() ); } // random seed void ?{}( PRNG & prng, uint32_t seed ) { set_seed( prng, seed ); } // fixed seed @@ -403,6 +422,20 @@ } // distribution +// Concurrent Pseudo Random-Number Generator : generate repeatable sequence of values that appear random. +// +// Interface : +// set_seed( 1009 ) - fixed seed for all kernel threads versus random seed +// get_seed() - read seed +// prng() - generate random value in range [0,UINT_MAX] +// prng( u ) - generate random value in range [0,u) +// prng( l, u ) - generate random value in range [l,u] +// +// Examples : generate random number between 5-21 +// prng() % 17 + 5; values 0-16 + 5 = 5-21 +// prng( 16 + 1 ) + 5; +// prng( 5, 21 ); + void set_seed( uint32_t seed_ ) OPTIONAL_THREAD; -uint32_t get_seed() __attribute__(( warn_unused_result )); +uint32_t get_seed() __attribute__(( warn_unused_result )) OPTIONAL_THREAD; uint32_t prng( void ) __attribute__(( warn_unused_result )) OPTIONAL_THREAD; // [0,UINT_MAX] static inline {