Changeset d2ad151


Ignore:
Timestamp:
Nov 20, 2022, 10:24:14 PM (3 years ago)
Author:
Peter A. Buhr <pabuhr@…>
Branches:
ADT, ast-experimental, master
Children:
910e1d0
Parents:
25b0fde
Message:

major update of PRNG

Files:
1 added
1 deleted
17 edited

Legend:

Unmodified
Added
Removed

  • libcfa/src/bits/random.hfa

    r25b0fde rd2ad151  
    1010// Created On       : Fri Jan 14 07:18:11 2022
    1111// Last Modified By : Peter A. Buhr
    12 // Last Modified On : Fri Jan 14 07:18:58 2022
    13 // Update Count     : 1
     12// Last Modified On : Sat Nov 19 17:47:43 2022
     13// Update Count     : 8
    1414//
    1515
    … …  
    1818#include <stdint.h>
    1919
     20#ifdef __x86_64__                                                                               // 64-bit architecture
     21#define LEHMER64
     22#else                                                                                                   // 32-bit architecture
     23#define XORSHIFT_6_21_7
     24#endif // __x86_64__
     25
    2026// Pipelined to allow out-of-order overlap with reduced dependencies. Critically, the current random state is returned
    2127// (copied), and then compute and store the next random value.
    … …  
    2329#if defined(__SIZEOF_INT128__)
    2430//--------------------------------------------------
     31        #ifdef LEHMER64
     32        #define PRNG_ARG_T __uint128_t
     33        #define PRNG_NAME lehmer64
     34        #endif // LEHMER64
     35
    2536        static inline uint64_t lehmer64( __uint128_t & state ) {
    2637                __uint128_t ret = state;
    … …  
    5162
    5263//--------------------------------------------------
     64
     65#ifdef XORSHIFT_6_21_7
     66#define PRNG_ARG_T uint32_t
     67#define PRNG_NAME xorshift_6_21_7
     68#endif // XORSHIFT_6_21_7
     69
    5370static inline uint32_t xorshift_6_21_7( uint32_t & state ) {
    5471        uint32_t ret = state;

  • libcfa/src/concurrency/invoke.h

    r25b0fde rd2ad151  
    1010// Created On       : Tue Jan 17 12:27:26 2016
    1111// Last Modified By : Peter A. Buhr
    12 // Last Modified On : Sun Jan  9 19:06:45 2022
    13 // Update Count     : 48
     12// Last Modified On : Fri Nov 18 12:20:26 2022
     13// Update Count     : 49
    1414//
    1515
    … …  
    222222                struct processor * last_proc;
    223223
    224                 uint32_t random_state;                                                  // fast random numbers
     224                __uint128_t random_state;                                               // fast random numbers
    225225
    226226                #if defined( __CFA_WITH_VERIFY__ )

  • libcfa/src/concurrency/kernel/startup.cfa

    r25b0fde rd2ad151  
    3939#include "limits.hfa"
    4040#include "math.hfa"
     41#include "bits/random.hfa"                                                              // prng
    4142
    4243#define CFA_PROCESSOR_USE_MMAP 0
    … …  
    107108extern void __wake_proc(processor *);
    108109extern int cfa_main_returned;                                                   // from interpose.cfa
    109 uint32_t __global_random_prime = 4_294_967_291u, __global_random_mask = false;
     110PRNG_ARG_T __global_random_prime = 4_294_967_291u;
     111bool __global_random_mask = false;
    110112
    111113//-----------------------------------------------------------------------------

  • libcfa/src/concurrency/thread.cfa

    r25b0fde rd2ad151  
    1010// Created On       : Tue Jan 17 12:27:26 2017
    1111// Last Modified By : Peter A. Buhr
    12 // Last Modified On : Sat Feb 12 15:24:18 2022
    13 // Update Count     : 66
     12// Last Modified On : Sun Nov 20 17:17:50 2022
     13// Update Count     : 80
    1414//
    1515
    … …  
    2626#include "invoke.h"
    2727
    28 extern uint32_t __global_random_seed, __global_random_prime, __global_random_mask;
     28extern PRNG_ARG_T __global_random_seed, __global_random_prime;
     29extern bool __global_random_mask;
    2930
    3031#pragma GCC visibility push(default)
    … …  
    221222
    222223//-----------------------------------------------------------------------------
    223 #define GENERATOR LCG
    224 
    225 void set_seed( uint32_t seed ) {
    226         uint32_t & state = active_thread()->random_state;
     224
     225void set_seed( uint64_t seed ) {
     226        PRNG_ARG_T & state = active_thread()->random_state;
    227227        state = __global_random_seed = seed;
    228         GENERATOR( state );
     228        (void)PRNG_NAME( state );                                                       // prime PRNG
    229229        __global_random_prime = state;
    230230        __global_random_mask = true;
    231231} // set_seed
    232232
    233 uint32_t prng( void ) {                                                                 // [0,UINT_MAX]
    234         uint32_t & state = active_thread()->random_state;
    235         return GENERATOR( state );
     233uint64_t prng( void ) {                                                                 // [0,UINT_MAX]
     234        PRNG_ARG_T & state = active_thread()->random_state;
     235        return PRNG_NAME( state );
    236236} // prng
    237237

  • libcfa/src/concurrency/thread.hfa

    r25b0fde rd2ad151  
    1010// Created On       : Tue Jan 17 12:27:26 2017
    1111// Last Modified By : Peter A. Buhr
    12 // Last Modified On : Fri Feb 11 16:34:07 2022
    13 // Update Count     : 20
     12// Last Modified On : Sat Nov 19 16:41:27 2022
     13// Update Count     : 30
    1414//
    1515
    … …  
    2323#include "monitor.hfa"
    2424#include "exception.hfa"
     25#include "bits/random.hfa"
    2526
    2627//-----------------------------------------------------------------------------
    … …  
    142143// prng
    143144static inline {
    144         uint32_t prng( thread$ & th ) __attribute__(( warn_unused_result )) { return LCG( th.random_state ); } // [0,UINT_MAX]
    145         uint32_t prng( thread$ & th, uint32_t u ) __attribute__(( warn_unused_result )) { return prng( th ) % u; } // [0,u)
    146         uint32_t prng( thread$ & th, uint32_t l, uint32_t u ) __attribute__(( warn_unused_result )) { return prng( th, u - l + 1 ) + l; } // [l,u]
     145        uint64_t prng( thread$ & th ) __attribute__(( warn_unused_result )) { return PRNG_NAME( th.random_state ); } // [0,UINT_MAX]
     146        uint64_t prng( thread$ & th, uint64_t u ) __attribute__(( warn_unused_result )) { return prng( th ) % u; } // [0,u)
     147        uint64_t prng( thread$ & th, uint64_t l, uint64_t u ) __attribute__(( warn_unused_result )) { return prng( th, u - l + 1 ) + l; } // [l,u]
    147148        forall( T & | is_thread(T) ) {
    148                 uint32_t prng( T & th ) __attribute__(( warn_unused_result )) { return prng( (thread &)th ); } // [0,UINT_MAX]
    149                 uint32_t prng( T & th, uint32_t u ) __attribute__(( warn_unused_result )) { return prng( th ) % u; } // [0,u)
    150                 uint32_t prng( T & th, uint32_t l, uint32_t u ) __attribute__(( warn_unused_result )) { return prng( th, u - l + 1 ) + l; } // [l,u]
     149                uint64_t prng( T & th ) __attribute__(( warn_unused_result )) { return prng( (thread &)th ); } // [0,UINT_MAX]
     150                uint64_t prng( T & th, uint64_t u ) __attribute__(( warn_unused_result )) { return prng( th ) % u; } // [0,u)
     151                uint64_t prng( T & th, uint64_t l, uint64_t u ) __attribute__(( warn_unused_result )) { return prng( th, u - l + 1 ) + l; } // [l,u]
    151152        } // distribution
    152153} // distribution

  • libcfa/src/startup.cfa

    r25b0fde rd2ad151  
    1010// Created On       : Tue Jul 24 16:21:57 2018
    1111// Last Modified By : Peter A. Buhr
    12 // Last Modified On : Thu Oct  6 13:51:57 2022
    13 // Update Count     : 57
     12// Last Modified On : Sun Nov 20 21:26:40 2022
     13// Update Count     : 59
    1414//
    1515
    … …  
    1818#include <stdlib.h>                                                                             // getenv
    1919#include "bits/defs.hfa"                                                                // rdtscl
     20#include "bits/random.hfa"                                                              // rdtscl
    2021#include "startup.hfa"
    2122
    22 extern uint32_t __global_random_seed;                                   // sequential/concurrent
    23 extern uint32_t __global_random_state;                                  // sequential
     23extern PRNG_ARG_T __global_random_seed;                                 // sequential/concurrent
     24extern PRNG_ARG_T __global_random_state;                                // sequential
    2425
    2526extern "C" {

  • libcfa/src/stdlib.cfa

    r25b0fde rd2ad151  
    1010// Created On       : Thu Jan 28 17:10:29 2016
    1111// Last Modified By : Peter A. Buhr
    12 // Last Modified On : Thu Aug 25 22:41:14 2022
    13 // Update Count     : 604
     12// Last Modified On : Sat Nov 19 16:42:26 2022
     13// Update Count     : 612
    1414//
    1515
    … …  
    225225//---------------------------------------
    226226
    227 #define GENERATOR LCG
    228 
    229227// would be cool to make hidden but it's needed for libcfathread
    230 __attribute__((visibility("default"))) uint32_t __global_random_seed;                                                   // sequential/concurrent
    231 __attribute__((visibility("hidden"))) uint32_t __global_random_state;                                                   // sequential only
    232 
    233 void set_seed( PRNG & prng, uint32_t seed_ ) with( prng ) { state = seed = seed_; GENERATOR( state ); } // set seed
    234 
    235 void set_seed( uint32_t seed ) { __global_random_state = __global_random_seed = seed; GENERATOR( __global_random_state ); }
    236 uint32_t get_seed() { return __global_random_seed; }
    237 uint32_t prng( void ) { return GENERATOR( __global_random_state ); } // [0,UINT_MAX]
     228__attribute__((visibility("default"))) PRNG_ARG_T __global_random_seed; // sequential/concurrent
     229__attribute__((visibility("hidden"))) PRNG_ARG_T __global_random_state; // sequential only
     230
     231void set_seed( uint64_t seed ) { __global_random_state = __global_random_seed = seed; PRNG_NAME( __global_random_state ); }
     232uint64_t get_seed() { return __global_random_seed; }
     233uint64_t prng( void ) { return PRNG_NAME( __global_random_state ); } // [0,UINT_MAX]
    238234
    239235//---------------------------------------

  • libcfa/src/stdlib.hfa

    r25b0fde rd2ad151  
    1010// Created On       : Thu Jan 28 17:12:35 2016
    1111// Last Modified By : Peter A. Buhr
    12 // Last Modified On : Thu Aug 25 18:07:06 2022
    13 // Update Count     : 645
     12// Last Modified On : Sun Nov 20 17:12:37 2022
     13// Update Count     : 730
    1414//
    1515
    … …  
    404404//   calls( sprng );
    405405
    406 struct PRNG {
     406trait basic_prng( PRNG &, S, R ) {
     407        void set_seed( PRNG & prng, S seed );                           // set seed
     408        S get_seed( PRNG & prng );                                                      // get seed
     409        R prng( PRNG & prng );
     410        void ?{}( PRNG & prng );                                                        // random seed
     411        void ?{}( PRNG & prng, S seed );                                        // fixed seed
     412}; // basic_prng
     413
     414static inline forall( PRNG &, S, R | basic_prng( PRNG, S, R ) | { R ?%?( R, R ); } ) {
     415        R prng( PRNG & prng, R u ) { return prng( prng ) % u; } // [0,u)
     416}
     417static inline forall( PRNG &, S, R | basic_prng( PRNG, S, R ) | { R ?+?( R, R ); R ?-?( R, R ); R ?%?( R, R ); void ?{}( R &, one_t ); } ) {
     418        R prng( PRNG & prng, R l, R u ) { return prng( prng, u - l + (R){1} ) + l; } // [l,u]
     419}
     420
     421struct PRNG32 {
    407422        uint32_t callcnt;                                                                       // call count
    408423        uint32_t seed;                                                                          // current seed
    409         uint32_t state;                                                                         // random state
     424        PRNG_ARG_T state;                                                                       // random state
    410425}; // PRNG
    411426
    412 void set_seed( PRNG & prng, uint32_t seed_ );
    413 static inline {
    414         void ?{}( PRNG & prng ) with( prng ) { callcnt = 0; set_seed( prng, rdtscl() ); } // random seed
    415         void ?{}( PRNG & prng, uint32_t seed ) with( prng ) { callcnt = 0; set_seed( prng, seed ); } // fixed seed
    416         uint32_t get_seed( PRNG & prng ) __attribute__(( warn_unused_result )) with( prng ) { return seed; } // get seed
    417         uint32_t prng( PRNG & prng ) __attribute__(( warn_unused_result )) with( prng ) { callcnt += 1; return LCG( state ); } // [0,UINT_MAX]
    418         uint32_t prng( PRNG & prng, uint32_t u ) __attribute__(( warn_unused_result )) { return prng( prng ) % u; } // [0,u)
    419         uint32_t prng( PRNG & prng, uint32_t l, uint32_t u ) __attribute__(( warn_unused_result )) { return prng( prng, u - l + 1 ) + l; } // [l,u]
    420         uint32_t calls( PRNG & prng ) __attribute__(( warn_unused_result )) with( prng ) { return callcnt; }
     427static inline {
     428        void set_seed( PRNG32 & prng, uint32_t seed_ ) with( prng ) { state = seed = seed_; PRNG_NAME( state ); } // set seed
     429        uint32_t get_seed( PRNG32 & prng ) __attribute__(( warn_unused_result )) with( prng ) { return seed; } // get seed
     430        uint32_t prng( PRNG32 & prng ) __attribute__(( warn_unused_result )) with( prng ) { callcnt += 1; return PRNG_NAME( state ); } // [0,UINT_MAX]
     431        uint32_t calls( PRNG32 & prng ) __attribute__(( warn_unused_result )) with( prng ) { return callcnt; }
     432        void ?{}( PRNG32 & prng ) with( prng ) { callcnt = 0; set_seed( prng, rdtscl() ); } // random seed
     433        void ?{}( PRNG32 & prng, uint32_t seed ) with( prng ) { callcnt = 0; set_seed( prng, seed ); } // fixed seed
     434} // distribution
     435
     436struct PRNG64 {
     437        uint64_t callcnt;                                                                       // call count
     438        uint64_t seed;                                                                          // current seed
     439        PRNG_ARG_T state;                                                                       // random state
     440}; // PRNG
     441
     442static inline {
     443        void set_seed( PRNG64 & prng, uint64_t seed_ ) with( prng ) { state = seed = seed_; PRNG_NAME( state ); } // set seed
     444        uint64_t get_seed( PRNG64 & prng ) __attribute__(( warn_unused_result )) with( prng ) { return seed; } // get seed
     445        uint64_t prng( PRNG64 & prng ) __attribute__(( warn_unused_result )) with( prng ) { callcnt += 1; return PRNG_NAME( state ); } // [0,UINT_MAX]
     446        uint64_t calls( PRNG64 & prng ) __attribute__(( warn_unused_result )) with( prng ) { return callcnt; }
     447        void ?{}( PRNG64 & prng ) with( prng ) { callcnt = 0; set_seed( prng, rdtscl() ); } // random seed
     448        void ?{}( PRNG64 & prng, uint64_t seed ) with( prng ) { callcnt = 0; set_seed( prng, seed ); } // fixed seed
    421449} // distribution
    422450
    … …  
    435463//   prng( 5, 21 );
    436464
    437 void set_seed( uint32_t seed_ ) OPTIONAL_THREAD;
    438 uint32_t get_seed() __attribute__(( warn_unused_result ));
    439 uint32_t prng( void ) __attribute__(( warn_unused_result )) OPTIONAL_THREAD; // [0,UINT_MAX]
    440 static inline {
    441         uint32_t prng( uint32_t u ) __attribute__(( warn_unused_result )) { return prng() % u; } // [0,u)
    442         uint32_t prng( uint32_t l, uint32_t u ) __attribute__(( warn_unused_result )) { return prng( u - l + 1 ) + l; } // [l,u]
     465// Harmonize with concurrency/thread.hfa.
     466void set_seed( uint64_t seed_ ) OPTIONAL_THREAD;
     467uint64_t get_seed() __attribute__(( warn_unused_result ));
     468uint64_t prng( void ) __attribute__(( warn_unused_result )) OPTIONAL_THREAD; // [0,UINT_MAX]
     469static inline {
     470        uint64_t prng( uint64_t u ) __attribute__(( warn_unused_result )) { return prng() % u; } // [0,u)
     471        uint64_t prng( uint64_t l, uint64_t u ) __attribute__(( warn_unused_result )) { return prng( u - l + 1 ) + l; } // [l,u]
    443472} // distribution
    444473

  • tests/.expect/nested_function.txt

    r25b0fde rd2ad151  
    1 total 105
     1total 80

  • tests/PRNG.cfa

    r25b0fde rd2ad151  
    88// Created On       : Wed Dec 29 09:38:12 2021
    99// Last Modified By : Peter A. Buhr
    10 // Last Modified On : Sat Apr  9 15:21:14 2022
    11 // Update Count     : 344
     10// Last Modified On : Sun Nov 20 22:17:35 2022
     11// Update Count     : 377
    1212//
    1313
    … …  
    2222#include <mutex_stmt.hfa>
    2323
     24#ifdef __x86_64__                                                                               // 64-bit architecture
     25#define PRNG PRNG64
     26#else                                                                                                   // 32-bit architecture
     27#define PRNG PRNG32
     28#endif // __x86_64__
     29
    2430#ifdef TIME                                                                                             // use -O2 -nodebug
    2531#define STARTTIME start = timeHiRes()
    … …  
    5460
    5561
    56 uint32_t seed = 1009;
     62unsigned int seed = 1009;
    5763
    5864thread T1 {};
    … …  
    158164#if 1
    159165        PRNG prng;
     166
    160167        if ( seed != 0 ) set_seed( prng, seed );
    161168
    … …  
    164171        for ( 20 ) {
    165172                sout | wd(13, prng( prng )) | nonl;                             // cascading => side-effect functions called in arbitary order
    166                 sout | wd(10, prng( prng, 5 )) | nonl;
    167                 sout | wd(13, prng( prng, 0, 5 ));
     173                sout | wd(10, prng( prng, 5z )) | nonl;
     174                sout | wd(13, prng( prng, 0, 5z ));
    168175        } // for
    169176        sout | sepEnable;
    … …  
    199206        for ( 20 ) {
    200207                sout | wd(13, prng()) | nonl;                                   // cascading => side-effect functions called in arbitary order
    201                 sout | wd(10, prng( 5 )) | nonl;
    202                 sout | wd(13, prng( 0, 5 ));
     208                sout | wd(10, prng( 5z )) | nonl;
     209                sout | wd(13, prng( 0, 5z ));
    203210        } // for
    204211        sout | sepEnable;
    … …  
    235242        for ( 20 ) {
    236243                sout | wd(13, prng( th )) | nonl;                               // cascading => side-effect functions called in arbitary order
    237                 sout | wd(10, prng( th, 5 )) | nonl;
    238                 sout | wd(13, prng( th, 0, 5 ));
     244                sout | wd(10, prng( th, 5z )) | nonl;
     245                sout | wd(13, prng( th, 0, 5z ));
    239246        } // for
    240247        sout | sepEnable;

  • tests/concurrent/barrier/generation.cfa

    r25b0fde rd2ad151  
    3737                for(c; 'A' ~= 'Z') {
    3838                        // Yield for chaos
    39                         yield(prng(this, 10));
     39                        yield( (unsigned)prng(this, 10) );
    4040
    4141                        // Print the generation, no newline because
    … …  
    4343
    4444                        // Yield again for more chaos
    45                         yield(prng(this, 10));
     45                        yield( (unsigned)prng(this, 10) );
    4646
    4747                        // Block on the barrier

  • tests/concurrent/barrier/order.cfa

    r25b0fde rd2ad151  
    3737        for(l; NUM_LAPS) {
    3838                // Yield for chaos
    39                 yield(prng(this, 10));
     39                yield( (unsigned)prng(this, 10) );
    4040
    4141                // Block and what order we arrived

  • tests/concurrent/once.cfa

    r25b0fde rd2ad151  
    3030
    3131                // sometime yields
    32                 yield(prng(this, 3));
     32                yield( (unsigned)prng(this, 3) );
    3333        }
    3434}

  • tests/concurrent/readyQ/leader_spin.cfa

    r25b0fde rd2ad151  
    2626}
    2727
    28 PRNG lead_rng;
     28PRNG64 lead_rng;
    2929volatile unsigned leader;
    3030volatile size_t lead_idx;
    3131
    32 const unsigned nthreads = 17;
    33 const unsigned stop_count = 327;
     32const uint64_t nthreads = 17;
     33const uint64_t stop_count = 327;
    3434
    3535thread$ * the_main;

  • tests/io/away_fair.cfa

    r25b0fde rd2ad151  
    6767                #endif
    6868
    69                 yield( prng( this, 15 ) );
     69                yield( (unsigned)prng( this, 15 ) );
    7070
    7171                #if CFA_HAVE_LINUX_IO_URING_H

  • tests/io/comp_basic.cfa

    r25b0fde rd2ad151  
    5858                block( globals.bar );
    5959
    60                 yield( prng( this, 15 ) );
     60                yield( (unsigned)prng( this, 15 ) );
    6161
    6262                unsigned i = __atomic_add_fetch( &counter, 1, __ATOMIC_SEQ_CST );

  • tests/io/comp_fair.cfa

    r25b0fde rd2ad151  
    7878                block( globals.bar );
    7979
    80                 yield( prng( this, 15 ) );
     80                yield( (unsigned)prng( this, 15 ) );
    8181
    8282                unsigned i = __atomic_add_fetch( &counter, 1, __ATOMIC_SEQ_CST );
Note: See TracChangeset for help on using the changeset viewer.