¿Cuál es la mejor solución para un problema embarazosamente paralelo?

Question

Disculpe la vaga pregunta por tema, pero estoy trabajando en algunas rutinas académicas de procesamiento de video. Los algoritmos están escritos en MATLAB, y aunque está bien para fines de desarrollo, procesó un video a aproximadamente 60spf, o alrededor de .0166 fps. Huelga decir que esto no será suficiente para demostraciones y cosas así, así que mi trabajo de verano es convertir la rutina en algo que funcionará drásticamente más rápido.

He reescrito la parte más lenta del código para CUDA, la solución GPGPU de nvidia. Sin embargo, también hay una gran porción del código que parece estar mejor hecho en la CPU, ya que es relativamente serial. El problema es que la máquina que me dieron tiene 2 procesadores Xeon, con 8 núcleos lógicos en total, y parece una pena estrangular el código de la GPU al codificar solo para un solo núcleo. El proceso de conversión de video es funcional porque cada cuadro no depende de otros marcos, así que pensé que algún tipo de cola/flujo asíncrono sería lo mejor.

Aquí está mi pregunta: ¿cuál sería la mejor manera de lograr este tipo de paralelismo con la mejor relación de esfuerzo para acelerar el rendimiento?

Algunas de las soluciones que he analizado son OpenMP, .net TPL y simplemente pthreads simples.

Solo tengo una exposición básica a la programación asíncrona, así que prefiero usar una biblioteca o algo así en lugar de perder el tiempo con mutexes y barreras y dispararme en el pie varias veces. No me importa aprender, porque ese es uno de mis objetivos para este verano, pero al mismo tiempo, el paralelismo es difícil. Sin embargo, si la diferencia de velocidad es realmente notable, estoy dispuesto a sacarme el pelo por un par de semanas. : P

Gracias de antemano.

Answer 1

Si maximizar tu esfuerzo es tu objetivo, recomendaría mirar el TPL en .NET. Esta es probablemente la forma más simple de implementar esto. Dependiendo de lo que esté haciendo su código, puede formar una tubería o simplemente usar Parallel.For (o ForEach) en cada "marco".

Dicho esto, si usted quiere meter a código nativo, no administrado, una buena opción podría ser Parallel Patterns Library o Intel's Threading Building Blocks Microsoft de nuevo. Ambos tienen construcciones similares al nuevo TPL, especialmente para el paralelismo de datos, y harían esto bastante fácil de paralelizar, siempre y cuando "cada cuadro no dependa de otros marcos" siga siendo cierto.

Answer 2

Mi consejo sería abordar esto paso a paso.

1. Primero, demuestre que tiene una implementación funcional que no es MATLAB. Esto no es trivial y, francamente, creo que debes planear gastar el 100% de tus ciclos cerebrales para obtener la corrección antes de pensar en el rendimiento.

2. Particione su solución: demuestre que puede tomar la rutina que cree que está desacoplada del resto de la implementación y aislarla sintácticamente del resto del código. Por ejemplo, si estuvieras hablando de un rastreador de rayos, podrías tomar la matemática que resulta de un punto de vista único al disparar un rayo a través de un solo píxel hacia el entorno común. Esto tampoco es trivial, ya que requerirá que piense sobre lo que es realmente común (por ejemplo, la geometría del entorno, los mapas de textura, etc.) y lo que es específico de una situación única (por ejemplo, un rayo de ojo a píxel) . El perfil de rendimiento es tu amigo aquí.

3. Identifique la sintaxis de las bibliotecas o marcos que le interesen que se necesitarán para crear subprocesos/procesos en paralelo, ejecutarlos y unir sus resultados después de la finalización. Nota: deberá tener una exclusión mutua en los datos compartidos, etc. Por ejemplo, en el mundo de Java, esto sería java.util.concurrency.

4. Intente crear dos (solo dos) hilos para dividir su trabajo en dos. Escriba puntos de referencia que le permitan medir su solución inicial, la solución para N = 2 hilos y perfilar el infierno de los resultados.

5. Solo entonces debería pensar incluso en una mayor paralelización.

Si usted sigue los pasos como estos, usted (a) tener éxito en su tarea actual (puerto de MATLAB), (b) tienen algo que funciona para algunos parámetros de rendimiento conocidos y (c) tener una clara camino a seguir si desea aprovechar aún más las oportunidades de parallización.