Por que é que em ciclos separados os suplementos de estigma são muito mais rápidos do que no ciclo combinado?

Suponha que a1 , b1 , c1 e d1 apontem para a memória heap e meu código numérico tenha o seguinte loop principal.

 const int n = 100000; for (int j = 0; j < n; j++) { a1[j] += b1[j]; c1[j] += d1[j]; } 

Este loop é executado 10.000 vezes através de outro loop externo. Para acelerar, mudei o código para:

 for (int j = 0; j < n; j++) { a1[j] += b1[j]; } for (int j = 0; j < n; j++) { c1[j] += d1[j]; } 

Compilado no MS Visual C ++ 10.0 com otimização total e SSE2 habilitado para 32 bits no Intel Core 2 Duo (x64), o primeiro exemplo leva 5,5 segundos e o exemplo com um loop duplo leva apenas 1,9 segundos. Minha pergunta é: (Por favor, consulte a minha pergunta rehashed abaixo)

PS: Não tenho certeza se isso vai ajudar:

A desmontagem do primeiro ciclo basicamente se parece com isso (este bloco é repetido cerca de cinco vezes no programa completo):

 movsd xmm0,mmword ptr [edx+18h] addsd xmm0,mmword ptr [ecx+20h] movsd mmword ptr [ecx+20h],xmm0 movsd xmm0,mmword ptr [esi+10h] addsd xmm0,mmword ptr [eax+30h] movsd mmword ptr [eax+30h],xmm0 movsd xmm0,mmword ptr [edx+20h] addsd xmm0,mmword ptr [ecx+28h] movsd mmword ptr [ecx+28h],xmm0 movsd xmm0,mmword ptr [esi+18h] addsd xmm0,mmword ptr [eax+38h] 

Cada loop no exemplo de loop duplo cria esse código (o bloco a seguir é repetido cerca de três vezes):

 addsd xmm0,mmword ptr [eax+28h] movsd mmword ptr [eax+28h],xmm0 movsd xmm0,mmword ptr [ecx+20h] addsd xmm0,mmword ptr [eax+30h] movsd mmword ptr [eax+30h],xmm0 movsd xmm0,mmword ptr [ecx+28h] addsd xmm0,mmword ptr [eax+38h] movsd mmword ptr [eax+38h],xmm0 movsd xmm0,mmword ptr [ecx+30h] addsd xmm0,mmword ptr [eax+40h] movsd mmword ptr [eax+40h],xmm0 

A questão acabou por ser irrelevante, uma vez que o comportamento depende fortemente do tamanho das matrizes (n) e do cache da CPU. Então, se houver mais interesse, eu reformulo a pergunta:

Você poderia dar uma visão detalhada dos detalhes que levam a diferentes comportamentos de cache, como mostrado nas cinco áreas do gráfico a seguir?

Também seria interessante apontar as diferenças entre as arquiteturas de CPU e cache, fornecendo um cronograma semelhante para essas CPUs.

PPS: aqui está o código completo. Ele usa TBB Tick_Count para sincronizar com uma resolução maior, que pode ser desativada sem especificar TBB_TIMING :

 #include <iostream> #include <iomanip> #include <cmath> #include <string> //#define TBB_TIMING #ifdef TBB_TIMING #include <tbb/tick_count.h> using tbb::tick_count; #else #include <time.h> #endif using namespace std; //#define preallocate_memory new_cont enum { new_cont, new_sep }; double *a1, *b1, *c1, *d1; void allo(int cont, int n) { switch(cont) { case new_cont: a1 = new double[n*4]; b1 = a1 + n; c1 = b1 + n; d1 = c1 + n; break; case new_sep: a1 = new double[n]; b1 = new double[n]; c1 = new double[n]; d1 = new double[n]; break; } for (int i = 0; i < n; i++) { a1[i] = 1.0; d1[i] = 1.0; c1[i] = 1.0; b1[i] = 1.0; } } void ff(int cont) { switch(cont){ case new_sep: delete[] b1; delete[] c1; delete[] d1; case new_cont: delete[] a1; } } double plain(int n, int m, int cont, int loops) { #ifndef preallocate_memory allo(cont,n); #endif #ifdef TBB_TIMING tick_count t0 = tick_count::now(); #else clock_t start = clock(); #endif if (loops == 1) { for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++){ a1[j] += b1[j]; c1[j] += d1[j]; } } } else { for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { a1[j] += b1[j]; } for (int j = 0; j < n; j++) { c1[j] += d1[j]; } } } double ret; #ifdef TBB_TIMING tick_count t1 = tick_count::now(); ret = 2.0*double(n)*double(m)/(t1-t0).seconds(); #else clock_t end = clock(); ret = 2.0*double(n)*double(m)/(double)(end - start) *double(CLOCKS_PER_SEC); #endif #ifndef preallocate_memory ff(cont); #endif return ret; } void main() { freopen("C:\\test.csv", "w", stdout); char *s = " "; string na[2] ={"new_cont", "new_sep"}; cout << "n"; for (int j = 0; j < 2; j++) for (int i = 1; i <= 2; i++) #ifdef preallocate_memory cout << s << i << "_loops_" << na[preallocate_memory]; #else cout << s << i << "_loops_" << na[j]; #endif cout << endl; long long nmax = 1000000; #ifdef preallocate_memory allo(preallocate_memory, nmax); #endif for (long long n = 1L; n < nmax; n = max(n+1, long long(n*1.2))) { const long long m = 10000000/n; cout << n; for (int j = 0; j < 2; j++) for (int i = 1; i <= 2; i++) cout << s << plain(n, m, j, i); cout << endl; } } 

(Mostra FLOP / s para diferentes valores de n .)

2019

2073
17 дек. Johannes Gerer definido em 17 de dezembro 2011-12-17 23:40 '11 às 23:40 2011-12-17 23:40
@ 10 respostas

Após uma análise mais aprofundada disso, acredito que isso (pelo menos em parte) se deve ao alinhamento dos quatro indicadores. Isso levará a algum conflito de cache / caminho.

Se eu entendi como você aloca seus arrays, eles provavelmente estarão alinhados com a string da página .

Isso significa que todas as suas chamadas em cada ciclo cairão no mesmo arquivo de cache. No entanto, os processadores Intel há algum tempo tinham uma associatividade de cache L1 de 8 vias. Mas na verdade o desempenho não é completamente uniforme. O acesso aos canais de 4 canais ainda é mais lento que o bidirecional.

EDIT: Na verdade, parece que você seleciona todos os arrays separadamente. Normalmente, quando grandes alocações são solicitadas, o distribuidor solicita novas páginas do sistema operacional. Portanto, há uma alta probabilidade de que seleções grandes sejam exibidas com o mesmo deslocamento da borda da página.

Aqui está o código de teste:

 int main(){ const int n = 100000; #ifdef ALLOCATE_SEPERATE double *a1 = (double*)malloc(n * sizeof(double)); double *b1 = (double*)malloc(n * sizeof(double)); double *c1 = (double*)malloc(n * sizeof(double)); double *d1 = (double*)malloc(n * sizeof(double)); #else double *a1 = (double*)malloc(n * sizeof(double) * 4); double *b1 = a1 + n; double *c1 = b1 + n; double *d1 = c1 + n; #endif // Zero the data to prevent any chance of denormals. memset(a1,0,n * sizeof(double)); memset(b1,0,n * sizeof(double)); memset(c1,0,n * sizeof(double)); memset(d1,0,n * sizeof(double)); // Print the addresses cout << a1 << endl; cout << b1 << endl; cout << c1 << endl; cout << d1 << endl; clock_t start = clock(); int c = 0; while (c++ < 10000){ #if ONE_LOOP for(int j=0;j<n;j++){ a1[j] += b1[j]; c1[j] += d1[j]; } #else for(int j=0;j<n;j++){ a1[j] += b1[j]; } for(int j=0;j<n;j++){ c1[j] += d1[j]; } #endif } clock_t end = clock(); cout << "seconds = " << (double)(end - start) / CLOCKS_PER_SEC << endl; system("pause"); return 0; } 

Resultados do teste:

EDIT: Resultados sobre Core 2 Real Architecture:

2 x Intel Xeon X5482 Harpertown a 3,2 GHz:

 #define ALLOCATE_SEPERATE #define ONE_LOOP 00600020 006D0020 007A0020 00870020 seconds = 6.206 #define ALLOCATE_SEPERATE //#define ONE_LOOP 005E0020 006B0020 00780020 00850020 seconds = 2.116 //#define ALLOCATE_SEPERATE #define ONE_LOOP 00570020 00633520 006F6A20 007B9F20 seconds = 1.894 //#define ALLOCATE_SEPERATE //#define ONE_LOOP 008C0020 00983520 00A46A20 00B09F20 seconds = 1.993 

observações:

  • 6,206 segundos com um ciclo e 2,116 segundos com dois ciclos. Isso reproduz com precisão os resultados do OP.

  • Nos dois primeiros testes, os arrays são alocados separadamente. Você notará que todos eles têm o mesmo alinhamento em relação à página.

  • Nos dois testes, os arrays são empacotados juntos para quebrar esse alinhamento. Aqui você notará que ambos os ciclos são mais rápidos. Além disso, o segundo ciclo (duplo) é agora mais lento, como você normalmente espera.

Como observa @Stephen Cannon nos comentários, há uma possibilidade muito provável de que esse alinhamento cause uma falsa suavização em termos de carga / armazenamento ou cache. Eu pensei sobre isso e descobri que a Intel realmente tem um contador de hardware para suavizar os endereços parciais :

http://www.google.com/support


border=0

5 Regiões - Explicações

Região 1:

É fácil. O conjunto de dados é tão pequeno que os custos indiretos, como ciclo e ramificação, prevalecem.

Região 2:

Aqui, quando os tamanhos de dados aumentam, o número de despesas gerais relativas diminui e o desempenho é “saturado”. Aqui, dois ciclos são mais lentos, porque tem o dobro de segmentos e ramificações.

Não tenho certeza do que está acontecendo aqui ... O alinhamento ainda pode ter um efeito, já que Agner Fog menciona conflitos de cache do banco . (Este link se aplica ao Sandy Bridge, mas a ideia deve se aplicar ao Core 2).

Região 3:

Neste ponto, os dados não se encaixam mais no cache L1. Assim, o desempenho é limitado pela largura de banda L1 ↔ L2.

Região 4:

A diminuição do desempenho em um ciclo é o que observamos. E, como já mencionado, isso se deve ao alinhamento, que (muito provavelmente) causa o bloqueio de aliases falsos em blocos de carga / armazenamento do processador.

No entanto, para que a suavização falsa ocorra, deve haver uma etapa suficientemente grande entre os conjuntos de dados. É por isso que você não vê na região 3.

Região 5:

Neste ponto, nada se encaixa no cache. Então você está conectado pela largura de banda da memória.


border=0

2019

1585
18 дек. A resposta é dada Mysticial 18 de dezembro 2011-12-18 00:17 '11 às 0:17 2011-12-18 00:17

OK, a resposta correta deve definitivamente fazer alguma coisa com o cache do processador. Mas usar o argumento do cache pode ser bastante complicado, especialmente sem dados.

Há muitas respostas que levaram a muita discussão, mas deixe-as enfrentar isso: problemas de cache podem ser muito complexos e não unidimensionais. Eles são altamente dependentes do tamanho dos dados, então minha pergunta era injusta: acabou sendo muito interessante no gráfico de cache.

@ A resposta mística convenceu muitas pessoas (inclusive eu), provavelmente porque ele era o único que parecia confiar nos fatos, mas era apenas um “ponto de dados” da verdade.

É por isso que combinei seu teste (usando uma distribuição contínua ou separada) e a resposta @James Answer.

Os gráficos abaixo mostram que a maioria das respostas, e especialmente a maioria dos comentários para a pergunta e respostas, pode ser considerada completamente errada ou verdadeira, dependendo do cenário específico e dos parâmetros usados.

Por favor, note que a minha pergunta inicial foi n = 100.000 . Este ponto (por acaso) exibe um comportamento especial:

  • Tem a maior discrepância entre uma e duas versões do ciclo (quase três vezes)

  • Este é o único ponto em que o loop único (ou seja, distribuição contínua) excede a versão de dois ciclos. (Isso tornou possível a resposta mística).

Resultado usando dados inicializados:

border=0

2019

203
18 дек. Resposta dada por Johannes Gerer 18 de dezembro 2011-12-18 04:29 '11 às 4:29 2011-12-18 04:29

O segundo ciclo inclui muito menos atividade de cache, portanto, o processador é mais fácil de manter os requisitos de memória.

69
17 дек. Responder dada Puppy 17 dez 2011-12-17 23:47 '11 às 23:47 2011-12-17 23:47

Imagine que você está trabalhando em uma máquina em que n era o valor correto para que você possa armazenar simultaneamente dois dos seus arrays na memória, mas a quantidade total de memória disponível via cache de disco ainda era suficiente para armazenar todos os quatro.

Assumindo uma política simples de caching LIFO, este código:

 for(int j=0;j<n;j++){ a[j] += b[j]; } for(int j=0;j<n;j++){ c[j] += d[j]; } 

primeiro fará com que b carregue na RAM e trabalhe completamente na RAM. Quando o segundo ciclo começa, c e d então carregados do disco para a RAM e funcionam.

outro ciclo

 for(int j=0;j<n;j++){ a[j] += b[j]; c[j] += d[j]; } 

irá gerar dois arrays e uma página em dois outros cada vez ao redor do loop . Isso obviamente será muito mais lento.

Você provavelmente não vê o cache de disco em seus testes, mas provavelmente verá os efeitos colaterais de alguma outra forma de armazenamento em cache.


Parece que há um pouco de confusão / incompreensão aqui, então tentarei esclarecer um pouco pelo exemplo.

Diga n = 2 e estamos trabalhando com bytes. Assim, no meu cenário, temos apenas 4 bytes de RAM, e o restante da memória é muito mais lento (digamos, 100 vezes mais acesso).

Supondo uma política de cache bastante estúpida, se um byte não estiver no cache, coloque-o lá e obtenha o próximo byte enquanto estiver nele, você terá um script como este:

  • Com

     for(int j=0;j<n;j++){ a[j] += b[j]; } for(int j=0;j<n;j++){ c[j] += d[j]; } 
  • armazenamos em cache a[0] e a[1] então b[0] b[1] e definimos a[0] = a[0] + b[0] para o cache - agora há quatro bytes no cache, a[0], a[1] e b[0], b[1] . Custo = 100 + 100

  • defina a[1] = a[1] + b[1] no cache. Custo = 1 + 1.
  • Repita para c e d .
  • Custo Total = (100 + 100 + 1 + 1) * 2 = 404

  • Com

     for(int j=0;j<n;j++){ a[j] += b[j]; c[j] += d[j]; } 
  • armazenamos em cache a[0] e a[1] então b[0] b[1] e definimos a[0] = a[0] + b[0] para o cache - agora há quatro bytes no cache, a[0], a[1] e b[0], b[1] . Custo = 100 + 100

  • remova a[0], a[1], b[0], b[1] do cache e cache c[0] c[1] depois d[0] d[1] e defina c[0] = c[0] + d[0] no cache. Custo = 100 + 100
  • Eu suspeito que você está começando a ver para onde estou indo.
  • Custo Total = (100 + 100 + 100 + 100) * 2 = 800

Este é um cenário clássico de cache de lixo.

41
18 дек. A resposta é dada por OldCurmudgeon 18 de dezembro. 2011-12-18 04:36 '11 às 4:36 2011-12-18 04:36

Isso não é devido a um código diferente, mas devido ao armazenamento em cache: a RAM é mais lenta que os registros do processador e a memória cache fica dentro da CPU para evitar que a RAM seja gravada sempre que a variável for alterada. Mas o cache é pequeno, desde RAM, portanto, ele exibe apenas parte dele.

O primeiro código altera os endereços da memória remota, alternando-os em cada ciclo, exigindo, portanto, descartar constantemente o cache.

O segundo código não alterna: ele simplesmente se move para endereços adjacentes duas vezes. Isso faz com que todas as tarefas sejam concluídas no cache, cancelando-as somente após o início do segundo ciclo.

29
17 дек. Resposta dada por Emilio Garavaglia em 17 de dezembro 2011-12-17 23:49 '11 às 11:49 PM 2011-12-17 23:49

Não posso repetir os resultados discutidos aqui.

Eu não sei se o código de teste ruim é o culpado, ou o que, mas esses dois métodos estão dentro de 10% um do outro na minha máquina usando o código a seguir, e um ciclo é geralmente um pouco mais rápido do que dois - como você esperaria.

Tamanhos de array variaram de 2 ^ 16 a 2 ^ 24 usando oito ciclos. Tive o cuidado de inicializar os arrays originais para que a designação += não solicitasse ao FPU adicionar lixo de memória, interpretado como duplo.

Eu joguei com vários esquemas, como colocar a atribuição b[j] , d[j] para InitToZero[j] dentro dos ciclos, bem como usar += b[j] = 1 e += d[j] = 1 , e Eu tenho resultados bastante consistentes.

Como seria de se esperar, a inicialização de b e d dentro do loop usando InitToZero[j] deu uma vantagem à abordagem combinada, uma vez que eles foram executados de perto antes de atribuir a e c , mas ainda dentro de 10%. Vá descobrir.

Hardware - Dell XPS 8500 com processador 3 Core i7 @ 3,4 GHz e 8 GB de memória. Para 2 ^ 16 a 2 ^ 24, usando oito ciclos, o tempo cumulativo foi de 44,987 e 40,965, respectivamente. Visual C ++ 2010 é totalmente otimizado.

PS: Eu mudei os ciclos de contagem regressiva para zero, e o método combinado foi um pouco mais rápido. Arranhando a cabeça Preste atenção ao novo tamanho da matriz e ao número de ciclos.

 // MemBufferMystery.cpp : Defines the entry point for the console application. // #include "stdafx.h" #include <iostream> #include <cmath> #include <string> #include <time.h> #define dbl double #define MAX_ARRAY_SZ 262145 //16777216 // AKA (2^24) #define STEP_SZ 1024 // 65536 // AKA (2^16) int _tmain(int argc, _TCHAR* argv[]) { long i, j, ArraySz = 0, LoopKnt = 1024; time_t start, Cumulative_Combined = 0, Cumulative_Separate = 0; dbl *a = NULL, *b = NULL, *c = NULL, *d = NULL, *InitToOnes = NULL; a = (dbl *)calloc( MAX_ARRAY_SZ, sizeof(dbl)); b = (dbl *)calloc( MAX_ARRAY_SZ, sizeof(dbl)); c = (dbl *)calloc( MAX_ARRAY_SZ, sizeof(dbl)); d = (dbl *)calloc( MAX_ARRAY_SZ, sizeof(dbl)); InitToOnes = (dbl *)calloc( MAX_ARRAY_SZ, sizeof(dbl)); // Initialize array to 1.0 second. for(j = 0; j< MAX_ARRAY_SZ; j++) { InitToOnes[j] = 1.0; } // Increase size of arrays and time for(ArraySz = STEP_SZ; ArraySz<MAX_ARRAY_SZ; ArraySz += STEP_SZ) { a = (dbl *)realloc(a, ArraySz * sizeof(dbl)); b = (dbl *)realloc(b, ArraySz * sizeof(dbl)); c = (dbl *)realloc(c, ArraySz * sizeof(dbl)); d = (dbl *)realloc(d, ArraySz * sizeof(dbl)); // Outside the timing loop, initialize // b and d arrays to 1.0 sec for consistent += performance. memcpy((void *)b, (void *)InitToOnes, ArraySz * sizeof(dbl)); memcpy((void *)d, (void *)InitToOnes, ArraySz * sizeof(dbl)); start = clock(); for(i = LoopKnt; i; i--) { for(j = ArraySz; j; j--) { a[j] += b[j]; c[j] += d[j]; } } Cumulative_Combined += (clock()-start); printf("\n %6i miliseconds for combined array sizes %i and %i loops", (int)(clock()-start), ArraySz, LoopKnt); start = clock(); for(i = LoopKnt; i; i--) { for(j = ArraySz; j; j--) { a[j] += b[j]; } for(j = ArraySz; j; j--) { c[j] += d[j]; } } Cumulative_Separate += (clock()-start); printf("\n %6i miliseconds for separate array sizes %i and %i loops \n", (int)(clock()-start), ArraySz, LoopKnt); } printf("\n Cumulative combined array processing took %10.3f seconds", (dbl)(Cumulative_Combined/(dbl)CLOCKS_PER_SEC)); printf("\n Cumulative seperate array processing took %10.3f seconds", (dbl)(Cumulative_Separate/(dbl)CLOCKS_PER_SEC)); getchar(); free(a); free(b); free(c); free(d); free(InitToOnes); return 0; } 

Não sei por que foi decidido que o MFLOPS era um indicador relevante. Embora a ideia fosse focar no acesso à memória, tentei minimizar o tempo de flutuação. Eu fui para += , mas não tenho certeza do porquê.

Uma atribuição direta sem cálculos seria um teste mais preciso do tempo de acesso à memória e criaria um teste que seria uniforme, independentemente do número de ciclos. Talvez eu tenha perdido alguma coisa na conversa, mas vale a pena pensar duas vezes. Se o sinal de adição não estiver incluído na tarefa, o tempo acumulado será quase o mesmo e será de 31 segundos.

18
30 дек. A resposta é dada por user1899861 30 dez. 2012-12-30 04:34 '12 às 4:34 2012-12-30 04:34

Isso ocorre porque o processador não tem tantos erros de cache (onde é preciso esperar que os dados da matriz venham dos chips de RAM). Seria interessante ajustar o tamanho das matrizes o tempo todo para que você exceda o tamanho do nível de cache 1 (L1) e depois o nível de cache 2 (L2) do seu processador e calcule o tempo gasto na execução do código em relação ao tamanho das matrizes. O gráfico não deve ser direto, como seria de se esperar.

15
17 дек. Resposta dada por James em 17 de dezembro 2011-12-17 23:52 '11 às 11:52 PM 2011-12-17 23:52

O primeiro loop alterna a entrada em cada variável. O segundo e o terceiro fazem apenas pequenos saltos de tamanho de elemento.

Tente escrever duas linhas paralelas de 20 cruzes com uma caneta e uma folha, separadas por 20 centímetros. Tente terminar uma vez e depois outra linha uma vez e tente novamente pressionando a cruz em cada linha alternadamente.

13
17 авг. a resposta é dada Guillaume Kiz 17 ago. 2012-08-17 18:23 '12 às 18:23 2012-08-17 18:23

Pergunta original

Por que um ciclo é muito mais lento que dois?


Conclusão:

O caso 1 é um problema clássico de interpolação ineficaz. Eu também acho que esta foi uma das principais razões pelas quais muitas arquiteturas de máquinas e desenvolvedores terminaram de criar e projetar sistemas multi-core com a capacidade de executar aplicativos multi-threaded, bem como programação paralela.

Considerando isso usando essa abordagem, sem afetar como o hardware, sistema operacional e compilador (s) trabalham juntos para destacar o heap, o que inclui trabalhar com RAM, cache, arquivos de paginação, etc .; A matemática subjacente a esses algoritmos nos mostra qual dessas duas opções é a melhor solução. Podemos usar a analogia, onde Boss ou Summation , que será um For Loop , que deve se mover entre B trabalhadores A B , podemos ver facilmente que o caso 2 é pelo menos 1/2 , com que rapidez, se não um pouco mais, caso 1 por causa da diferença na distância necessária para a viagem e o tempo gasto entre os trabalhadores. Essa matemática é quase virtual e combina perfeitamente com o Bench Mark Times e a diferença nas instruções de montagem.

Agora vou começar a explicar como tudo funciona abaixo.


Avaliando o problema

Código OP:

 const int n=100000; for(int j=0;j<n;j++){ a1[j] += b1[j]; c1[j] += d1[j]; }