GPGPU y Algoritmos Genéticos

elkaoD #1 Nov '11

No sé por qué siempre que abro hilo en este foro es para poner dudas rarísimas xD

No sé si conocéis "Evolution of Mona Lisa" (original C#, online). Utiliza un algoritmo genético para generar una imagen a partir de polígonos sobrepuestos que van mutando, intentando parecerse a una imagen rasterizada de entrada.

Se me ha ocurrido hacer exactamente lo mismo utilizando GPGPU para aumentar la velocidad. El problema es que nunca he tocado GPU para programar fuera de gráficos y tengo algunas dudas que a lo mejor si alguien ha toqueteado me podría resolver.

La historia es que a priori se me ocurren dos formas de hacerlo. La primera sería usar la pipeline de la tarjeta gráfica para renderizar los polígonos (usando la CPU para generar y mandar los polígonos) y luego, mediante un shader y multitexturas, "exploitar" la GPU para que realice los cáculos de la función de fitness (anglicismos everywhere), efectivamente agilizando el proceso.

La segunda opción sería utilizar algún tipo de programación basada en GPGPU (OpenCL, CUDA) para que sea la propia GPU la que haga las mutaciones, por lo que podría haber un montón de núcleos en la GPU trabajando en paralelo tanto en la mutacion como en la función de fitness. Mi GPU tiene 336 cores, así que es posible que esta opción sea la correcta para agilizar de verdad.

Del primer enfoque me gusta que se utilice la CPU también porque efectivamente los cálculos son menos costosos en CPU y además mientras puede trabajar la GPU en los cálculos costosos (el cálculo de la función de fitness.) El problema de este enfoque es que obviamente pierdo la opción de usar los 336 núcleos de la GPU para las mutaciones y por tanto me limito a una mutación por frame GPU.

Del segundo enfoque es obvio que me gusta la paralelización, pero se me presenta un problema: no creo que desde OpenCL (¿quizá desde CUDA sí? no creo) permita usar la pipeline de la gráfica para renderizar los polígonos, por lo que me quedo sin poder utilizar efectivamente los cores en paralelo y vuelvo al caso 1. Podría utilizar OpenCL para las mutaciones, pero estoy obligado a hacer la función de fitness usando el método de los shaders (al fin y al cabo estoy gastando 1 frame por pelotas al renderizar con la GPU), además que probablemente obtenga más rendimiento usando la CPU en paralelo con la GPU (es decir, usando el método 1 sin GPGPU.) No sólo eso: ni siquiera sé si puedo usar CUDA y renderizar a la vez sin usar carísimas llamadas a cargas y descargas de shaders en cada frame.

Si alguien ha trabajado con esto alguna vez, ¿hay alguna forma de usar una solución mixta que se me escapa? ¿Me jodo y pruebo ambas a ver cuál da más rendimiento? A mí me da la impresión de que el segundo método agilizaría igualmente.

r2d2rigo #2 Nov '11 Inocente

El primero te va a dar un rendimiento penoso, aparte que si lo que quieres es number crunching a lo basto, no hay una manera eficiente de obtener los resultados de vuelta desde el driver grafico (bueno, si, con un rendertarget, pero luego tienes que reinterpretar el valor de los pixeles en cpu).

TL;DR: yo encasquetaria todo el trabajo a CUDA y si hace falta lanzaria entre medias algun frame de dibujado segun vas obteniendo valores de vuelta.

1 respuesta

elkaoD #3 Nov '11

#2 entonces, ¿propones realizar el rasterizado en CUDA también? ¿Realmente merece la pena? Recuerda que de alguna forma hay que dibujar cada conjunto de polígonos para evaluar la función de fitness. Esto es necesario hacerlo para toda mutación y por tanto "necesito" el pipeline original.

Por cierto, subestimas el primer método. Si no me equivoco, si renderizas sobre un FBO y este FBO lo pasas con multitexturado junto a la imagen a comparar, sólo hay que usar un shader que pinte la diferencia entre ambas texturas. Esta nueva textura se guarda en otro FBO distinto. Luego renderizas ese nuevo FBO sobre otro FBO que evalúe la función sobre un número limitado de fragmentos (el mínimo que permita la textura, sólo es necesario 1.) Vamos que no hay que interpretar nada más que un resultado de vuelta. El único trabajo que no realiza la GPU entonces es el de mutación, que en realidad es lo más rápido.

El gran problema de esto es que pierdes paralelización por doquier (1 mutación = 1 frame, por mucho que paralelices la función de fitness), pero no se me ocurre como implantarlo en CUDA sin comerme el pipeline de renderizado (y tener que hacerlo a mano entonces.)

A lo mejor no es mala idea hacerlo en CUDA, no debe ser muy dificil hacer un raster 2D simplón en realidad.

skv #4 Nov '11

+1 para CUDA, conozco el programa aunque no he visto el código fuente, pero en general los algoritmos genéticos tienen una representación paralela bastante natural. En general CUDA te quita bastante trabajo de la paralelización, simplemente tienes que representar tu problema con una estructura de grid y ver que tipo de información quieres que compartan los threads para guardarla en un tipo de memoria u otro (hay como 4 tipos si no recuerdo mal).

1 respuesta

elkaoD #5 Nov '11

#4 vale, ¿pero cómo soluciono el problema?

El algoritmo tiene 3 fases:

1. Creación de las mutaciones.
Simple, la puede realizar la CPU mismo. También la puede realizar CUDA paralelizando sobre cada ejemplar.
2. Raster de los ejemplares mutados.
Esta es la que podría usar OpenGL a secas. No sé si CUDA soporta trabajar en paralelo a OpenGL y utilizar sus buffers (sin andar cargando y descargando el programa/shaders), si no es así, tendría que crear el motor de raster yo mismo en CUDA.
3. Comparación de los ejemplares con el modelo.
Con un shader GLSL puedo paralelizar el cómputo de diferencias. Con CUDA también, usando el mísmo método (paralelizar en píxel.) Realizar el cómputo estadístico a partir de la diferencia es mucho más fácil en CUDA que en OpenGL (por la memoria compartida.)

Cada una tiene sus ventajas e inconvenientes. Vale que CUDA me puede dar mucho juego con la paralelización, pero es que OpenGL ya se preocupa de rasterizar todo y los shaders me dan el mismo nivel de paralelización a nivel de píxel, escalado automático (y probablemente menos trabajo en programación.) Mi gran duda es si podría usarlos en conjunto y quedarme con lo bueno de ambos más o menos sin perder mucho rendimiento, o me tengo que quedar con un método y comerme sus defectos (con CUDA programar el raster, con OpenGL pérdida de paralelización en las mutaciones que la verdad no sé si es TAN grave, la CPU puede calcularlas mientras la GPU hace el raster y comparación de ejemplares.)

Usuarios habituales