Padrões de acesso a dados que deixam a CPU realmente irritada

 (blog.weineng.me)
1 pontos por GN⁺ 3 시간 전 | 1 comentários | Compartilhar no WhatsApp
  • Mesmo em um loop que soma os mesmos inteiros, apenas mudar a ordem de acesso pode alterar muito o tempo de execução; o experimento mostra que é possível criar uma permutação mais de 30% mais lenta que o acesso aleatório
  • O acesso linear é rápido, com 133 milhões de ciclos, enquanto o acesso aleatório chega a 1,57 bilhão de ciclos porque a CPU tem dificuldade para prever a próxima posição
  • Ao espaçar os acessos usando linhas de cache e limites de página, o prefetcher e o reaproveitamento de cache ficam mais fracos e, devido às características do cache associativo por conjuntos, a capacidade efetivamente utilizável do L1d cai para cerca de 768 B
  • Com page stride de 8, até a localidade das linhas de cache de PTE é quebrada, registrando 2,06 bilhões de ciclos e se tornando um padrão pior que um embaralhamento aleatório simples
  • Um padrão aproximado visando conflitos de bank/row da DRAM foi um pouco mais lento, com 2,08 bilhões de ciclos, mas é difícil controlá-lo totalmente porque o mapeamento de DRAM dos endereços físicos depende da plataforma

Condições do experimento e base de comparação

  • O objetivo é criar o maior tempo de execução possível alterando apenas a permutação de positions em uma função accumulator fixa que soma os inteiros do array data
  • O tempo de geração de positions é excluído; mede-se apenas o tempo de execução da função de acumulação, em contagem de ciclos via rdtsc
  • O tamanho dos dados é de 2^26 inteiros uint32_t
    • Usa 65.536 páginas
    • Cada página tem 4.096 bytes
    • Cada página contém 1.024 inteiros
  • huge pages estão desativadas
  • A máquina de medição é um sistema x86_64 baseado em Intel Core Ultra 7 268V
    • 8 CPUs
    • L1d total de 320 KiB, L1i total de 512 KiB
    • L2 total de 14 MiB
    • L3 de 12 MiB
  • O código completo está no repositório do GitHub, e o exemplo é executado com g++ -std=c++2a -O3 slowest.cc && taskset -c 3 sudo ./a.out
  • O loop principal é uma forma simples que soma, em ordem, data[pos], apontado por positions[i]

Diferença entre acesso linear e acesso aleatório

  • O padrão mais simples, linear, acessa o array sequencialmente do início ao fim com positions[i] = i
  • O acesso linear levou 132.752.394 ciclos e está entre os mais rápidos, pois a CPU é fortemente otimizada para acesso sequencial
  • Ao transformar positions em uma permutação aleatória com fisher_yates_shuffle, fica difícil para a CPU prever os dados que serão acessados em seguida
  • O acesso aleatório levou 1.572.108.618 ciclos, mais de 10 vezes mais lento que o acesso linear
  • O experimento vai além disso e verifica se é possível criar intencionalmente uma permutação pior que a aleatória

Espaçando acessos por linha de cache e por página

  • O primeiro padrão de degradação organiza positions de modo que acessos consecutivos fiquem sempre separados por uma linha de cache
  • Esse padrão usa apenas um inteiro de 4 bytes em uma linha de cache de 64 bytes e depois passa para a próxima linha de cache
    • Quando voltar à mesma linha de cache, é provável que os dados reutilizáveis já tenham sido expulsos do cache
  • O acesso com espaçamento de linha de cache levou 718.804.156 ciclos, mais de 4 vezes mais lento que a varredura linear
  • Ainda assim, nesse caso, o prefetcher de hardware consegue detectar um padrão simples de streaming sobre data e trazer linhas de cache futuras antecipadamente
  • Muitos prefetchers de dados de hardware da Intel não fazem prefetch atravessando limites de páginas de 4 KiB
  • O padrão seguinte espaça os acessos não por linha de cache, mas por uma página inteira
    • Cada página tem 4.096 bytes
    • Primeiro acessa o mesmo offset de cada página, no formato page_index * elements_per_page + element_index
  • O acesso com espaçamento de página ficou muito mais lento, com 1.411.153.154 ciclos

Cache associativo por conjuntos e distância de reutilização

  • O cache L1d por núcleo da máquina de teste tem 48 KB, 12-way, com 64 sets
  • Como há 64 sets no L1d, os endereços A e A + 4096 bytes são mapeados para o mesmo set do L1d
    • 4.096 bytes equivalem a 64 sets * 64-byte cache line
  • O stride por página faz com que cada loop interno acerte continuamente o mesmo set, em vez de se espalhar de forma uniforme pelos 64 sets
  • Como um set tem apenas 12 ways, se mais de 12 linhas de cache ativas competirem, a CPU precisa expulsar e recarregar linhas repetidamente
  • A capacidade total do L1d é 48 KB, mas a capacidade do L1d útil para esse padrão de acesso fica em torno de 768 B, isto é, 12 ways * 64B
  • O padrão separated_by_a_page acessa 65.536 linhas de cache antes de voltar à mesma linha de cache, portanto a distância de reutilização de linha de cache é 65.536
  • O padrão separated_by_a_page_and_cacheline, que também separa as linhas de cache dentro da página, aumenta a distância de reutilização para 65536 pages * 4096 page size / 64 cacheline size
  • No entanto, o resultado foi 1.408.519.172 ciclos, quase igual ao acesso por página
  • O experimento foi executado no core 3, que tem 2,5 MB de L2 e 48 KB de L1
    • Percorrer 65.536 páginas uma vez acessa 4 MB de dados
    • Isso é maior que a capacidade dos caches private L1/L2 desse core
    • É baixa a chance de a próxima linha de cache necessária ainda estar no private cache
  • Só se pode esperar reutilização no private cache quando a distância de reutilização da linha de cache é menor que aproximadamente 40 mil, isto é, cerca de ((2560+48)*1024/64)

Atormentando page stride, PTE e até a DRAM

  • A variação seguinte é o padrão separated_by_stride_pages_and_cacheline, que acessa não páginas consecutivas, mas em intervalos de N páginas
  • Após medir vários strides, o pior resultado apareceu quando o page stride era 8, ficando mais lento que o acesso aleatório
  • Executado isoladamente com -DSTRIDE=8, ele levou 2.058.425.640 ciclos
  • Uma possível razão para o pico no stride 8 é a tradução de endereços
    • Acessos a endereços virtuais são traduzidos pela MMU para endereços físicos
    • A tradução usa uma page table entry (PTE)
    • Uma PTE tem 8 bytes, e uma linha de cache contém 8 PTEs
    • A avaliação é que, com stride de 8 páginas, além da linha de cache dos dados, uma linha de cache separada para o mapeamento da página também precisa ser buscada a cada vez
  • A etapa final é uma tentativa de atrapalhar até o funcionamento do controlador de DRAM
  • A DRAM é composta por channel, rank, chip, bank, row e column
    • Dentro de um bank há várias rows
    • Para acessar uma row específica, é preciso ativá-la e copiá-la para o row buffer
    • Para acessar outra row no mesmo bank, é preciso fechar a row existente com precharge e ativar a nova row
  • Alternar o acesso entre rows dentro do mesmo bank causa row-buffer conflict, tornando a resposta do controlador de DRAM mais lenta
  • Por outro lado, acessar uma row já aberta gera um row-buffer hit, e usar vários banks ao mesmo tempo permite que o memory controller sobreponha operações
  • A estratégia para criar um padrão lento é a seguinte
    • Converter o virtual page number em physical frame number (PFN) via page table
    • Preservar o page offset para construir o endereço físico
    • Interpretar o endereço físico como DRAM channel, rank, bank group, bank, row e column
    • Acessar repetidamente rows diferentes dentro do mesmo bank, forçando precharge e activation em quase toda requisição
  • Porém, o mapeamento de endereço físico para DRAM channel, rank, bank e row não é documentado e depende da plataforma
    • Pode variar conforme CPU, tipo de memória, configurações de BIOS/firmware, configuração de channel/rank e address hashing
    • Ferramentas como DRAMA ou Sudoku poderiam ser usadas, mas não foi possível fazê-las funcionar nesta máquina de teste
  • Com base no artigo do DRAMA e em experimentos locais, foi feita uma aproximação usando 4 bank groups, 4 banks por group e DRAM_ROW_SHIFT = 18
  • O padrão que também considera conflitos de DRAM bank/row levou 2.082.308.014 ciclos, um pouco mais lento de forma consistente que o stride 8, mas a diferença não é grande
  • Há algumas restrições que impediram criar conflitos de row perfeitos
    • As estimativas de bank group hash, bank hash e row shift podem não estar corretas
    • O stride de 8 páginas acessa intervalos de cerca de 32 KB, então é difícil que estejam na mesma DRAM row
    • Por causa do bank hashing da Intel, na prática vários banks acabam sendo usados simultaneamente
  • Um exemplo de execução completa mostra os seguintes resultados
    • linear: 132.752.394
    • fisher_yates_shuffle: 1.572.108.618
    • separated_by_a_cacheline: 718.804.156
    • separated_by_a_page: 1.411.153.154
    • separated_by_a_page_and_cacheline: 1.408.519.172
    • stride=8 separated_by_stride_pages_and_cacheline: 2.058.425.640
    • separated_by_stride_bank_conflicts_and_cacheline: 2.082.308.014
  • Ao piorar, em sequência, cache, prefetcher, reutilização de linhas de cache, acesso a PTE e características de DRAM bank/row, é possível criar um padrão de soma 33% mais lento que o acesso aleatório
  • Também há formas de tornar a acumulação mais lenta, como acionar modos de economia de energia, mas isso é separado do experimento que altera apenas o padrão de acesso

Leituras relacionadas

1 comentários

 
GN⁺ 3 시간 전
Comentários no Lobste.rs

  • Li com interesse, pensando: então é assim que se parece uma pesquisa interna de desenvolvimento do Windows 11 /s

  • Aprendi isso enquanto criava https://github.com/ob/cache

    • Fiquei curioso sobre como interpretar duas frases do README
      Uma diz que a técnica para gerar números de latência foi vista pela primeira vez no exercício 5.2 da página 476 de Computer Architecture: A Quantitative Approach, e a outra diz que a ideia veio da tese de doutorado de Rafael Héctor Saavedra‑Barrera
      Quero verificar se estão falando de coisas diferentes, se há uma contradição, ou se é a mesma coisa e Saavedra-Barrera é citado em CA:AQA
      Também não está claro se o programa Claude foi excluído da redação do README e, como ele também aparece como contribuidor do repositório, quero primeiro confirmar se as referências são reais

  • Se quiser experimentar um acesso customizado à hierarquia de cache, também recomendo o simulador que criei
    https://github.com/TheCloudlet/Stratum

  • Fico curioso sobre como separaram o overhead de calcular os índices do custo do acesso em si

    • Se a pergunta é sobre como medir apenas os ciclos do accumulator, sem contar junto o tempo para criar positions, usei uma macro que primeiro executa reset e arrange_positions, e depois coloca apenas accumulator(data, positions) entre rdtsc_start() e rdtsc_end()
      Depois disso, imprimi os resultados, validei sum == linear_scan_sum e usei do_not_optimize(sum) para impedir que a otimização eliminasse o cálculo

  • Se formos fazer isso também com os padrões de acesso a dados que os professores ensinaram, primeiro precisamos criar uma classe SafeNumber.java e um membro add(SafeNumber b)
    No próximo semestre, acho que vamos aprender uma arquitetura que coloca isso atrás do Redis para obter desempenho em escala web
    Graças ao Claude, portei o benchmark para Java, e Java SafeNumber[] ficou cerca de 3,6 vezes mais lento que uint32_t[] em C++ no acesso linear, e 52,2 vezes mais lento que o acesso linear em C++ no shuffle Fisher-Yates
    Em tempo absoluto, para 67 milhões de elementos, foram 10.258.584 ns no linear em C++, 36.740.667 ns no linear em Java, 264.856.042 ns no shuffle em C++ e 535.724.208 ns no shuffle em Java; achei impressionante que, no fim, foi “só 4 vezes” mais lento do que eu esperava

    • O multiplicador do Java não é lá muito bom, mas com o Project Valhalla talvez fique mais próximo