Diseño de firmware FPGA: ¿Qué tan grande es demasiado grande?

12

Tengo una transformación de procesamiento de señal particularmente grande que necesita ser portada de matlab a VHDL. Definitivamente requiere algún tipo de intercambio de recursos. Un poco de cálculo me dio lo siguiente:

  • 512 ffts de 64 puntos
  • 41210 operaciones de adición múltiple

Teniendo en cuenta que el FPGA Virtex 6 más grande tiene ~ 2000 bloques DSP48E, sé que puedo compartir recursos para reutilizar los recursos varias veces. El tiempo de ejecución no es realmente un problema, el tiempo de procesamiento puede tomar relativamente tiempo en términos de FPGA.

Al observar el uso de recursos, el uso de la arquitectura radix-2 lite me da bloques de 4dsp / operación FFT = 2048 bloques DSP, un total de ~ 43k. El mayor Virtex FPGA tiene 2k bloques, o 20 operaciones / mux.

Obviamente, incluir muxes tan grandes en la tela también va a tomar rodajas. ¿Dónde encuentro el límite superior de este límite? No puedo compartir infinitamente los recursos de FPGA. ¿Los multiplicadores 41210 son demasiado grandes? ¿Cómo calculo lo que es demasiado grande?

También he visto otros recursos (Slices, Brams, etc.). Radix-2 Lite también da 4 x 18k brams / fft = 2048 brams más grande Xilinx FPGA contiene 2128 Brams. Muy limítrofe. Me preocupa que mi diseño sea demasiado grande.


ACTUALIZAR:

Un poco más de información sobre el diseño en sí. No puedo entrar en detalles, pero esto es lo que puedo dar:

Initial conditions -> 512 ffts -> 40k multipliers ---------|----> output data to host 

                 ^------re-calculate initial conditions----|

especificación de salida de datos: "más rápido que la simulación matlab"

cálculos sabios, aquí es donde estoy:

Etapa FFT: fácil. Puedo implementar 1/2/4/8 FFT, almacenar los resultados en SDRAM y acceder más tarde. Relativamente pequeño, incluso si lleva mucho tiempo, está bien. usando radix-2 lite puedo obtener 2 DSP48Es y 2 BRAMS / FFT de 18k. la transmisión da 6 DSP48Es 0BRAMS / FFT. en cualquier caso, la FFT de 64 puntos es pequeña en términos de recursos FPGA.

Multiplicadores : este es mi problema. Las entradas de multiplicación se toman de tablas de búsqueda o de datos FFT. Realmente es solo un montón de sumas múltiples. No hay mucho para optimizar. No es un filtro, pero tiene características similares a un filtro.

Considerando el uso compartido de recursos en el FPGA, las matemáticas funcionan de la siguiente manera: un LUT-6 puede usarse como un mux de 4 vías. La fórmula para un N-way, M bit mux es la siguiente:

N*M/3 = number of luts, or N*M/12 = slices (4 LUTS/slice).

No es bueno obtener cifras para mi implementación. El 90% de la familia virtix-6 no tiene suficientes sectores para compartir recursos en sus DSP para realizar 40k operaciones.

Stanri
fuente
Las formas más eficientes de compartir recursos son la serialización parcial donde puede acceder a los datos dirigiéndose a la memoria. Por supuesto, en el extremo de esto, volverá a un procesador convencional de programas almacenados: la falta de requisitos de rendimiento difíciles comienza a señalar la flexibilidad de una implementación de software que tal vez se ejecute en una nube de cómputo.
Chris Stratton
1
Esto no es parte de su pregunta, pero en su cálculo de recursos no indicó qué tamaño de operando. 512 FFT x 64 puntos x ¿cuántos bits? En un FPGA, el tamaño del operando depende totalmente de usted, por lo que debe tenerlo en cuenta al resolver el tamaño de su problema.
El fotón
No sé si te diste cuenta, pero esos grandes FPGA son bastante caros. Algunos pueden estar por encima de $ 5k. Quizás debería considerar eso también, a menos que el costo no sea un problema.
Gustavo Litovsky
1
Desafortunadamente, más allá del tipo de sugerencias de soluciones alternativas que obtuviste en las respuestas hasta ahora, dudo si podemos hacer mucho más por ti. Quiero decir, podrías crear un solo núcleo FFT y ejecutar tus 512 entradas uno tras otro, y obviamente eso encajaría incluso en un FPGA bastante pequeño. En algún punto entre eso y hacer todo en paralelo está el equilibrio correcto de velocidad frente a recursos para su aplicación ... pero es difícil para cualquiera, excepto usted, decir dónde debería estar ese equilibrio.
The Photon
1
¿Tiene un número de presupuesto para esto? Como Gustavo señaló, los FPGA de gama alta son caros, al igual que desarrollar un PCB para instalarlos. Mientras que al duplicar (o cuadruplicar o ...) la cantidad de hardware de cómputo y continuar usando el existente, probado (?), El código de Matlab probablemente podría cumplir con la especificación de velocidad como se indica.
The Photon

Respuestas:

8

Me pregunto si hay otra forma de ver el problema.

Reproduciendo su estimación de 512 operaciones FFT (64 puntos cada una) y 42k operaciones MAC ... ¿Supongo que esto es lo que necesita para una pasada a través del algoritmo?

Ahora ha encontrado un núcleo FFT con 4 unidades DSP ... pero, ¿cuántos ciclos de reloj tarda por FFT? (rendimiento, no latencia)? Digamos 64, o 1 ciclo por punto. Luego debe completar esas 42k operaciones de Mac en 64 ciclos, quizás 1k MAC por ciclo, con cada MAC manejando 42 operaciones.

Ahora es el momento de ver el resto del algoritmo con más detalle: identifique no las MAC sino las operaciones de nivel superior (filtrado, correlación, lo que sea) que puedan reutilizarse. Cree núcleos para cada una de estas operaciones, con capacidad de reutilización (por ejemplo, filtros con diferentes conjuntos de coeficientes seleccionables) y pronto encontrará que se requieren relativamente pocos multiplexores entre núcleos relativamente grandes ...

Además, ¿es posible alguna reducción de fuerza? Tuve algunos casos en los que se requerían multiplicaciones en bucles para generar cuadráticos (y superiores). Al desenrollarlos, pude generarlos iterativamente sin multiplicación: ¡estaba muy satisfecho conmigo mismo el día que construí un motor de diferencia en FPGA!

Sin conocer la aplicación, no puedo dar más detalles, pero es probable que algunos de estos análisis hagan posibles algunas simplificaciones importantes.

Además, dado que parece que no tiene una plataforma definida en mente, considere si puede dividir entre múltiples FPGA ... eche un vistazo a esta placa o esta que ofrece múltiples FPGA en una plataforma conveniente. También tienen una placa con 100 dispositivos Spartan-3 ...

(PD: me decepcionó cuando los chicos del software cerraron esta otra pregunta, creo que al menos es lo apropiado allí)

Editar: re su edición - Creo que está comenzando a llegar allí. Si todas las entradas del multiplicador son salidas FFT o coeficientes "sin filtro", está comenzando a ver el tipo de regularidad que necesita explotar. Una entrada a cada multiplicador se conecta a una salida FFT, la otra entrada a una ROM de coeficiente (BlockRam implementado como una matriz constante).

La secuenciación de diferentes operaciones FFT a través de la misma unidad FFT secuenciará automáticamente las salidas FFT más allá de este multiplicador. La secuenciación de los coeficientes correctos en la otra entrada MPY ahora es "meramente" una cuestión de organizar las direcciones ROM correctas en el momento correcto: un problema de organización, en lugar de un gran dolor de cabeza de MUX.

Sobre el rendimiento: creo que Dave Tweed estaba siendo innecesariamente pesimista: la FFT tomaba n * log (n) operaciones, pero puedes elegir O (n) unidades de mariposa y O (logN) ciclos, o O (logN) unidades y O ( n) ciclos, o alguna otra combinación para adaptarse a sus objetivos de recursos y velocidad. Una de esas combinaciones puede hacer que la estructura de multiplicación posterior a la FFT sea mucho más simple que otras ...

Brian Drummond
fuente
Una FFT implementada con una sola mariposa de hardware requerirá ciclos de reloj NlogN para completarse; por 512 puntos, eso sería 256 * 8 mariposas, o 2048 relojes. Eso significa que los MAC 41210 (¿o 32768?) Solo requerirían 8-10 multiplicadores de hardware para realizarse en la misma cantidad de tiempo.
Dave Tweed
Quiero decir, 16-20 multiplicadores.
Dave Tweed
Lo siento, me di cuenta de que entendí eso al revés. Las FFT individuales son de 64 puntos, por lo que la implementación de una sola mariposa requerirá 32 * 5 = 160 relojes. Los MAC se pueden hacer con 200-250 multiplicadores de hardware.
Dave Tweed
Esto es lo que me desconcierta. ¿Cómo puede xilinx diseñar un núcleo capaz de hacer 16k / 32k ffts que requieren 400k operaciones de adición múltiple (NlogN) y, sin embargo, estoy luchando con mi 41k? ¡debe haber una forma!
Stanri 01 de
@Dave: Creo que te refieres a 160 multiplicaciones, no 160 ciclos, ¿verdad? No hay nada tan intrínsecamente serializado en una FFT ...
Brian Drummond el
2

Si este problema no tiene restricciones duras en tiempo real, y parece que no lo tiene, solo desea que se ejecute "más rápido", entonces parece que podría ser bastante susceptible a la aceleración en una o más GPU. Hay varias bibliotecas de software que hacen de esta una propuesta relativamente sencilla, y esto sería aproximadamente un orden de magnitud más fácil que ir directamente al hardware FPGA personalizado.

Solo Google para "biblioteca habilitada para GPU" o "biblioteca acelerada por GPU" para comenzar.

Dave Tweed
fuente
Curiosamente, mencioné las GPU al cliente cuando escuché sobre este proyecto, y no estaba interesado.
Stanri 01 de
@StaceyAnneRieck: ¿Dijo por qué?
Dave Tweed
Realmente no dijo por qué, solo que lo había investigado antes de usar un FPGA parecía menos trabajo, aparentemente. Voy a tener que volver a mencionarlo.
stanri
@stanri: Incluso si finalmente terminas en una implementación de FPGA, me parece que la GPU podría ser una buena forma de "panel" de la arquitectura general del sistema. ¿Tiene (y podría compartir?) Algún tipo de gráfico de flujo de datos de alto nivel para el algoritmo, y ¿puede darnos una idea de la cantidad de datos involucrados? Sin respuestas a preguntas como estas, será realmente difícil darle algo más que consejos genéricos.
Dave Tweed
En realidad es un algoritmo muy muy simple, es solo la escala lo que lo hace tan complicado. Básicamente como sigue: condiciones iniciales -> 512 pies en paralelo -> 32768 operaciones de multiplicación en salida FFT -> ajustar condiciones iniciales -> enjuagar y repetir
stanri
1

Es posible utilizar un hardware especializado o un FPGA (o incluso un CPLD) para acelerar en gran medida ciertos tipos de operaciones matemáticas. La clave para tener en cuenta al tratar de diseñar hardware (circuitos o lógica FPGA) para acelerar las operaciones matemáticas es averiguar qué datos de pedido necesitarán entrar y salir de su dispositivo. Un dispositivo con un diseño de E / S eficiente puede ofrecer un rendimiento mucho mejor que uno con un diseño ineficiente, incluso si este último dispositivo requiere muchos más circuitos.

No he intentado elaborar un diseño de asistencia de hardware para una FFT, pero una que he visto es la asistencia de hardware para grandes operaciones de multiplicación (como podría usarse para el cifrado RSA). Muchos microcontroladores, incluso aquellos con hardware especial de multiplicación rápida, no son terriblemente eficientes en tales operaciones porque requieren una gran cantidad de registros aleatorios. El hardware diseñado para minimizar el intercambio de registros podría lograr un rendimiento mucho mejor con operaciones de multiplicación de precisión múltiple, incluso si el hardware en sí no fuera tan sofisticado. Por ejemplo, el hardware que puede realizar una multiplicación canalizada de 16xN de dos bits a la vez (cambiando en dos bits inferiores de multiplicación y desplazando dos bits superiores de resultado) puede lograr un mejor rendimiento que el hardware que puede realizar una multiplicación de 8x8 en un ciclo, a pesar de que los primeros pueden tener menos circuitos (y, en virtud de la canalización, tienen una ruta de datos críticos más corta). La clave es descubrir cómo se verá el "bucle interno" del código necesario y determinar si hay alguna ineficiencia que pueda eliminarse fácilmente.

Super gato
fuente
¿Qué tipos de operaciones son particularmente adecuadas para esta forma de optimización? He editado la pregunta anterior para detallar un poco más sobre la naturaleza de la operación de multiplicación. ¡El diseño asistido por hardware suena realmente interesante!
stanri 01 de
0

¿Qué tan poco nos preocupa el tiempo de ejecución?

Esto realmente parece una situación en la que realmente debería implementar una MCU blanda, una FPGA con una MCU rígida integrada, o incluso un dispositivo MCU separado, y serializar todas sus operaciones.

Suponiendo que tiene el tiempo de ejecución, hacer sus FFT en software será mucho más fácil de depurar, y probablemente también mucho más simple de diseñar.

Connor Wolf
fuente
1
Hacer cálculos pesados ​​en una CPU de núcleo blando en un FPGA es una tontería; si va a hacer el cálculo en una arquitectura de programa almacenada (algo que debe considerarse), debido a CPU (s) duras de alto rendimiento / dólar donde no paga la penalización de velocidad de la lógica flexible en comparación con fab- Generación lógica dura.
Chris Stratton
@ChrisStratton - Buen punto. Se agregó una nota adicional a ese efecto.
Connor Wolf
1
Incluso las CPU rígidas integradas no van a ser una vela para los procesadores / GPU convencionales para tareas basadas en software, y costarán drásticamente más.
Chris Stratton
@ChrisStratton: ¿pensé que las arquitecturas integradas de CPU dura más comunes eran ARM o POWER? En ese caso, básicamente es una CPU de consumo.
Connor Wolf
1
Dada su otra pregunta de FPGA, es probable que construir la placa FPGA sea una experiencia de aprendizaje que costará bastante más de lo estimado. Creo que lo que debería hacer en este momento sería darle al cliente algunos números de precio / rendimiento difíciles de las ejecuciones de la nube de cómputo de prueba (que eventualmente podrían convertirse en hardware comprado), frente a una idea del precio más alto y un riesgo mucho mayor del esfuerzo de FPGA .
Chris Stratton