Generando imágenes de mandelbrot en c ++ usando multiproceso. No hay aceleración?

Así que publiqué una pregunta similar a esto anteriormente, pero no publiqué suficiente código para obtener la ayuda que necesitaba. Incluso si volví y agregué ese código ahora, no creo que se notaría porque la pregunta es antigua y “contestada”. Así que aquí está mi problema:

Estoy tratando de generar una sección del fractal de mandelbrot. Puedo generarlo bien, pero cuando agrego más núcleos, no importa el tamaño del problema, los subprocesos adicionales no generan aceleración. Soy completamente nuevo en el multihilo y probablemente sea algo pequeño que me estoy perdiendo. De todos modos, aquí están las funciones que generan el fractal:

void mandelbrot_all(std::vector<std::vector>& pixels, int X, int Y, int numThreads) { using namespace std; vector threads (numThreads); int rowsPerThread = Y/numThreads; mutex m; for(int i=0; i<numThreads; i++) { threads[i] = thread ([&](){ vector row; for(int j=(i-1)*rowsPerThread; j<i*rowsPerThread; j++) { row = mandelbrot_row(j, X, Y); { lock_guard lock(m); pixels[j] = row; } } }); } for(int i=0; i<numThreads; i++) { threads[i].join(); } } std::vector mandelbrot_row(int rowNum, int topX, int topY) { std::vector row (topX); for(int i=0; i<topX; i++) { row[i] = mandelbrotOne(i, rowNum, topX, topY); } return row; } int mandelbrotOne(int currX, int currY, int X, int Y) { //code adapted from http://en.wikipedia.org/wiki/Mandelbrot_set double x0 = convert(X, currX, true); double y0 = convert(Y, currY, false); double x = 0.0; double y = 0.0; double xtemp; int iteration = 0; int max_iteration = 255; while ( x*x + y*y < 2*2 && iteration < max_iteration) { xtemp = x*x - y*y + x0; y = 2*x*y + y0; x = xtemp; ++iteration; } return iteration; } 

A mandelbrot_all se le pasa un vector para contener los píxeles, la X y la Y máximas del vector y el número de subprocesos a usar, que se toma de la línea de comandos cuando se ejecuta el progtwig. Intenta dividir el trabajo por filas entre varios hilos. Desafortunadamente, parece que incluso si eso es lo que está haciendo, no lo está haciendo más rápido. Si necesita más detalles, no dude en preguntar y haré todo lo posible para proporcionarles.

Gracias de antemano por la ayuda.

Edición: vectores reservados por adelantado Edición 2: ejecuté este código con un tamaño de problema de 9600×7200 en una computadora portátil de cuatro núcleos. Tomó un promedio de 36590000 ciclos por un hilo (más de 5 ejecuciones) y 55142000 ciclos por cuatro hilos.

Su código puede parecer que realiza un parallel processing, pero en la práctica no lo hace. Básicamente, está gastando su tiempo copiando datos y haciendo colas para los accesos de asignador de memoria.

Además, está utilizando el índice de bucle i no protegido como si no hubiera nada en él, lo que alimentará los subprocesos de su trabajador con basura aleatoria en lugar de hermosos cortes de la imagen.

Como de costumbre, C ++ está ocultando estos tristes hechos bajo una gruesa capa de azúcar sintáctica.

Pero el mayor defecto de su código es el algoritmo mismo, como puede ver si lee más adelante.

Como este ejemplo me parece un caso de libro de texto de parallel processing y nunca vi un análisis “educativo” de él, lo intentaré.

Análisis funcional

Desea utilizar todos los núcleos de la CPU para crujir los píxeles del conjunto de Mandelbrot. Este es un caso perfecto de cómputo paralelizable, ya que cada cómputo de píxeles se puede hacer de manera independiente.

Básicamente, si tiene N núcleos en su máquina, debe tener exactamente un hilo por núcleo haciendo 1 / N del procesamiento.

Desafortunadamente, dividir los datos de entrada para que cada procesador termine haciendo 1 / N del procesamiento necesario no es tan obvio como podría parecer.

Un píxel dado puede tomar de 0 a 255 iteraciones para calcular. Los píxeles “negros” son 255 veces más costosos que los “blancos”.

Por lo tanto, si simplemente divide su imagen en N superficies iguales, es probable que todos los procesadores pasen por las áreas “blancas”, excepto por una que se arrastre por un área “negra”. Como resultado, el tiempo de cálculo del área más lento dominará y la paralelización no ganará prácticamente nada.

En casos reales, esto no será tan dramático, pero seguirá siendo una gran pérdida de potencia informática.

Balanceo de carga

Para equilibrar mejor la carga, es más eficiente dividir la imagen en bits mucho más pequeños y hacer que cada subproceso de trabajo seleccione y calcule el siguiente bit disponible tan pronto como termine con el anterior. De esa manera, un trabajador que procesa trozos “blancos” terminará su trabajo y comenzará a elegir trozos “negros” para ayudar a sus hermanos menos afortunados.

Lo ideal es que los trozos se clasifiquen según la complejidad decreciente, para evitar agregar el costo lineal de un trozo grande al tiempo total de computación.

Desafortunadamente, debido a la naturaleza caótica del conjunto de Mandlebrot, no hay una forma práctica de predecir el tiempo de cálculo de un área determinada.

Si decidimos que los trozos serán cortes horizontales de la imagen, clasificarlos en orden natural es claramente subóptimo. Si esa área en particular es un tipo de gradiente “blanco a negro”, las líneas más costosas se agruparán al final de la lista de fragmentos y terminará calculando los bits más costosos al final, lo cual es el peor de los casos para el equilibrio de carga.

Una posible solución es mezclar los trozos en un patrón de mariposa, de modo que la probabilidad de tener un área “negra” concentrada al final sea pequeña.
Otra forma sería simplemente mezclar patrones de entrada al azar.

Aquí hay dos salidas de mi implementación de prueba de concepto:

Los trabajos se ejecutan en orden inverso (los trabajos 39 son los primeros, los trabajos 0 son los últimos). Cada línea se decodifica de la siguiente manera:

t ab: hilo n ° a en el procesador b
b : tiempo de inicio (desde el inicio del cálculo de la imagen)
e : hora final
d : duración (todos los tiempos en milisegundos)

1) 40 trabajos con pedidos de mariposas

 job 0: t 1-1 b 162 e 174 d 12 // the 4 tasks finish within 5 ms from each other job 1: t 0-0 b 156 e 176 d 20 // job 2: t 2-2 b 155 e 173 d 18 // job 3: t 3-3 b 154 e 174 d 20 // job 4: t 1-1 b 141 e 162 d 21 job 5: t 2-2 b 137 e 155 d 18 job 6: t 0-0 b 136 e 156 d 20 job 7: t 3-3 b 133 e 154 d 21 job 8: t 1-1 b 117 e 141 d 24 job 9: t 0-0 b 116 e 136 d 20 job 10: t 2-2 b 115 e 137 d 22 job 11: t 3-3 b 113 e 133 d 20 job 12: t 0-0 b 99 e 116 d 17 job 13: t 1-1 b 99 e 117 d 18 job 14: t 2-2 b 96 e 115 d 19 job 15: t 3-3 b 95 e 113 d 18 job 16: t 0-0 b 83 e 99 d 16 job 17: t 3-3 b 80 e 95 d 15 job 18: t 2-2 b 77 e 96 d 19 job 19: t 1-1 b 72 e 99 d 27 job 20: t 3-3 b 69 e 80 d 11 job 21: t 0-0 b 68 e 83 d 15 job 22: t 2-2 b 63 e 77 d 14 job 23: t 1-1 b 56 e 72 d 16 job 24: t 3-3 b 54 e 69 d 15 job 25: t 0-0 b 53 e 68 d 15 job 26: t 2-2 b 48 e 63 d 15 job 27: t 0-0 b 41 e 53 d 12 job 28: t 3-3 b 40 e 54 d 14 job 29: t 1-1 b 36 e 56 d 20 job 30: t 3-3 b 29 e 40 d 11 job 31: t 2-2 b 29 e 48 d 19 job 32: t 0-0 b 23 e 41 d 18 job 33: t 1-1 b 18 e 36 d 18 job 34: t 2-2 b 16 e 29 d 13 job 35: t 3-3 b 15 e 29 d 14 job 36: t 2-2 b 0 e 16 d 16 job 37: t 3-3 b 0 e 15 d 15 job 38: t 1-1 b 0 e 18 d 18 job 39: t 0-0 b 0 e 23 d 23 

Puede ver el equilibrio de carga en el trabajo cuando un subproceso que ha procesado unos pocos trabajos pequeños superará a otro que tomó más tiempo para procesar sus propios fragmentos.

2) 40 trabajos con ordenamiento lineal

 job 0: t 2-2 b 157 e 180 d 23 // last thread lags 17 ms behind first job 1: t 1-1 b 154 e 175 d 21 job 2: t 3-3 b 150 e 171 d 21 job 3: t 0-0 b 143 e 163 d 20 // 1st thread ends job 4: t 2-2 b 137 e 157 d 20 job 5: t 1-1 b 135 e 154 d 19 job 6: t 3-3 b 130 e 150 d 20 job 7: t 0-0 b 123 e 143 d 20 job 8: t 2-2 b 115 e 137 d 22 job 9: t 1-1 b 112 e 135 d 23 job 10: t 3-3 b 112 e 130 d 18 job 11: t 0-0 b 105 e 123 d 18 job 12: t 3-3 b 95 e 112 d 17 job 13: t 2-2 b 95 e 115 d 20 job 14: t 1-1 b 94 e 112 d 18 job 15: t 0-0 b 90 e 105 d 15 job 16: t 3-3 b 78 e 95 d 17 job 17: t 2-2 b 77 e 95 d 18 job 18: t 1-1 b 74 e 94 d 20 job 19: t 0-0 b 69 e 90 d 21 job 20: t 3-3 b 60 e 78 d 18 job 21: t 2-2 b 59 e 77 d 18 job 22: t 1-1 b 57 e 74 d 17 job 23: t 0-0 b 55 e 69 d 14 job 24: t 3-3 b 45 e 60 d 15 job 25: t 2-2 b 45 e 59 d 14 job 26: t 1-1 b 43 e 57 d 14 job 27: t 0-0 b 43 e 55 d 12 job 28: t 2-2 b 30 e 45 d 15 job 29: t 3-3 b 30 e 45 d 15 job 30: t 0-0 b 27 e 43 d 16 job 31: t 1-1 b 24 e 43 d 19 job 32: t 2-2 b 13 e 30 d 17 job 33: t 3-3 b 12 e 30 d 18 job 34: t 0-0 b 11 e 27 d 16 job 35: t 1-1 b 11 e 24 d 13 job 36: t 2-2 b 0 e 13 d 13 job 37: t 3-3 b 0 e 12 d 12 job 38: t 1-1 b 0 e 11 d 11 job 39: t 0-0 b 0 e 11 d 11 

Aquí, los costosos trozos tienden a agruparse al final de la cola, por lo tanto, una pérdida de rendimiento notable.

3) una ejecución con solo un trabajo por núcleo, con uno a 4 núcleos activados

 reported cores: 4 Master: start jobs 4 workers 1 job 0: t 0-0 b 410 e 590 d 180 // purely linear execution job 1: t 0-0 b 255 e 409 d 154 job 2: t 0-0 b 127 e 255 d 128 job 3: t 0-0 b 0 e 127 d 127 Master: start jobs 4 workers 2 // gain factor : 1.6 out of theoretical 2 job 0: t 1-1 b 151 e 362 d 211 job 1: t 0-0 b 147 e 323 d 176 job 2: t 0-0 b 0 e 147 d 147 job 3: t 1-1 b 0 e 151 d 151 Master: start jobs 4 workers 3 // gain factor : 1.82 out of theoretical 3 job 0: t 0-0 b 142 e 324 d 182 // 4th packet is hurting the performance badly job 1: t 2-2 b 0 e 158 d 158 job 2: t 1-1 b 0 e 160 d 160 job 3: t 0-0 b 0 e 142 d 142 Master: start jobs 4 workers 4 // gain factor : 3 out of theoretical 4 job 0: t 3-3 b 0 e 199 d 199 // finish at 199ms vs. 176 for butterfly 40, 13% loss job 1: t 1-1 b 0 e 182 d 182 // 17 ms wasted job 2: t 0-0 b 0 e 146 d 146 // 44 ms wasted job 3: t 2-2 b 0 e 150 d 150 // 49 ms wasted 

Aquí obtenemos una mejora de 3x, mientras que un mejor balanceo de carga podría haber producido un 3.5x.
Y este es un caso de prueba muy leve (puede ver que los tiempos de cálculo solo varían en un factor de aproximadamente 2, mientras que teóricamente podrían variar en un factor de 255).

En cualquier caso, si no implementa algún tipo de equilibrio de carga, todo el código shiny de multiprocesador que pueda escribir seguirá produciendo rendimientos deficientes.

Implementación

Para que los hilos funcionen sin obstáculos, deben mantenerse libres de interferencias del mundo exterior.

Una de esas interferencias es la asignación de memoria. Cada vez que asigna incluso un byte de memoria, hará cola para obtener acceso exclusivo al asignador de memoria global (y desperdiciará un poco de CPU haciendo la asignación).

Además, crear tareas de trabajo para cada cálculo de imagen es otra pérdida de tiempo y recursos. El cálculo podría usarse para mostrar el conjunto de Mandlebrot en una aplicación interactiva, por lo que es mejor que los trabajadores se creen y sincronicen de forma premanente para calcular las imágenes sucesivas.

Por último, están las copias de los datos. Si sincroniza con el progtwig principal cada vez que termine de calcular algunos puntos, nuevamente pasará una buena parte de su tiempo en la cola para obtener acceso exclusivo al área de resultados. Además, las copias inútiles de una cantidad considerable de datos afectarán aún más las actuaciones.

La solución obvia es prescindir de las copias y trabajar con los datos originales.

diseño

Debe proporcionar a sus hilos de trabajo todo lo que necesitan para trabajar sin obstáculos. Para eso necesitas:

  • Determine el número de núcleos disponibles en su sistema
  • preasignar toda la memoria necesaria
  • dé acceso a una lista de fragmentos de imágenes para cada uno de sus trabajadores
  • inicie exactamente un hilo por núcleo y déjelos correr libremente para hacer su trabajo

cola de trabajos

No hay necesidad de sofisticados no-espera o cualquier artilugio, ni tenemos que prestar especial atención a la optimización del caché.
Aquí nuevamente, el tiempo necesario para calcular los píxeles empequeñece el costo de sincronización entre subprocesos y los problemas de eficiencia de caché.

Básicamente, la cola se puede calcular como un todo al inicio de una generación de imágenes. Los trabajadores solo tendrán que leer los trabajos: nunca habrá accesos concurrentes de lectura / escritura en esta cola, por lo que los bits de código más o menos estándar para implementar las colas de trabajos serán subóptimos y demasiado complejos para el trabajo en cuestión.

Necesitamos dos puntos de sincronización:

  1. Que los trabajadores esperen un nuevo lote de trabajos.
  2. dejar que el maestro espere a que se complete la imagen

los trabajadores esperarán hasta que la longitud de la cola cambie a un valor positivo. Luego, todos se activarán y comenzarán a disminuir de forma atómica la longitud de la cola. El valor actual de la longitud de la cola les proporcionará acceso exclusivo a los datos de trabajo asociados (básicamente, un área del conjunto de Mandlebrot para calcular, con un área de bitmap asociada para almacenar los valores de iteración calculados).

El mismo mecanismo se utiliza para despedir a los trabajadores. En lugar de encontrar un nuevo lote de trabajos, los trabajadores pobres se despertarán para encontrar una orden para terminar.

el trabajador que terminará de procesar el último trabajo despertará al maestro que espera la finalización de la imagen. Esto se basará en un contador atómico de la cantidad de trabajos a procesar.

Así es como lo implementé:

 class synchro { friend class mandelbrot_calculator; mutex lock; // queue lock condition_variable work; // blocks workers waiting for jobs/termination condition_variable done; // blocks master waiting for completion int pending; // number of jobs in the queue atomic_int active; // number of unprocessed jobs bool kill; // poison pill for workers termination void synchro (void) { pending = 0; // no job in queue kill = false; // workers shall live (for now :) ) } int worker_start(void) { unique_lock waiter(lock); while (!pending && !kill) work.wait(waiter); return kill ? -1 // worker should die : --pending; // index of the job to process } void worker_done(void) { if (!--active) // atomic decrement (exclusive with other workers) done.notify_one(); // last job processed: wakeup master } void master_start(int jobs) { unique_lock waiter(lock); pending = active = jobs; work.notify_all(); // wakeup all workers to start jobs } void master_done(void) { unique_lock waiter(lock); while (active) done.wait(waiter); // wait for workers to finish } void master_kill(void) { kill = true; work.notify_all(); // wakeup all workers (to die) } }; 

Poniendo todos juntos:

 class mandelbrot_calculator { int num_cores; int num_jobs; vector workers; // worker threads vector jobs; // job queue synchro sync; // synchronization helper mandelbrot_calculator (int num_cores, int num_jobs) : num_cores(num_cores) , num_jobs (num_jobs ) { // worker thread auto worker = [&]() { for (;;) { int job = sync.worker_start(); // fetch next job if (job == -1) return; // poison pill process (jobs[job]); // we have exclusive access to this job sync.worker_done(); // signal end of picture to the master } }; jobs.resize(num_jobs, job()); // computation windows workers.resize(num_cores); for (int i = 0; i != num_cores; i++) workers[i] = thread(worker, i, i%num_cores); } ~mandelbrot_calculator() { // kill the workers sync.master_kill(); for (thread& worker : workers) worker.join(); } void compute(const viewport & vp) { // prepare worker data function butterfly_jobs; butterfly_jobs = [&](int min, int max) // computes job windows in butterfly order { if (min > max) return; jobs[min].setup(vp, max, num_jobs); if (min == max) return; jobs[max].setup(vp, min, num_jobs); int mid = (min + max) / 2; butterfly_jobs(min + 1, mid ); butterfly_jobs(mid + 1, max - 1); }; butterfly_jobs(0, num_jobs - 1); // launch workers sync.master_start(num_jobs); // wait for completion sync.master_done(); } }; 

Probando el concepto

Este código funciona bastante bien en mis 2 cores / 4 CPU Intel I3 a 3.1 GHz, comstackdo con Microsoft Dev Studio 2013.

Uso un poco del conjunto que tiene un promedio de 90 iteraciones / píxel, en una ventana de 1280×1024 píxeles.

El tiempo de cálculo es de aproximadamente 1.700 con un solo trabajador y se reduce a 0.480 con 4 trabajadores.
La ganancia máxima posible sería un factor 4. Obtengo un factor 3.5. No está mal.

Supongo que la diferencia se debe en parte a la architecture del procesador (el I3 tiene solo dos núcleos “reales”).

Manipulación del progtwigdor.

Mi progtwig obliga a los subprocesos a ejecutarse en un núcleo cada uno (utilizando MSDN SetThreadAffinityMask ).
Si se deja libre al progtwigdor para asignar las tareas, el factor de ganancia cae de 3,5 a 3,2.

Esto es significativo, pero aún así, el progtwigdor de Win7 hace un trabajo bastante bueno cuando se deja solo.

sobrecarga de sincronización

ejecutar el algoritmo en una ventana “blanca” (fuera del área r <2) da una buena idea de las sobrecargas de llamadas del sistema.

Se requieren aproximadamente 7 ms para calcular este área “blanca”, en comparación con los 480 ms de un área representativa.

Algo así como el 1.5%, que incluye tanto la sincronización como el cálculo de la cola de trabajos. Y esto está haciendo una sincronización en una cola de 1024 trabajos.

Absolutamente despreciable, diría yo. Eso podría ser motivo de reflexión para todos los fanáticos de la fila de espera.

optimizando iteraciones

La forma en que se realizan las iteraciones es un factor clave para la optimización.
Después de algunas pruebas, me conformé con este método:

 static inline unsigned char mandelbrot_pixel(double x0, double y0) { register double x = x0; register double y = y0; register double x2 = x * x; register double y2 = y * y; unsigned iteration = 0; const int max_iteration = 255; while (x2 + y2 < 4.0) { if (++iteration == max_iteration) break; y = 2 * x * y + y0; x = x2 - y2 + x0; x2 = x * x; y2 = y * y; } return (unsigned char)iteration; } 

Ganancia neta: + 20% en comparación con el método OP.

(Las directivas de register no hacen una gran diferencia, solo están ahí para la decoración)

Matando las tareas después de cada cálculo.

El beneficio de dejar vivos a los trabajadores es aproximadamente el 5% del tiempo de cálculo.

efecto mariposa

En mi caso de prueba, la orden "mariposa" está funcionando muy bien, con un aumento de más del 30% en casos extremos y rutinariamente del 10 al 15% debido a la "extracción" de las solicitudes más voluminosas.

El problema en su código es que todos los hilos capturan y acceden a la misma variable i . Esto crea una condición de carrera y los resultados son tremendamente incorrectos.

Debe pasarlo como un argumento al hilo lambda, y también corregir los rangos ( i-1 hará que su indexación salga de los límites).