A divisão de um programa em 4 threads é mais lento do que um único thread

Question

Eu tenho escrito um raytracer semana passada, e chegaram a um ponto onde ele está fazendo o suficiente para que a multi-threading faria sentido.Eu tentei usando OpenMP para paralelizar a ele, mas a execução com mais de threads é realmente mais lento do que executá-lo com um.

Lendo sobre outras questões semelhantes, especialmente, sobre o OpenMP, uma sugestão é que o gcc otimiza o código de série, melhor.No entanto executando o código compilado abaixo com export OMP_NUM_THREADS=1 é duas vezes mais rápido que com export OMP_NUM_THREADS=4.I. e.É o mesmo código compilado em ambas as corridas.

Executando o programa com 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

O tempo do usuário, é muito menor que o real, o que é incomum durante o uso de várias cores- utilizador deve ser maior do que real como vários núcleos estão em execução ao mesmo tempo.

O código que tenho paralelizado, 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);
            }
        }
    }
}

Quando a leitura esta pergunta Eu pensei que tinha encontrado a minha resposta.Ele fala sobre a implementação de gclib rand() sincronização chama para si, para preservar o estado para a geração de um número aleatório entre threads.Eu estou usando rand() bastante por amostragem de monte carlo, então eu pensei que era o problema.Eu me livrei de chamadas para rand, substituindo-os por um único valor, mas com vários segmentos ainda é mais lento. EDITAR:ops acontece que eu não teste esse corretamente, era o de valores aleatórios!

Agora, aqueles que estão fora do caminho, vou discutir uma visão geral do que está sendo feito em cada chamada para computePixel, e , esperamos, uma solução pode ser encontrada.

Na minha raytracer eu tem, essencialmente, uma cena de árvore, com todos os objetos.Esta árvore é percorrida muito durante computePixel quando os objetos são testados para cruzamento, no entanto, não escreve são feitas para esta árvore ou quaisquer objetos. computePixel essencialmente, lê a cena de um monte de vezes, chamar métodos em objetos (os quais são const métodos), e no final escreve um valor único para o seu próprio conjunto de pixels.Esta é a única parte que eu estou consciente de onde mais do que um thread tenta escrever para a mesma variável de membro.Não há nenhuma sincronização em qualquer lugar pois não existem dois threads podem escrever para a mesma célula no conjunto de pixels.

Alguém pode sugerir locais onde poderia haver algum tipo de contenção?Coisas para tentar?

Obrigado antecipadamente.

EDITAR: Desculpe, era estúpido, não para fornecer mais informações sobre o meu sistema.

• Compilador gcc 4.6 (com -O2 optimization)
• Ubuntu Linux 11.10
• OpenMP 3
• Intel i3-2310M Quad-core de 2.1 Ghz (no meu laptop no momento)

Código para calcular pixel:

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

Entre as sugestões, pode ser a passagem de árvore que faz com que o slow-down.Alguns outros aspectos:há uma porção de recursão envolvidos, uma vez que a função de amostragem é chamada (recursiva saltando de raios)- isso poderia causar esses problemas?

Answer 1

Obrigado a todos pelas sugestões, mas depois de mais de perfil, e livrar-se de outros fatores, geração de número aleatório fiz vir a ser o culpado.

Conforme descrito na pergunta acima, rand() precisa manter o controle de seu estado a partir de uma chamada para o próximo.Se vários threads estão tentando modificar esse estado, poderia causar uma condição de corrida, para a implementação padrão da glibc é bloqueio em cada chamada, para tornar a função de thread-safe.Isso é terrível para o desempenho.

Infelizmente, as soluções para esse problema que eu vi no stackoverflow são todos os locais, i.e.lidar com o problema no âmbito onde rand() é chamado.Em vez disso, proponho uma "rápida e suja" solução de que qualquer pessoa pode usar no seu programa para implementar independente de geração de número aleatório para cada segmento, sem a necessidade de sincronização.

Eu testei o código, e ele funciona - não há bloqueio, e não perceptível desaceleração, como resultado de chamadas para threadrand.Sinta-se livre para apontar qualquer tipo de erros.

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

Agora, você pode inicializar o aleatório estados para os segmentos de main usando init_threadrand(), e , posteriormente, obter um número aleatório usando threadrand() quando utilizar vários threads OpenMP.

Answer 2

A resposta é, sem saber qual máquina você está sendo executado, e sem realmente ver o código do seu computePixel função que depende.

Há alguns fatores que podem afetar o desempenho do seu código, uma coisa que vem à mente é o cache de alinhamento.Talvez suas estruturas de dados, e você fez menção a uma árvore, não são realmente ideal para armazenamento em cache e a CPU acaba de espera para os dados vêm da memória RAM, pois não é possível ajustar as coisas para o cache.Errado cache-linha de alinhamentos poderia fazer algo assim.Se a CPU tem que esperar para que as coisas vêm de RAM, é provável, que a thread vai ser o contexto de comutação de fora, e outra vai ser executado.

O seu sistema operacional agendador de thread é não-determinística, portanto, quando um thread vai executar não é uma coisa previsível, de modo que se, por acaso, que suas threads não estão funcionando, ou está lutando para núcleos de CPU, isso também poderia abrandar as coisas.

Thread afinidade, também desempenha um papel.Um thread será agendada em um determinado núcleo, e normalmente ele será tentado manter este thread no núcleo do mesmo.Se mais de uma de suas threads em execução em um único núcleo, eles vão ter que compartilhar o mesmo núcleo.Outra razão para as coisas poderiam diminuir.Por motivos de desempenho, uma vez que um determinado segmento foi executado em um núcleo, ele é normalmente mantido lá, a menos que haja um bom motivo para trocá-lo para outro núcleo.

Há alguns outros fatores, que não me lembro de cima da minha cabeça, no entanto, sugiro que faça algumas leituras sobre threading.É um complicado e extenso do assunto.Há muito material lá fora.

É a dados que estão sendo gravados no final, os dados que outros threads precisa ser capaz de fazer computePixel ?

Answer 3

Uma forte possibilidade é falso compartilhamento.Parece que você está de computação os pixels em sequência, assim, cada thread pode estar trabalhando em interleaved pixels.Isso geralmente é uma coisa muito ruim para o fazer.

O que pode estar acontecendo é que cada thread está tentando escrever o valor de um pixel ao lado de um escrito em outro thread (todos eles escrever a matriz do sensor).Se estes dois valores de saída compartilham o mesmo cache da CPU-a linha de força a CPU para liberar o cache entre os processadores.Isso resulta em uma quantidade excessiva de nivelamento entre CPUs, o que é relativamente lento operação.

Para corrigir isso, você precisa assegurar-se de que cada thread realmente funciona independente de região.Agora parece que você divida em linhas (eu não sou positivo desde que eu não sei OMP).Se isso funciona depende de quão grande as linhas são -- mas ainda assim o final de cada linha irá sobrepor-se com o início do próximo (em termos de linhas de cache).Você pode querer tentar quebrar a imagem em quatro blocos e cada thread de trabalho em uma série sequencial de linhas (como 1..10 11..20 21..30 31..40).Isso reduziria o compartilhamento.

Não se preocupe com a leitura constante de dados.Tão longo como o bloco de dados não está sendo modificado a cada thread pode ler esta informação de forma eficiente.No entanto, estar desconfiado de qualquer mutável de dados que você tem em seu constante de dados.

Answer 4

Eu só olhei e o Intel i3-2310M na verdade não tem 4 núcleos, ele tem 2 núcleos e hyper-threading.Tente executar o código com apenas 2 linhas e ver que ajuda.Eu acho, em geral, o hyper-threading é totalmente inútil quando você tem um monte de cálculos, e no meu laptop eu desliguei e ficou muito melhor tempo de compilação dos meus projetos.

Na verdade, basta ir na BIOS e desligar HT-não é útil para o desenvolvimento/computação máquinas.