¿Ejemplos de algoritmos de propósito general que se han beneficiado de la ejecución en una GPU? [cerrado]

Estoy buscando ejemplos de algoritmos de propósito general (es decir, no relacionados con gráficos) que se ha demostrado que funcionan un orden de magnitud más rápido en una GPU que en una CPU. Usaré estos ejemplos para pensar creativamente sobre otros algoritmos que podría implementar en una GPU.

Algunas cosas me vienen a la mente de inmediato:

Se escribió un cliente especializado de Bitcoin para usar la GPU para realizar los hashes criptográficos. El cliente de GPU generalmente funciona más de 10 veces mejor que el cliente de CPU SMP en un sistema típico de 4 núcleos. Bitcoin depende del cálculo de un gran número de hashes criptográficos no relacionados, que se pueden calcular en paralelo.

El proyecto Folding @ Home ofrece un cliente de GPU para sus simulaciones de dinámica molecular. Estos cálculos se realizan en los enlaces individuales entre átomos en diversos entornos y condiciones. La matemática es relativamente simple, pero debe calcularse miles de millones de veces para que cada enlace simule meros nanosegundos de actividad.

El popular ejemplo de "juguete" utilizado por los defensores de la computación GPU es el problema del cuerpo n .

Lo que estas cosas tienen en común es que son vergonzosamente paralelas . Es decir, el problema puede descomponerse en una pequeña cantidad de cálculos discretos que se realizan muchas veces en un conjunto de datos grande. Ese es el tipo de cálculo en el que la GPU es buena.

Los cálculos complejos que dependen de los resultados de cálculos anteriores no son adecuados para la GPU.

La transcodificación de video y audio es un gran ejemplo. Es la conversión de un formato de archivo a otro. Un ejemplo es MPEG-2 a H.264.

_{Tenga en cuenta que la transcodificación de video no está relacionada con los gráficos 3D. No puede codificar un video usando un sombreador de vértices y píxeles.}

La minería de Bitcoins usando una GPU se ha vuelto muy popular.

... sistema de efectivo electrónico de igual a igual. La creación y transferencia de Bitcoin se basa en un protocolo criptográfico de código abierto y no es administrado por ninguna autoridad central. Cada bitcoin se subdivide en ocho decimales, formando 100 millones de unidades más pequeñas llamadas satoshis. Los bitcoins se pueden transferir a través de una computadora o teléfono inteligente sin una institución financiera intermedia.

El procesamiento de las transacciones de bitcoin está asegurado por servidores llamados mineros de Bitcoin. Estos servidores se comunican a través de una red basada en Internet y confirman las transacciones agregándolas a un libro mayor que se actualiza y archiva periódicamente. Además de archivar transacciones, cada nueva actualización del libro mayor crea algunos bitcoins recientemente acuñados ...

Otra aplicación está en los mercados financieros para el comercio en tiempo real utilizando modelos como Black-Scholes .

... Un requisito clave para utilizar opciones es calcular su valor razonable. Encontrar formas de resolver eficientemente este problema de fijación de precios ha sido un campo de investigación activo durante más de treinta años, y continúa siendo un foco de la ingeniería financiera moderna. A medida que se aplica más cálculo a los problemas relacionados con las finanzas, es cada vez más importante encontrar formas eficientes de implementar estos algoritmos en arquitecturas modernas.

Este capítulo describe cómo se puede fijar el precio de las opciones de manera eficiente utilizando la GPU. Realizamos nuestras evaluaciones utilizando dos modelos de precios diferentes: el modelo Black-Scholes y los modelos de celosía. Ambos enfoques se corresponden bien con la GPU, y ambos son sustancialmente más rápidos en la GPU que en las CPU modernas. Aunque ambos también tienen asignaciones directas a la GPU, la implementación de modelos de red requiere un trabajo adicional debido a las interdependencias en los cálculos ...

El juego de la vida de Conway es un buen ejemplo académico.

... El universo del Juego de la Vida es una cuadrícula ortogonal bidimensional infinita de celdas cuadradas, cada una de las cuales se encuentra en uno de los dos estados posibles, vivo o muerto. Cada celda interactúa con sus ocho vecinos, que son las celdas que están adyacentes horizontal, vertical o diagonalmente. En cada paso en el tiempo, ocurren las siguientes transiciones:

1. Cualquier célula viva con menos de dos vecinos vivos muere, como si fuera causada por una subpoblación.
2. Cualquier célula viva con dos o tres vecinos vivos vive hasta la próxima generación.
3. Cualquier célula viva con más de tres vecinos vivos muere, como por hacinamiento.
4. Cualquier célula muerta con exactamente tres vecinos vivos se convierte en una célula viva, como por reproducción.

El patrón inicial constituye la semilla del sistema. La primera generación se crea aplicando las reglas anteriores simultáneamente a cada célula de la semilla: los nacimientos y las muertes ocurren simultáneamente, y el momento discreto en el que esto sucede a veces se llama tic (en otras palabras, cada generación es una función pura de uno anterior). Las reglas continúan aplicándose repetidamente para crear más generaciones ...

Problemas que requieren muchas matemáticas que se pueden hacer al mismo tiempo. Donde solía trabajar, queríamos jugar con GPU para sumar / restar / multiplicar 2 matrices para resolver la corrilación genética. La primera vez que oí hablar de las GPU fue que estaban siendo utilizadas por una casa de software financiera para hacer algunos de sus modelos (monte carlo, etc.). Sería útil para descifrar códigos.

Las GPU probablemente no le ayudarán mucho con sus problemas de programación más regulares, donde un par de núcleos de CPU son suficientes porque la mayoría de los programas regulares solo necesitan ejecutar algunos procesos concurrentes. (Podría ser diferente con la memoria / disco que es mucho más rápido de lo que tenemos actualmente)

Tal vez estoy siendo muy específico en computación matemática / ciencia / ingeniería, pero uno que viene a la mente es el algoritmo FFT.

He visto este punto de referencia de FFT antes, y aunque tiene algunos años, creo que fue bien hecho por lo que es: http://www.sharcnet.ca/~merz/CUDA_benchFFT