Hace seis meses, quería crear el mejor generador de números pseudoaleatorios (PRNG) con una arquitectura inusual. Pensé que el comienzo sería fácil, y mientras trabajas, la tarea se volverá lentamente más compleja. Y pensé que si podía aprender todo lo suficientemente rápido como para hacer frente a lo más difícil.Para mi sorpresa, la complejidad no aumentó linealmente. ¡La prueba de bytes de chi-cuadrado resultó ser muy difícil! Más tarde, fue igual de difícil pasar pruebas acérrimas. Me publicaron los resultados actuales para entender lo que otras dificultades me esperan. Sin embargo , la prueba PractRand falló en ese momento .Entonces fue muy difícil pasar la prueba BigCrush .Entonces fue muy difícil transferir 32 terabytes de datos al pasar PractRand. La velocidad se ha convertido en un problema. No fue suficiente crear un diseño que generara diez megabytes por segundo, porque pasar PractRand llevaría un mes. Pero debo admitir que fue muy difícil pasar esta prueba a una velocidad de gigabytes por segundo .Cuando te elevas a tal altura ... quieres saber si puedes llegar al borde de Pareto. Desea crear el PRNG más rápido del mundo, que pasará las pruebas estadísticas más complejas.He tenido éxito.En un artículo anterior, hablé sobre lo que aprendí para lograr mi objetivo. Y aquí te diré cómo funciona la arquitectura final.propósito
Comencemos con lo obvio: la velocidad depende de la plataforma . Me centré en optimizar para la arquitectura moderna x86-64 (procesadores Intel y AMD).Para comparar el rendimiento, se utiliza la métrica cpb clásica : este es el número de ciclos de procesador dedicados a generar un byte. Esta métrica se calcula y compara en todos los trabajos criptográficos. Un cpb ligeramente inferior en el mundo del software o hardware puede garantizar la victoria en la competencia o el uso en sitios web de todo el mundo.Para mejorar cpb, puedes:- Genera más bytes con la misma cantidad de trabajo,
- O haga menos trabajo para generar el mismo número de bytes,
- O paralelizar el trabajo.
Haremos todo lo anterior.Según el primer punto, necesitamos producir más bits en cada iteración.Tenía miedo de que me dijeran: "Si no da números de 32 bits, entonces este no es el DELP", o lo mismo con los números de 64 bits. O: "El PRNG solo debe ser para arquitectura x86-64", como si las instrucciones como POPCNT o registros como% xmm7 estuvieran prohibidos.Sin embargo, el PRNG es ingeniería: ¡los generadores han estado tratando durante varias décadas de exprimir todo lo posible de los procesadores! Cuando apareció ROL, comenzaron a confiar en él. Con la llegada de los procesadores de 64 bits, comenzaron a confiar en% rax. Por supuesto, en ARM, tales algoritmos pueden funcionar más lentamente (aunque esto aún está por verse), sin embargo, los PRN de 64 bits se usaron activamente incluso antes de que Android comenzara a requerir soporte para 64 bits en 2019.Es decir, esta área se está desarrollando junto con el hardware. Y hoy, los procesadores Intel y AMD debido a AVX2 ya admiten operaciones de 256 bits. RC4 produjo 1 byte, drand48 podría producir 4 bytes a la vez, pcg64 - 8 bytes, y ahora podemos generar inmediatamente 32 bytes.8 bytes pueden ser un número de 64 bits, y la mayoría de los lenguajes de programación tienen tipos incorporados para esto. Pero pocos idiomas proporcionan tipos para 16 bytes (una excepción notable es __uint128_t en C). Incluso menos idiomas tienen tipo para 32 bytes (excepto interno).Entonces podemos decir adiós al prototipo habitual de la función PRNG (ejemplo del punto de referencia Vigny HWD ):static uint64_t next(void);
En cambio, puede hacer un generador que llene el búfer (ejemplo de mi punto de referencia ):void prng_gen(prng_state *s, __uint64_t buf[], __uint64_t size);
¿Cuáles son las desventajas de esta solución?Si su generador produce 32 bytes a la vez, entonces necesita que el consumidor proporcione una matriz que sea un múltiplo de 32 (idealmente alineado a 32 bytes). Aunque puede prescindir de él, simplemente llenaremos el búfer. Eliminaremos los datos no utilizados y los rellenaremos nuevamente según sea necesario. El retraso se vuelve impredecible: algunas llamadas solo leerán el búfer. Pero en promedio todo será igual.Ahora generamos más bytes, haciendo la misma cantidad de trabajo. ¿Cómo lo paralelizamos?Paralelismo
Los procesadores ofrecen un increíble conjunto de herramientas de paralelización en todos los niveles.En primer lugar, estas son instrucciones SIMD (Instrucción única, Datos múltiples). Por ejemplo, AVX2 realiza simultáneamente cuatro adiciones de 64 bits, u ocho adiciones de 32 bits, etc.Se ha utilizado en criptografía durante aproximadamente quince años. La concurrencia proporcionó el increíble rendimiento de ChaCha20 . Lo usan las primitivas más importantes que no usan AESNI. Por ejemplo, NORX y Gimli están diseñados con el paralelismo en mente.Recientemente, el interés en este tema también ha aumentado en la comunidad PRNG no criptográfica. En particular, las primitivas existentes que no fueron diseñadas para SIMD pueden ser la base para crear PRN muy rápidas.Cuando Sebastiano Vigna promocionó su arquitectura xoshiro256 ++ en la biblioteca estándar de Julia, descubrió que los resultados de ocho instancias de PRNG competitivas y con inicialización diferente pueden concatenarse muy rápidamente si cada operación se realiza simultáneamente en todas las PRNR.SIMD es solo uno de los niveles de paralelización en el procesador. Recomiendo leer el artículo anterior sobre este tema para tener una mejor idea, pero daré algunas explicaciones.Las canalizaciones del procesador permiten procesar varias instrucciones en diferentes etapas. Si el orden de su ejecución está bien organizado para reducir las dependencias entre etapas, entonces el procesamiento de las instrucciones puede acelerarse.La ejecución superescalar le permite procesar simultáneamente las partes informáticas de las instrucciones. Pero para esto no deberían tener dependencias de lectura-escritura. Puede adaptar la arquitectura para reducir el riesgo de tiempo de inactividad grabando mucho antes de leer.La ejecución extraordinaria permite que el procesador ejecute instrucciones no en el orden de secuencia, sino como están listas, incluso si las instrucciones anteriores aún no están listas. Pero para esto no debería haber dependencia de lectura-escritura.¡Y ahora pasamos a la implementación!Arquitectura
Considere un esquema llamado semi-SHISHUA. De dónde viene ese nombre se hará gradualmente aparente a medida que leas.El esquema se ve así:Considere su línea por línea.typedef struct prng_state {
__m256i state[2];
__m256i output;
__m256i counter;
} prng_state;
El estado se divide en dos partes, que se colocan en el registro AVX2 (256 bits). Para aumentar la velocidad, mantenemos el resultado cerca del estado en sí, pero no es parte del estado.También tenemos un contador de 64 bits. Para simplificar el cálculo, también es un registro AVX2. El hecho es que AVX2 tiene una pequeña característica: los registros ordinarios (% rax y similares) no se pueden transferir directamente a SIMD a través de MOV, deben pasar a través de RAM (a menudo a través de la pila), lo que aumenta el retraso y cuesta dos instrucciones de procesador (MOV en la pila, VMOV de la pila).Ahora echemos un vistazo a la generación. Comencemos cargando, luego revise el búfer y llénelo con 32 bytes en cada iteración.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;
}
Dado que la función está en línea, el llenado inmediato del búfer al inicio permite que el procesador ejecute inmediatamente las instrucciones dependiendo de esto mediante un mecanismo de ejecución extraordinario.Dentro del ciclo, realizamos rápidamente tres operaciones de estado:- SHI ft
- SHU ffle
- A dd
De ahí el nombre de SHISHUA!Primer turno
u0 = _mm256_srli_epi64(s0, 1); u1 = _mm256_srli_epi64(s1, 3);
Desafortunadamente, el AVX2 no admite revoluciones. ¡Pero quiero mezclar los bits de una posición en un número de 64 bits con los bits de otra posición! Y shift es la mejor manera de darse cuenta de esto. Cambiaremos por un número impar, de modo que cada bit visitará todas las posiciones de 64 bits, y no la mitad de ellas.Durante el cambio, se pierden bits, lo que conduce a la eliminación de información de nuestro estado. Esto es malo, debe minimizar las pérdidas. Los números impares más pequeños son 1 y 3, utilizaremos diferentes valores de desplazamiento para aumentar la discrepancia entre las dos partes. Esto ayudará a reducir la similitud de su autocorrelación.Nos desplazaremos a la derecha, porque los bits más a la derecha tienen la difusión más baja durante la suma: por ejemplo, el bit menos significativo en A + B es solo el XOR de los bits menos significativos A y B.Emocionante
t0 = _mm256_permutevar8x32_epi32(s0, shu0); t1 = _mm256_permutevar8x32_epi32(s1, shu1);
Utilizaremos la mezcla de 32 bits, ya que proporciona una granularidad diferente en comparación con las operaciones de 64 bits que usamos en todas partes (se viola la alineación de 64 bits). También puede ser una operación de carril cruzado: otras barajas pueden mover bits dentro de los 128 bits de la izquierda si comienzan a la izquierda, o dentro de los 128 bits de la derecha si comienzan a la derecha.Constantes de mezcla:__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);
Para que la mezcla realmente mejore el resultado, trasladaremos las partes débiles (baja dispersión) de 32 bits de las adiciones de 64 bits a posiciones fuertes, de modo que las siguientes adiciones las enriquezcan.La parte de 32 bits de gama baja del fragmento de 64 bits nunca se mueve al mismo fragmento de 64 bits que la parte de orden superior. Por lo tanto, ambas partes no permanecen dentro del mismo fragmento, lo que mejora la mezcla.Al final, cada parte de 32 bits pasa por todas las posiciones en un círculo: de A a B, de B a C, ... de H a A.Es posible que haya notado que la mezcla más simple que tiene en cuenta todos estos requisitos es dos 256 bits rotación (revoluciones de 96 bits y 160 bits a la derecha, respectivamente).Adición
Agreguemos fragmentos de 64 bits de dos variables temporales: cambio y mezcla.s0 = _mm256_add_epi64(t0, u0); s1 = _mm256_add_epi64(t1, u1);
La adición es la principal fuente de dispersión: en esta operación, los bits se combinan en combinaciones irreducibles de expresiones XOR y AND distribuidas en posiciones de 64 bits.Almacenar el resultado de la adición dentro de un estado preserva permanentemente esta dispersión.Función de salida
¿De dónde obtenemos la salida?Es simple: la estructura que creamos nos permite generar dos partes independientes del estado s0 y s1, que no se afectan entre sí de ninguna manera. Aplique XOR a ellos y obtenga un resultado completamente al azar.Para fortalecer la independencia entre los datos a los que aplicamos XOR, tomamos un resultado parcial: la parte desplazada de un estado y la parte mixta de otro.o = _mm256_xor_si256(u0, t1);
Esto es similar a reducir las dependencias de lectura y escritura entre instrucciones en un procesador superescalar, como si u0 y t1 estuvieran listas para leer en s0 y s1.Ahora discuta el mostrador. Lo procesamos al comienzo del ciclo. Primero, cambie el estado y luego aumente el valor del contador:s1 = _mm256_add_epi64(s1, counter);
counter = _mm256_add_epi64(counter, increment);
¿Por qué primero cambiamos el estado y luego actualizamos el contador? s1 está disponible antes, esto reduce la probabilidad de que las instrucciones posteriores que lo lean se detengan en la tubería del procesador. Además, esta secuencia ayuda a evitar la dependencia directa del contador de lectura-escritura.Aplicamos el contador a s1, y no a s0, porque ambos afectan la salida de todos modos, sin embargo, s1 pierde más bits debido al cambio, por lo que le ayuda a "ponerse de pie" después del cambio.El contador no puede grabar la prueba PractRand. Su único propósito es establecer un límite inferior de 2 69bytes = 512 exbibytes para el período PRNG: comenzamos a repetir el ciclo solo después de un milenio de trabajo a una velocidad de 10 gibytes por segundo. Es poco probable que sea demasiado lento para su uso práctico en los próximos siglos.Incremento:__m256i increment = _mm256_set_epi64x(1, 3, 5, 7);
Los números impares se eligen como incrementos, porque solo los números primos básicos cubren todo el ciclo del campo finito GF (2 64 ), y todos los números impares son primos para 2. En otras palabras, si incrementa en un entero par en el rango de 0 a 4, volviendo a 0 después de 4, obtenemos la secuencia 0-2-0-2- ..., que nunca conducirá a 1 o 3. Y el incremento impar pasa por todos los enteros.Para todos los números de 64 bits en estado, utilizaremos diferentes números impares, que los separarán aún más y aumentarán ligeramente la mezcla. Elegí los números impares más pequeños para que no se vean mágicos.Así es como funcionan la transición de estado y la función de salida. ¿Cómo inicializarlos?Inicialización
Inicializamos el estado usando los dígitos hexadecimales Φ, el número irracional que es menos aproximado por la fracción.static __uint64_t phi[8] = {
0x9E3779B97F4A7C15, 0xF39CC0605CEDC834, 0x1082276BF3A27251, 0xF86C6A11D0C18E95,
0x2767F0B153D27B7F, 0x0347045B5BF1827F, 0x01886F0928403002, 0xC1D64BA40F335E36,
};
Toma una semilla de 256 bits. Esto a menudo se realiza en criptografía y no daña el trabajo de los PRNG no criptográficos:prng_state prng_init(SEEDTYPE seed[4]) {
prng_state s;
// …
return s;
}
No queremos redefinir toda la parte del estado (s0 o s1) con este número inicial, solo necesitamos afectar la mitad. De esta manera, evitaremos el uso de números iniciales atenuantes, que accidental o intencionalmente dan lugar a un estado inicial débil conocido.Como no cambiamos la mitad de cada estado, conservamos el control sobre 128 bits de estado. Tal entropía es suficiente para comenzar y mantener una posición fuerte.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]);
Luego repetimos ( ROUNDS) varias veces la siguiente secuencia:- Ejecute los pasos (
STEPS) de las iteraciones de SHISHUA. - Asignamos una parte del estado a otro estado, y la otra parte a la salida.
for (char i = 0; i < ROUNDS; i++) {
prng_gen(&s, buf, 4 * STEPS);
s.state[0] = s.state[1];
s.state[1] = s.output;
}
La asignación de un resultado de salida aumenta la dispersión del estado. Durante la inicialización, el trabajo adicional y la correlación de estados no importa, porque esta serie de operaciones se realiza una vez. Solo estamos interesados en la dispersión durante la inicialización.Después de evaluar el efecto sobre la correlación de los valores iniciales, elegí STEPS2 para el valor y ROUNDS10 para 10. Calculé la correlación calculando las anomalías "inusuales" y "sospechosas" que surgen de la herramienta de control de calidad PRNG en PractRand.Actuación
Es difícil medir la velocidad por varias razones:- La medición del reloj puede no ser lo suficientemente precisa.
- , , - , -, .
- , . .
- : , .
Uso la instrucción del procesador RDTSC, que calcula el número de ciclos.Para que cualquiera pueda reproducir mis resultados, uso una máquina virtual basada en la nube. Esto no cambia el nivel de los resultados de referencia en comparación con las pruebas locales. Además, no tiene que comprar la misma computadora que la mía. Finalmente, hay muchas situaciones en las que el PRNG se lanza en las nubes.Elegí Google Cloud Platform N2 (procesador Intel) y N2D (procesador AMD). La ventaja de GCP es que ofrecen servidores con procesadores de ambos fabricantes. En este artículo, nos centraremos en Intel, pero para AMD los resultados estarán en el mismo orden.Para profundizar en el tema, primero eliminemos el antiguo generador criptográfico RC4. Incapaz de paralelizar el trabajo, obtuve7.5 cpb (ciclos por byte generado).Ahora ejecutemos un MCG muy popular y rápido: el Lehmer128 PRNG más simple , que pasa la prueba BigCrush, mostró 0.5 cpb . ¡Wow asombroso!Luego ejecutaremos el último desarrollo, que se utiliza para tablas hash rápidas: wyrand . 0.41 cpb , un poco mejor!Algunos PRSP no pasan la prueba PractRand de 32 terabytes, pero funcionan muy rápidamente. Xoshiro256 + alcanzó solo 512 mebibytes, pero mostró una velocidad muy alta: 0.34 cpb .Otro desarrollo reciente de RomuTrio . Ella dice ser la PRNG más rápida del mundo: 0,31 cpb.Ok, eso es suficiente. ¿Qué mostró semi-SHISHUA?0,14 cpb . Dos veces más rápido que RomuTrio.Frio. Ahora pruebe el generador criptográfico ChaCha8. Alcanzó ... 0.12 cpb .Oh.SIMD es verdadera magia!Para la comunidad criptográfica, esto no fue una sorpresa especial . ChaCha8 es extremadamente fácil de paralelizar. Esto es solo un contador bien hash en un estado difuso.¿Y recuerda cómo el equipo de lenguaje de Julia intentó combinar varias instancias de la arquitectura de Vigny para crear un PRNG rápido basado en SIMD? Veamos su resultado usando esta técnica ( 8 piezas de Xoshiro256 + ). 0.09 cpb !Técnicamente, mi computadora portátil podría afectar los resultados. No estoy seguro de por qué el desarrollo del equipo de Julia es más rápido que ChaCha8 en GCP, pero más lento cuando se prueba localmente. En mi máquina, semi-SHISHUA funciona más rápido que el desarrollo del equipo de Julia, pero más lento que ChaCha8.Es necesario derrotar a todos los competidores.Probablemente ya se esté preguntando por qué llamamos a la versión anterior del generador semi-SHISHUA. Porque resultó fácil duplicar la velocidad si ejecuta dos copias de semi-SHISHUA.Similar a la idea del comando Julia, inicializamos por separado dos PRNG (cuatro bloques de un estado de 256 bits), suministrando alternativamente la salida de su trabajo.Pero si hacemos más estados, entonces podemos producir aún más datos, combinando cuatro estados en pares:o0 = _mm256_xor_si256(u0, t1);
o1 = _mm256_xor_si256(u2, t3);
o2 = _mm256_xor_si256(s0, s3);
o3 = _mm256_xor_si256(s2, s1);
Entonces obtuvimos SHISHUA, que mostró una velocidad de 0.06 cpb .Esto es dos veces más rápido que el competidor más rápido anterior en el mundo, que pasó la prueba PractRand de 32 terabytes. El resultado está en el gráfico.Creo que el desarrollo resultó ser competitivo. Funciona aún más rápido en mi computadora portátil: 0.03 cpb, pero cumpliré con mis principios con respecto al punto de referencia.Espero que por unas semanas más mi generador se mantenga en el podio de los más rápidos del mundo (por favor hágalo).Calidad
El generador honestamente pasa BigCrush y la prueba PractRand de 32 terabytes. Y todo gracias a cuatro flujos de salida.Las desventajas de la arquitectura incluyen su irreversibilidad . Esto se puede ver reduciendo a un estado de 4 bits con s0 = [a, b]y s1 = [c, d]. Con un cambio, obtenemos [0, a]y [0, d], y con agitación, [b, c]y [d, a]. Nuevo s0igual [b, c] + [0, a] = [b⊕(a∧c), a⊕c], pero s1igual [d, a] + [0, c] = [d⊕(a∧c), a⊕c]. Si a = ¬c, entonces, a⊕c = 1y a∧c = 0por lo tanto, s0 = [b, 1]y s1 = [d, 1]. Es decir, obtenemos dos combinaciones de ay c, que nos dan el mismo estado final.En nuestro caso, esto no es un problema, porque el contador de 64 bits también es parte del estado. Resulta el ciclo mínimo de 2 71bytes (128 bytes por transición de estado), que es a una velocidad de 10 gibytes / seg. durará siete mil años. Esto equilibra los estados perdidos.Además, incluso a pesar de la irreversibilidad, el período de transición promedio entre estados es 2 ^ ((256 + 1) ÷ 2). Esto proporciona un ciclo promedio de 2,135 bytes (a una velocidad de 10 gibytes / seg. Durará más de un billón de veces más de lo que existe el universo). Aunque creo que los ciclos intermedios están sobreestimados, porque no nos dicen nada sobre la calidad del generador.Aquí están los resultados de referencia:- Rendimiento : el número de ciclos de procesador gastados en un byte generado. Recibido en máquinas en la nube N2 GCP y N2D (AMD), el orden es el mismo.
- Calidad : el nivel en el que el generador no pasa la prueba PractRand. Si no falla, hay un signo>. Si no se prueba el resultado, hay un signo de interrogación.
- Correlación de números semilla : PractRand transversal con bytes alternos de ocho flujos con semillas número 0, 1, 2, 4, 8, 16, 32, 64. Utilizamos PractRand con doble convolución y pruebas avanzadas.
Más lejos
Aunque en nuestro caso no hay problemas con la irreversibilidad, aún podemos mejorar SHISHUA.En mi opinión, el PRNG ideal tiene las siguientes propiedades:- , 21024. 10 /. 10282 , . «» ( ). , . , 128- NEON ARM? , , .
- . , SHISHUA XOR . , .
- , 2128 ( ). SHISHUA, , . , ( ) (, , . 2).
- La inicialización del estado tiene una dispersión perfecta : todos los bits del número inicial afectan a todos los bits del estado con la misma probabilidad. Quiero averiguar en relación con SHISHUA.
Uno de los problemas que frena el desarrollo de los PRNG y la criptografía en su conjunto es la falta de mejores herramientas de uso general. Necesito una herramienta que pueda darme inmediatamente el resultado exacto de la medición para poder comparar diferentes arquitecturas sobre la marcha.Sin embargo, PractRand es excelente en comparación con lo que era antes:- No permite evaluar generadores de alta calidad, por lo que es imposible compararlos entre sí. Tenemos que decir: "bueno, después de 32 terabytes no tienen anomalías ..."
- Lleva semanas ejecutarlo ...
Espero que la situación mejore mucho pronto.