La división de un programa en 4 hilos es más lento que un solo hilo

Question

He estado escribiendo un raytracer la semana pasada, y han llegado a un punto donde está haciendo lo suficiente que el multi-threading tendría sentido.He intentado usando OpenMP para paralelizar, pero se ejecuta con más hilos en realidad es más lenta que la ejecución con uno.

La lectura sobre otras cuestiones similares, especialmente acerca de OpenMP, una sugerencia fue que gcc optimiza el código de serie mejor.Sin embargo, se ejecuta el código compilado de abajo con export OMP_NUM_THREADS=1 es dos veces tan rápido como con export OMP_NUM_THREADS=4.I. e.Es el mismo código compilado en ambas pistas.

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

De tiempo de los usuarios es mucho menor que la real, lo cual es inusual cuando se utilizan múltiples núcleos- usuario debe ser mayor que real como varios núcleos se están ejecutando al mismo tiempo.

El código que me han paralelizado el uso de 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);
            }
        }
    }
}

Cuando la lectura esta pregunta Pensé que había encontrado mi respuesta.Habla acerca de la aplicación de gclib rand() sincronizar las llamadas a sí mismo para preservar el estado para la generación de números aleatorios entre subprocesos.Estoy utilizando la función rand() bastante de monte carlo de muestreo, así que pensé que ese era el problema.Me deshice de las llamadas a rand, en sustitución de ellos con un solo valor, pero el uso de varios hilos, es aún más lento. EDITAR:oops resulta que yo no prueba esto correctamente, fue el de valores aleatorios!

Ahora que aquellos que están fuera del camino, voy a hablar de una visión general de lo que se está haciendo en cada llamada a computePixel, así que esperemos que se pueda encontrar una solución.

En mi raytracer me tienen esencialmente una escena de árbol, con todos los objetos que hay en ella.Este árbol es atravesada mucho durante computePixel cuando los objetos son probados para la intersección, sin embargo, no se escribe se hace a este árbol, o de los objetos. computePixel esencialmente lee la escena un montón de veces, llamar a métodos en los objetos (todos los cuales son const métodos), y al final escribe un valor único a su propia matriz de píxeles.Esta es la única parte de la que soy consciente de que más de un hilo que trate de escribir a la misma variable miembro.No hay sincronización en cualquier lugar ya que no hay dos hilos pueden escribir a la misma celda en la matriz de píxeles.

Puede alguien sugerir lugares donde podría haber algún tipo de contención?Cosas para probar?

Gracias de antemano.

EDITAR: Lo siento, fue estúpido por no dar más info en mi sistema.

• Compilador gcc 4.6 (con -O2 optimización)
• Linux Ubuntu 11.10
• OpenMP 3
• Intel i3-2310M Quad core 2.1 Ghz (en mi ordenador portátil en el momento)

Código para calcular píxeles:

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;
}

A partir de las sugerencias, podría ser el árbol de recorrido que provoca la ralentización.Algunos otros aspectos:hay un montón de recursividad involucrados una vez que el muestreo se llama a la función (recursivo rebote de los rayos)- esto podría causar estos problemas?

Answer 1

Gracias a todos por las sugerencias, pero después de más de perfilado, y deshacerse de los otros factores que contribuyen, al azar de la generación de números ¿ llegar a 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 están tratando de modificar este estado, podría causar una condición de carrera, por lo que la implementación predeterminada en glibc es bloqueo en cada llamada, para hacer la función de hilo de seguridad.Esto es terrible para el rendimiento.

Por desgracia, las soluciones a este problema que he visto en stackoverflow son todos locales, es decir,lidiar con el problema en el ámbito en el que rand() es llamado.En su lugar, propongo una "rápida y sucia" de la solución que cualquiera puede utilizar en su programa de implementación independiente de generación de números aleatorios para cada subproceso, sin necesidad de sincronización.

He probado el código y funciona - no hay ningún bloqueo, y no con notable desaceleración como consecuencia de las llamadas a threadrand.Siéntase libre de señalar cualquier flagrantes errores.

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 usted puede inicializar el azar unidos por hilos de main el uso de init_threadrand(), y, posteriormente, obtener un número aleatorio usando threadrand() cuando el uso de varios hilos en OpenMP.

Answer 2

La respuesta es, sin saber qué máquina en la que estamos ejecutando en este, y sin ver el código de su computePixel la función, que depende.

Hay bastantes factores que podrían afectar el rendimiento de su código, una cosa que viene a la mente es el caché de la alineación.Tal vez sus estructuras de datos, y se hizo mención de un árbol, realmente no son ideales para el almacenamiento en caché, y la CPU termina la espera de los datos provienen de la RAM, ya que no caben las cosas en la memoria caché.Caché incorrecto de la línea de las alineaciones pueden causar que algo como eso.Si la CPU tiene que esperar para que las cosas vienen de RAM, es probable, que el hilo conductor será contexto de conmutación de salida, y otro de su ejecución.

Su sistema operativo hilo programador no es determinista, por lo tanto, cuando un hilo de ejecución no es una predicción cosa, así que si lo que ocurre es que los hilos no están corriendo mucho, o están contendiendo por los núcleos de la CPU, esto también podría ralentizar las cosas.

Hilo de afinidad, también juega un papel.Un hilo se programará en un determinado núcleo, y normalmente va a ser tratado de mantener este hilo en el mismo núcleo.Si es más de uno de los hilos se ejecutan en un solo núcleo, tendrá que compartir el mismo núcleo.Otra razón por la que las cosas podrían ralentizar.Por motivos de rendimiento, una vez que un hilo en concreto se ha ejecutado en un núcleo, normalmente se mantuvo allí, a menos que haya una buena razón para cambiar a otro núcleo.

Hay algunos otros factores, de la cual no recuerdo la parte superior de mi cabeza, sin embargo, sugiero hacer un poco de lectura en las operaciones de roscado.Se trata de un complejo y extenso tema.Hay un montón de material por ahí.

Es que los datos se escriban en el final, los datos que otros hilos deben ser capaces de hacer computePixel ?

Answer 3

Una posibilidad sólida es False Sharing . Parece que está calculando los píxeles en secuencia, por lo que cada hilo puede estar trabajando en píxeles intercalados. Esto suele ser 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 a la matriz del sensor). Si estos dos valores de salida comparten la misma línea de memoria caché de la CPU, esto obliga a la CPU para eliminar el caché entre los procesadores. Esto se traduce en una cantidad excesiva de lavado entre CPU, que es una operación relativamente lenta.

Para solucionar esto, debe asegurarse de que cada hilo trabaje realmente en una región independiente. En este momento, parece que se divide en filas (no soy positivo ya que no conozco OMP). Si esto funciona depende de qué tan grandes sean tus filas, pero aún así, 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 romper la imagen en cuatro bloques y hacer que cada hilo funcione en una serie de filas secuenciales (para como 1..10 11..20 21..30 31..40). Esto reduciría enormemente el intercambio.

No te preocupes por leer datos constantes. Mientras no se modifique el bloque de datos, cada hilo puede leer esta información de manera eficiente. Sin embargo, tenga en nombre de los datos mutables que tenga en sus datos constantes.

Answer 4

Acabo de mirar y el Intel i3-2310m en realidad no tiene 4 núcleos, tiene 2 núcleos y hiper-roscado.Intente ejecutar su código con solo 2 hilos y verlo lo que ayuda.En general, lo encuentro en general Hyper-Threading es totalmente inútil cuando tiene muchos cálculos, y en mi computadora portátil lo apagé y obtuve mejores tiempos de compilación de mis proyectos.

De hecho, simplemente entra en su BIOS y apague HT: no es útil para las máquinas de desarrollo / computación.