Será multi threading fornecer qualquer aumento de desempenho?

https://stackoverflow.com/questions/1106481

12-09-2019
|

Pergunta

Eu sou novo em programação, em geral, por isso, manter isso em mente quando você responder a minha pergunta.

I tem um programa que leva uma grande matriz 3D (1 bilhão de elementos) e resume os vários elementos ao longo do eixo para produzir um conjunto 2D de uma projecção de cada lado dos dados. O problema aqui é que ele é muito ram intensivo como o programa é a informação constantemente atraente do carneiro, leitura e escrita.

A questão é, será que eu ganhar qualquer aumento de desempenho se eu multithread o programa ou vou acabar correndo para um acesso gargalo RAM? Quando digo multithreading, eu só multithreading média para 2 ou 4 núcleos, não mais.

Se isso ajuda, a configuração do computador atual é quad 2.4ghz core2, 1033 FSB, 4 gb de ram em 667 MHz.

Agradecemos antecipadamente,

-Faken

Editar:

Parece-me que as pessoas aqui estão muito mais interessados ??nesta questão que eu esperava em primeiro lugar. Vou expandir a pergunta e postar algum código para aqueles que estão interessados.

Em primeiro lugar, um pouco de fundo sobre mim para que possa entender onde eu estou vindo. Eu sou um estudante de engenharia mecânica que de alguma forma conseguiu escolher um tema que praticamente não tinha nada a ver com a engenharia mecânica. Tomei um curso de java introdutória (forçada) de aproximadamente 5 anos e nunca ter tocado programação até cerca de um mês atrás, quando eu comecei a minha tese a sério. Eu também tenho tido (mais uma vez forçado, ainda não sei porque) um curso de eletrônica e engenharia de computação, nós lidamos com micro-controladores (8 bits), o seu funcionamento interno, e alguns codificação para eles ASM. Fora isso, eu sei quase nada sobre programação.

Aqui está o código:

int dim = 1000;
int steps = 7 //ranges from 1 to  255

for (int stage = 1; stage < steps; stage++)
for (int j = 0; j < dim; j++)
    for (int i = 0; i < dim; i++)
    {
        sum = 0;
        for (int k = 0; k < dim; k++)
            if (partMap[(((i * dim) + k) * dim) + j] >= stage)
                sum++;

        projection[(j*dim) + i] = sum;
    }

Esta seção do código opera no único eixo z. Os principais dados, devido à forma como foi construído, tem um sistema de endereçamento estranho, mas você não precisa se preocupar com isso. Há também outro código para fazer as projeções de outros lados do cubo, mas eles fazem coisas muito diferentes.

Solução

Há apenas uma maneira de código optimize: descobrir o que você está fazendo isso é lento, e fazer menos. Um caso especial de "fazer menos do que" é para fazer outra coisa em vez que é mais rápido.

Então, primeiro de tudo, aqui está o que eu estou fazendo com base no seu código de publicação:

#include <fstream>
#include <sstream>
using std::ios_base;

template<typename Iterator, typename Value>
void iota(Iterator start, Iterator end, Value val) {
    while (start != end) {
        *(start++) = val++;
    }
}

int main() {

    const int dim = 1000;
    const int cubesize = dim*dim*dim;
    const int squaresize = dim*dim;
    const int steps = 7; //ranges from 1 to  255
    typedef unsigned char uchar;

    uchar *partMap = new uchar[cubesize];
    // dummy data. I timed this separately and it takes about
    // a second, so I won't worry about its effect on overall timings.
    iota(partMap, partMap + cubesize, uchar(7));
    uchar *projection = new uchar[squaresize];

    for (int stage = 1; stage < steps; stage++) {
        for (int j = 0; j < dim; j++) {
                for (int i = 0; i < dim; i++)
                {
                        int sum = 0;
                        for (int k = 0; k < dim; k++)
                            if (partMap[(((i * dim) + k) * dim) + j] >= stage)
                                sum++;

                        projection[(j*dim) + i] = sum;
                }
        }

        std::stringstream filename;
        filename << "results" << stage << ".bin";
        std::ofstream file(filename.str().c_str(), 
            ios_base::out | ios_base::binary | ios_base::trunc);
        file.write((char *)projection, squaresize);
    }

    delete[] projection;
    delete[] partMap;
}

(Edit:... Apenas notou que "projeção" deve ser uma matriz de int, não uchar My bad Isso vai fazer a diferença para alguns dos horários, mas espero que não muito grande de um)

Então eu copiei result*.bin para gold*.bin, para que eu possa verificar as minhas futuras alterações da seguinte forma:

$ make big -B CPPFLAGS="-O3 -pedantic -Wall" && time ./big; for n in 1 2 3 4 5
6; do diff -q results$n.bin gold$n.bin; done
g++  -O3 -pedantic -Wall   big.cpp   -o big

real    1m41.978s
user    1m39.450s
sys     0m0.451s

OK, então 100 segundos no momento.

Assim, especulando que ele está caminhando através da matriz de dados de bilhões de item que é lento, vamos tentar indo só por uma vez, em vez de uma vez por etapa:

    uchar *projections[steps];
    for (int stage = 1; stage < steps; stage++) {
         projections[stage] = new uchar[squaresize];
    }

    for (int j = 0; j < dim; j++) {
            for (int i = 0; i < dim; i++)
            {
                    int counts[256] = {0};
                    for (int k = 0; k < dim; k++)
                            counts[partMap[(((i * dim) + k) * dim) + j]]++;

                    int sum = 0;
                    for (int idx = 255; idx >= steps; --idx) {
                        sum += counts[idx];
                    }
                    for (int stage = steps-1; stage > 0; --stage) {
                        sum += counts[stage];
                        projections[stage][(j*dim) + i] = sum;
                    }
            }
    }

    for (int stage = 1; stage < steps; stage++) {
        std::stringstream filename;
        filename << "results" << stage << ".bin";
        std::ofstream file(filename.str().c_str(),
            ios_base::out | ios_base::binary | ios_base::trunc);
        file.write((char *)projections[stage], squaresize);
    }

    for (int stage = 1; stage < steps; stage++) delete[] projections[stage];
    delete[] partMap;

É um pouco mais rápido:

$ make big -B CPPFLAGS="-O3 -pedantic -Wall" && time ./big; for n in 1 2 3 4 5
6; do diff -q results$n.bin gold$n.bin; done
g++  -O3 -pedantic -Wall   big.cpp   -o big

real    1m15.176s
user    1m13.772s
sys     0m0.841s

Agora, steps é muito pequena neste exemplo, por isso estamos fazendo um monte de trabalho desnecessário com a matriz de "contagem". Sem sequer profiling, eu estou supondo que a contagem para 256 duas vezes (uma vez para limpar a matriz e uma vez para resumir) é bastante significativa, em comparação com a contagem a 1000 (para ser executado ao longo de nossa coluna). Então, vamos mudança que:

    for (int j = 0; j < dim; j++) {
            for (int i = 0; i < dim; i++)
            {
                    // steps+1, not steps. I got this wrong the first time,
                    // which at least proved that my diffs work as a check
                    // of the answer...
                    int counts[steps+1] = {0};
                    for (int k = 0; k < dim; k++) {
                        uchar val = partMap[(((i * dim) + k) * dim) + j];
                        if (val >= steps) 
                            counts[steps]++;
                        else counts[val]++;
                    }

                    int sum = counts[steps];
                    for (int stage = steps-1; stage > 0; --stage) {
                        sum += counts[stage];
                        projections[stage][(j*dim) + i] = sum;
                    }
            }
    }

Agora estamos apenas usando como muitos baldes como nós realmente precisa.

$ make big -B CPPFLAGS="-O3 -pedantic -Wall" && time ./big; for n in 1 2 3 4 5
6; do diff -q results$n.bin gold$n.bin; done
g++  -O3 -pedantic -Wall   big.cpp   -o big

real    0m27.643s
user    0m26.551s
sys     0m0.483s

Hurrah. O código é quase 4 vezes mais rápido que a primeira versão, e produz os mesmos resultados. Tudo o que eu tenho feito é a mudança que ordem as contas é feito: não temos sequer olhou para multi-threading ou pré-busca ainda. E eu não tentei qualquer otimização de circuito altamente técnico, apenas deixou para o compilador. Portanto, este pode ser considerado um começo decente.

No entanto, é ainda de tomar uma ordem de magnitude maior do que os 1s que iota funciona. Então, provavelmente há grandes ganhos ainda de encontrar. Uma diferença principal é que o iota corre sobre a matriz 1-D de modo sequencial, em vez de saltar sobre todo o lugar. Como eu disse na minha primeira resposta, você deve procurar utilizar sempre ordem sequencial no cubo.

Então, vamos fazer uma mudança de uma linha, trocando os iej laços:

            for (int i = 0; i < dim; i++)
    for (int j = 0; j < dim; j++) {

Este ainda não é ordem sequencial, mas isso não significa que nós estamos focando uma fatia milhões de bytes de nosso cubo de cada vez. A CPU moderna tem pelo menos 4MB de cache, assim com um pouco de sorte nós só vai bater memória principal para qualquer parte do cubo de uma vez em todo o programa. Com ainda melhor localidade poderíamos reduzir o tráfego dentro e fora de cache L1, também, mas a memória principal é o mais lento.

Quanta diferença isso faz?

$ make big -B CPPFLAGS="-O3 -pedantic -Wall" && time ./big; for n in 1 2 3 4 5
6; do diff -q results$n.bin gold$n.bin; done
g++  -O3 -pedantic -Wall   big.cpp   -o big

real    0m8.221s
user    0m4.507s
sys     0m0.514s

Não é mau. Na verdade, essa mudança só traz o código original de 100s a 20s. Portanto, este é responsável por um fator de 5, e tudo o que eu fiz é responsável por um outro fator de 5 (acho que a diferença entre 'usuário' e tempo 'real' no exemplo acima é principalmente explicada pelo fato do meu scanner de vírus é execução, o que não era anteriormente. 'user' é quanto tempo o programa ocupava uma CPU, 'real' inclui o tempo gasto suspenso, quer à espera de I / o ou dar outro tempo de processo de execução).

Claro, meu balde confia tipo no fato de que tudo o que estamos fazendo com os valores em cada coluna é comutativo e associativo. Reduzir o número de baldes só funcionou porque valores grandes são todos tratados da mesma forma. Isto pode não ser verdade para todas as suas operações, de forma que você tem que olhar para o loop interno de cada um por sua vez, para descobrir o que fazer com ele.

E o código é um pouco mais complicado. Em vez de correr ao longo dos dados fazendo "blah" para cada fase, estamos computando todas as etapas ao mesmo tempo em uma única corrida sobre os dados. Se você começar a fazer de linha e coluna cálculos em uma única passagem, como recomendado na minha primeira resposta, isso vai piorar. Você pode ter que começar a quebrar seu código em funções para mantê-lo legível.

Finalmente, muito do meu ganho de desempenho veio de uma otimização para ofato de que "os passos" é pequena. Com steps=100, eu recebo:

$ make big -B CPPFLAGS="-O3 -pedantic -Wall" && time ./big; for n in 1 2 3 4 5
6; do diff -q results$n.bin gold$n.bin; done
g++  -O3 -pedantic -Wall   big.cpp   -o big

real    0m22.262s
user    0m10.108s
sys     0m1.029s

Este não é tão ruim. Com passos = 100 o código original provavelmente leva cerca de 1400 segundos, embora eu não estou indo para executá-lo para provar isso. Mas vale a pena lembrar que eu não completamente tirado a dependência do tempo em "passos", apenas fez sub-linear.

Outras dicas

Multithreading em vários núcleos poderia reduzir o tempo necessário para resumir através dos eixos, mas cuidado especial é necessário. Você pode realmente obter aumentos de performance maiores de algumas mudanças que você pode fazer ao seu código único segmento:

Você só precisa de tantos tópicos para coincidir com o número de núcleos disponíveis para você. Esta é uma operação intensiva da CPU, e tópicos não são susceptíveis de estar à espera de I / O.
A suposição acima pode não se realizar se a matriz inteira não cabe na RAM. Se porções da matriz são paginada dentro e para fora, alguns fios será espera para operações para completar o paging. Nesse caso, o programa pode beneficiar de ter mais fios do que núcleos. Muitos, no entanto, eo desempenho vai cair devido ao custo de troca de contexto. Você pode ter que experimentar com a contagem da linha. A regra geral é a de minimizar o número de mudanças de contexto entre threads prontos.
Se o array inteiro não cabe na RAM, que pretende minimizar paginação! A ordem em que cada thread acessa as questões de memória, assim como o padrão de acesso memória de todas as threads em execução. Na medida do possível, que você gostaria de terminar com uma parte da matriz antes de se mudar para o outro, para nunca mais voltar a uma área coberta.
Cada núcleo se beneficiariam de ter que acessar uma região completamente separada da memória. Você quer evitar atrasos de acesso de memória causadas por bloqueios e contenção de barramento. Pelo menos para uma dimensão do cubo, que deve ser simples:. Definir cada segmento com a sua própria porção do cubo
Cada núcleo também beneficiar de acesso a mais dados de seu cache (s), em oposição à busca de RAM. Isso significaria encomendar os laços de tal forma que laços internos acessar palavras próximas, em vez de pular em linhas.
Finalmente, dependendo dos tipos de dados na matriz, as instruções SIMD de processadores Intel / AMD (SSE, em suas diversas gerações) pode ajudar a acelerar o desempenho de núcleo único pela soma várias células ao mesmo tempo. VC ++ tem algum suporte embutido .
Se você tem que priorizar seu trabalho, você pode querer primeiro minimizar paginação disco, então se concentrar em otimizar o acesso de memória para fazer uso dos caches de CPU, e só então lidar com multithreading.

Como funciona o código. Será que vão assim?

for each row: add up the values
for each column: add up the values
for each stack: add up the values

Se assim for, você pode querer ler sobre "localidade de referência". Dependendo de como seus dados são armazenados, você pode achar que enquanto você está fazendo as pilhas, uma linha de cache inteiro tem que ser puxado para cada valor, porque os valores estão longe um do outro na memória. Na verdade, com um bilhão de valores, você poderia estar puxando as coisas todo o caminho do disco. acesso sequencial com um longo passo (distância entre os valores) é o pior uso possível para cache. Tente profiling, e se você ver que somando as pilhas está demorando mais que somando as linhas, este é quase certamente o porquê.

Eu acho que você poderia ser saturar o barramento de memória (*), caso em que multithreading seria apenas ajuda se quad core2 usa ônibus diferentes para diferentes núcleos. Mas se você não está saturando a largura de banda, você não pode obter melhor desempenho desta forma mesmo depois de multi-thread. Você terá 4 núcleos gastando todo o seu tempo parado sobre erros de cache em vez de um.

Se você é cache de memória associados, então seu objetivo deve ser para visitar cada página / linha de memória como poucas vezes quanto possível. Então eu tentar coisas como correr ao longo dos dados uma vez, acrescentando cada valor de três totais diferentes que você vá. Se isso corre mais rápido em um único núcleo, então nós estamos no negócio. O próximo passo é que, com um cubo 1000x1000x1000, você tem 3 milhões totais em movimento. Que não se encaixa no cache ou, então, você tem que se preocupar com os mesmos problemas Cache Miss escrita como você leitura.

Você quer ter certeza de que como você correr ao longo de uma fileira de 1000 valores adjacentes na RAM adicionando ao total de linhas que todos compartilham, você também está adicionando aos totais adjacentes para as colunas e pilhas (que não fazer loja). Assim, o "quadrado" de totais de coluna devem ser armazenados de forma adequada, tal como a "quadrado" de pilhas. Dessa forma, você lidar com 1000 de seus bilhão de valores apenas puxando cerca de 12k de memória no cache (4k para 1000 valores, além de 4k para 1000 totais de coluna, além de 4k para 1000 totaliza pilha). Como contra isso, você está fazendo mais lojas do que você seria concentrando-se em total de 1 de cada vez (que, portanto, poderia ser num registo).

Então, eu não prometo nada, mas acho que vale a pena olhar para ordem de acesso de memória, se você multi-thread ou não. Se você pode fazer mais trabalho CPU ao acessar apenas uma quantidade relativamente pequena de memória, então você vai acelerar a versão single-threaded, mas também colocar-se em muito melhor forma para multi-threading, desde os núcleos compartilham um cache limitado, memória ônibus, e RAM principal.

(*) Voltar de cálculo envelope: em aleatórios comentários aleatórios fora da internet a maior largura de banda estimada FSB para processadores Core2 que eu encontrei até agora é um extremo a 12GB / s, com 2 canais em 4x199MHz cada). tamanho da linha de cache é de 64 bytes, que é menos do que o seu passo. Então soma uma coluna ou pilha do mau caminho, agarrando 64 bytes por valor, só iria saturar o ônibus se ele estava fazendo 200 milhões de valores por segundo. Eu estou supondo que é nada como este jejum (10-15 segundos para toda a coisa), ou você não estaria perguntando como acelerá-lo.

Assim, a minha primeira suposição foi provavelmente longe. A menos que seu compilador ou CPU inseriu alguns muito inteligente pré-busca, um único núcleo não pode estar usando 2 canais e 4 transferências simultâneas por ciclo. Para essa matéria, 4 núcleos não poderia usar 2 canais e 4 transferências simultâneas. A largura de banda efetiva para uma série de pedidos pode ser muito menor do que o limite físico, caso em que você poderia esperar para ver boas melhorias de multi-enfiar simplesmente porque você tem 4 núcleos pedindo para 4 linhas de cache diferentes, todos os quais podem ser carregados simultaneamente, sem incomodar o FSB ou o controlador da memória cache. Mas a latência ainda é o assassino, e por isso, se você pode carregar menos de uma linha de cache por valor somado, você vai fazer muito melhor.

É impossível dizer, em geral, porque você não especificou o quão rápido o seu CPU e memória RAM são. Boas chances são de que ele irá melhorar as coisas, porque eu não posso imaginar como até 4 threads somando em paralelo iria saturar o suficiente RAM que se tornaria um gargalo (e não a CPU).

Meu instinto diz que você verá melhorias modestas. No entanto, prever os resultados de otimizações é um erro de notoriamente caso de bruços.

Experimente e referência os resultados.

Se, e este é um grande se, ele é codificado apropriadamente você definitivamente vai ver um acelerar. Agora, como um dos meus professores sempre observado, muitas vezes as pessoas tentam tomar um algoritmo, passe-o e, no fim, é mais lento. Isso é muitas vezes devido a sincronização ineficiente. Então, basicamente, se você sentir vontade de aprofundar em enfiar (eu sinceramente não gostaria de sugerir que se você é novo em programação) ter ir.

No seu caso particular, a sincronização pode ser bastante simples. Isso quer dizer, você poderia atribuir a cada segmento para um quadrante da grande matriz 3-d, onde cada segmento está garantido para ter acesso exclusivo a uma área específica das matrizes de entrada e saída, assim, não há nenhuma necessidade real para 'proteger 'os dados de acesso múltiplo / escreve.

Em resumo, neste específico caso simples encadeamento pode ser muito fácil, mas em geral de sincronização quando mal feito pode causar o programa para demorar mais tempo. É realmente tudo depende.

Multithreading só vai fazer seu código mais rápido se os cálculos pode ser dividido em pedaços que podem ser trabalhados em forma independente e ao mesmo tempo.

Editar

eu disse acima (é quase uma resposta automática), porque eu vejo muitos desenvolvedores gastam muito tempo com multithreading código para nenhum aumento de desempenho em tudo. É claro, então eles acabam com os mesmos (ou até mesmo desempenho mais lento) eo extras complicações da gestão dos vários segmentos.

Sim, parece depois de ler a sua pergunta novamente e tendo em conta o seu caso específico você se beneficiaria de multithreading.

RAM é muito rápido, então eu acho que seria muito difícil para saturar a largura de banda de memória, a menos que você tem muitos, muitos tópicos.

Eu acho que mesmo se multithreading pode produzir um aumento de desempenho é a maneira errada de otimização abordagem. Vários núcleos são toda a raiva porque eles são a única maneira para os fabricantes de CPU para fornecer mais rápido velocidades de CPU em uma taxa comercial - não necessariamente porque eles são uma ferramenta de programação incrível (ainda há um monte de amadurecimento que precisa acontecer) <. / p>

Sempre olhe para o algoritmo que você está usando acima de tudo. Você diz que seu programa é muito RAM intensiva - o que você pode fazer para melhorar os acessos ao cache? Existe uma maneira de classificar sua matriz para que os cálculos podem ser aplicados de forma linear? Que linguagem de programação que você está usando e seria beneficiá-lo para otimizar em uma linguagem de nível mais baixo? Existe uma maneira que você pode usar programação dinâmica para armazenar seus resultados?

Em geral, passar todos os seus recursos trabalhando em direção a um algoritmo mais eficiente, matematicamente e, como otimizações do compilador, então se preocupar com multi-core. Claro, você pode já estar nessa fase, caso em que este comentário não é muito útil; p

Antes de ir multithread, você deve executar um profiler contra seu código. É provavelmente uma questão diferente a respeito de onde uma boa (possivelmente) livre C ++ profiler pode ser encontrado.

Isso irá ajudá-lo a identificar quaisquer pedaços de seu código que estão ocupando porções significativas de tempo de computação. Um ajuste aqui e ali após alguns perfis às vezes pode fazer grandes diferenças no desempenho.

As perguntas que você precisa responder para sua aplicação específica são bem conhecidos.

Em primeiro lugar, é a parallelisable trabalho? da Lei lhe dará um limite superior de quanto você pode acelerar as coisas com multithreading. Amdahl

Em segundo lugar, seria uma solução multithreaded introduzir uma grande quantidade de sobrecarga? Você diz que o programa é "RAM intensiva como o programa é a informação constantemente buscar a partir da RAM, leitura e escrita." Então, você precisa determinar se a leitura / escrita vai causar significativa coordenação sobrecarga . Isto não é fácil. Embora cada CPU pode acessar todo RAM do computador (ler e escrever) a qualquer momento, isso pode retardar acessos à memória - mesmo sem fechaduras - porque as várias CPUs manter seus próprios caches e necessidade de coordenar o que está em seus caches com o outro (CPU 1 tem um valor em cache, CPU 2 atualizações esse valor na RAM, CPU 2 tem a dizer CPU 1 para invalidar sua cache). E se você fizer fechaduras necessidade (que é quase uma garantia de que você está tanto "ler e escrever" memória), então você vai precisar para contenção de evitar, tanto quanto possível.

Em terceiro lugar, você está memória ligada? "RAM intensiva." não é a mesma coisa que "memória obrigado." Se você está atualmente vinculado à CPU, em seguida, multithreading irá acelerar as coisas. Se você está actualmente a memória Vinculadas então multithreading pode coisas ainda lentos para baixo (se uma thread é muito rápido para a memória, então o que vai acontecer com vários segmentos?).

Em quarto lugar, você está lento por algum outro motivo? Se você está newing ou mallocing um monte de memória em seu algoritmo que você pode estar vendo despesas gerais do que sozinho. E em muitas plataformas tanto new e malloc não lidar com multithreading bem , então se você é lento agora porque malloc é ruim, um programa multithread será ainda mais lento porque malloc será pior.

No geral, no entanto, sem ver seu código, eu esperaria que ele seja obrigado CPU e eu esperaria multithreading para acelerar as coisas - quase tanto quanto a lei de Amdahl sugeriria, de fato. Você pode querer olhar para OpenMP ou biblioteca Threading Building Blocks da Intel, ou algum tipo de fila de thread para fazê-lo, no entanto.

Embora isso provavelmente seria muito difícil para você, se você é novo para programação, uma forma muito poderosa para acelerar as coisas seria usar o poder da GPU. Não é só a VRAM muito mais rápido do que a RAM de costume, a GPU também pode executar seu código em paralelo em alguns 128 ou mais núcleos. Claro que, para esta quantidade de dados que você precisará ter uma muito grande VRAM.

Se você decidir verificar isso possibilidade, você deve olhar para cima nVidia CUDA. Eu não tenho verificado-lo eu mesmo, mas que está destinado para problemas como este.

Se você está partitionning seus dados corretamente, então sim, você vai ter um impulso no desempenho. Se você verificar o uso da CPU agora, um núcleo estará em 100% e os outros 3 deve ser perto de 0%

Tudo depende de quão bem você estruturar suas linhas e uso de memória.

Além disso, não esperar uma melhoria x4. x4 é o máximo alcançável, será sempre menor do que dependendo de uma série de fatores.

O seu sistema de computador normalmente tem alguns elementos que limitam o desempenho bruto. Que parte é seus elementos limitantes, depende da situação concreta. Normalmente um dos seguintes fatores podem ser a causa de seus problemas de desempenho.

Disk I / O de largura de banda: Na maioria dos aplicativos corporativos a dimensão dos dados processados ??requer que ele seja armazenado em algum banco de dados. Acessando esses dados podem ser abrandado por ambos: a velocidade de transferência máxima, mas muitas vezes o maior impacto será causado por um grande número de pequenos acessos ao disco ler alguns blocos aqui e ali. O que você vai ver o tempo de latência das cabeças dos discos em movimento ao redor e até mesmo o tempo o disco requer para uma rotação completa pode limitar a sua aplicação. Longos tempos atrás eu tive um problema real usando alguma instalação SUN E430 expansiva que foi superado pelo meu pequeno NeXTstation ... Foi o fsync constante () ing de meu banco de dados que foi retardado por discos não cache acessos escrita (por uma boa razão) . Normalmente, você pode acelerar o seu sistema adicionando discos adicionais para obter mais eu S por segundo /. Dedicando suas unidades para tarefas específicas pode até fazer melhor em alguns casos.
Rede de Latência:. Quase tudo o que afeta a velocidade de aplicação disse para discos é equivalente para o Network I / O
RAM: Se a sua memória RAM não é grande o suficiente para armazenar sua imagem aplicação completa você precisa armazená-lo em um disco externo. Portanto, os / picadas de desaceleração Disk i o que você novamente.
velocidade de processamento da CPU (ou inteiro ou ponto flutuante): poder de processamento da CPU é o próximo fator que é um limite para tarefas intensivas de CPU. A CPU tem um limite de velocidade física que não pode ser ultrapassaram. A única maneira de acelerar é adicionar mais CPU.

Estes limites podem ajudá-lo a encontrar uma resposta para o seu problema específico.

Você precisa simplesmente mais poder de processamento e seu sistema tem mais de uma CPU ou Core? Nesse caso multithreading irá melhorar o seu desempenho.

Você observa significativa rede ou disco Latência? Se você ver isso, o seu CPU valioso pode jogar fora ciclos de CPU espera de alguns lento I / O. Se mais que um segmento está ativo, esta discussão pode encontrar todos os dados necessários para o processamento na memória e poderia pegar esses ciclos de CPU desperdiçados.

Portanto, você precisa observar o seu aplicativo existente. tentar extimate a largura de banda de memória dos dados embaralhado. Se o aplicativo está ativo em uma CPU abaixo de 100%, você pode ter atingido o limite de largura de banda de memória. Nesse caso, segmentação adicional não fará nenhum bom para você, porque isso não lhe dá mor largura de banda da memória.

Se a CPU é em 100%, experimentá-lo, mas ter um olhar para os algoritmos. Multi-threading irá adicionar sobrecarga adicional para a sincronização (e complexidade, toneladas de complexidade) que pode reduzir um pouco a largura de banda de memória. Prefere alorithms que podem ser implementadas evitando grão fino sincronizações.

Se você ver o tempo de espera de E / S, pense sobre particionamento inteligente ou cache e, em seguida, sobre threading. Há uma razão pela qual GNU make-suportado volta construção paralelo na década de 90: -)

O domínio do problema que você descreveu me leva a GAV uma olhada algoritmos inteligentes em primeiro lugar. Tente usar operações de leitura / gravação seqüencial na memória principal, tanto quanto possível para apoiar os subsistemas de CPU e memória, tanto quanto possível. Manter as operações "local" e datastructures como pequeno e optimzed quanto possível para reduzir a quantidade de memória que precisa ser embaralhado antes de mudar para um segundo núcleo.

eliminar falsos Sharing

Este é o lugar onde é múltiplos núcleos estão bloqueando uns sobre os outros tentando ler ou atualizar endereços de memória diferentes que compartilham o mesmo cache de bloco. bloqueio cache do processador é por bloco, e apenas um thread pode escrever para esse bloco ao mesmo tempo.

Herb Sutter tem um artigo muito bom sobre a Partilha de Falso, como descobri-lo e como evitá-la em seus algoritmos paralelos.

Obviamente, ele tem uma infinidade de outros excelentes articals sobre programação concorrente também, ver a sua blogue .

É um problema matricial?

Tanto a Intel e AMD têm bibliotecas super-otimizado para todos os tipos de problemas de matemática pesados. Estas bibliotecas usam roscas, organizar os dados para melhor uso cache, prefetch cache, instruções SSE vetor. Tudo.

Eu acredito que você tem que pagar para as bibliotecas, mas eles são bem vale o dinheiro.

Se você pode dividir a matriz de uma maneira que os fios não de leitura / gravação de / para as mesmas posições na matriz deve aumentar sua velocidade.

Eu acho que se você está lidando apenas com pedaços você pode não ter a página ou usar um arquivo de swap e, nesse caso SIM multi-threading vai ajudar.

Se você não pode carregar tudo na memória de uma vez, você precisa ser mais específico sobre sua solução - que tem de ser adaptado para threading.

Por exemplo: Suponha que você carrega sua matriz em blocos menores (poder Tamanho não importa muito). Se você estava a carga em um cubo 1000x1000x1000, você poderia resumir sobre isso. Os resultados poderiam ser armazenados temporarially em suas próprias três planícies, em seguida, adicionado aos seus 3 aviões "resultado final", então o bloco 1000 ^ 3 poderia ser jogado fora para nunca mais ser lido novamente.

Se você faz algo como isso, você não vai ficar sem memória, você não vai enfatizar a swapfile e você não terá que se preocupar com qualquer sincronização de threads, exceto em algumas áreas muito pequenas, específicas (se todos).

O único problema, então, é para garantir que seus dados está em tal formato que você pode acessar uma única 1000 ^ 3 cubo diretamente -. Sem buscar a cabeça do disco rígido em todo o lugar

Edit: O comentário foi correto e que estou errado - ele totalmente faz sentido.

Desde ontem eu percebi que todo o problema poderia ser resolvido como foi lido em - cada pedaço de dados lidos em puderam ser imediatamente resumida nos resultados e descartados. Quando eu penso sobre isso dessa forma, você está certo, não vai ser de muita ajuda, a menos que a rosca pode ler duas correntes ao mesmo tempo, sem colidir.

Tente este código:

int dim = 1000;
int steps = 7 //ranges from 1 to  255

for (int stage = 1; stage < steps; stage++)
for (int k = 0; k < dim; k++)
    for (int i = 0; i < dim; i++)
    {
            sum = 0;
            for (int j = 0; j < dim; j++)
                    if (partMap[(((i * dim) + k) * dim) + j] >= stage)
                            projection[i*dim + j] ++ ;
                            // changed order of i and j
    }


transponse(projection)

Eu mudei a ordem de loops para fazer o cache de código amigável ... Você ganharia com isso uma ordem de aumento de desempenho magninute ... Seja shure.

Este é o passo que você deve fazer antes de tentar correr para multithreading

Absolutamente. Pelo menos ficando cada núcleo em um segmento de trabalho sobre o seu problema ao mesmo tempo vai ajudar. Não está claro se mais threads iria ajudar, mas é possível.

Licenciado em: CC-BY-SA com atribuição

Não afiliado a StackOverflow