2020/12/30

Nexys4 DDR FPGA: Implementación de MD5

¿Venís de leer la intro, la parte 1, la parte 2, la parte 3,  la parte 4 y la parte 5?

 Contexto


Tenía unos pocos días para implementar en el Zynq de la Parallella el forzador brutal de MD5 para proponerlo a un evento.

Como veía que se me venía difícil, intenté prepararme un [entorno de TDD] que no usé, pero me puso en sintonía.

(Nota: cada texto entre llaves indica un link que aún no está disponible, en algún momento actualizaré)

Sabía algo de VHDL, pero mi punto de entrada a esa plataforma es Verilog así que intenté aprender un poco [migrando ejemplos] e investigando y eso me dejó con soltura en el lenguaje y el entorno de desarrollo.

En lugar de respetar el plan que me había propuesto, fui más tipo blitzkrieg, tomé algunos componentes de la migración y los hice funcionar juntos, en una primera etapa un contador con botones de start, stop y reset, display de 7 segmentos y unos leds de estado, lo cual ocupa casi nada de la PL disponible:



Sin el pipeline




Luego agregué el pipeline:



Diagrama de bloques simplificado



Y lo fui implementando stage por stage, primero a mano y luego me cansé y programé un [generador en C]. Tambien hice una salida de referencia con los valores intermedios y conectando sucesivamente la entrada del selector de display a estos estados intermedios en el pipeline, verifiqué que funcionara ok.



8 stages



Y así hasta el stage63... puse lógica de detección de coincidencia y perdí un tiempo ridículo en conseguir que start/stop, reset, found, done y running hicieran lo que yo quería.


El pipeline completo

Resultados


Tengo un circuito que calcula 4 GHashes en 40 segundos, esto es 100 MHashes por segundo, que es exactamente lo que había previsto.



Los IO no importan pues no harían falta en cada instancia, no?



Para la demo y para github lo instancié ocho veces, se acerca a 1100 MHashes que había alcanzado con GPGPU. Tambien para probar la superficie instancié 10 pero sin la lógica necesaria para distribuir los rangos de exploración, las potencias de 2 son más fáciles.


Deuda técnica y aprendizajes


Como que esto fué tiro con arco zen, pero sin la sabiduría que implica, casi que manotazos de ahogado, entiendo que si funciona es por una acumulación inconsciente de conocimiento, hay partes que no puedo explicar responsablemente.

El tiempo de síntesis e implementación arrancó en cuatro minutos y se duplicó con el pipeline completo, yo aproveché para ir haciendo estas entradas en el blog o ir pensando el siguiente paso (sin salvar, que puede afectar el flujo actual o siguiente), no es bueno irse a colgar ropa o ponerse a pensar en otra cosa.


Cerca de cuarenta horas a lo largo de cuatro días me llevó esto.

Cuando aprenda a [simular] supongo que será todo más fluido.

Hay que mirar permanentemente los warnings, sobre todo los critical warnings, varias veces me avisaron de cables no conectados.

Sin embargo, en la etapa de debugging del pipeline ocurrió algo muy interesante: por desviar hacia el display etapas intermedias y no usar la salida de pipeline para nada, lo quita por optimización:


Efecto de conectar el display al stage00 en lugar del stage63






Seguí con la parte 6

Forzando Brutalmente MD5 - parte 7 - caminos no tomados

¿Venís de leer la intro, la parte 1, la parte 2, la parte 3, la parte 4, la parte 5, la  implementación FPGA en nexys4ddr y la parte 6?

Dejo registradas acá todas las ideas y caminos no explorados, ya sea por falta de tiempo, ganas, dinero, interés o acceso.


No garantizo que sea la última, pues me falta usar la FPGA de la Parallella y la PYNQ y dejando de lado esto específico de md5, es una experiencia que me falta. La diferencia entre Parallella y PYNQ es el doble de FPGA.

 

Mainframe


Aunque tengo acceso parcial a un mainframe, se trata de un elemento crítico y debería programarlo en assembly por motivos de licencias. No sería la primera vez, en una materia de la facultad lo hice con un simulador, tendría que instalarme un hercules para hacer que funcione primero.

Tambien podría programarlo en cobol, pero estuve mirando y es una patada en los piés. No tengo acceso a la licencia para compilar en C, que sería lo más sencillo. Entiendo que hay oferta de acceso gratuito a mainframes para hacer pruebas, pero ya he perdido el impulso, quedará para otra reencarnación, si es que recuerdo la clave de acceso a este blog.


Se consigue acceso gratuito vía Master the Mainframe, pero parece que no tiene compilador C, habría que mirar. No vale la pena usar el emulador Hercules para la medición, pues queda desvirtualizada. Chiste nerd.

 

NEON


Otra prueba que no hice fue SIMD en ARM, que se llama NEON. Si buscás en ese lugar, al momento de escribir esto te lleva a una página que te ofrece:

 

Arm Architecture Reference Manual Armv8, for Armv8-A architecture profile

Contains reference documentation for all Advanced SIMD instructions.

 

pero al intentar ir por ahí, falla, no importa, con esas palabras claves se consigue un pdf con una versión beta del 2013 que tiene más de 5000 páginas. Tras mirar superficialmente, desistí y vía la descripción de instrinsics parece que soporta 4 x 32 bits, la mitad que AVX2, no logré encontrar rapido las instrucciones, justamente no tengo tiempo para esto. Hubiese servido para Raspberry Pi y celulares.


Cell Processor


Mencioné en la parte de GPGPU la existencia del Cell Processor, la verdad es que me quedé con la ganas. Algo que no dije, es que no es como una GPU, un conjunto de procesadores especializados que se agregan a un sistema, si no más bien como la Parallella o como los micros A de AMD, o sea un(os) cores llamados PPU (PowerPC Processing Element) tipo los ARM de zynq o los x86_64 de AMD más los SPE (Synergistic Processor Elements), como el multicore Epiphany de la Parallella o la GPU de AMD.

 

El problema era conseguir uno:

  • Playstation 3: hay un rango muy específico de modelos que permiten ejecutar linux y nadie lo tenía.
  • Servidor: había encontrado un server, lo vendían por ebay en Inglaterra
  • Placa PCI: tambien existe como una placa aceleradora.

 

Cell Processor
Cell Processor

Por suerte no tomé este camino, recientemente me enteré que aunque son increiblemente potentes al punto que se podrían seguir usando, son increiblemente difíciles de programar.

 

Sistemas Distribuido


No quiero dictar cátedra de sistemas distribuidos, más por que no la cursé, pero en mi mediano entender alcanzo a vislumbrar algunos escenarios.

 

Homogéneos

 

Hay múltiples técnicas para esto, mí única experiencia, académica, ha sido con MPI.

 

Agente en Javascript para el browser


No sé como andará la performance de webassembly, no apareció nada que no fuera youtube en google al buscar o que fuera una clara comparación fácil de leer e interpretar. Además está el problemita del multicore, no sé pero apuesto a que no se puede usar más de un core a la vez.

Todo eso no importa, por que bien aplica la frase "no somos machos pero somos muchos" y el agente en javascript para el browser se llama...

 

Botnet 

 

Del mismo modo que hay sitios que cuando entrás te dan un javascript para ponerte a minar bitcoin, se puede confeccionar un agente similar en Javascript o webassembly, si te conseguís muchos, todo bien.

 

Heterogéneo


Esto corresponde a un escenario más colaborativo y artesanal que el anterior,  donde podríamos distribuir la carga sobre CPUs con y sin SIMD, GPUs y FPGAs en una red no necesariamente local. Por ejemplo:


  • Mi laptop soporta AVX2 y GPU
  • La Parallella soporta FPGA, los 16 cores del Epiphany y los dos del PS, que no sé si soportan SIMD
  • Nexys4 soporta FPGA

 Como podrás apreciar, nos movemos en varias dimensiones

 

¿Cómo distribuir la carga?
¿Cómo distribuir la carga?

Estas deben estar coordinadas entre sí, fijate que para la nexys4 deberías contar con una computadora que le configure los rangos y esté atenta a los hallazgos, todo un subproyecto de por sí.

 

Y ahí empiezan las preguntas, ahora no estoy hablando de armar un sistema de cero, ahi sin duda hay diseñar para usar GPU y/o FPGA, digo a partir de lo uno (yo en este caso) tiene.

 

Si la FPGA y/o GPU es XXX veces más rápida, ¿vale la pena molestarse en usar las CPUs asociadas de ese dispositvio?

Otra, ¿y si ya tenemos las CPUs como puede ser un montón de netbooks o celulares? ¿alcanzará SIMD para justificar?


Luego hay que pensar en la distribución de carga entre todos los nodos, evidentemente hay que hacer lotes de distinto tamaño según la potencia del nodo. 

También hay que implementar un mecanismo de corte generalizado ante el primer hallazgo. Pero si en lugar de estar buscando estuviésemos calculando para almacenar, ¿Cómo hacemos para sacar toda esa información, sobre todo en FPGA?