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

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

  • 512 ftts de 64 puntos
  • 41210 operaciones de suma y multiplicación

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 ser relativamente largo en términos de FPGA.

En cuanto al uso de recursos, el uso de la arquitectura radix-2 lite me da 4 bloques dsp/operación FFT = 2048 bloques DSP, un total de ~43k. El Virtex FPGA más grande tiene 2k bloques o 20 operaciones/mux.

Obviamente, incluir muxes tan grandes en la tela también tomará porciones. ¿Dónde encuentro el extremo 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 buscado en otros recursos (Slices, Brams, etc.). Radix-2 Lite también ofrece 4 x 18k brams/fft = 2048 brams. El Xilinx FPGA más grande contiene 2128 Brams. muy límite. Me preocupa que mi diseño sea demasiado grande.

ACTUALIZAR:

Algo 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 tasa de datos de salida: "más rápido que la simulación matlab"

En cuanto a los cálculos, 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 DSP48E y 2 18k BRAMS/FFT. la transmisión proporciona 6 DSP48Es 0BRAMS/FFT. en cualquier caso, la FFT de 64 puntos es pequeña en términos de recursos de FPGA.

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

Teniendo en cuenta el uso compartido de recursos en el FPGA, las matemáticas funcionan de la siguiente manera: un LUT-6 se puede usar como mux de 4 vías. La fórmula para un multiplexor de bits M de N vías es la siguiente:

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

procesar los números para mi implementación no da buenos resultados. El 90 % de la familia virtix-6 no tiene suficientes segmentos para compartir los recursos de sus DSP a fin de realizar operaciones de 40k.

Las formas más eficientes de compartir recursos son la serialización parcial donde puede acceder a los datos direccionando la memoria. Por supuesto, en el extremo de esto, vuelve a un procesador de programa almacenado convencional: la falta de requisitos estrictos de rendimiento comienza a apuntar hacia la flexibilidad de una implementación de software que tal vez se ejecute en una nube informática.
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 cuantos bits? En un FPGA, el tamaño del operando depende totalmente de usted, por lo que debe tenerlo en cuenta al calcular el tamaño de su problema.
No sé si te diste cuenta, pero esos grandes FPGA son bastante caros. Algunos pueden estar por encima de $ 5k. Tal vez debería considerar eso también, a menos que el costo no sea un problema.
@ThePhoton: utilicé el generador central para estimar el uso de recursos de FFT, cada FFT tiene 64 puntos, punto fijo y 32 bits de datos, 24 de datos de fase.
Desafortunadamente, más allá de las sugerencias de soluciones alternativas que recibió en las respuestas hasta ahora, dudo que podamos hacer mucho más por usted. Quiero decir, podría hacer solo un núcleo FFT y ejecutar sus 512 entradas una tras otra, y obviamente eso encajaría incluso en un FPGA bastante pequeño. En algún punto entre eso y hacer todo en paralelo se encuentra el equilibrio adecuado entre velocidad y recursos para su aplicación... pero es difícil para cualquiera excepto para usted decir dónde debería estar ese equilibrio.
Este podría ser el tipo de idea para lanzar en el chat en lugar de aquí en el área de preguntas y respuestas... pero no creo que haya ningún gurú digital serio que sea habitual en el chat.
No estoy demasiado preocupado por la FFT, sinceramente. con un poco de SDRAM puedo almacenar las operaciones FFT realizadas secuencialmente y recuperar los datos más tarde. Estoy más preocupado por las operaciones de multiplicación de ~ 40k. a 18 bits cada uno, y suponiendo multiplicadores de 2k, tendría que multiplicar cada multiplicador de 20 maneras. un mux de 20 vías y 18 bix necesita 7 LUT-6/bit, o 40 segmentos. 40 x 2k = 80k. Lo suficientemente pequeño como para caber en los dos FPGA Virtex 6 más grandes:/
@StaceyAnneRieck, supongo que no entendí a qué te referías con los multiplicadores. Pensé que los multiplicadores eran los necesarios para hacer las FFT.
sí, mirándolo de nuevo, es un poco ambiguo de mi parte. Las FFT se suman a las operaciones de multiplicación.
@ThePhoton He agregado más detalles sobre el diseño a la pregunta.
¿Tiene un número de presupuesto para esto? Como señaló Gustavo, los FPGA de gama alta son caros, al igual que desarrollar una PCB para colocarlos. Mientras que simplemente duplicar (o cuadruplicar o...) la cantidad de hardware de cómputo y continuar usando el código existente, probado (?), Matlab probablemente podría cumplir con la especificación de velocidad tal como se indica.
"Originalmente asumí que el profesor que escribió el artículo sobre el algoritmo lo habría optimizado todo lo posible..." ¿Podría proporcionar un enlace al artículo en cuestión?
Si tiene una nueva pregunta, publíquela como una nueva pregunta, proporcione los detalles requeridos para la pregunta específica que desea y haga otra. Los usuarios también votarán a favor de eso y ayudará a mantener cada pregunta enfocada en un solo problema técnico.
Si siempre está organizando las entradas del multiplicador en la misma secuencia, puede salirse con la suya con los cambiadores, en lugar de muxes de entrada amplios. Es decir, la implementación de mult_in <= mux[n]where nse incrementa en uno en cada ciclo se puede minimizar de forma masiva.

Respuestas (4)

Me pregunto si hay otra forma de ver el problema.

Jugando con su estimación de 512 operaciones FFT (64 puntos cada una) y 42k operaciones MAC... ¿Supongo que esto es lo que necesita para pasar por el algoritmo?

Ahora ha encontrado un núcleo FFT que utiliza 4 unidades DSP... pero ¿cuántos ciclos de reloj se necesitan por FFT? (rendimiento, no latencia)? Digamos 64, o 1 ciclo por punto. Luego, debe completar esas 42k operaciones 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 se pueden reutilizar. Construya núcleos para cada una de estas operaciones, con 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áticas (y superiores). Al desenrollarlos, pude generarlos iterativamente sin multiplicación: ¡estaba bastante satisfecho conmigo mismo el día que construí un motor diferencial en FPGA!

Sin conocer la aplicación, no puedo dar más detalles, pero es probable que algún análisis de este tipo haga posibles algunas simplificaciones importantes.

Además, dado que parece que no tiene una plataforma definida en mente, considere si puede particionar en múltiples FPGA ... eche un vistazo a esta placa o a 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 es al menos tan 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á empezando 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 coeficientes (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. Secuenciar los coeficientes correctos en la otra entrada MPY ahora es "simplemente" una cuestión de organizar las direcciones ROM correctas en el momento correcto: un problema organizativo, en lugar de un gran dolor de cabeza de MUXes.

Sobre el rendimiento: creo que Dave Tweed estaba siendo innecesariamente pesimista: la FFT toma operaciones n * log (n), pero puede elegir O (n) unidades de mariposa y ciclos O (logN), o unidades O (logN) 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 post-FFT sea mucho más simple que otras...

Una FFT implementada con una sola mariposa de hardware requerirá ciclos de reloj NlogN para completarse; para 512 puntos, serían 256*8 mariposas, o 2048 relojes. Eso significa que los MAC 41210 (¿o 32768?) solo requerirían 8-10 multiplicadores de hardware para funcionar en la misma cantidad de tiempo.
Quiero decir, 16-20 multiplicadores.
Lo siento, me acabo de dar cuenta de que lo entendí al revés. Las FFT individuales son 64 puntos, por lo que la implementación de una sola mariposa requerirá 32*5 = 160 relojes. Luego, los MAC se pueden hacer con 200-250 multiplicadores de hardware.
esto es lo que me deja perplejo. ¿Cómo puede xilinx diseñar un núcleo capaz de hacer ffts de 16k/32k que requieren 400k operaciones de suma y multiplicación (NlogN) y, sin embargo, tengo problemas con mis 41k? ¡debe haber una forma!
@Dave: Creo que te refieres a 160 multiplicaciones, no a 160 ciclos, ¿no? No hay nada tan inherentemente serializado en una FFT...
Una mariposa FFT radix-2 requiere 4 multiplicaciones y dos sumas. Supongo que la "arquitectura radix-2 lite" mencionada por el OP puede producir un par de resultados en cada ciclo de reloj, según los recursos utilizados. La secuenciación de los datos y coeficientes de entrada/intermedios a través del hardware se deja como un ejercicio para el lector, pero es bastante fácil de canalizar.

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

Simplemente busque en Google "biblioteca habilitada para GPU" o "biblioteca acelerada por GPU" para comenzar.

Curiosamente, le mencioné las GPU al cliente cuando me enteré de este proyecto y no estaba interesado.
@StaceyAnneRieck: ¿Dijo por qué?
Realmente no dijo por qué, solo que lo había investigado antes y aparentemente usar un FPGA parecía menos trabajo. Voy a tener que traerlo de nuevo.
@stanri: incluso si finalmente termina en una implementación de FPGA, me parece que la GPU podría ser una buena manera de "ensamblar" la arquitectura general del sistema. ¿Tiene (¿y podría compartirlo?) 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, va a ser muy difícil darle algo que no sea un consejo muy genérico.
En realidad, es un algoritmo muy, muy simple, es solo la escala lo que lo hace tan complicado. Básicamente de la siguiente manera: condiciones iniciales -> 512 ffts en paralelo -> 32768 operaciones de multiplicación en la salida FFT -> ajustar las condiciones iniciales -> enjuagar y repetir
El hecho de que el mismo bucle FFT -> multiplicador se produzca repetidamente hace que esta implementación en particular sea particularmente adecuada para un FPGA, sin embargo, eso es solo si el diseño se ajusta.
Eso significa que para cada iteración del algoritmo, debe realizar 512*32*5 = 81920 mariposas. Si ensambla un FPGA con, digamos, dos mariposas de hardware y una MAC, podría completar una iteración en algo así como 40000 ciclos de reloj, o 4 ms a un reloj conservador de 100 MHz. 32 mariposas (una iteración de una fila completa de una FFT) y 16 MAC lo harían en 2560 ciclos de reloj. ¿Qué ancho tienen las palabras de datos? Si necesita o no almacenar en búfer en la memoria externa determinará hasta dónde puede impulsar el rendimiento en la práctica.
Nuevamente, esto suena como una muy buena opción para la aceleración de GPU.

¿Qué tan pequeño es el problema del tiempo de ejecución?

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

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

Hacer cálculos pesados ​​en una CPU de núcleo blando en un FPGA es una tontería; si va a realizar el cálculo en una arquitectura de programa almacenada (algo que debe tenerse en cuenta), hágalo en CPU(s) duras de alto rendimiento/dólares en las que no pague la penalización de velocidad de la lógica flexible sobre fábricas comparables. generación lógica dura.
@ChrisStratton - Buen punto. Se agregó una nota adicional a tal efecto.
Incluso las CPU integradas no van a competir con los procesadores/GPU convencionales de productos básicos para tareas basadas en software, y costarán drásticamente más.
@ChrisStratton: pensé que las arquitecturas de CPU dura integradas más comunes eran ARM o POWER. En ese caso, básicamente es una CPU básica.
No del tipo que alguien usaría para una tarea basada en computación. No sé si Amazon publica los detalles del hardware que está comprando para su nube informática, pero dicha instalación (compartida o privada) será una consideración cuidadosa de la intersección de las ganancias de rendimiento en las ofertas más recientes, el costo de adquisición y el poder. costo de operación. Una CPU atascada en una esquina de un troquel FPGA no se acercará en costo o rendimiento a lo que puede hacer al elegir lo que el mercado de computación de propósito general drásticamente más grande tiene para ofrecer en un día determinado.
@ChrisStratton: creo que estamos pensando en escalas de cómputo radicalmente diferentes. Si desea una gran cantidad de funciones (como una GPU moderna o una CPU X86), tiene razón en que necesitará un procesador separado. Sin embargo, diseñar un sistema que utilice dichos procesadores será extremadamente difícil e imposible. Si necesita tanto crujido, es mejor que compre una PC de escritorio y convierta su dispositivo FPGA en una tarjeta PCIe.
Digo que el tiempo de ejecución no es un problema porque no estoy transmitiendo datos a través de la FPGA, los estoy generando en la FPGA. Actualmente, la implementación de la PC lleva horas. Desafortunadamente, GPU o CPU no son una opción aquí, el cliente insiste en FPGA.
Entonces no sé qué decirte. Parece que su proyecto es ideal para una implementación de GPGPU. ¿Es su cliente totalmente intratable?
Dada su otra pregunta sobre FPGA, es probable que construir la placa FPGA sea una experiencia de aprendizaje que costará un poco más de lo estimado. Creo que lo que hay que hacer en este punto sería darle al cliente algunas cifras concretas de precio/rendimiento de las ejecuciones de cómputo en la nube de prueba (que eventualmente podrían convertirse en hardware comprado), frente a una idea del precio más alto y el riesgo mucho mayor del esfuerzo de FPGA. .

Es posible usar un hardware especializado o un FPGA (o incluso un CPLD) para acelerar en gran medida ciertos tipos de operaciones matemáticas. Lo más importante a tener en cuenta cuando se trata de diseñar hardware (circuitos o lógica FPGA) para acelerar las operaciones matemáticas es averiguar en qué orden los datos deberá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 el último dispositivo requiere muchos más circuitos.

No he intentado elaborar un diseño de asistencia de hardware para una FFT, pero uno que he analizado es la asistencia de hardware para operaciones de multiplicación grandes (como podría usarse para el cifrado RSA). Muchos microcontroladores, incluso aquellos con hardware especial de multiplicación rápida, no son muy eficientes en este tipo de operaciones porque requieren una gran cantidad de cambios de registros. 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 de 16xN canalizada dos bits a la vez (desplazando 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. aunque el primero puede requerir menos circuitos (y, en virtud de la canalización, tiene una ruta de datos crítica más corta). La clave es descubrir cómo se verá el "bucle interno" del código necesario y averiguar si hay alguna ineficiencia que pueda eliminarse fácilmente.

¿Qué tipos de operaciones son particularmente adecuadas para esta forma de optimización? Edité 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!
Diseño de firmware FPGA: ¿Qué tan grande es demasiado grande?
RespuestasAquíPolítica de privacidad1y, 0v