O que é importante ao otimizar para o cache da CPU (em C)?

Lendo essas duas perguntas , vejo que entender o comportamento do cache da CPU pode ser importante ao lidar com grandes quantidades de dados na memória. Gostaria de entender como o cache funciona para adicionar outra ferramenta à minha caixa de ferramentas de otimização.

Quais são os principais pontos sobre a maneira como o cache da CPU funciona para que eu possa escrever um código que o use de maneira sensata? De maneira semelhante, existe uma maneira de criar um perfil do código para ver se o uso inadequado do cache está atrasando as coisas?

• Mantenha seus dados pequenos, se possível
• Mantenha as coisas que serão acessadas juntas (ou logo após a outra) próximas umas das outras na memória
• Aprenda sobre os parâmetros de otimização do seu compilador
• Leia O que todo programador deve saber sobre memória para obter mais detalhes do que você poderia desejar

A complexidade dessa questão está além da compreensão humana atualmente. (Tem sido assim desde os últimos 5 anos.) Combine isso com o paralelismo de vetores curtos (SIMD) e você tem uma sensação de desesperança de que a otimização manual do código não é mais economicamente viável - não que isso não seja possível, mas seria não será mais econômico.

A abordagem atual consiste em ensinar os computadores a otimizar - fazendo variações de código que calculam as mesmas respostas com estruturas diferentes (loops, estrutura de dados, algoritmos) e avaliando automaticamente o desempenho. As regras para transformações de código são especificadas com um modelo matemático muito rigoroso, para que seja algo que os cientistas da computação possam entender e os computadores possam executar.

A seguir, um link publicado por Larry OBrien em uma de suas respostas .

http://onward-conference.org/2011/images/Pueschel_2011_AutomaticPerformanceProgramming_Onward11.pdf

É bem possível entender e otimizar para caches. Começa com a compreensão do hardware e continua com o controle do sistema. Quanto menos controle você tiver sobre o sistema, menor a probabilidade de obter sucesso. Linux ou Windows executando um monte de aplicativos / threads que não estão ociosos.

A maioria dos caches é um pouco semelhante em suas propriedades, usa parte do campo de endereço para procurar ocorrências, possui profundidade (caminhos) e largura (linha de cache). Alguns têm buffers de gravação, outros podem ser configurados para gravar ou ignorar o cache em gravações, etc.

Você precisa estar ciente de todas as transações de memória que estão ocorrendo nesse cache (alguns sistemas possuem caches de instruções e dados independentes, facilitando a tarefa).

Você pode facilmente tornar um cache inútil não gerenciando cuidadosamente sua memória. Por exemplo, se você tiver vários blocos de dados que estiver processando, na esperança de mantê-los no cache, mas eles estiverem na memória em endereços até múltiplos em relação à verificação de acertos / perdidos dos caches, diga 0x10000 0x20000 0x30000 e você terá mais de Como essas maneiras no cache, você pode acabar rapidamente criando algo que é muito lento com o cache ativado, mais lento do que faria com o cache desativado. Mas mude isso para talvez 0x10000, 0x21000, 0x32000 e isso pode ser suficiente para aproveitar ao máximo o cache, reduzindo os despejos.

Resumindo, a chave para otimizar um cache (além de conhecer o sistema muito bem) é manter todas as coisas pelas quais você precisa de desempenho no cache ao mesmo tempo, organizando esses dados para que seja possível ter tudo no cache de uma vez. E impedir que coisas como execução de código, interrupções e outros eventos regulares ou aleatórios despejem partes significativas desses dados que você está usando.

O mesmo vale para o código. É um pouco mais difícil, pois você precisa controlar os locais onde o código está localizado para evitar colisões com outro código que você deseja manter no cache. Ao testar / criar um perfil de qualquer código que passa por um cache que adiciona uma única linha de código aqui e ali ou até mesmo um único nop, qualquer coisa que muda ou altera os endereços onde o código vive de uma compilação para outra para o mesmo código, muda onde as linhas de cache se enquadram nesse código e alteram o que é despejado e o que não é para as seções críticas.

As respostas de nwong e Michael Borgwardt dão bons conselhos.

Além disso, confie primeiro nas otimizações do compilador sobre esses problemas.

Se você estiver usando um compilador GCC recente, poderá usar (com parcimônia) sua __builtin_prefetchfunção. Veja esta resposta no stackoverflow.