¿Venís de leer la
intro, la
parte 1, la
parte 2, la
parte 3 la
parte 4, la
parte 5 y la
implementación FPGA en nexys4ddr?
El tema
Habiendo agotado en lo que a mi respecta las maneras de calcular MD5 usando una o varias CPU, ya sean sus instrucciones básicas o extendidas, habiendo aplicado una optimización llamada "loop unroll", que consiste en tomar un loop, quitarle el contador y escribir su cuerpo tantas veces como hubiese sido ejecutado, adaptando cada iteración a los valores que hubiese recibido del contador, llegó el momento de no usar más CPU.
Fijate que más arriba le dediqué mucho al loop unroll. Es que desde el primer día que decidí encarar este proyecto, sabía que era lo que en última instancia iba a utilizar.
Todo el caminito que recorrí por las CPUs, aunque muy divertido e instructivo, realmente aprendí mucho, asenté, fundamenté y completé mucho conocimiento, no era para mi, era para vos.
Lo que yo quería hacer desde el comienzo era esto, implementar el forzador de MD5 en una FPGA, pero si vos no sabés nada de técnicas digitales, ni cómo funcionan la computadoras, ni assembly, ni C, ni programar quizás, te muestro esto primero y te mato.
En el trabajo fui mostrando cada etapa en una charlas a gente de diverso
conocimiento técnico y apuesto que de no haber seguido este camino, a
la mayoría ahora le costaría asimilar algo de todo esto, no habría
ninguna conexión con su conocimiento.
FPGA
Ni instrucciones básicas, ni extendidas, ni multithread/multiprocess, ni optimizaciones del compilador, nada.
Había
comentado antes que la velocidad del clock se había convertido en un
limitante y eso había impulsado el paralelismo del multicore.
Tambien
que en el caso de supercomputadoras como Epiphany y GPGPU, que esos
cores fueran lo más sencillos posibles para ahorra silicio y poner más
cores.
Aondando en esa tendencia, pensá que un core es una
CPU de propósito más o menos general y aunque sea de propósito muy
específico, cada problema que resuelvas no va a utilizar buena parte de
los recursos que ofrezca.
Si además, es muy especifica y el problema cambia, no la vas a poder utilizar.
Si
pudieras reconfigurar el hardware para que el silicio existente esté
íntegramente dedicado a la resolución del problema que estás encarando,
alcanzarías el máximo rendimiento.
El hardware reconfigurable se llama FPGA y se programa principalmente en VHDL como en este caso y Verilog.
 |
Pipeline
|
La idea es que con un contador vas generando las claves candidatas y le vas a aplicando algo así como el loop unroll que habíamos visto antes, pero con la diferencia que cada etapa, cada ronda es un circuito que está ejecutando las operaciones en simultáneo con las demas.
Durante los primeros 63 clicks del reloj el comparador recibe basura, de ahí en más lo que había en el contador hace 64 ticks.
De esta manera tenemos un paralelismo de 64, así como con AVX2 8, con GPU varios centenares y con multicore x 32.
La ventaja abismal, es que en cada tick se obtiene un hash entero, a diferencia de CPU/GPU que lleva muchísimimos ticks, al punto de que el clock de la FPGA que tengo es de sólo 100Mhz y aún así, como tengo espacio suficiente en la FPGA para instanciar hasta 10 pipelines, alcanza a la GPGPU, consumiendo mucho menos.
Si además este diseño lo ajustar para poder pasarlo a un ASIC, esto es un chip no reconfigurable, carísimo para un sólo ejemplar pero baratísimo por millón, podría aumentar la velocidad de clock y agregar instancias del pipeline, pues FPGA ocupa mucho espacio por ser reconfigurable.
Según he leido, ese cambio lo haría 10 veces más rápido por el clock y supongo que otras 10 veces más rápido por poner más instancias. De hecho, para minar bitcoins existen ASICs.
El camino
Tuve que tomar diversos caminos, divergente, simultáneos e incluso superpuestos debido en parte a mi desorden mental, en parte a mis conocimientos limitados, al tiempo disponible, al hardware disponible y a las dificultades de los entornos de desarrollo.
Una vez que tuve una versión que malamente funcionaba, le quité todo lo superfluo y lo instancié varias veces en mi hardware para ver cual era el rendimiento máximo.
Utilicé la placa Nexys4-DDR que entre que la pedí y antes de llegar ya me quedó obsoleta, mala suerte. Es una FPGA de las más caras de las baratas o más baratas de las caras, tiene VGA, switches, botones, 7 segmentos, audio, usb, de todos.
Más arriba mencioné el loop unroll como gran protagonista. Es que de no utilizarlo, tendría que diseñar una circuitería de control que comenzaría a parecerse a una CPU, perdiendo las ventajas ganadas.
De todos modos, esa proto CPU tendría sólo las instrucciones necesarias para este problema.
| cpu | cpu
unroll | avx2
+ unroll | threads
x 4
+ avx2 | threads
x 32 | gpu
| fpga
x 1 | fpga
x 8 | fpga
x 10 |
| velocidad | 5.7 | 9.6 | 47.9 | 153.4 | 179 | 1090.1 | 100 | 800 | 1000 |
| rendimiento watt | 0.86 | 1.44 | 7.19 | 23.01 | 3.1 | 106.64 | 45 | 360 | 450 |
| rendimiento dolar | 2.38 | 4 | 19.96 | 63.92 | 13.16 | 454.21 | 78.13 | 625 | 781.25 |
|
| cpu | cpu
unroll | avx2
+ unroll | threads
x 4
+ avx2 | threads
x 32 | gpu
| fpga
x 1 | fpga
x 8 | fpga
x 10 |
|
| 5.7 | 9.6 | 47.9 | 153.4 | 179 | 1090.1 | 100 | 800 | 1000 |
| cpu | 5.7 | 1.00 | 1.68 | 8.40 | 26.91 | 31.40 | 191.25 | 17.54 | 140.35 | 175.44 |
cpu
unroll | 9.6 |
| 1.00 | 4.99 | 15.98 | 18.65 | 113.55 | 10.42 | 83.33 | 104.17 |
avx2
+ unroll | 47.9 |
|
| 1.00 | 3.20 | 3.74 | 22.76 | 2.09 | 16.70 | 20.88 |
threads
x 4
+ avx2 | 153.4 |
|
|
| 1.00 | 1.17 | 7.11 | 0.65 | 5.22 | 6.52 |
threads
x 32 | 179 |
|
|
|
| 1.00 | 6.09 | 0.56 | 4.47 | 5.59 |
gpu
| 1090.1 |
|
|
|
|
| 1.00 | 0.09 | 0.73 | 0.92 |
fpga
x 1 | 100 |
|
|
|
|
|
| 1.00 | 8.00 | 10.00 |
fpga
x 8 | 800 |
|
|
|
|
|
|
| 1.00 | 1.25 |
Con 8 pipelines, como corre a 100Mhz, tenemos 800 de velocidad, no muy
lejos de los 1090 de la GPU. Aunque no lo hice funcionar pues se me
complica la lógica, podría tener 10 pipelines y estoy seguro que de
tener un poco más de praćtica y aprovechando los DSPs podria llega a
meter 11 o incluso 12.
|
| nexys4ddr | parallella | PYNQ-Z2 |
|
| artix-7 | zynq 7010 | zynq 7020 |
| luts | 15k | 25k | 85k |
| dsp | 240 | 80 | 220 |
pipelines | implementados
o implementables | 8 | 13 | 45 |
máximo
estimado | 11 | 14 | 47 |
Utilizando sólo los luts y dsp disponibles, proyecto los números para las otras dos placas que tengo. No estoy considerando que quizás podría subir la velocidad del clock por encima de 100Mhz. Para ello tendría que usar los PLLs disponibles y evaluar los timings a ver si llegan a hacerse las operaciones a tiempo.
Con respecto a los DSP, supongo que no haría un pipeline de DSPs si no que una etapa de cada pipeline estaría implementada así, futuro improbable.
Si juntara todo, tendría entonces entre 6600M y 7200M hashes por segundo y 1090 con la GPU. Luego, tendría que pedirle a alguien que tenga una GPU decente que ejecute mi programa, pues mi GPU es GeForce 940MX, al momento de hacer este análisis, 2019, un GeForce GTX 1080 Ti era casi 9 veces más veloz según algún benchmark que no registré.
Al momento de escribir esto, GeForce RTX 2080 Ti sale u$s 1000, el doble que las tres FPGA que tengo y consume 250 Watts vs los menos de 15 Watts que consumen las tres juntas, pero, si se puede proyectar la comparación de mi GPU, tendría una velocidad de 15000M, así que el rendimiento dolar sería apenas mejor para GPU y el energético 15 veces mejor para las FPGA, pero tomalo con pinzas.
No sé cuántos LUTs se consiguen por u$s 1000.
De todos modos, todo esto es para MD5, habría que ver que pasa con algoritmos modernos tipo SHAx.
Código
- https://github.com/cpantel/Forzando-Brutalmente-MD5/tree/master/v8_fpga
Seguí en la parte 7
