[jira] [Commented] (RNG-181) LXM generators to implement SplittableUniformRandomProvider

["Alex Herbert (Jira)" <ji...@apache.org>]

    [ https://issues.apache.org/jira/browse/RNG-181?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=17602754#comment-17602754 ] 

Alex Herbert commented on RNG-181:
----------------------------------

h2. Implementation Update

The previous description indicated that the seed for each RNG in the stream can be composed as a shifted set of random seed bits and the stream position:
{noformat}
rngSeed = ((seed << shift) | position){noformat}
If the lowest bit of the initial random seed is set to 1 then overlap between position after each increment and the seed can be detected with a bitwise and. If overlap occurs the seed is shifted to remove overlap.

However this is not the minimum requirement for the seed. To ensure uniqueness of each rngSeed the possibility of the seed bits matching the shifted seed must be eliminated. The seed can be viewed as a set of n-bit chars. These are left shifted n-bits to avoid overlap as the position increases in magnitude:
{noformat}
seed      = abcdefgh
position  =    ...XX

start:      abcdefgh
low:        bcdefghX  
high:       efghXXXX
very high:  hXXXXXXX
limit:      XXXXXXXX{noformat}
If the lowest character in the seed is repeated then duplicates can occur:
{noformat}
seed      = aaabaaab

low:        aabaaabX
very high:  aabXXXXX{noformat}
Note that the XXXXX is a stream position and thus can enumerate all possible bit combinations in the range. Thus there is a combination of XXXXX == aaabX and a duplicate occurs.

This can be avoided by ensuring the lowest character in the seed is not repeated in the higher bits. This requires sampling the higher n-bit characters from an alphabet of (n-1). 

The size of the characters can be in the range [2, 63] bits. The character size is a compromise between the maximum stream size and the number of possible matches to the lowest seed character. Since shifts must be done by a whole character this supports streams of up to 2^(64-n) in size before the seed is left shifted out of the 64-bit long. The match probability for each character is 2^-n, e.g. 2-bit chars is 1/4, 3-bit is 1/8, 4-bit is 1/16. Depending on the implementation it may be useful for the characters to fit exactly within 64. This would be a power of 2.

The JDK implementation uses 4-bit characters with a fixed lowest character of 15. The remaining characters are sampled from [0, 15) using a multiply congruential generator (MCG). This requires  [Math.multiplyHigh|https://docs.oracle.com/en/java/javase/11/docs/api/java.base/java/lang/Math.html#multiplyHigh(long,long)] which is not available in the current target version of Java 8. Note: When reading the JDK implementation in the source code I identified a bug which has been registered as [JDK-8293567|http://example.com/].

Here is the proposed generation algorithm:

Seed requirements:
 * The least significant bit is set
 * The seed is composed of characters from an n-bit alphabet
 * The character used in the least significant bits is unique
 * The other characters are sampled uniformly from the remaining (n-1) characters

Algorithm:
 * Start with a random series of bits
 * Set the lowest bit to 1 and extract the lowest n-bit character
 * Any occurrences of the least significant character in the remaining characters are replaced using UniformRandomProvider.nextInt(int)

Using a 4-bit character the algorithm must inspect 15 characters above the lowest character. The rejection rate is 1/16. Approximately 1 character will be replaced per seed. This requires in total approximately 12 bytes of randomness from the RNG: the initial 8 bytes for the seed and approximately 4 bytes to sample 1 int in the range [0, 15). This is approximate as the nextInt algorithm has a very low chance of rejection; and there may be more than 1 character to replace in the upper 60-bits of the seed.

This algorithm is different from the JDK algorithm in that the lowest character can be from 8 possible odd digits. The maximum stream size where the seed can be prepended to the stream position is the same: 2^60. This is far larger than the expected use-case size of a stream of RNGs. This implementation requires branching within the character inspection loop. The JDK's use of a MCG is branchless and expected to run fast when the intrinsic Math.multiplyHigh is available. A similar implementation on Java 8 may not be as fast. The seed generation time is expected to be insignificant relative to the CPU time consumed by an application using all the RNGs in the stream.

 

> LXM generators to implement SplittableUniformRandomProvider
> -----------------------------------------------------------
>
>                 Key: RNG-181
>                 URL: https://issues.apache.org/jira/browse/RNG-181
>             Project: Commons RNG
>          Issue Type: New Feature
>          Components: core
>    Affects Versions: 1.5
>            Reporter: Alex Herbert
>            Assignee: Alex Herbert
>            Priority: Major
>             Fix For: 1.5
>
>
> The LXM family of generators use a linear congruential generator (LCG) mixed with a xor-based generator. The paper introducing these generators indicates that these are suitable for splitting as the streams are demonstrated to be independent when the addition parameter for the LCG is different. The authors provide results for outputting the combined (interleaved) sequence from up to 2^24 generators with different LCG add parameters through Test U01 BigCrush with no failures.
> These generators are splittable in the JDK 17 java.util.random package. Splitting functionality should be added to the family in Commons RNG.
> A single split of the generator is made by randomly seeding a new generator using the existing one. This is no different than simply creating a new generator from any source of randomness.
> When the generator is used to make a Stream<SplittableUniformRandomProvider> then each stream instance can be created using a different addition parameter. This can be done by exploiting the fact that the spliterator for the stream maintains the stream position as a count in [0, streamSize). The addition parameter can be created by using this count. To ensure a second stream will have different seeding the count can be combined with random bits that change for each stream instance.
> h2. JDK Implementation
> The exact mechanism used in the JDK is not documented (in the public javadoc) so may be subject to change. The present source code adds the stream position bits to random bits to create the addition. The seed random bits are generated with the some of the lowest bits set to 1. The addition parameter is created by shifting the seed random addition left until the lowest 1-bit is above the highest 1-bit of the position. The two can be combined (with xor) to create an addition which will be unique among the stream. 
> The present implementation in the JDK creates the initial seed as a series of n-bit characters using a seed generation algorithm; the lowest n-bits are set to 1 to act as a marker for the end of the seed. The algorithm to create the initial seed characters uses the overflow from a multiply congruential generator (MCG) with m=15 to create the digits as 4-bits. The source code indicates that the character size could be any supported number in [2, 63]. However the more bits that are set to mark the lower position of the seed impacts the amount of randomness left in the remaining bits.
> The initial seed characters are created using Math.multiplyHigh which is signed. The result is that the digits in the seed have a non-uniform distribution as the overflow character is subject to sign extension correction in the multiply. If the same algorithm uses JDK 18s Math.unsignedMultiplyHigh then the digits have a uniform distribution.
> Since the intrinsic functions Math.multiplyHigh and Math.unsignedMultiplyHigh are not available in JDK 8 then a similar approach using a MCG would be slow.
> Details to take away are that the counter and initial random seed are combined. Overlap of the seed and the counter are avoided by shifting the seed left. Some bits are used as a marker in the seed which reduces the randomness. Ideally the initial seed should have randomly distributed bits; this is not the case in the JDK 17 implementation due to the generation algorithm used.
> h2. Proposed Implementation
> To create a random addition combine the stream position with random bits.
> Notes:
>  # The stream position will be a positive long. However the addition for the LCG must be odd. This is done in the LXM family by setting the lowest 1 bit to 1. Thus the count must be shifted left 1-bit to avoid duplications in the seed sequence. This removes the ability to add extra bits to seed additions when the stream size exceeds 2^63. Such large streams are not expected in common use.
>  # A counter that is enumerated from 0 to 2^n - 1 will be uniformly distributed for each bit in the first n-bits. However when used as an addition to a sum in an LCG all of these possible additions may not trickle up changes very far into higher bits. 1-bits must be present in higher positions of the addition to effect higher bits in the sum. If all the higher bits are the same then the trickle up effect will be similar. So it is an advantage to have the seed counter combined with different random bits.
> A random seed could be xor'd with the counter. However the upper bits for all additions would be the same above the highest 1-bit in the sequence size. This reduces the variation in the addition parameter for use by the LXM generator.
> Thus is makes sense to create a random seed, then shift it left as the counter increases in magnitude. Note that the shift to avoid overlap with the counter could be maintained using a separate shift counter. However if the initial random seed bits have many zeros in the low bits it may be possible to left shift this and have nothing to combine with a large value counter. This may lead to duplications of previous ((seed << shift) | count) values as the counter increases in magnitude. If there is always at least 1 bit to prepend to the counter then no duplications will occur as any larger counts that match a previous ((seed << shift) | count) will also have at least 1 bit prepended. This limits the seed addition to 63-bits of randomness.
> Since the lowest 1-bit is enabled for the LCG add parameter this leaves 62-bits of randomness to seed the addition parameter. A stream with more than 2^62 elements would not be able to ensure a unique addition parameter for each RNG in the stream. Such streams are unlikely to be used. A more realistic parallel stream size of less than 1024 generators would only consume 9 bits for the counter and the seed addition will contain at least 53 bits of randomness accounting for the two bits lost to the marker bit and the odd LCG add parameter.
> h2. Code changes
> This functionality can be introduced in a new abstract base class for splittable generators that can split using a seed value. The seed value would be ensured to be unique within a stream (subject to the size limitations above). The current LXM generators extend either IntProvider or LongProvider. The LongProviders all use a 64 or 128-bit LCG and can thus use the entire seed value when splitting. The IntProvider is the L32X64Mix generator which uses a 32-bit LCG. This can only use 31-bits from the seed for the LCG add parameter. It limits the number of unique add parameters within a stream to 2^30 before duplications may be observed. This generator is splittable in the JDK. It is used as the default generator in JDK 17 for RandomGenerator.getDefault(). Supporting splitting in Commons RNG provides parity with the modern JDK random implementation.



--
This message was sent by Atlassian Jira
(v8.20.10#820010)