tipos - Procesamiento de imágenes multiproceso en C++

lenguaje c

Question

Estoy trabajando en un programa que manipula imágenes de diferentes tamaños. Muchas de estas manipulaciones leen datos de píxeles de una entrada y escriben en una salida separada (por ejemplo, desenfoque). Esto se hace en una base por píxel.

Dichos mapas de imagen son muy estresantes para la CPU. Me gustaría utilizar el multihilo para acelerar las cosas. ¿Cómo haría esto? Estaba pensando en crear un hilo por fila de píxeles.

Tengo varios requisitos:

• El tamaño del ejecutable debe ser minimizado. En otras palabras, no puedo usar bibliotecas masivas. ¿Cuál es la biblioteca de subprocesos portátil más liviana para C / C ++?
• El tamaño del ejecutable debe ser minimizado. Estaba pensando en tener una función para EachRow (fp *) que ejecuta un hilo para cada fila, o incluso un forEachPixel (fp *) donde fp opera en un solo píxel en su propio hilo. ¿Cuál es el mejor?
  • ¿Debo usar funciones normales o funtores o funciones o algunas funciones lambda o ... algo más?
  • Algunas operaciones usan optimizaciones que requieren información del píxel anterior procesado. Esto hace que EchoRow sea favorable. ¿Sería mejor usar ForEachPixel incluso considerando esto?
• ¿Tendría que bloquear mis matrices de solo lectura y de solo escritura?
  • La entrada solo se lee, pero muchas operaciones requieren la entrada de más de un píxel en la matriz.
  • La salida solo se escribe una vez por píxel.
• La velocidad también es importante (por supuesto), pero optimizar el tamaño del ejecutable tiene prioridad.

Gracias.

Más información sobre este tema para los curiosos: Bibliotecas de paralelización C ++: OpenMP vs. Thread Building Blocks

Answer 1

¿Puedo preguntar en qué plataforma estás escribiendo esto? Supongo que porque el tamaño del ejecutable es un problema al que no se está apuntando en una máquina de escritorio. ¿En qué caso la plataforma tiene múltiples núcleos o hyperthreaded? De lo contrario, agregar subprocesos a su aplicación podría tener el efecto opuesto y ralentizarlo ...

Answer 2

¿Tal vez escribir su propia pequeña biblioteca que implementa unas pocas funciones de enhebrado estándar usando #ifdef para cada plataforma? Realmente no hay mucho, y eso reduciría el tamaño del ejecutable mucho más que cualquier biblioteca que puedas usar.

Actualización: Y para la distribución del trabajo: divida su imagen en pedazos y dele a cada hilo una pieza. Entonces, cuando termina la pieza, ya está hecho. De esta forma evitará implementar colas de trabajos que aumentarán aún más el tamaño de su ejecutable.

Answer 3

Como una pequeña idea de campo izquierdo ...

¿En qué sistemas estás ejecutando esto? ¿Has pensado en usar la GPU en tu PC?

Nvidia tiene las API de CUDA para este tipo de cosas

Answer 4

Hay otra opción de usar el ensamblaje para la optimización. Ahora, un proyecto interesante para la generación dinámica de código es softwire (que data de hace un tiempo, aquí está el sitio original del proyecto). Ha sido desarrollado por Nick Capens y creció hasta convertirse en swiftshader comercialmente disponible. Pero el spin-off del softwire original todavía está disponible en gna.org.

Esto podría servir como una introducción a su solución.

Personalmente, no creo que pueda obtener un rendimiento significativo al utilizar varios hilos para su problema.

Answer 5

No creo que quieras tener un hilo por fila. Puede haber muchas filas y gastará muchos recursos de memoria / CPU tan solo ejecutando / destruyendo los hilos y para que la CPU cambie de uno a otro. Además, si tiene procesadores P con núcleo C, probablemente no obtendrá muchas ganancias con más hilos C * P.

Le aconsejo que use un número definido de subprocesos de cliente, por ejemplo N subprocesos, y utilice el subproceso principal de su aplicación para distribuir las filas a cada subproceso, o simplemente pueden obtener instrucciones de una "cola de trabajos". Cuando un hilo ha terminado con una fila, puede verificar en esta cola otra fila para hacer.

En cuanto a las bibliotecas, puede usar boost :: thread, que es bastante portátil y no demasiado pesado.

Answer 6

Recomendaría boost::thread y boost::gil (genérico de la imagen de libray). Como hay muchas plantillas involucradas, no estoy seguro de si el tamaño del código seguirá siendo aceptable para usted. Pero es parte del impulso, por lo que probablemente valga la pena echarle un vistazo.

Answer 7

Si su compilador es compatible con OpenMP (sé que VC ++ 8.0 y 9.0 do, al igual que gcc), puede hacer que esto sea mucho más fácil de hacer.

No solo desea crear muchos hilos: hay un punto de disminución de retornos en el que agregar nuevos subprocesos ralentiza las cosas a medida que comienza a obtener más y más conmutadores de contexto. En algún momento, usar demasiados hilos puede hacer que la versión paralela sea más lenta que usar un algoritmo lineal. El número óptimo de subprocesos es una función del número de cpus / núcleos disponibles, y del porcentaje de tiempo que cada subproceso permanece bloqueado en cosas como E / S. Eche un vistazo a este artículo de Herb Sutter para una discusión sobre ganancias de rendimiento paralelas.

OpenMP le permite adaptar fácilmente la cantidad de subprocesos creados a la cantidad de CPU disponibles. Su uso (especialmente en casos de procesamiento de datos) a menudo implica simplemente poner #pragma omp s en el código existente, y dejar que el compilador maneje la creación de hilos y la sincronización.

En general, siempre que los datos no cambien, no tendrá que bloquear los datos de solo lectura. Si puede estar seguro de que cada espacio de píxel solo se escribirá una vez y puede garantizar que toda la escritura se haya completado antes de comenzar a leer el resultado, tampoco tendrá que bloquearlo.

Para OpenMP, no hay necesidad de hacer nada especial en cuanto a funtores / objetos de función. Escríbelo de cualquier forma que tenga más sentido para ti. Aquí hay un ejemplo de procesamiento de imágenes de Intel (convierte rgb a escala de grises):

#pragma omp parallel for
for (i=0; i < numPixels; i++)
{
   pGrayScaleBitmap[i] = (unsigned BYTE)
       (pRGBBitmap[i].red * 0.299 +
        pRGBBitmap[i].green * 0.587 +
        pRGBBitmap[i].blue * 0.114);
}

Esto se divide automáticamente en tantos subprocesos como CPU y asigna una sección de la matriz a cada subproceso.

Answer 8

Un hilo por fila de píxeles es una locura, mejor tener alrededor de n-1 a 2n hilos (para n cpu), y hacer que cada uno de los bucles recupere una unidad de trabajo (puede ser una fila u otro tipo de partición)

en modo unix, usar pthreads es simple y liviano.

Answer 9

Creo que independientemente del modelo de threading que elijas (boost, pthread, threads nativos, etc.). Creo que debería considerar un grupo de subprocesos en lugar de un subproceso por fila. Los subprocesos de un grupo de subprocesos son muy baratos para "comenzar", ya que ya se crearon en lo que respecta al sistema operativo, solo se trata de darle algo que hacer.

Básicamente, podrías decir 4 hilos en tu grupo. Luego, en forma de serie, para cada píxel, indique el siguiente subproceso en el grupo de subprocesos para procesar el píxel. De esta manera, está procesando efectivamente no más de 4 píxeles a la vez. Puede hacer que el tamaño del grupo se base en la preferencia del usuario o en la cantidad de CPU que informa el sistema.

Esta es, de lejos, la forma más sencilla en mi humilde opinión de agregar subprocesos a una tarea SIMD.

Answer 10

Para optimizar las transformaciones de imagen simples, es mucho mejor usar matemáticas vectoriales SIMD que tratar de hacer múltiples hilos de su programa.

Answer 11

¡No se embarque en el enhebrado a la ligera! Las condiciones de carrera pueden ser un gran dolor en el culo para descubrir. ¡Especialmente si no tienes mucha experiencia con hilos! (Has sido advertido: ¡Aquí hay dragones! ¡Grandes dragones peludos, no deterministas, imposibles de reproducir con seguridad!)

¿Sabes qué punto muerto es? ¿Qué tal Livelock?

Eso dijo ...

Como ckarmann y otros ya han sugerido: utilizar un modelo de cola de trabajo. Un hilo por núcleo de CPU. Divida el trabajo en N pedazos. Haga los pedazos razonablemente grandes, como muchas filas. A medida que cada hilo se libera, atrapa el siguiente trozo de trabajo fuera de la cola.

En la versión IDEAL más simple, tiene N núcleos, N subprocesos y N subparte del problema con cada subproceso que sabe desde el principio exactamente qué es lo que va a hacer.

Pero eso no suele ocurrir en la práctica debido a la sobrecarga de iniciar / detener los hilos. Realmente desea que los hilos ya se generen y estén esperando la acción. (Por ejemplo, a través de un semáforo)

El modelo de cola de trabajo en sí es bastante poderoso. Le permite paralelizar cosas como la clasificación rápida, que normalmente no se paraleliza en N subprocesos / núcleos con gracia.

¿Más hilos que núcleos? Solo estás perdiendo el control. Cada hilo tiene sobrecarga. Incluso en # hilos = # núcleos, nunca logrará un factor de aceleración Nx perfecto.

¡Un hilo por fila sería muy ineficiente! Un hilo por píxel? Ni siquiera quiero pensar en eso. (Ese enfoque por píxel tiene mucho más sentido cuando se juega con unidades procesadoras vectorizadas que tenían en los viejos Crays. ¡Pero no con hilos!)

Bibliotecas? ¿Cuál es tu plataforma? Bajo Unix / Linux / g ++ sugeriría pthreads y semáforos. (Pthreads también está disponible en Windows con una capa de compatibilidad de Microsoft. Pero, ¡realmente no lo creo! Cygwin podría ser una mejor opción allí).

En Unix / Linux, hombre :

* pthread_create, pthread_detach.
* pthread_mutexattr_init, pthread_mutexattr_settype, pthread_mutex_init,
* pthread_mutexattr_destroy, pthread_mutex_destroy, pthread_mutex_lock,
* pthread_mutex_trylock, pthread_mutex_unlock, pthread_mutex_timedlock.
* sem_init, sem_destroy, sem_post, sem_wait, sem_trywait, sem_timedwait.

Algunas personas prefieren las variables de condición de pthreads. Pero siempre preferí los semáforos POSIX 1003.1b. Manejan la situación en la que desea señalar otro hilo ANTES de que comience a esperar algo mejor. O donde otro hilo se señala varias veces.

Ah, y hazte un favor: envuelve tus conversaciones hilo / mutex / semáforo pthread en un par de clases de C ++. ¡Eso simplificará mucho las cosas!

¿Tendría que bloquear mis matrices de solo lectura y de solo escritura?

Depende de su hardware y software precisos. Por lo general, las matrices de solo lectura se pueden compartir libremente entre subprocesos. Pero hay casos en que eso no es así.

Escribir es muy parecido. Por lo general, siempre y cuando solo un hilo esté escribiendo en cada punto de memoria en particular, usted está bien. ¡Pero hay casos en que eso no es así!

Escribir es más problemático que leer ya que puedes entrar en estas situaciones raras. La memoria a menudo se escribe como palabras, no como bytes. Cuando un hilo escribe una parte de la palabra y otro escribe una parte diferente, dependiendo del momento exacto de qué hilo hace qué y cuándo (por ejemplo, no determinístico), ¡puede obtener resultados muy impredecibles!

Me arriesgaría: dale a cada hilo su propia copia de las áreas de lectura y escritura. Después de que terminen, copie los datos nuevamente. Todo bajo mutex, por supuesto.

A menos que esté hablando de gigabytes de datos, las memorias de memoria son muy rápidas. Ese par de microsegundos de tiempo de rendimiento no vale la pena la pesadilla de depuración.

Si tuviera que compartir un área de datos común entre hilos utilizando mutexes, las ineficiencias mutex de colisión / espera se acumularían y devastarían su eficiencia.

Mire, los límites de datos limpios son la esencia del buen código multiproceso. Cuando tus límites no están claros, es cuando te metes en problemas.

Del mismo modo, es esencial mantener todo en el límite mutexed! ¡Y para mantener cortas las áreas mutexed!

Intente evitar bloquear más de un mutex al mismo tiempo. Si bloquea más de un mutex, siempre enciérrelos en el mismo orden.

Siempre que sea posible, use el método de ERROR-CHECKING o RECUTSIVE mutexes. Los mutexes RÁPIDOS solo piden problemas, con muy poca ganancia de velocidad real (medida).

Si te metes en una situación de punto muerto, ejecútalo en gdb, presiona ctrl-c, visita cada hilo y marca de retroceso. Puede encontrar el problema bastante rápido de esa manera. (Livelock es mucho más difícil!)

Una última sugerencia: compilarla de un solo hilo, luego comenzar a optimizar. En un sistema de un solo núcleo, es posible que gane más velocidad con cosas como foo [i ++] = bar ==> * (foo ++) = barra que con el subprocesamiento.

Adición: ¿Qué dije acerca de mantener las áreas mutexed corta arriba? Considere dos hilos: (Dado un objeto mutex compartido global de una clase Mutex).

/*ThreadA:*/ while(1){  mutex.lock();  printf("a/n");  usleep(100000); mutex.unlock(); }
/*ThreadB:*/ while(1){  mutex.lock();  printf("b/n");  usleep(100000); mutex.unlock(); }

¿Lo que sucederá?

Bajo mi versión de Linux, un hilo se ejecutará continuamente y el otro morirá de hambre. Muy raramente cambiarán de lugar cuando se produce un intercambio de contexto entre mutex.unlock () y mutex.lock ().

Adición: En su caso, es poco probable que esto sea un problema. Pero con otros problemas, uno puede no saber de antemano cuánto tardará un pedazo de trabajo particular en completarse. Romper un problema en 100 partes (en lugar de 4 partes) y usar una cola de trabajo para dividirlo en 4 núcleos alivia tales discrepancias.

Si un trozo de trabajo tarda 5 veces más en completarse que otro, bueno, al final todo se nivela. Aunque con demasiados trozos, la sobrecarga de adquirir nuevos trozos de trabajo crea retrasos notables. Es un acto de equilibrio específico del problema.

Answer 12

Creo que el marco de mapa / reducir será lo ideal para usar en esta situación. Puede usar la transmisión Hadoop para usar su aplicación C ++ existente.

Simplemente implemente el mapa y reduzca los trabajos.

Como dijo, puede usar manipulaciones a nivel de fila como una tarea de mapa y combinar las manipulaciones de nivel de fila a la imagen final en la tarea de reducir.

Espero que esto sea útil.

Answer 13

Tu compilador no es compatible con OpenMP. Otra opción es utilizar un enfoque de biblioteca, ya que están disponibles los bloques de construcción Threading de Microsoft y Microsoft Concurrency Runtime (VS 2010).

También hay un conjunto de interfaces denominadas Parallel Pattern Library, que son compatibles con ambas bibliotecas y en estas tienen una llamada a la biblioteca parallel_for con plantilla. Entonces, en lugar de:

#pragma omp parallel for 
for (i=0; i < numPixels; i++) 
{ ...} 

usted escribiría:

parallel_for(0,numPixels,1,ToGrayScale());

donde ToGrayScale es un functor o puntero para funcionar. (Tenga en cuenta que si su compilador admite expresiones lambda que probablemente no pueda alinear el funtor como una expresión lambda).

parallel_for(0,numPixels,1,[&](int i)
{  
   pGrayScaleBitmap[i] = (unsigned BYTE)  
       (pRGBBitmap[i].red * 0.299 +  
        pRGBBitmap[i].green * 0.587 +  
        pRGBBitmap[i].blue * 0.114);  
});

-Almiar

Answer 14

Es muy posible que el cuello de botella no sea la CPU, sino el ancho de banda de la memoria, por lo que el multi-threading NO ayudará mucho. Intente minimizar el acceso a la memoria y trabaje en bloques de memoria limitados, para poder almacenar más datos. Tuve un problema similar hace un tiempo y decidí optimizar mi código para usar las instrucciones de SSE. ¡El aumento de velocidad fue casi 4 veces por cada hilo!

Answer 15

Consulte la guía de creación de una red de procesamiento de imágenes en MSDN, que explica cómo utilizar Parallel Patterns Library para componer un canal de procesamiento de imágenes concurrente.

También sugiero Boost.GIL , que genera código altamente eficiente. Para un simple ejemplo de subprocesos múltiples, consulte gil_threaded por Victor Bogado. Una red de procesamiento de imágenes que utiliza Dataflow.Signals y Boost.GIL también explica un modelo de flujo de datos de interés.

Answer 16

También podría utilizar bibliotecas como IPP o Cassandra Vision C ++ API, que en su mayoría son mucho más optimizadas que su propio código.