Quero usar a operação de varredura inclusiva no OpenMP para implementar um algoritmo. O que se segue é uma descrição da minha tentativa de fazer isso, e não conseguindo mais do que uma aceleração morna.
A operação inclusiva é definida como segue: para um vetor de entrada, digamos que [x1,x2,x3,x4]ele produz a sequência de somas parciais [x1, x1+x2, x1+x2+x3, x1+x2+x3+x4]. Esta é uma operação altamente paralelizável e aparentemente foi bem implementada no OpenMP.
Dei uma olhada na seguinte referência: https://theartofhpc.com/pcse/omp-reduction.html#Scanprefixoperations (A referência do manual https://www.openmp.org/spec-html/5.0/openmpsu45.html#x68-1940002.9.6 parece muito enigmática para mim agora)
O site artofhpc diz que a cláusula de redução recebe um modificador inscan:
#pragma omp parallel for reduction(inscan,+:sumvar)`
No corpo do loop paralelo há uma diretiva scan que permite que você armazene os resultados parciais. Para scans inclusivos, a variável reduction é atualizada antes do pragma scan:
sumvar // update
#pragma omp scan inclusive(sumvar)
partials[i] = sumvar
Tentei seguir a mesma sintaxe, para medir o desempenho versus redução serial padrão e os resultados foram bem decepcionantes. Meu código está no final do post.
No código, estou apenas fazendo um teste simples considerando um vetor muito grande de tamanho 90 milhões consistindo de valores aleatórios no intervalo [-1,1], e realizando uma varredura nele usando um número crescente de threads e medindo a aceleração. Aqui estão meus resultados (recebo a mesma resposta em execuções repetidas). A CPU do meu laptop tem 16 threads de hardware, mas a aceleração geral é decepcionante 1,36. (Eu esperaria algo substancialmente maior!)
Há algo errado na maneira como estou usando a sintaxe OpenMP para redução?
➜ Desktop gcc -fopenmp scantest.c && ./a.out
NumThreads Speedup
1 0.458
2 1.173
3 1.424
4 1.686
5 1.635
6 1.501
7 1.522
8 1.499
9 1.455
10 1.416
11 1.395
12 1.393
13 1.352
14 1.336
15 1.353
16 1.357
#include<stdio.h>
#include<omp.h>
#include<math.h>
#include<stdlib.h>
#include<assert.h>
int main(int argc, char** argv){
int N = 9e7; // vector size
double* x; // vector to reduce
double* partials_s; // vector to scan into
double* partials_p; // vector to scan into
double end, start; // timing variables
double sumvar;
int tmax = argc>1? atoi(argv[1]):35;
int threadcount ;
// Allocate space for all vectors
x = (double*) malloc(sizeof(double)*N);
partials_s = (double*) malloc(sizeof(double)*N);
partials_p = (double*) malloc(sizeof(double)*N);
// Populate the input vectors
for(int i=0 ; i<N ; ++i){
x[i] = -1+2.0*rand()/(double)RAND_MAX;
partials_s[i] = 0.0;
partials_p[i] = 0.0;
}
//-----------------------------------------
// Serial inclusive scan
//-----------------------------------------
start = omp_get_wtime();
sumvar = 0.0;
for(int i=0 ; i<N ; ++i){
sumvar += x[i];
partials_s[i] = sumvar;
}
end = omp_get_wtime();
double stime = end-start; // Time to run the serial code
//-----------------------------------------------------------------------------
// Performance of parallel inclusive scan. Print ratio of serial/parallel time
//----------------------------------------------------------------------------
printf("\nNumThreads Speedup \n");
for(threadcount=1;threadcount<=tmax;++threadcount){
start = omp_get_wtime();
sumvar = 0.0;
#pragma omp parallel for num_threads(threadcount) reduction(inscan,+:sumvar)
for(int i=0 ; i<N ; ++i){
sumvar = sumvar + x[i]; // updating the value of sumvar
#pragma omp scan inclusive(sumvar)
partials_p[i] = sumvar;
}
end = omp_get_wtime();
double ptime = end-start;
printf("%d \t %.3f\n",threadcount,stime/ptime);
}
//for(int i=0 ; i<N ; ++i){
// printf("%.4f %.4f\n", partials_s[i], partials_p[i]);
//}
// Deallocate
free(x);
free(partials_s);
free(partials_p);
return 0;
}
TL;DR: Isso não é escalável porque tal operação de varredura é simplesmente limitada pela memória . Mais especificamente, ela é limitada pela largura de banda da DRAM .
Análise
Em PCs comuns, apenas alguns núcleos conseguem saturar a largura de banda da DRAM. Às vezes, um único núcleo consegue (normalmente um PC com uma boa CPU e uma DRAM de canal único). A varredura sequencial já é uma operação limitada à memória e, na minha máquina (CPU i5-9600KF com uma DDR4-DRAM de 2 x 3200 MHz), não está tão longe de saturar a DRAM. De fato, ela atinge 24 GiB/s de taxa de transferência. Minha DRAM pode teoricamente atingir 48 GiB/s apenas para leituras de memória, mas na prática é geralmente de 40~42 GiB/s para leituras e 36~38 GiB/s para leituras/gravações mistas. Isso significa que o código sequencial já satura ~65% da largura de banda da minha DRAM !
Com o código paralelo, eu alcanço 20 GiB/s com 1 thread, 30 GiB/s com 2 threads, 35 GiB/s com 3 threads, 36 GiB/s com 4 threads, 35 GiB/s com 6 threads (máximo útil, já que eu só tenho 6 núcleos). Como podemos ver, apenas 3 threads são suficientes para quase saturar a largura de banda na minha máquina. 2 threads na verdade não são tão longe para saturá-la (~80%).
Na verdade, isso é bastante consistente com a velocidade impressa pelo seu programa:
Com mais de 3 threads, o desempenho na verdade diminui. Isso provavelmente ocorre porque os acessos DRAM (e o do cache L3) parecem mais aleatórios da perspectiva da CPU e os acessos aleatórios são um pouco menos eficientes (mais difíceis de pré-buscar). Além disso, o cache trashing pode fazer com que mais dados sejam carregados do DRAM, então a eficiência diminui enquanto o throughput permanece praticamente estável.
Há outra coisa interessante: a implementação paralela é na verdade mais lenta do que a sequencial na minha máquina, mesmo com 6 threads! Isso ocorre porque a implementação paralela precisa executar mais trabalho . De fato, AFAIK, a varredura paralela requer várias etapas de memória: por exemplo, uma para calcular a redução parcial e uma para calcular a varredura real por bloco com base nas somas parciais computadas antes. Com essa implementação, significa que mais dados devem ser lidos da memória (duas vezes mais), tornando a operação mais lenta se a memória já for o gargalo. Existem outras implementações possíveis, mas todas as que consigo pensar exigem ler/escrever significativamente mais dados de/para DRAM neste loop (com um agendamento estático padrão).
Note que usei o GCC com os sinalizadores
-fopenmp -O3para compilar o programa perfilado (-mavx2não impactou os resultados do perfil). Na prática, o GOMP (a implementação OpenMP do GCC usada para perfilar isso na minha máquina) aparentemente executa 2 etapas de leitura/gravação, o que é um pouco menos eficiente do que o mencionado acima. Vi isso ao criar o perfil do código assembly gerado: podemos ver dois loops vinculados à memória ativa no código paralelo e os dois parecem executar um tipo de operação semelhante a uma varredura (certamente uma varredura local seguida por uma atualização de varredura). Essa implementação de 2 etapas de leitura/gravação deve ser teoricamente duas vezes mais lenta. Isso é consistente com a aceleração da implementação OpenMP, que é duas vezes mais lenta com 1 thread (tanto na sua máquina quanto na minha).Possíveis otimizações
Há 2 otimizações principais que podemos executar para tornar isso mais rápido. No entanto, elas não são triviais de aplicar e têm desvantagens significativas.
Primeiro de tudo, a CPU x86-64 realmente lê dados para gravá-los na DRAM devido à alocação de gravação de linha de cache . Você pode fazer armazenamentos de streaming não temporais para evitar isso. Isso só vale a pena se você tiver certeza de que os dados gravados não cabem no cache. Em geral, os desenvolvedores não podem garantir tal coisa a menos que conheçam a arquitetura da CPU de destino ou façam suposições (às vezes razoáveis) sobre ela. Por exemplo, eles podem assumir que o cache LLC não é maior do que algumas centenas de MiB (o que não é tão verdadeiro porque há algumas CPUs com muito cache LLC como Xeon Phi e uma futura pode ter caches LLC tão grandes). O OpenMP pode teoricamente gerar instruções de armazenamento de streaming não temporais com a
nontemporalcláusula. Dito isso, AFAIK ainda não foi implementado na implementação OpenMP convencional no momento da escrita. Essa otimização pode tornar os códigos sequenciais/paralelos cerca de 50% mais rápidos.Outra maneira de tornar isso mais rápido é escrever sua própria implementação paralela mais eficiente e amigável ao cache . Você pode ler dados pedaço por pedaço (com pedaços se encaixando bem no cache LLC). Uma vez que um pedaço é lido da memória, você pode calcular as somas parciais dos sub-pedaços em paralelo e, em seguida, calcular a varredura de forma mais eficiente (já que os dados já devem caber no cache LLC e não precisam ser recarregados). Isso deve melhorar muito a eficiência das implementações paralelas para torná-las muito mais competitivas com a sequencial (embora ainda um pouco mais lentas com 1 thread). Observe que as sincronizações adicionais podem diminuir o desempenho desta implementação. Além disso, os efeitos NUMA também podem tornar as coisas mais complicadas em máquinas com vários nós NUMA. Idealmente, fazer essa otimização você mesmo não é ótimo, e acho que deveria ser o trabalho da implementação OpenMP...
As duas otimizações podem ser combinadas. O armazenamento de streaming deve reduzir o cache trashing e melhorar um pouco o desempenho da segunda otimização. Na minha máquina, espero que as 2 otimizações tornem a implementação paralela cerca de duas vezes mais rápida do que a sequencial fornecida. Isso ainda não é escalável, mas não há muito mais que você possa fazer sobre isso, já que a operação é limitada à memória em primeiro lugar e os códigos limitados à memória geralmente não são escaláveis.
Uma isenção de responsabilidade inicial: ao fazer benchmarking de códigos tão simples, você sempre precisa ter certeza de produzir um efeito colateral observável (
printf("%.4f %.4f\n", partials_s[N-1], partials_p[N-1]);) que garanta que o compilador não otimizará o código inteiro.Seu problema tem dependências de dados para cada iteração e, portanto, é difícil de executar eficientemente em paralelo. Uma implementação paralela ingênua se traduziria efetivamente em:
Este código serializa efetivamente a execução e adiciona custo adicional de sincronização de thread entre as etapas de iteração.
Para realmente calcular a varredura em paralelo, o compilador pode gerar código que distribui as iterações do loop para os threads. Em uma primeira etapa, cada thread executa a varredura no pedaço local. Em uma segunda etapa, os threads determinam o deslocamento para seu thread e precisam adicionar o deslocamento a todos os seus valores de array. Como já apontado na outra resposta, seu problema é limitado à memória e adicionar uma segunda passagem em todo o array não é muito benéfico.
Agora, como isso pode ser benéfico? O OpenMP geralmente não é bom para distribuir cargas de trabalho de granularidade fina e/ou limitadas à memória. O caso de uso para o scan do OpenMP é ter um loop com trabalho computacional para distribuir para vários threads e, como resultado, você precisa do scan dos resultados das iterações.
Conceitualmente, isso pode ser novamente entendido como:
O quão bem ele escalaria
ordereddepende do trabalho a ser feito em cada iteração, ou seja, calcularires. Além disso, ele escalará bem apenas se cada iteração tiver o mesmo custo de cálculo, porque sincronizamos com cada iteração. Qualquer desequilíbrio entre as iterações afetará a escalabilidade. Usar scan tem a vantagem de não sincronizarmos entre cada iteração, mas apenas no final. Então, os desequilíbrios entre as iterações podem ser compensados, desde que os desequilíbrios não sejam sistemáticos entre os threads.Com um custo computacional substancial para cada iteração, a passagem final pela memória não será tão cara.
Quando executo o código modificado acima compilado
gcc -fopenmp -O3 -lmno meu notebook com 4 núcleos, obtenho estes resultados de dimensionamento:Eu tentei esse programa em uma CPU com toneladas de largura de banda, e ainda estou obtendo apenas um fator ou 2 de aceleração, começando com 12 núcleos e nunca mais indo além. Eu culpo uma implementação ruim da parte de redução da varredura. Além disso, a redução vai até 20 níveis, então há toneladas de trabalho extra e com má utilização da cacheline. Como o loop não tem absolutamente nenhum trabalho fora da redução, eu realmente esperaria um desempenho ruim. Tente introduzir alguma quantidade de trabalho escalar no loop.