Forzando Brutalmente MD5 - parte 2 - SIMD

¿Venís de leer la intro y la parte 1?

El tema

Lo anterior es Single Instruction Single Data, esto es, que se ejecuta una instrucción sobre un dato.

En el hack expuesto anteriormente, se ejecuta una instrucción sobre un dato tambien, pero hacemos que sean como dos datos, lo que vendría a ser SIMD, Single Instruction Multiple Data. Este hack está limitado a operaciones lógicas, donde no hay relación entre los bits, está ok hacer AND u OR pero si querés hacer operaciones aritméticas, donde los bits si están relacionados, se "contaminan", por ejemplo al sumar cuando los bits bajos desbordan lo hacen sobre los altos.

AVX2

Quizás podríamos lidiar con ello, pero todas las operaciones involucradas nos sólo nos quitarían la ventaja sino que nos haría perder performance.

De todos modos, tanto como concepto como implentación sí existe SIMD y en las PC se ha llamado MMX, SSEx, AVX y consiste en hacer registros de 64, 128, 256, 512 bits y generar como pistas para operar en 8, 16,32, 64 bits dependiendo de que sistema se use.

Entonces con AVX2 tenemos 256 / 32 = 8 operaciones simultáneas. Uso AVX2 pues es lo que tiene mi CPU, pero existe tambien AVX512 con el cuál lograría 16.

	cpu	cpu unroll	avx2	avx2 + unroll
velocidad	5.7	9.6	28.4	47.9
rendimiento watt	0.86	1.44	4.26	7.19
rendimiento dolar	2.38	4	11.83	19.96

 

		cpu	cpu unroll	avx2	avx2 + unroll
		5.70	9.60	28.40	47.90
cpu	5.70	1.00	1.68	4.98	8.40
cpu unroll	9.60		1.00	2.96	4.99
avx2	28.40			1.00	1.69
avx2 + unroll	47.90				1.00

 

El factor no es necesariamente 8 pues hay otras operaciones involucradas y he leido pero no recuerdo dónde, que por disipación de calor hay momentos en que se duerme parcialmente, no me consta que sea cierto pero el artículo parecía razonable.

No se calcula más rápido pero si varios cálculos a la vez.

Se puede notar que aplica loop unroll también.

Con respecto al rendimiento dolar, hay un inconveniente que es que es la misma CPU, de un modo tiene un rendimiento, del otro otro.

Para programar se usan "instrinsics" que es una manera de decirle al compilador que se van a utilizar ciertas características de la ISA.

En el siguiente código vemos como cargar en a0 ocho veces 0x67452301, luego en A ocho valores y finalmente sumarlos:

#include <immintrin.h>

uint32_t M[LANES][BUFFER_LEN];

...

__m256i a0 = _mm256_set1_epi32(0x67452301);

__m256i A = _mm256_set_epi32(
            0x0360ac33,
            0x330dab62,
            0x4300ab66,
            0x6300ab33,
            0xa300a9d2,
            0xf3003c32,
            0x2300ab23,
            0x03433b31
);

a0 = _mm256_add_epi32(a0, A);

En el proceso de aprendizaje, no hallé la operación NOT, por lo que tuve que implementar un horrible hack que impidió alcanzar el rendimiento esperado. Luego caí en cuenta que estaba la instrucción _notand_ que es es !A & B, así que ejecuté _notand_(A,A). En avx512 si existe NOT.

Links útiles

• https://software.intel.com/sites/landingpage/IntrinsicsGuide/#

Videos

• https://www.youtube.com/channel/UCKsHdgvwvmCNnGD1Az8SSUQ

Código

• https://github.com/cpantel/Forzando-Brutalmente-MD5/tree/master/v3_avx2
• https://github.com/cpantel/Forzando-Brutalmente-MD5/tree/master/v3_avx2_unroll

Seguí con la parte 3