4

O que significa o termo?

Qual é a diferença entre "código não amigável de cache" e o "código amigável de cache"?

Como posso ter certeza de que escrevo um código eficiente em cache?

1 Resposta 1

2

Preliminares

Em computadores modernos, apenas as estruturas de memória de nível mais baixo (os registradores) podem mover dados em ciclos de clock únicos. No entanto, os registradores são muito caros e a maioria dos núcleos de computador tem menos de algumas dezenas de registradores. No outro extremo do espectro de memória (DRAM), a memória é muito barata (ou seja, literalmente milhões de vezes mais barata), mas leva centenas de ciclos após uma solicitação para receber os dados. Para preencher essa lacuna entre super-rápido e caro, e superlento e barato, estão as memórias cache, denominadas L1, L2, L3 em velocidade e custo decrescentes. A ideia é que a maior parte do código em execução atingirá um pequeno conjunto de variáveis com frequência e o restante (um conjunto muito maior de variáveis) com pouca frequência. Se o processador não conseguir encontrar os dados no cache L1, ele procurará no cache L2. Se não estiver lá, o cache L3 e, se não estiver, a memória principal. Cada um desses "erros" é caro no tempo.

(A analogia é que a memória cache está para a memória do sistema, assim como a memória do sistema está para o armazenamento em disco rígido. O armazenamento em disco rígido é super barato, mas muito lento).

O armazenamento em cache é um dos principais métodos para reduzir o impacto da latência. Parafraseando Herb Sutter (veja os links abaixo): aumentar a largura de banda é fácil, mas não podemos comprar nossa saída da latência.

Os dados são sempre recuperados por meio da hierarquia de memória (menor == mais rápido para o mais lento). Um acerto/erro de cache (cache miss/hit) geralmente se refere a um acerto/erro no nível mais alto do cache na CPU -- por nível mais alto, quero dizer o maior == mais lento. A taxa de acerto do cache é crucial para o desempenho, pois cada cache fault resulta na busca de dados da RAM (ou pior ...), o que leva muito tempo (centenas de ciclos para a RAM, dezenas de milhões de ciclos para o HDD). Em comparação, a leitura de dados do cache (nível mais alto) geralmente leva apenas alguns ciclos.

Nas arquiteturas de computador modernas, o gargalo de desempenho está saindo do die da CPU (por exemplo, acessando a RAM ou superior). Isso só vai piorar com o tempo. O aumento na frequência do processador atualmente não é mais relevante para aumentar o desempenho. O problema é o acesso à memória. Os esforços de design de hardware em CPUs, portanto, concentram-se fortemente na otimização de caches, pré-busca, pipelines e simultaneidade. Por exemplo, as CPUs modernas gastam cerca de 85% do die em caches e até 99% para armazenar/mover dados!

Há muito a ser dito sobre o assunto. Aqui estão algumas ótimas referências sobre caches, hierarquias de memória e programação adequada:

Conceitos principais para código amigável ao cache

Um aspecto muito importante do código amigável ao cache é o princípio da localidade, cujo objetivo é colocar os dados relacionados próximos à memória para permitir um armazenamento em cache eficiente. Em relação ao cache da CPU, é importante estar ciente das linhas de cache para entender como isso funciona: Como funcionam as linhas de cache?

Os seguintes aspectos particulares são de grande importância para otimizar o cache:

  1. Localidade temporal: quando um determinado local de memória foi acessado, é provável que o mesmo local seja acessado novamente em um futuro próximo. Idealmente, essas informações ainda serão armazenadas em cache nesse ponto.

  2. Localidade espacial: refere-se a colocar dados relacionados próximos uns dos outros. O armazenamento em cache ocorre em muitos níveis, não apenas na CPU. Por exemplo, quando você lê da RAM, geralmente é obtido um pedaço maior de memória do que o especificamente solicitado, porque muitas vezes o programa exigirá esses dados em breve. Os caches de HDD seguem a mesma linha de pensamento. Especificamente para caches de CPU, a noção de linhas de cache é importante.

Use contêineres C++ apropriados

Um exemplo simples de cache-friendly vs cache-unfriendly é std::vector vs std::list do C++. Os elementos de um std::vector são armazenados em memória contígua e, como tal, acessá-los é muito mais amigável ao cache do que acessar elementos em um std::list, que armazena seu conteúdo em qualquer lugar. Isso se deve à localidade espacial.

Uma ilustração muito boa disso é dada por Bjarne Stroustrup neste clipe do Youtube (obrigado a @Mohammad Ali Baydoun pelo link!).

Não negligencie o cache na estrutura de dados e no design do algoritmo

Sempre que possível, tente adaptar suas estruturas de dados e ordem de cálculos de forma a permitir o uso máximo do cache. Uma técnica comum nesse sentido é o cache blocking (versão Archive.org), que é de extrema importância na computação de alto desempenho (conforme por exemplo ATLAS).

Conheça e explore a estrutura implícita dos dados

Outro exemplo simples, que muitas pessoas na área às vezes esquecem é a ordenação da coluna principal (ex. Fortran, Matlab) versus a ordenação da linha principal (ex. C, C++) para armazenar arrays bidimensionais. Por exemplo, considere a seguinte matriz:

1 2
3 4

Na ordenação da linha principal, isso é armazenado na memória como 1 2 3 4; na ordenação da coluna principal, isso seria armazenado como 1 3 2 4. É fácil ver que as implementações que não exploram essa ordenação rapidamente se depararão com problemas de cache (facilmente evitáveis!). Infelizmente, vejo coisas assim com muita frequência em meu domínio (aprendizado de máquina). @MatteoItalia mostrou este exemplo com mais detalhes em sua resposta.

Ao buscar um determinado elemento de uma matriz da memória, os elementos próximos a ela também serão buscados e armazenados em uma linha de cache. Se a ordenação for explorada, isso resultará em menos acessos à memória (porque os próximos valores necessários para cálculos subsequentes já estão em uma linha de cache).

Para simplificar, suponha que o cache compreende uma única linha de cache que pode conter 2 elementos de matriz e que, quando um determinado elemento é buscado na memória, o próximo também é. Digamos que queremos fazer a soma de todos os elementos no exemplo da matriz 2x2 acima (vamos chamá-la de M):

Explorando a ordenação (por exemplo, alterando o índice da coluna primeiro em C++):

M[0][0] (memória) + M[0][1] (em cache) + M[1][0] (memória) + M[1][1] (em cache)
= 1 + 2 + 3 + 4`insira o código aqui`
--> 2 ocorrências de cache, 2 acessos à memória

Não explorando a ordem (por exemplo, alterando o índice de linha primeiro em C++):

M[0][0] (memória) + M[1][0] (memória) + M[0][1] (memória) + M[1][1] (memória)
= 1 + 3 + 2 + 4
--> 0 ocorrências de cache, 4 acessos à memória

Neste exemplo simples, explorar a ordenação dobra aproximadamente a velocidade de execução (já que o acesso à memória requer muito mais ciclos do que computar as somas). Na prática, a diferença de desempenho pode ser muito maior.

Evite ramificações imprevisíveis

As arquiteturas modernas apresentam pipelines e os compiladores estão se tornando muito bons em reordenar o código para minimizar atrasos devido ao acesso à memória. Quando seu código crítico contém ramificações (imprevisíveis), é difícil ou impossível pré-buscar dados. Isso levará indiretamente a mais perdas de cache.

Isso é explicado muito bem aqui (graças a @ 0x90 pelo link): Por que o processamento de uma matriz classificada é mais rápido do que o processamento de uma matriz não classificada?

Evite funções virtuais

No contexto do C++, os métodos virtuais representam uma questão controversa em relação aos erros de cache (existe um consenso geral de que eles devem ser evitados quando possível em termos de desempenho). As funções virtuais podem induzir faltas de cache durante a pesquisa, mas isso só acontece se a função específica não for chamada com frequência (caso contrário, provavelmente seria armazenada em cache), portanto, isso é considerado um problema por alguns. Para referência sobre esse problema, confira: Qual é o custo de desempenho de ter um método virtual em uma classe C++?

Problemas comuns

Um problema comum em arquiteturas modernas com caches de multiprocessador é chamado de falso compartilhamento. Isso ocorre quando cada processador individual está tentando usar dados em outra região de memória e tenta armazená-los na mesma linha de cache. Isso faz com que a linha de cache - que contém dados que outro processador pode usar - seja substituída repetidas vezes. Efetivamente, threads diferentes fazem uns aos outros esperarem induzindo faltas de cache nessa situação. Veja também (obrigado a @Matt pelo link): Como e quando alinhar ao tamanho da linha de cache?

Um sintoma extremo de cache ruim na memória RAM (que provavelmente não é o que você quer dizer neste contexto) é o chamado thrashing. Isso ocorre quando o processo gera continuamente falhas de página (por exemplo, acessa a memória que não está na página atual) que requer acesso ao disco.

Da resposta do Marc Claesen no SOen.

Você deve fazer log-in para responder a esta pergunta.

Esta não é a resposta que você está procurando? Pesquise outras perguntas com a tag .