Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

add documentation for DPRNG (and user-controllable runtime parameters?) #191

Open
behoppe opened this issue Dec 5, 2022 · 1 comment
Open
Assignees
Labels
documentation Improvements or additions to documentation

Comments

@behoppe
Copy link
Member

behoppe commented Dec 5, 2022

@neboat @DorothyCurtis @ailiop @timkaler @cleiserson I am curious what you think about creating an entry in our reference documentation for user-controllable runtime parameters, as a place where we would include documentation for deterministic random number generation. More below:

Issues
OpenCilk 2.0 supports deterministic pseudo-random number generation, but the website does not document how to use it.

Improvements
Let's add documentation, perhaps based on this explanation from @neboat

OpenCilk 2.0 supports pedigrees and DPRNG. Simply link the Cilk program with the additional library -lopencilk-pedigrees to enable pedigrees and DPRNG. No need to recompile. (PS: Include the header file <cilk/cilk_api.h> to get declarations for __cilkrts_get_dprand(), __cilkrts_dprand_set_seed(), and __cilkrts_get_pedigree(), as well as the __cilkrts_pedigree structure type.)

There are three options for DPRNG using OpenCilk 2.0.

  • Use the OpenCilk runtime's builtin DPRNG. To generate a pseudorandom number, call __cilkrts_get_dprand(). A __cilkrts_get_dprand() call returns a 64-bit unsigned integer, although the return value will be one of 2^64-59 possible results. (You can also reseed that pseudorandom number generator by calling __cilkrts_dprand_set_seed(seed) at the beginning of the program, where seed is a 64-bit unsigned integer.) The __cilkrts_get_dprand() function is easy to use and fast, but it offers only limited control over the DPRNG.
  • Use an existing DPRNG library that uses pedigrees. The only existing library I know of is the DotMix implementation from CilkPub. We have a copy of the CilkPub code among the OpenCilk repositories, but CilkPub is implemented entirely in C++, so I doubt that's helpful to you right now.
  • Write your own DPRNG library that uses pedigrees. The library can read the pedigree of the current strand by calling __cilkrts_get_pedigree(), which returns the pedigree as a singly-linked list. (Specifically, it returns a __cilkrts_pedigree structure, which contains a rank and a pointer to a parent __cilkrts_pedigree structure.) This option allows one to flexibly implement a new DPRNG in C or C++, but doing so may be more complicated than you're looking for.

Additional discussion
Where does this documentation fit into the website? It looks to me like reference documentation (not tutorial, user's guide, or discussion). Are there similar items? I propose to wrap this documentation task within a larger task to create a reference page for user-controllable runtime parameters.

@behoppe behoppe added the documentation Improvements or additions to documentation label Dec 5, 2022
@timkaler
Copy link
Contributor

timkaler commented Dec 9, 2022

Here is a preliminary rough draft:

https://deploy-preview-195--sage-licorice-6da44d.netlify.app/doc/tutorials/tutorial-for-dprng/

TB has noted that in the example code, it is not necessary to keep track of both "inside_circle" and "outside_circle" because the total number of points is known from the number of iterations in the cilk_for loop.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
documentation Improvements or additions to documentation
Projects
None yet
Development

No branches or pull requests

2 participants