Algoritmos Los FPGA dominan las CPU en

Question

La mayor parte de mi vida he programado CPU; y aunque para la mayoría de los algoritmos, el gran tiempo de ejecución de Oh sigue siendo el mismo en las CPU/FPGA, las constantes son bastante diferentes (por ejemplo, se desperdicia mucha potencia de la CPU mezclando datos, mientras que para FPGA a menudo se computa).

me gustaría aprender más acerca de esto - alguien sabe de buenos libros/documentos de referencia/tutoriales que se ocupa de la cuestión de:

¿Qué tareas FPGAs dominan CPU en (en términos de velocidad pura) ¿qué tareas FPGAs dominan CPU en (en términos de trabajo por Jule)

Nota: marcado wiki de la comunidad

Answer 1

[sin enlaces, sólo mis reflexiones]

FPGAs son esencialmente intérpretes para el hardware! La arquitectura es como los ASIC dedicados, pero para obtener un desarrollo rápido, y usted paga un factor de ~ 10 en frecuencia y un factor [no sé, al menos 10?] En la eficiencia energética.

Así que tome cualquier tarea donde HW dedicado pueda masivamente supere las CPUs, divida por los factores de FPGA 10/[?], Y probablemente aún tenga un ganador. cualidades típicas de este tipo de tareas:

• enormes oportunidades para paralelismo de grano fino.
  (Hacer 4 operaciones a la vez no cuenta, 128 lo hace)
• Oportunidad para canalización profunda.
  Esto también es un tipo de paralelismo, pero es difícil aplicarlo a una única tarea , por lo que ayuda si puede obtener muchas tareas por separado a trabajar en paralelo.
• (Mayormente) Flujo de datos fijo rutas.
  Algunos multiplexores son correctos, pero los accesos aleatorios masivos son malos, porque no se pueden poner en paralelo. Pero mira a continuación sobre recuerdos.
• Alto ancho de banda total a muchos recuerdos pequeños.
  FPGAs tienen cientos de pequeños (O (1 KB)) memorias internas (BlockRAMs en Xilinx jerga), por lo que si se puede particionar uso de la memoria en muchas memorias intermedias independientes, se puede disfrutar de un dato ancho de banda que las CPU nunca soñó.
• Anchura de banda externa pequeña (en comparación con el trabajo interno). La tarea FPGA ideal tiene entradas y salidas pequeñas, pero requiere una gran cantidad de trabajo interno . De esta manera su FPGA no morirá de hambre esperando I/O. (Las CPU ya sufren de hambre, y lo alivian con cachés muy sofisticados (y grandes), inigualables en los FPGA.) Es perfectamente posible para conectar un gran ancho de banda de E/S a un FPGA (~ 1000 pines hoy en dia, algunas de ellas con SERDESes de alta tasa) - pero haciendo que requiere un tablero de encargo con arquitectura para tal ancho de banda; en la mayoría de los escenarios, su E/S externa será un cuello de botella .
• Lo suficientemente simple para HW (también conocido como SW/HW partición).
  Muchas tareas consisten en un 90% de lógica de pegamento irregular y solo un 10% de trabajo duro ("kernel" en el sentido DSP). Si pone todo lo que en un FPGA, perderá preciosos área en la lógica que no funciona la mayor parte del tiempo. Idealmente, usted quiere que todo el estiércol se maneje en SW y utilice completamente el HW para el kernel. (CPU "soft-core" dentro FPGAs son una forma popular para empacar un montón de lógica irregular lenta en la zona media, si no se puede sacar datos a una CPU real.)
• manipulaciones poco raro son un plus.
  Las cosas que no se asignan también a los conjuntos de instrucciones de la CPU tradicionales, tales como el acceso sin alinear a los bits de relleno, las funciones hash, codificación de compresión & ... Sin embargo, no sobrestimar el factor Esto le da - la mayoría de los formatos de datos y los algoritmos que conocerá ya se han diseñado para facilitar los juegos de instrucciones de la CPU, y las CPU mantienen agregando instrucciones especializadas para multimedia.
  Muchos de El punto flotante específicamente es un signo menos porque tanto las CPU como las GPU las procesan en silicio dedicado extremadamente optimizado. (los llamados FPGA "DSP" también tienen una gran cantidad de unidades dedicadas mul/add, pero que yo sepa estos sólo hacen enteros?) Requisitos
• baja latencia/en tiempo real son un plus.
  El hardware realmente puede brillar bajo tales demandas.

EDITAR: Varias de estas condiciones - esp. flujos de datos fijos y muchas tareas separadas para trabajar; también habilite bit slicing en las CPU, lo que de alguna manera nivela el campo.

Answer 2

para la velocidad pura: - los Paralizable - DSP, por ejemplo, filtros de video - Datos móviles, p. DMA

Answer 3

Bueno, la última generación de piezas Xilinx acaba de anunciar brag 4.7TMACS y lógica de propósito general a 600MHz. (Estos son básicamente Virtex 6s fabbed en un proceso más pequeño.)

En una bestia como esta si puede implementar sus algoritmos en operaciones de punto fijo, principalmente multiplique, suma y resta, y aproveche el paralelismo ancho y el paralelismo canalizado puedes comer la mayoría de las PC vivas, en términos de potencia y procesamiento.

Puede hacer flotante en estos, pero habrá un golpe de rendimiento. Los bloques DSP contienen un MACC de 25x18 bit con una suma de 48 bits. Si puede salirse con la suya con los formatos de oddball y eludir parte de la normalización de punto flotante que normalmente ocurre, todavía puede aspirar a la carga de rendimiento de un camión. (es decir, utilice la entrada de 18 bits como punto fijo de flotación o float con una mantisia de 17 bits, en lugar de los 24 bits normales). Los flotadores dobles van a consumir muchos recursos, por lo que si necesita eso, probablemente lo haga mejor en una PC.

Si sus algoritmos se pueden expresar en términos de operaciones de suma y resta, la lógica de propósito general en estos se puede utilizar para implementar sumadores de gazillion. Cosas como los algoritmos de línea/círculo/yadda/yadda/yadda de Bresenham son MUY buenos ajustes para diseños de FPGA.

SI necesita división ... EH ... es doloroso, y probablemente va a ser relativamente lento a menos que pueda implementar sus divisiones como multiplicaciones.

Si necesita muchas funciones trigonométricas de alta precisión, no tanto ... De nuevo, se puede hacer, pero no va a ser bonito ni rápido. (Al igual que se puede hacer en un 6502). Si puede manejar simplemente usando una tabla de búsqueda en un rango limitado, ¡entonces su oro!

Hablando de la 6502, un codificador de demostración 6502 podría hacer cantar a una de estas cosas. Cualquiera que esté familiarizado con todos los viejos trucos matemáticos que los programadores solían usar en la máquina de la vieja escuela así se aplicará. Todos los trucos que el programador moderno le dice "deje que la biblioteca lo haga por usted" son los tipos de cosas que necesita saber para implementar las matemáticas en estos. Si puedes encontrar un libro que habla sobre hacer 3d en un Atari o Amiga basado en 68000, discutirán mucho sobre cómo implementar cosas solo en números enteros.

ACTUALMENTE, cualquier algoritmo que pueda implementarse utilizando tablas de búsqueda será MUY adecuado para FPGA. No solo tiene bloques de bloques distribuidos a través de la pieza, sino que las mismas celdas lógicas se pueden configurar como LUTS de varios tamaños y mini rams.

¡Puede ver cosas como manipulación de bits fija como GRATIS! Es simplemente manejar por enrutamiento. Los cambios fijos o las inversiones de bits no cuestan nada. ¡Las operaciones dinámicas de bit como cambio en una cantidad aceptable costarán una cantidad mínima de lógica y se pueden hacer hasta que las vacas vuelvan a casa!

¡La parte más grande tiene 3960 multiplicadores! Y 142.200 rebanadas que CADA UNO puede ser un sumador de 8 bits. (4 6Bit Luts por porción o 8 5bit Luts por porción, dependiendo de la configuración.)

Answer 4

Elija un algoritmo de Gnarly SW. Nuestra empresa realiza la aceleración HW de SW algo para ganarse la vida.

Hemos hecho implementaciones HW de motores de expresiones regulares que harán 1000 conjuntos de reglas en paralelo a velocidades de hasta 10 Gb/seg. El mercado objetivo para eso son los enrutadores donde los antivirus y los ips/ids pueden ejecutarse en tiempo real a medida que los datos se transmiten sin ralentizar el enrutador.

Hemos hecho codificación de video HD en HW. Solía ​​tomar varias horas de tiempo de procesamiento por segundo de película para convertirlo a HD. Ahora podemos hacerlo casi en tiempo real ... tarda casi 2 segundos de procesamiento para convertir 1 segundo de película. Netflix usó nuestro HW casi exclusivamente para su producto de video bajo demanda.

Incluso hemos hecho cosas simples como encriptación y descifrado RSA, 3DES y AES en HW. Hemos hecho un simple zip/descomprimir en HW. El mercado objetivo para eso es para cámaras de video de seguridad. El gobierno tiene una gran cantidad de cámaras de video que generan enormes flujos de datos en tiempo real. Lo comprimen en tiempo real antes de enviarlo a través de su red, y luego lo descomprimen en tiempo real en el otro extremo.

Heck, otra empresa para la que trabajaba solía hacer receptores de radar con FPGA. Ellos tomarían muestras de los datos del radar enemigo digitalizados directamente en varias antenas diferentes, y desde el delta de llegada del tiempo, descubrirán qué dirección y qué tan lejos está el transmisor enemigo. Diablos, incluso pudimos verificar la modulación involuntaria en el pulso de las señales en los FPGA para averiguar la huella de los transmisores específicos, para poder saber que esta señal proviene de un sitio SAM ruso específico que solía estar estacionado en un borde diferente. , para poder rastrear los movimientos y las ventas de armas.

¡Intente hacer eso en el software! :-)