STL and SYCL compatible C++ version

[MathiasMagnus]

Hi!

I would like to humbly bring forth a feature request, namely having a C++ STL compatible version satisfying UniformRandomBitGenerator, something along the lines of std::mersenne_twister_engine.

The problem with most STL implementations is that they do not satisfy the StandardLayoutType concept, which precludes its usage in ComputeCpp, the only true, OpenCL accelerated SYCL implementation thus far. SYCL is the CUDA of OpenCL, to put it shortly, a single-source, language extension-free abstraction over OpenCL. The next best thing after ice cream. :)

ComputeCpp because is not a single-pass compiler and has to interact with other host compiler, mandates that classes used in device code be standard layout. Compilers have a limited amount of freedom in how to layout types in memory and if the host and device compilers do not agree on their layout, one will read garbled things originating from the other, hence the least common denominator is standard layout types.

I have created a stub implementation based on cppreference and started tweaking it based on MSVCs implementation and tinymt64.h. Ideally, the implementations of tinymt64 and tinymt32 should not differ. Some compile-time trickery (TMP) might be needed, but mostly flat constexpr functions. MSVCs implementation has no specializations as far as I saw, so it's fairly C code with minimal inheritance (the source of non-stanard layout) and a few static constexpr helper variables.

TinyMT.zip

I believe that someone with deep knowledge and mediocre C++ knowledge can put together this class in a fairly short amount of time. It might just be that std::mersenne_twister_engine is actually TineMT compatible, I just couldn't identify all the template params inside tinymt64.h.

Again, I would like to kindly ask for a standard layout tiny_mersenne_twister_engine implementation that satisfies UniformRandomBitGenerator to be used either with only the STL or even inside SYCL device code for parallel Monte-Carlo simulations.

[MSaito]

I'm sorry, but I don't think I'm a man with deep knowledge and mediocre C++ knowledge. And I'd like to keep this code simple, to show basic algorithm. You can fork and make your own version. If you tell me your STL compatible nice code, I will add link to your github page in our web page: http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/VERSIONS/C-LANG/c-lang.html

[MathiasMagnus]

Thank you for @MSaito for coming back to me on this.

I'm going forward and do a straight-forward port of the provided TinyMT.h code available. I've come across someone else who also took on this endeavor, but could not find documentation regarding TinyMT and its relation to MT.

MSVCs implementation is in fairly good accordance to the paper, namely

MSVC

_Ty _Res = this->_Ax[this->_Idx++] & _WMSK;
_Res ^= (_Res >> _Ux) & _Dxval;
_Res ^= (_Res << _Sx) & _Bx;
_Res ^= (_Res << _Tx) & _Cx;
_Res ^= (_Res & _WMSK) >> _Lx;
return (_Res)

Paper

y := x + (x >> u)
x := y + ((y << s) AND b)
y := y + ((y << t) AND c)
z := y + (y >> l)

I can see the connection between them. However, the relevant part of TinyMT.h is

random->status[0] &= TINYMT64_MASK;
x = random->status[0] ^ random->status[1];
x ^= x << TINYMT64_SH0;
x ^= x >> 32;
x ^= x << 32;
x ^= x << TINYMT64_SH1;

There are so many shortcuts taken inside the code, it's impossible to decipher. Not even the direction of the shifts match, the name of the defines have no connection to the names found in the article. What I've managed to identify thus far:

• The recalculation of the state vector happens unconditionally on every step, there is no branching required due to the extremely limited length of the vector.

It would be nice if the math behind TinyMT were documented somewhere and all of the shortcuts employed in the code compared to regular MT.

[MSaito]

I'm sorry, I did not write about TInyMT in English. Following page may help you a bit: http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/TINYMT/index.html Following PDF may not help you, it is written in Japanese and it may old. tinymt.pdf And following page will confuse you. https://github.com/MSaito/TinyMTPeke

TinyMTdc is main result of this project. Parameter set used in TinyMT64.h is one of generated parameters by TinyMTdc. Shift parameters you mentioned are selected 'ad hoc' or 'heuristic'

[MathiasMagnus]

Thank you for the clarifications. I did see the project page and also found the paper holding the original work with pseudo-code as well. Very enlightening.

I'm currently at building the dc project for myself and seeing what sort of output it has. What I'm trying to achieve here is get a generator that may be a drop-in replacement to those random engines found in the STL, provide a working set of default params (just like std::mt199937 is an alias of a much longer type name holding one set of working params).

I found that the version found in this repo doesn't seem to make a clear distinction between parameters of the generator and the state of a given instance. I intend to decouple these two and provide both a version where the generator parameters are compile-time constants encoded in the template parameters (hence they don't use memory) for the random seeding and jump multi-sequence case AND create one where they are dynamic values for the multi-generator case, in case more than doubling the register usage is not an issue.

You can follow along my work in this repo. I will gladly contribute the code back here once it's in working shape, but I do intend on having a more comprehensive set of generators to use with SYCL, hence I think it's best development goes on there. (Shortly following TinyMT, I want to also add MWC64X, another small and sexy prng which has served me well in the past.) As for the license, I'm really not good at stuff like this. How would you like me to mark that even though the code has been turned inside out, the guts are largely based on your work? (Is this significant a change enough to not inherit the copyright notice? Link to your repo (as it is now)? Do you have experience with this?)

[MSaito]

We (Mutsuo Saito and Makoto Matsumoto) are not very nervous about copyright, but an user of your program (maybe a company) may be nervous and may want to avoid litigation risk. BSD-3-Clause License, we adopted for TinyMT, is one of the most popular open source licenses, and it is not so severe with users. If you adopt the same or compatible license, an user of your program can use it without worrying about litigation risk.

[majiang]

As far as I know, translation to another language, compatible version with another library, etc, are considered a derived work. So, your LICENSE file should look like:

Copyright (c) 2011, 2013 Mutsuo Saito, Makoto Matsumoto, Hiroshima University and The University of Tokyo. Copyright (c) 2018 Nagy-Egri Máté Ferenc, Wigner GPU-Laboratory. All rights reserved.

Redistribution and use in source and binary forms, ....

[MathiasMagnus]

@majiang Thanks for the info. Will update all source files accordingly.