Evan, as the person who has done the vast majority of the testing, are you happy about changing the xoroshiro32++ constants?
From the distribution tests there is no doubt that two successive 16-bit outputs using [13,5,10,9] come the closest of all the candidates to a random 32-bit output. Now this would not be a good enough reason to switch if it performed poorly as a 16-bit generator but the PractRand and Crush tests seem to me to be very acceptable.
One question: is the d = 0 slot in the distribution binaries really for d = 0 or is it xoroshiro32+p?
d = 0 in those files represents a test of the original xoroshiro+ algorithm. If parity was enabled then parity would be active for the d != 0 tests as well.
Making the constants programable would make a huge difference to the logic size for the instruction. Like a 1000 fold increase, to pluck a number out of the air. EDIT: Thinking about it more, it's not that bad. There is already four 16-bit adders. It would need another eight 16-bit barrel shifters, and four 4-bit registers to hold the presets. I'm not sure how bulky a barrel shifter is compared to an adder.
Here's repost from previous page in this topic:
// Verilog HDL for Xoroshiro32++ candidate [13 5 10 9]
///////////////////////////////////////////////////////////
wire [15:0] xoro32z = d[31:16] ^ d[15:0]; // first iteration
wire [31:0] xoro32y = { xoro32z[5:0], xoro32z[15:6], // rol #10
{d[2:0], d[15:3]} ^ // rol #13
{xoro32z[10:0], 5'b0} ^ xoro32z }; // shl #5
wire [15:0] xoro32x = xoro32y[31:16] ^ xoro32y[15:0]; // second iteration
wire [31:0] xoro32 = { xoro32x[5:0], xoro32x[15:6], // rol #10, xoro32 = d result (state store)
{xoro32y[2:0], xoro32y[15:3]} ^ // rol #13
{xoro32x[10:0], 5'b0} ^ xoro32x }; // shl #5
wire [15:0] xoro32a = d[31:16] + d[15:0]; // hashing sum of input state
wire [15:0] xoro32b = xoro32y[31:16] + xoro32y[15:0]; // hashing sum of first iterator state output
assign xoro32r = { {xoro32b[6:0], xoro32b[15:7]} + xoro32y[15:0], // rol #9
{xoro32a[6:0], xoro32a[15:7]} + d[15:0] }; // rol #9, xoro32r = prng result, next instruction's s value
OK, while I don't quite follow the correlation of the [13 5 10 9], the implementation is a fixed barrel shifter which is heaps less than a programmable barrel shifter. It could be possible to implement two variants but I would expect that might be it. A full barrel shifter would take a lot of logic unless the code is using an existing one in the ALU.
Call it a fixed shift. Can't call it a barrel when it's fixed mapping like this.
Also to get the speed up, it's not one reusable shifter, but eight parallel shifts. It's not one reused adder, but four parallel adders. All firing on the same clock cycle.
It's possible for different instructions to reuse the same operations (up to the optimiser) but RISC is based around rapid execution. And that means lots of parallel operations in hardware.
I've talked about ALU ports in the Prop2 in the past too when discussing timings and operations of specific instructions. Chip has never concurred with my statements in those ramblings. That's because the term ALU is long dead and I probably should have stopped using it.
There isn't a specific pair of databuses feeding a logic block of operations like there was of old. There is only the cogram ports, instruction register and pipeline registers. Everything else goes to the logic optimiser.
[13,5,10,9] will be in the respin (thanks Chip!) and it will do full justice to Chip's double-iteration brainwave. A macro that takes [a,b,c,d] and spews out the right Verilog would have saved us some thinking. Anyway, it's all done now, I hope.
As XORO32 is basically a black box this change is risk-free and in fact the logic for [13,5,10,9] will be a tiny bit smaller as two 5-bit left shifts replace two 2-bit ones.
A possible way to tell future versions of the P2 apart is to rotate the state bits by varying amounts in the logic that calculates the PRN so that a specific state will generate different outputs but over the whole period the distributions will be the same.
Evan, I plan to get in touch with Seba again to update him. For the purely 16-bit output xoroshiro32++, is there any candidate that stands out as better than the rest? In other words, could we now recommend something other than [14,2,7,5] that is mentioned in the paper?
Obviously, stating the new choice of [13 5 10 9] is in order. There's no other of particular note.
I would certainly like to know his thoughts on the effectiveness of your approach with distribution. On the one hand it seems too easy a solution so it can't be that simple. But, on the other hand, the shear smallness of Xoroshiro32's state space means we can run a test that doesn't get used for any "real" generators ...
I think, only him answering this question can we offer anything of note back to Seba.
Evan, I will ask for Seba's thoughts. The distribution tests are simple but impossible to do with 64-bit or 128-bit states. One could argue that the latter are less "real" in the sense they are too big to test fully, whereas the XORO32 distribution data are certainly real.
As you tested xoroshiro++ with all 15 non-zero rotations and xoroshiro+, we can see from their Chi-Square results how the two scramblers compare. The improvement in quality that the extra rotation and addition gives is huge. The table below is a summary of results posted earlier with xoroshiro32+[13,5,10] added at the bottom:
Although [13,5,10] appears to be terrible, it is actually the best xoroshiro+ with rankings of 3 for pfreq and 1 for both zfreq and nzfreq. This seems to be confirmation that the engine common to [13,5,10] and [13,5,10,9] is the best one as regards the distributions.
Am I to understand that the xo???, whatever, algorithm in the P2 is no longer conformant with any of the published algorithms? http://xoshiro.di.unimi.it/
For the XORO32 instruction, correct. That has been true for some time. Seba and Dave provided the algorithm for Xoroshiro++ to us before they published their recent work. It wasn't included in the publication.
The free running generator in the hub is using Xoroshiro128** that turned up along with the newly published Xoshiro engine.
Xoroshiro++ is still the same Xoroshiro engine, with the same three constants. Only the scrambler has been extended to have a second adder and a (fourth) constant.
Am I to understand that the xo???, whatever, algorithm in the P2 is no longer conformant with any of the published algorithms? http://xoshiro.di.unimi.it/
For the XORO32 instruction, correct. That has been true for some time. Seba and Dave provided the algorithm for Xoroshiro++ to us before they published their recent work. It wasn't included in the publication.
The free running generator in the hub is using Xoroshiro128** that turned up along with the newly published Xoshiro engine.
Xoroshiro++ is still the same Xoroshiro engine, with the same three constants. Only the scrambler has been extended to have a second adder and a (fourth) constant.
Before publication Seba told me xoroshiro++ would not be in the paper but it ended up being included (para 10.7, p.38). A link to the paper and mention of xoroshiro32++ is at http://xoshiro.di.unimi.it/. The paper does not make it clear in my view how much better the ++ scramber is than +, although it does call the former strong and the latter weak.
Evan, do you think any xoroshiro16++ might pass the extended PractRand tests? About half the candidates had max scores in the tests you did in February, but I can't remember when you started using the extended test.
Looks like I've deleted whatever I had in the testing directories. The oldest s8 Practrand reports are from March and those are only single + scrambler.
EDIT: I've found a Feb dated s8 zip file labelled with "te1tf2", so that's the full extended PR tests. Attached:
EDIT2: Hmm, that looks a tad limited in the number of reports. The culling is too strong.
Oh, that's interesting. Gridding everything I'm getting a bunch of cases that lock/crash Practrand at the 32KB mark. I've seen this once before but had forgotten all about it. It must have been the last time I ran the s8's.
EDIT: Odd, it seems to be fine as long as I exclude the d=0 cases. :shrug:
Looks like I've deleted whatever I had in the testing directories. The oldest s8 Practrand reports are from March and those are only single + scrambler.
EDIT: I've found a Feb dated s8 zip file labelled with "te1tf2", so that's the full extended PR tests. Attached:
EDIT2: Hmm, that looks a tad limited in the number of reports. The culling is too strong.
Thanks, Evan. I didn't have the full extended results.
Re culling, remember there aren't many [a,b,c] and 8 bits is the most you get with xoroshiro16 !
Comments
From the distribution tests there is no doubt that two successive 16-bit outputs using [13,5,10,9] come the closest of all the candidates to a random 32-bit output. Now this would not be a good enough reason to switch if it performed poorly as a 16-bit generator but the PractRand and Crush tests seem to me to be very acceptable.
One question: is the d = 0 slot in the distribution binaries really for d = 0 or is it xoroshiro32+p?
d = 0 in those files represents a test of the original xoroshiro+ algorithm. If parity was enabled then parity would be active for the d != 0 tests as well.
PM sent to the "Parallax developers".
ie could there be an option to change or is it hardcoded in the verilog?
Here's repost from previous page in this topic:
// Verilog HDL for Xoroshiro32++ candidate [13 5 10 9] /////////////////////////////////////////////////////////// wire [15:0] xoro32z = d[31:16] ^ d[15:0]; // first iteration wire [31:0] xoro32y = { xoro32z[5:0], xoro32z[15:6], // rol #10 {d[2:0], d[15:3]} ^ // rol #13 {xoro32z[10:0], 5'b0} ^ xoro32z }; // shl #5 wire [15:0] xoro32x = xoro32y[31:16] ^ xoro32y[15:0]; // second iteration wire [31:0] xoro32 = { xoro32x[5:0], xoro32x[15:6], // rol #10, xoro32 = d result (state store) {xoro32y[2:0], xoro32y[15:3]} ^ // rol #13 {xoro32x[10:0], 5'b0} ^ xoro32x }; // shl #5 wire [15:0] xoro32a = d[31:16] + d[15:0]; // hashing sum of input state wire [15:0] xoro32b = xoro32y[31:16] + xoro32y[15:0]; // hashing sum of first iterator state output assign xoro32r = { {xoro32b[6:0], xoro32b[15:7]} + xoro32y[15:0], // rol #9 {xoro32a[6:0], xoro32a[15:7]} + d[15:0] }; // rol #9, xoro32r = prng result, next instruction's s valueAlso to get the speed up, it's not one reusable shifter, but eight parallel shifts. It's not one reused adder, but four parallel adders. All firing on the same clock cycle.
It's possible for different instructions to reuse the same operations (up to the optimiser) but RISC is based around rapid execution. And that means lots of parallel operations in hardware.
There isn't a specific pair of databuses feeding a logic block of operations like there was of old. There is only the cogram ports, instruction register and pipeline registers. Everything else goes to the logic optimiser.
As XORO32 is basically a black box this change is risk-free and in fact the logic for [13,5,10,9] will be a tiny bit smaller as two 5-bit left shifts replace two 2-bit ones.
A possible way to tell future versions of the P2 apart is to rotate the state bits by varying amounts in the logic that calculates the PRN so that a specific state will generate different outputs but over the whole period the distributions will be the same.
I would certainly like to know his thoughts on the effectiveness of your approach with distribution. On the one hand it seems too easy a solution so it can't be that simple. But, on the other hand, the shear smallness of Xoroshiro32's state space means we can run a test that doesn't get used for any "real" generators ...
I think, only him answering this question can we offer anything of note back to Seba.
As you tested xoroshiro++ with all 15 non-zero rotations and xoroshiro+, we can see from their Chi-Square results how the two scramblers compare. The improvement in quality that the extra rotation and addition gives is huge. The table below is a summary of results posted earlier with xoroshiro32+[13,5,10] added at the bottom:
Although [13,5,10] appears to be terrible, it is actually the best xoroshiro+ with rankings of 3 for pfreq and 1 for both zfreq and nzfreq. This seems to be confirmation that the engine common to [13,5,10] and [13,5,10,9] is the best one as regards the distributions.
wire [31:0] xi0 = d; // first iteration [13,5,10,9] wire [15:0] xx0 = xi0[31:16]^ xi0[15:00]; wire [31:0] xy0 = { xx0[05:00], xx0[15:06], // rol 10 {xi0[02:00], xi0[15:03]} ^ // rol 13 {xx0[10:00], 5'b0} ^ xx0 }; // shl 5 wire [31:0] xi1 = xy0; // second iteration wire [15:0] xx1 = xi1[31:16]^ xi1[15:00]; wire [31:0] xy1 = { xx1[05:00], xx1[15:06], // rol 10 {xi1[02:00], xi1[15:03]} ^ // rol 13 {xx1[10:00], 5'b0} ^ xx1 }; // shl 5 wire [31:0] xoro32 = xy1; // d result wire [16:0] xs0 = xi0[31:16] + xi0[15:00]; // first sum wire [16:0] xs1 = xi1[31:16] + xi1[15:00]; // second sum assign xoro32_r = { {xs1[06:00], xs1[15:07]} + xi1[15:00], // prng result is next instruction's s value {xs0[06:00], xs0[15:07]} + xi0[15:00] }; // rol 9Everything checks out on the result side, too.
Thanks a lot for improving this!
The free running generator in the hub is using Xoroshiro128** that turned up along with the newly published Xoshiro engine.
Xoroshiro++ is still the same Xoroshiro engine, with the same three constants. Only the scrambler has been extended to have a second adder and a (fourth) constant.
Before publication Seba told me xoroshiro++ would not be in the paper but it ended up being included (para 10.7, p.38). A link to the paper and mention of xoroshiro32++ is at http://xoshiro.di.unimi.it/. The paper does not make it clear in my view how much better the ++ scramber is than +, although it does call the former strong and the latter weak.
EDIT: I've found a Feb dated s8 zip file labelled with "te1tf2", so that's the full extended PR tests. Attached:
EDIT2: Hmm, that looks a tad limited in the number of reports. The culling is too strong.
EDIT: Odd, it seems to be fine as long as I exclude the d=0 cases. :shrug:
Thanks, Evan. I didn't have the full extended results.
Re culling, remember there aren't many [a,b,c] and 8 bits is the most you get with xoroshiro16 !
Something suspect though: Full period repeat is 64 KB so Practrand should be maxing out at 128 KB, but there is plenty of 512 KB!