Dividir un programa en 4 hilos es más lento que un solo hilo

Question

He estado escribiendo un raytracer la semana pasada, y he llegado a un punto en el que está haciendo suficiente para que el multi-threading tenga sentido. He intentado usar OpenMP para paralelizarlo, pero ejecutarlo con más hilos es en realidad más lento que ejecutarlo con uno.

Leyendo sobre otras preguntas similares, especialmente sobre OpenMP, una sugerencia fue que gcc optimiza mejor el código de serie. Sin embargo, ejecutar el siguiente código compilado con export OMP_NUM_THREADS=1 es dos veces más rápido que con export OMP_NUM_THREADS=4. Es decir. Es el mismo código compilado en ambas ejecuciones.

Ejecutar el programa con time:

> export OMP_NUM_THREADS=1; time ./raytracer 
real 0m34.344s 
user 0m34.310s 
sys  0m0.008s 


> export OMP_NUM_THREADS=4; time ./raytracer 
real 0m53.189s 
user 0m20.677s 
sys  0m0.096s 

tiempo del usuario es mucho más pequeño que real, lo cual es inusual cuando se utilizan múltiples cores- usuario debe ser mayor que como varios núcleos son reales corriendo al mismo tiempo.

Código que he parallelized usando OpenMP

void Raytracer::render(Camera& cam) { 

    // let the camera know to use this raytracer for probing the scene 
    cam.setSamplingFunc(getSamplingFunction()); 

    int i, j; 

    #pragma omp parallel private(i, j) 
    { 

     // Construct a ray for each pixel. 
     #pragma omp for schedule(dynamic, 4) 
     for (i = 0; i < cam.height(); ++i) { 
      for (j = 0; j < cam.width(); ++j) { 
       cam.computePixel(i, j); 
      } 
     } 
    } 
} 

Al leer this question pensé que había encontrado mi respuesta. Habla sobre la implementación de gclib rand() sincronización de llamadas a sí mismo para preservar el estado para la generación de números aleatorios entre hilos. Estoy usando rand() bastante para el muestreo de monte carlo, así que pensé que ese era el problema. Me deshice de las llamadas a rand, reemplazándolas por un único valor, pero el uso de múltiples hilos es aún más lento. EDITAR: ¡oops resulta que no lo probé correctamente, fueron los valores aleatorios!

Ahora que están fuera del camino, discutiré un resumen de lo que se está haciendo en cada llamada al computePixel, así que con suerte se puede encontrar una solución.

En mi raytracer, esencialmente tengo un árbol de escenas, con todos los objetos en él. Este árbol se recorre mucho durante computePixel cuando se prueba la intersección de objetos, sin embargo, no se realizan escrituras en este árbol ni en ningún objeto. computePixel esencialmente lee la escena un montón de veces, llamando a métodos en los objetos (todos ellos son métodos const), y al final escribe un único valor en su propia matriz de píxeles. Esta es la única parte que conozco en la que más de un subproceso intentará escribir en la misma variable miembro. No hay sincronización en ninguna parte, ya que no hay dos hilos que puedan escribir en la misma celda en la matriz de píxeles.

¿Alguien puede sugerir lugares donde podría haber algún tipo de disputa? Cosas que probar?

Gracias de antemano.

EDITAR: Disculpa, fue estúpido no proporcionar más información sobre mi sistema.

• compilador gcc 4.6 (con optimización -O2)
• Ubuntu Linux 11.10
• OpenMP 3
• Intel i3-2310M Quad núcleo 2.1Ghz (en mi portátil en el momento) Código

por píxel de cómputo:

class Camera { 

    // constructors destructors 
    private: 
     // this is the array that is being written to, but not read from. 
     Colour* _sensor; // allocated using new at construction. 
} 

void Camera::computePixel(int i, int j) const { 

    Colour col; 

    // simple code to construct appropriate ray for the pixel 
    Ray3D ray(/* params */); 
    col += _sceneSamplingFunc(ray); // calls a const method that traverses scene. 

    _sensor[i*_scrWidth+j] += col; 
} 

De las sugerencias, que podría ser el recorrido del árbol que provoca la ralentización. Algunos otros aspectos: hay una gran cantidad de recurrencia involucrada una vez que se llama a la función de muestreo (rebote recursivo de los rayos). ¿Podría esto causar estos problemas?

Answer 1

Gracias a todos por las sugerencias, pero después de un mayor perfil y deshacerse de otros factores contribuyentes, la generación de números aleatorios hizo resultó ser el culpable.

Como se indica en la pregunta anterior, rand() necesita realizar un seguimiento de su estado de una llamada a la siguiente. Si varios hilos intentan modificar este estado, causaría una condición de carrera, por lo que la implementación predeterminada en glibc es en para cada llamada, para hacer que la función sea segura para los hilos. Esto es terrible para el rendimiento.

Desafortunadamente las soluciones a este problema que he visto en stackoverflow son todas locales, es decir, ocupanme del problema en el ámbito donde rand() se llama. En su lugar, propongo una solución "rápida y sucia" que cualquiera puede utilizar en su programa para implementar la generación de números aleatorios independientes para cada hilo, sin requerir sincronización.

He probado el código, y funciona: no hay bloqueo ni desaceleración notable como resultado de llamadas a threadrand. Siéntase libre de señalar cualquier error flagrante.

threadrand.h

#ifndef _THREAD_RAND_H_ 
#define _THREAD_RAND_H_ 

// max number of thread states to store 
const int maxThreadNum = 100; 

void init_threadrand(); 

// requires openmp, for thread number 
int threadrand(); 

#endif // _THREAD_RAND_H_ 

threadrand.cpp

#include "threadrand.h" 
#include <cstdlib> 
#include <boost/scoped_ptr.hpp> 
#include <omp.h> 

// can be replaced with array of ordinary pointers, but need to 
// explicitly delete previous pointer allocations, and do null checks. 
// 
// Importantly, the double indirection tries to avoid putting all the 
// thread states on the same cache line, which would cause cache invalidations 
// to occur on other cores every time rand_r would modify the state. 
// (i.e. false sharing) 
// A better implementation would be to store each state in a structure 
// that is the size of a cache line 
static boost::scoped_ptr<unsigned int> randThreadStates[maxThreadNum]; 

// reinitialize the array of thread state pointers, with random 
// seed values. 
void init_threadrand() { 
    for (int i = 0; i < maxThreadNum; ++i) { 
     randThreadStates[i].reset(new unsigned int(std::rand())); 
    } 
} 

// requires openmp, for thread number, to index into array of states. 
int threadrand() { 
    int i = omp_get_thread_num(); 
    return rand_r(randThreadStates[i].get()); 
} 

Ahora se puede inicializar los estados aleatorios para hilos de main usando init_threadrand(), y posteriormente obtener un número aleatorio utilizando threadrand() al usar varios hilos en OpenMP.

Answer 2

La respuesta es que, sin saber en qué máquina está ejecutando esto, y sin realmente ver el código de su función computePixel, eso depende.

Hay muchos factores que pueden afectar el rendimiento de su código, una cosa que viene a la mente es la alineación de la caché. Tal vez sus estructuras de datos, y usted mencionó un árbol, no son realmente ideales para el almacenamiento en caché, y la CPU termina esperando que los datos provengan de la memoria RAM, ya que no cabe cosas en el caché. Las alineaciones erróneas de la línea de caché podrían causar algo así. Si la CPU tiene que esperar a que venga algo de la RAM, es probable que el hilo se desconecte por el contexto y se ejecute otro.

Su programador de subprocesos OS es no determinista, por lo tanto, cuando un hilo se ejecutará no es una cosa predecible, por lo que si se da la circunstancia de que sus hilos no están funcionando mucho, o están contendiendo por núcleos de CPU, esto también podría desacelerar las cosas.

La afinidad del hilo, también juega un papel. Un hilo será programado en un núcleo particular, y normalmente se intentará mantener este hilo en el mismo núcleo. Si más de uno de sus subprocesos se ejecuta en un solo núcleo, deberán compartir el mismo núcleo. Otra razón por la que las cosas podrían ralentizarse. Por motivos de rendimiento, una vez que un hilo en particular se ha ejecutado en un núcleo, normalmente se mantiene allí, a menos que haya una buena razón para cambiarlo a otro núcleo.

Hay algunos otros factores, que no recuerdo en la cabeza, sin embargo, sugiero leer un poco sobre el enhebrado. Es un tema complicado y extenso. Hay mucho material por ahí.

¿Están los datos escritos al final, datos que otros hilos deben poder hacer computePixel?

Answer 3

Una posibilidad fuerte es compartiendo falso. Parece que está calculando los píxeles en secuencia, por lo que cada hilo puede estar trabajando en píxeles intercalados. Esto generalmente es algo muy malo de hacer.

Lo que podría estar sucediendo es que cada hilo está tratando de escribir el valor de un píxel al lado de uno escrito en otro hilo (todos escriben en el conjunto de sensores). Si estos dos valores de salida comparten la misma línea de caché de la CPU, esto obliga a la CPU a vaciar la caché entre los procesadores. Esto resulta en una cantidad excesiva de enjuague entre las CPU, que es una operación relativamente lenta.

Para solucionar esto, debe asegurarse de que cada hilo realmente funcione en una región independiente. En este momento parece que divides en filas (no estoy seguro ya que no sé OMP). Si esto funciona depende de cuán grandes sean sus filas, pero igual el final de cada fila se superpondrá con el comienzo de la siguiente (en términos de líneas de caché). Es posible que desee intentar dividir la imagen en cuatro bloques y hacer que cada subproceso funcione en una serie de filas secuenciales (por ejemplo, 1..10 11..20 21..30 31..40). Esto reduciría en gran medida el intercambio.

No se preocupe por leer datos constantes.Siempre que el bloque de datos no se modifique, cada hilo puede leer esta información de manera eficiente. Sin embargo, desconfíe de los datos variables que tenga en sus datos constantes.

Answer 4

Acabo de buscar y el Intel i3-2310M en realidad no tiene 4 núcleos, tiene 2 núcleos y hyper-threading. Intenta ejecutar tu código con solo 2 hilos y verás que eso ayuda. En general, considero que el hyper-threading es totalmente inútil cuando tienes muchos cálculos, y en mi computadora portátil lo apagué y obtuve tiempos de compilación mucho mejores de mis proyectos.

De hecho, solo acceda a su BIOS y apague HT; no es útil para máquinas de desarrollo/cálculo.