Desempenho inesperadamente pobre e estranhamente bimodal para o loop de loja na Intel Skylake

Estou vendo um desempenho inesperadamente fraco para um loop de loja simples que possui dois armazenamentos: um com um avanço de 16 bytes e outro sempre no mesmo local 1 , assim:

volatile uint32_t value; void weirdo_cpp(size_t iters, uint32_t* output) { uint32_t x = value; uint32_t *rdx = output; volatile uint32_t *rsi = output; do { *rdx = x; *rsi = x; rdx += 4; // 16 byte stride } while (--iters > 0); } 

Na assembly esse loop provavelmente 3 se parece com:

 weirdo_cpp: ... align 16 .top: mov [rdx], eax ; stride 16 mov [rsi], eax ; never changes add rdx, 16 dec rdi jne .top ret 

Quando a região de memory acessada estiver em L2, esperaria que isso fosse executado em menos de 3 ciclos por iteração. A segunda loja continua batendo no mesmo local e deve adicionar cerca de um ciclo. A primeira loja implica em trazer uma linha de L2 e, portanto, também despejar uma linha a cada 4 iterações . Não tenho certeza de como você avalia o custo de L2, mas mesmo se você estimar de forma conservadora que o L1 só pode fazer um dos seguintes ciclos: (a) confirmar uma loja ou (b) receber uma linha de L2 ou (c) despeje uma linha para L2, você obteria algo como 1 + 0,25 + 0,25 = 1,5 ciclos para o stream da loja stride-16.

De fato, você comenta uma loja que recebe ~ 1,25 ciclos por iteração apenas para a primeira loja e ~ 1,01 ciclos por iteração para a segunda loja, portanto, 2,5 ciclos por iteração parecem uma estimativa conservadora.

O desempenho real é muito estranho, no entanto. Aqui está uma corrida típica do arnês de teste:

 Estimated CPU speed: 2.60 GHz output size : 64 KiB output alignment: 32 3.90 cycles/iter, 1.50 ns/iter, cpu before: 0, cpu after: 0 3.90 cycles/iter, 1.50 ns/iter, cpu before: 0, cpu after: 0 3.90 cycles/iter, 1.50 ns/iter, cpu before: 0, cpu after: 0 3.89 cycles/iter, 1.49 ns/iter, cpu before: 0, cpu after: 0 3.90 cycles/iter, 1.50 ns/iter, cpu before: 0, cpu after: 0 4.73 cycles/iter, 1.81 ns/iter, cpu before: 0, cpu after: 0 7.33 cycles/iter, 2.81 ns/iter, cpu before: 0, cpu after: 0 7.33 cycles/iter, 2.81 ns/iter, cpu before: 0, cpu after: 0 7.34 cycles/iter, 2.81 ns/iter, cpu before: 0, cpu after: 0 7.26 cycles/iter, 2.80 ns/iter, cpu before: 0, cpu after: 0 7.28 cycles/iter, 2.80 ns/iter, cpu before: 0, cpu after: 0 7.31 cycles/iter, 2.81 ns/iter, cpu before: 0, cpu after: 0 7.29 cycles/iter, 2.81 ns/iter, cpu before: 0, cpu after: 0 7.28 cycles/iter, 2.80 ns/iter, cpu before: 0, cpu after: 0 7.29 cycles/iter, 2.80 ns/iter, cpu before: 0, cpu after: 0 7.27 cycles/iter, 2.80 ns/iter, cpu before: 0, cpu after: 0 7.30 cycles/iter, 2.81 ns/iter, cpu before: 0, cpu after: 0 7.30 cycles/iter, 2.81 ns/iter, cpu before: 0, cpu after: 0 7.28 cycles/iter, 2.80 ns/iter, cpu before: 0, cpu after: 0 7.28 cycles/iter, 2.80 ns/iter, cpu before: 0, cpu after: 0 

Duas coisas são estranhas aqui.

Primeiro são os tempos bimodais: há um modo rápido e um modo lento . Começamos no modo lento, demorando cerca de 7,3 ciclos por iteração e, em algum ponto, transição para cerca de 3,9 ciclos por iteração. Esse comportamento é consistente e reproduzível e os dois intervalos de tempo são sempre consistentes em torno dos dois valores. A transição aparece em ambas as direções, do modo lento para o modo rápido e vice-versa (e, às vezes, várias transições em uma corrida).

A outra coisa estranha é o desempenho muito ruim. Mesmo no modo rápido , em cerca de 3,9 ciclos, o desempenho é muito pior do que o 1,0 + 1,3 = 2,3 ciclos que você esperaria da sum de cada um dos casos com um único armazenamento (e supondo que absolutamente zero trabalhado pode ser sobreposto) quando ambas as lojas estão no loop). No modo lento , o desempenho é péssimo comparado com o que você esperaria com base nos primeiros princípios: ele está consumindo 7,3 ciclos para fazer 2 lojas e, se você colocá-lo em termos de largura de banda de loja L2, são aproximadamente 29 ciclos por loja L2. armazene apenas uma linha de cache completa a cada 4 iterações).

Skylake é registrado como tendo uma taxa de transferência de 64B / ciclo entre L1 e L2, que é muito superior ao throughput observado aqui (cerca de 2 bytes / ciclo em modo lento ).

O que explica o baixo rendimento e o desempenho bimodal e posso evitá-lo?

Também estou curioso para saber se isso se reproduz em outras arquiteturas e até mesmo em outras checkboxs do Skylake. Sinta-se à vontade para include resultados locais nos comentários.

Você pode encontrar o código de teste e o chicote no github . Existe um Makefile para plataformas Linux ou Unix, mas deve ser relativamente fácil de construir no Windows também. Se você quer rodar a variante asm você precisará de nasm ou yasm para o assembly 4 – se você não tem isso, pode tentar a versão C ++.

Possibilidades eliminadas

Aqui estão algumas possibilidades que eu considerei e eliminei em grande parte. Muitas das possibilidades são eliminadas pelo simples fato de você ver a transição de desempenho aleatoriamente no meio do loop de benchmarking , quando muitas coisas simplesmente não mudaram (por exemplo, se ela estava relacionada ao alinhamento do array de saída, não mudar no meio de uma corrida desde o mesmo buffer é usado o tempo todo). Vou me referir a isso como a eliminação padrão abaixo (mesmo para coisas que são a eliminação padrão, muitas vezes há outro argumento a ser feito).

  • Fatores de alinhamento: a matriz de saída é alinhada em 16 bytes e eu tentei alinhamento de até 2 MB sem alteração. Também eliminado pela eliminação padrão .
  • Contenção com outros processos na máquina: o efeito é observado mais ou menos identicamente em uma máquina ociosa e mesmo em uma carga pesada (por exemplo, usando stress -vm 4 ). O benchmark em si deve ser completamente core-local de qualquer maneira, já que cabe em L2, e o perf confirma que há pouquíssimas perdas de L2 por iteração (cerca de 1 erro a cada 300-400 iterações, provavelmente relacionadas ao código printf ).
  • TurboBoost: O TurboBoost é completamente desativado, confirmado por três leituras diferentes de MHz.
  • Economia de energia: o governor de desempenho é intel_pstate no modo de performance . Nenhuma variação de freqüência é observada durante o teste (a CPU permanece essencialmente bloqueada em 2,59 GHz).
  • Efeitos de TLB: O efeito está presente mesmo quando o buffer de saída está localizado em uma página enorme de 2 MB. Em qualquer caso, as 64 inputs TLB de 4k cobrem mais que o buffer de saída de 128K. perf não reporta nenhum comportamento de TLB particularmente estranho.
  • Aliasing 4k: versões mais antigas e complexas deste benchmark mostraram um pouco de aliasing 4k, mas isso foi eliminado, já que não há cargas no benchmark (são cargas que podem incorretamente alias a armazenamentos anteriores). Também eliminado pela eliminação padrão .
  • Conflitos de associação de L2: eliminados pela eliminação padrão e pelo fato de que isso não desaparece mesmo com páginas de 2MB, onde podemos ter certeza de que o buffer de saída é apresentado linearmente na memory física.
  • Efeitos de hyperthreading: o HT está desativado.
  • Pré-busca: Apenas dois dos pré-buscadores poderiam estar envolvidos aqui (os pré-buscadores L1, aka L1, ou L1), já que todos os dados residem em L1 ou L2, mas o desempenho é o mesmo com todos os pré-buscadores habilitados ou todos desabilitados.
  • Interrupções: não há correlação entre contagem de interrupção e modo lento. Existe um número limitado de interrupções totais, principalmente pulsos de clock.

toplev.py

Eu usei o toplev.py, que implementa o método de análise Top Down da Intel e, para surpresa, ele identifica o benchmark como ligado à loja:

 BE Backend_Bound: 82.11 % Slots [ 4.83%] BE/Mem Backend_Bound.Memory_Bound: 59.64 % Slots [ 4.83%] BE/Core Backend_Bound.Core_Bound: 22.47 % Slots [ 4.83%] BE/Mem Backend_Bound.Memory_Bound.L1_Bound: 0.03 % Stalls [ 4.92%] This metric estimates how often the CPU was stalled without loads missing the L1 data cache... Sampling events: mem_load_retired.l1_hit:pp mem_load_retired.fb_hit:pp BE/Mem Backend_Bound.Memory_Bound.Store_Bound: 74.91 % Stalls [ 4.96%] <== This metric estimates how often CPU was stalled due to store memory accesses... Sampling events: mem_inst_retired.all_stores:pp BE/Core Backend_Bound.Core_Bound.Ports_Utilization: 28.20 % Clocks [ 4.93%] BE/Core Backend_Bound.Core_Bound.Ports_Utilization.1_Port_Utilized: 26.28 % CoreClocks [ 4.83%] This metric represents Core cycles fraction where the CPU executed total of 1 uop per cycle on all execution ports... MUX: 4.65 % PerfMon Event Multiplexing accuracy indicator 

Isso realmente não lança muita luz: nós já sabíamos que as lojas deveriam estar bagunçando as coisas, mas por quê? A descrição da Intel da condição não diz muito.

Aqui está um resumo razoável de algumas das questões envolvidas na interação L1-L2.


1 Este é um MCVE muito simplificado do meu loop original, que foi pelo menos 3 vezes o tamanho e que fez muito trabalho adicional, mas exibiu exatamente o mesmo desempenho que esta versão simples, afunilada no mesmo problema misterioso.

3 Em particular, parece exatamente assim se você escreve a assembly manualmente, ou se você a compila com o gcc -O1 (versão 5.4.1), e provavelmente os compiladores mais razoáveis ​​(o volatile é usado para evitar afundar o segundo quase morto armazenar fora do loop).

4 Sem dúvida, você poderia converter isso para a syntax MASM com algumas pequenas edições, já que a assembly é tão trivial. Puxe os pedidos aceitos.

O que eu encontrei até agora. Infelizmente, isso não oferece uma explicação para o fraco desempenho, e nem um pouco para a distribuição bimodal, mas é mais um conjunto de regras para quando você pode ver o desempenho e as notas sobre a atenuação:

  • A taxa de transferência da loja em L2 parece ser, no máximo, uma linha de cache de 64 bytes por três ciclos 0 , colocando um limite superior de ~ 21 bytes por ciclo na taxa de transferência da loja. Dito de outro modo, séries de lojas que falham em L1 e acertam em L2 levarão pelo menos três ciclos por linha de cache tocados.
  • Acima dessa linha de base, há uma penalidade significativa quando as lojas atingidas em L2 são intercaladas com as lojas em uma linha de cache diferente (independentemente de essas lojas terem sido atingidas em L1 ou L2).
  • A penalidade é aparentemente um pouco maior para as lojas próximas (mas ainda não na mesma linha de cache).
  • O desempenho bimodal é pelo menos superficialmente relacionado ao efeito acima, já que no caso de não-intercalação não parece ocorrer, embora eu não tenha uma explicação adicional para isso.
  • Se você garantir que a linha de cache já esteja em L1 antes do armazenamento, por pré-busca ou por uma carga fictícia, o desempenho lento desaparecerá e o desempenho não será mais bimodal.

Detalhes e Fotos

Stride de 64 bytes

A questão original arbitrariamente usou um passo de 16, mas vamos começar com provavelmente o caso mais simples: um passo de 64, ou seja, uma linha de cache completa. Como se vê, os vários efeitos são visíveis com qualquer passo, mas 64 garante um erro de cache L2 em cada passo e, portanto, remove algumas variables.

Vamos também remover a segunda loja por enquanto – então estamos apenas testando um único armazenamento de 64 bytes sobre 64K de memory:

 top: mov BYTE PTR [rdx],al add rdx,0x40 sub rdi,0x1 jne top 

Correndo isso no mesmo chicote acima, eu recebo cerca de 3,05 ciclos / loja 2 , embora haja um pouco de variação comparado ao que eu estou acostumado a ver (você pode até achar um 3.0 lá).

Então, sabemos que provavelmente não faremos melhor do que isso para as lojas sustentadas puramente para L2 1 . Enquanto o Skylake aparentemente tem um throughput de 64 bytes entre L1 e L2, no caso de um stream de lojas, essa largura de banda tem que ser compartilhada para ambos os despejos de L1, e para carregar a nova linha em L1. 3 ciclos parecem razoáveis ​​se for preciso dizer 1 ciclo cada para (a) expulsar a linha de vítima suja de L1 para L2 (b) atualizar L1 com a nova linha de L2 e (c) confirmar o armazenamento em L1.

O que acontece quando você adiciona uma segunda gravação na mesma linha de cache (para o próximo byte, embora não tenha importância) no loop? Como isso:

 top: mov BYTE PTR [rdx],al mov BYTE PTR [rdx+0x1],al add rdx,0x40 sub rdi,0x1 jne top 

Aqui está um histograma do tempo para 1000 execuções do chicote de teste para o loop acima:

  count cycles/itr 1 3.0 51 3.1 5 3.2 5 3.3 12 3.4 733 3.5 139 3.6 22 3.7 2 3.8 11 4.0 16 4.1 1 4.3 2 4.4 

Portanto, a maioria das vezes é agrupada em torno de 3,5 ciclos. Isso significa que essa loja adicional adicionou apenas 0,5 ciclos ao tempo. Pode ser algo como o buffer da loja é capaz de drenar duas lojas para o L1 se eles estão na mesma linha, mas isso só acontece na metade do tempo.

Considere que o buffer de armazenamento contém uma série de lojas como 1, 1, 2, 2, 3, 3 onde 1 indica a linha de cache: metade das posições tem dois valores consecutivos da mesma linha de cache e metade não. Como o buffer de armazenamento está esperando para drenar os armazenamentos, e o L1 está movimentando e aceitando linhas de L2, o L1 estará disponível para um armazenamento em um ponto “arbitrário”, e se estiver na posição 1, 1 talvez o armazena dreno em um ciclo, mas se for em 1, 2 leva dois ciclos.

Note que há outro pico de cerca de 6% de resultados em torno de 3,1 em vez de 3,5. Isso poderia ser um estado estável, onde sempre obtemos o resultado da sorte. Há outro pico de cerca de 3% em ~ 4.0-4.1 – o arranjo “sempre azarado”.

Vamos testar essa teoria observando vários desvios entre a primeira e a segunda loja:

 top: mov BYTE PTR [rdx + FIRST],al mov BYTE PTR [rdx + SECOND],al add rdx,0x40 sub rdi,0x1 jne top 

Tentamos todos os valores de FIRST e SECOND de 0 a 256 em passos de 8. Os resultados, com variados FIRST valores no eixo vertical e SECOND na horizontal:

ciclos / iter para diferentes offsets de lojas

Vemos um padrão específico – os valores brancos são “rápidos” (em torno dos valores 3.0-4.1 discutidos acima para o deslocamento de 1). Os valores amarelos são mais altos, até 8 ciclos, e vermelhos até 10. Os outliers roxos são os mais altos e geralmente são casos em que o “modo lento” descrito no OP entra em ação (geralmente com clock de 18,0 ciclos / iter). Notamos o seguinte:

  • A partir do padrão de células brancas, vemos que obtemos o resultado rápido de ~ 3,5 ciclos desde que a segunda loja esteja na mesma linha de cache ou a próxima em relação à primeira loja. Isso é consistente com a ideia acima de que as lojas para a mesma linha de cache são tratadas com mais eficiência. O motivo de ter a segunda loja na próxima linha de cache funcionando é que o padrão acaba sendo o mesmo, exceto pelo primeiro primeiro access: 0, 0, 1, 1, 2, 2, ... vs 0, 1, 1, 2, 2, ... – onde, no segundo caso, é a segunda loja que primeiro toca cada linha de cache. O buffer da loja não se importa. Assim que você entra em diferentes linhas de cache, você obtém um padrão como 0, 2, 1, 3, 2, ... e aparentemente isso é uma droga?

  • Os “outliers” roxos nunca aparecem nas áreas brancas, portanto, aparentemente, estão restritos ao cenário que já é lento (e o mais lento aqui o torna cerca de 2.5x mais lento: de ~ 8 a 18 ciclos).

Podemos reduzir um pouco e olhar para compensações ainda maiores:

Compensações até 2048

O mesmo padrão básico, apesar de vermos que o desempenho melhora (área verde) à medida que a segunda loja se distancia (à frente ou atrás) da primeira, até piorar novamente em um deslocamento de aproximadamente ~ 1700 bytes. Mesmo na área melhorada, nós só conseguimos no máximo 5,8 ciclos / iteração ainda muito pior do que o desempenho de mesma linha de 3,5.

Se você adicionar qualquer tipo de instrução de carregamento ou pré-busca que avança 3 das lojas, tanto o desempenho geral lento quanto o valor “modo lento” desaparecem:

tudo bom

Você pode transportar isso de volta para o stride original por 16 problemas – qualquer tipo de pré-busca ou carga no loop principal, praticamente insensível à distância (mesmo que esteja atrasado ), corrige o problema e você obtém 2,3 ciclos / iteração, próximo do ideal ideal de 2.0, e igual à sum das duas lojas com loops separados.

Portanto, a regra básica é que os armazenamentos em L2 sem as cargas correspondentes são muito mais lentos do que se o software os pré-buscasse – a menos que o stream de armazenamento inteiro acesse as linhas de cache em um único padrão sequencial. Isso é contrário à ideia de que um padrão linear como esse nunca se beneficia da pré-busca do SW.

Eu realmente não tenho uma explicação detalhada, mas poderia include esses fatores:

  • Ter outras lojas nos buffers de armazenamento pode reduzir a simultaneidade das solicitações indo para L2. Não está claro exatamente quando as lojas que vão perder em L1 alocarão um buffer de loja, mas talvez ocorra perto de quando a loja vai se aposentar e há uma certa quantidade de “lookhead” no buffer de loja para trazer locais L1, então ter lojas adicionais que não vão perder em L1 prejudica a simultaneidade, já que o lookahead não pode ver tantas solicitações que serão perdidas.
  • Talvez haja conflitos para resources L1 e L2, como portas de leitura e gravação, largura de banda entre caches, que são piores com esse padrão de lojas. Por exemplo, quando os armazenamentos em diferentes linhas são intercalados, talvez eles não possam drenar tão rapidamente da fila de lojas (veja acima onde parece que em alguns cenários mais de uma loja pode drenar por ciclo).

Esses comentários do Dr. McCalpin nos fóruns da Intel também são bastante interessantes.


0 Principalmente apenas atingível com o streamer L2 desativado, pois, caso contrário, a contenção adicional no L2 reduz a velocidade para cerca de 1 linha por 3,5 ciclos.

1 Compare isso com as lojas, onde recebo quase exatamente 1,5 ciclos por carga, para uma largura de banda implícita de ~ 43 bytes por ciclo. Isso faz sentido: a largura de banda L1 <-> L2 é de 64 bytes, mas supondo que o L1 esteja aceitando uma linha do L2 ou atendendo solicitações de carga do núcleo a cada ciclo (mas não em paralelo), então você tem 3 ciclos para duas cargas para diferentes linhas L2: 2 ciclos para aceitar as linhas de L2 e 1 ciclo para satisfazer duas instruções de carga.

2 Com a pré busca desativada . Acontece que o pré-buscador L2 compete pelo access ao cache L2 quando ele detecta o access por streaming: mesmo que ele sempre encontre as linhas candidatas e não vá para L3, isso atrasa o código e aumenta a variabilidade. As conclusões geralmente se baseiam na pré-busca, mas tudo é apenas um pouco mais lento (aqui está uma grande bolha de resultados com a pré-busca – você vê cerca de 3,3 ciclos por carga, mas com muita variabilidade).

3 Ele nem precisa estar à frente – a pré-busca de várias linhas por trás também funciona: Eu acho que a pré-busca / carga é executada rapidamente na frente das lojas que são afuniladas para que elas possam avançar de qualquer maneira. Dessa forma, a pré-busca é uma espécie de autocura e parece funcionar com praticamente qualquer valor que você coloca.

O Sandy Bridge possui “pré-busca de hardware de dados L1”. O que isto significa é que, inicialmente, quando você faz sua loja, a CPU precisa buscar dados de L2 em L1; mas depois que isso aconteceu várias vezes o pré-fetcher de hardware percebe o bom padrão sequencial e inicia a pré-busca de dados de L2 para L1 para você, de modo que os dados estejam em L1 ou “a meio caminho para L1” antes que seu código loja.