SHISHUA: le générateur de nombres pseudo-aléatoires le plus rapide au monde

objectif

1. Générez plus d'octets avec la même quantité de travail,
2. Ou faites moins de travail pour générer le même nombre d'octets,
3. Ou parallélisez le travail.

static uint64_t next(void);

void prng_gen(prng_state *s, __uint64_t buf[], __uint64_t size);

Parallélisme

Architecture

typedef struct prng_state {
  __m256i state[2];
  __m256i output;
  __m256i counter;
} prng_state;

inline void prng_gen(prng_state *s, __uint64_t buf[], __uint64_t size) {
  __m256i s0 = s->state[0], counter = s->counter,
          s1 = s->state[1],       o = s->output;
  for (__uint64_t i = 0; i < size; i += 4) {
    _mm256_storeu_si256((__m256i*)&buf[i], o);
    // …
  }
  s->state[0] = s0; s->counter = counter;
  s->state[1] = s1; s->output  = o;
}

1. SHI ft
2. SHU ffle
3. Un dd

Premier quart de travail

u0 = _mm256_srli_epi64(s0, 1);              u1 = _mm256_srli_epi64(s1, 3);

En remuant

t0 = _mm256_permutevar8x32_epi32(s0, shu0); t1 = _mm256_permutevar8x32_epi32(s1, shu1);

__m256i shu0 = _mm256_set_epi32(4, 3, 2, 1, 0, 7, 6, 5),
        shu1 = _mm256_set_epi32(2, 1, 0, 7, 6, 5, 4, 3);

Une addition

s0 = _mm256_add_epi64(t0, u0);              s1 = _mm256_add_epi64(t1, u1);

Fonction de sortie

o = _mm256_xor_si256(u0, t1);

s1 = _mm256_add_epi64(s1, counter);
counter = _mm256_add_epi64(counter, increment);

__m256i increment = _mm256_set_epi64x(1, 3, 5, 7);

Initialisation

static __uint64_t phi[8] = {
  0x9E3779B97F4A7C15, 0xF39CC0605CEDC834, 0x1082276BF3A27251, 0xF86C6A11D0C18E95,
  0x2767F0B153D27B7F, 0x0347045B5BF1827F, 0x01886F0928403002, 0xC1D64BA40F335E36,
};

prng_state prng_init(SEEDTYPE seed[4]) {
  prng_state s;
  // …
  return s;
}

s.state[0] = _mm256_set_epi64x(phi[3], phi[2] ^ seed[1], phi[1], phi[0] ^ seed[0]);
s.state[1] = _mm256_set_epi64x(phi[7], phi[6] ^ seed[3], phi[5], phi[4] ^ seed[2]);

1. Exécutez les étapes ( STEPS) des itérations SHISHUA.
2. Nous attribuons une partie de l'état à un autre état et l'autre partie à la sortie.

for (char i = 0; i < ROUNDS; i++) {
  prng_gen(&s, buf, 4 * STEPS);
  s.state[0] = s.state[1];
  s.state[1] = s.output;
}

Performance

• La mesure de l'horloge n'est peut-être pas suffisamment précise.
• , , - , -, .
• , . .
• : , .

o0 = _mm256_xor_si256(u0, t1);
o1 = _mm256_xor_si256(u2, t3);
o2 = _mm256_xor_si256(s0, s3);
o3 = _mm256_xor_si256(s2, s1);

Qualité

1. Performances : nombre de cycles de processeur passés sur un octet généré. Reçu sur les machines cloud N2 GCP et N2D (AMD), la commande est la même.
2. Qualité : niveau auquel le générateur ne réussit pas le test PractRand. S'il n'échoue pas, il y a un signe>. Si le résultat n'est pas prouvé, il y a un point d'interrogation.
3. Corrélation des nombres de graines : Traversée PractRand avec octets alternés de huit flux avec les nombres de graines 0, 1, 2, 4, 8, 16, 32, 64. Nous utilisons PractRand avec une double convolution et des tests avancés.
   
   
   
   
   

Plus loin

1. , 2¹⁰²⁴. 10 /. 10²⁸² , . «» ( ). , . , 128- NEON ARM? , , .
2. . , SHISHUA XOR . , .
3. , 2¹²⁸ ( ). SHISHUA, , . , ( ) (, , . 2).
4. L'initialisation d'état a une dispersion parfaite : tous les bits du nombre initial affectent tous les bits de l'état avec la même probabilité. Je veux en savoir plus sur SHISHUA.

• Il ne permet pas d'évaluer des générateurs de haute qualité, ce qui rend impossible leur comparaison les uns avec les autres. Nous devons dire: "eh bien, après 32 téraoctets, il n'y a pas d'anomalies ..."
• Cela prend des semaines pour l'exécuter ...