Projeto do código para caber no cache da CPU?

Question

Ao escrever simulações meu amigo diz que gosta de tentar escrever o programa pequeno o suficiente para caber em cache. Será que isso tem algum significado real? Eu entendo que o cache é mais rápida do que a RAM ea memória principal. É possível especificar que você deseja que o programa para ser executado a partir do cache ou pelo menos carregar as variáveis ??em cache? Estamos escrevendo simulações de modo que qualquer ganho de desempenho / optimization é um benefício enorme.

Se você souber de qualquer boas ligações explicando cache da CPU, então me aponte nesse sentido.

Answer 1

Pelo menos com um CPU de desktop típico, você não pode realmente especificar muito sobre uso de cache diretamente. Você ainda pode tentar escrever código amigável-cache embora. No lado do código, isso geralmente significa laços de desenrolamento (para apenas um exemplo óbvio) raramente é útil - ele se expande o código, e um processador moderno normalmente minimiza a sobrecarga de looping. Geralmente você pode fazer mais no lado dos dados, para melhorar a localidade de referência, proteger contra o falso compartilhamento (por exemplo, duas peças utilizadas com frequência de dados que vão tentar usar a mesma parte do cache, enquanto outras partes permanecem sem uso).

Editar (para fazer alguns pontos um pouco mais explícito):

A CPU típico tem um número de diferentes caches. Um processador de desktop moderno normalmente têm pelo menos 2 e, muitas vezes 3 níveis de cache. Por (pelo menos quase) um acordo universal, "nível 1" é o cache "mais próximo" para os elementos de processamento, e os números vão acima de lá (nível 2 é a próxima, nível 3, depois disso, etc.)

Na maioria dos casos, (pelo menos) o cache de nível 1 é dividido em duas metades: uma cache de instruções e um cache de dados (o Intel 486 é quase a única exceção de que estou consciente, com um único cache para ambos instruções e dados - mas é tão completamente obsoleto provavelmente não merece um monte de pensamento)

.

Na maioria dos casos, um cache é organizado como um conjunto de "linhas". O conteúdo de um cache é normalmente lido, escrito, e rastrearam uma linha de cada vez. Em outras palavras, se a CPU vai usar dados de qualquer parte de uma linha de cache, toda essa linha de cache é lida a partir do próximo nível mais baixo de armazenamento. Caches que estão mais perto da CPU são geralmente menores e têm linhas de cache menores.

Esta arquitetura básicas leva a maioria das características de um cache que importa em escrever código. Tanto quanto possível, você quer ler algo no cache uma vez, fazer tudo com ele que você vai, em seguida, passar para outra coisa.

Isto significa que, como você está processando dados, é tipicamente melhor para ler uma quantidade relativamente pequena de dados (pouco o suficiente para caber no cache), fazer o máximo de processamento em que os dados como você pode, em seguida, passar para a próximo bloco de dados. Algoritmos como Quicksort que rapidamente quebram grandes quantidades de entrada em pedaços cada vez menores fazer isso mais ou menos automaticamente, para que eles tendem a ser bastante-cache amigável, quase independentemente dos detalhes precisos do cache.

Isto também tem implicações na forma como você escreve código. Se você tem um loop como:

for i = 0 to whatever
   step1(data);
   step2(data);
   step3(data);
end for

Você é geralmente melhor amarrando como muitos dos passos juntos, como você pode até o valor que vai caber no cache. O minuto que você estourar o cache, o desempenho pode / vai cair drasticamente. Se o código para o passo 3 acima, foi grande o suficiente para que ele não iria caber no cache, você geralmente ser melhor para quebrar o ciclo se em duas partes como este (se possível):

for i = 0 to whatever
    step1(data);
    step2(data);
end for

for i = 0 to whatever
    step3(data);
end for

Curva desenrolar é um assunto bastante muito disputado. Por um lado, ele pode chumbo ao código que é muito mais amiga do CPU, reduzindo a sobrecarga de instruções executadas para o próprio loop. Ao mesmo tempo, ele pode (e geralmente faz) tamanho aumento código, por isso é relativamente cache de hostil. Minha própria experiência é que em benchmarks sintéticos que tendem a fazer realmente pequenas quantidades de processamento em realmente grandes quantidades de dados, que você ganhar um monte de desdobramento de loop. No código mais prático, onde você tende a ter mais processamento em uma peça individual de dados, você ganha muito menos - e transbordando o cache levando a uma perda de desempenho sério não é particularmente raro em tudo

.

O cache de dados também é limitado em tamanho. Isso significa que você geralmente quer embalado seus dados tão densamente quanto possível, para o máximo de dados possível vai caber no cache. Apenas para um exemplo óbvio, uma estrutura de dados que está vinculado, juntamente com necessidades ponteiros para ganhar um pouco em termos de complexidade computacional para compensar for a quantidade de espaço de cache de dados utilizados por esses ponteiros. Se você estiver indo para usar uma estrutura de dados associada, geralmente você quer, pelo menos, garantir que você está ligando em conjunto relativamente grandes pedaços de dados.

Em muitos casos, no entanto, eu descobri que truques que eu aprendi originalmente para a montagem de dados em minúsculas quantidades de memória em processadores minúsculos que foram (principalmente) obsoleto por décadas, funciona muito bem em processadores modernos. A intenção é agora para caber mais dados no cache em vez da memória principal, mas o efeito é quase o mesmo. Em muito poucos casos, você pode pensar de instruções da CPU como quase livre, e a velocidade geral de execução é regido pela largura de banda para o cache (ou a memória principal), processamento de modo extra para dados descompactação de um formato densa funciona em seu favor. Isto é particularmente verdadeiro quando você está lidando com dados suficientes de que ele não vai caber tudo no cache em tudo mais, então a velocidade geral é regido pela largura de banda para a memória principal. Neste caso, você pode executar um muito de instruções para salvar uma memória poucos lê, e ainda sair na frente.

O processamento paralelo pode agravar o problema. Em muitos casos, reescrever o código para permitir o processamento paralelo pode levar a praticamente nenhum ganho de desempenho, ou às vezes até mesmo uma perda de desempenho. Se a velocidade geral é regido pela largura de banda da CPU à memória, ter mais núcleos concorrentes para que a largura de banda é improvável que fazer algo de bom (e pode fazer danos substanciais). Em tal caso, um, uso de múltiplos núcleos para melhorar a velocidade muitas vezes se resume a fazer ainda mais para embalar os dados com mais força, e tirando partido da potência ainda mais o processamento para descompactar os dados, de modo que o ganho de velocidade real é de reduzir a largura de banda consumida e os núcleos extras apenas não perder tempo para descompactar os dados do formato mais denso.

Outro problema baseada em cache que podem surgir na codificação paralela está compartilhando (e falso compartilhamento) de variáveis. Se dois (ou mais) núcleos necessidade de escrever para o mesmo local na memória, a realização linha de cache que os dados podem acabar sendo empurrados para trás e para frente entre os núcleos de dar a cada um o acesso principal para os dados compartilhados. O resultado é muitas vezes o código que é executado mais lentas em paralelo do que em série (isto é, em um único núcleo). Há uma variação deste chamado de "falso compartilhamento", em que o código sobre os diferentes núcleos está escrevendo para separar os dados, e os dados para os diferentes núcleos acaba na mesma linha de cache. Uma vez que os dados de controles de cache puramente em termos de todo linhas de dados, os dados são embaralhadas e para trás entre os núcleos de qualquer maneira, levando a exatamente o mesmo problema.

Answer 2

Aqui está um link para um realmente bom em caches / otimização de memória por Christer Ericsson (de God of War I / II / III fama). É um par de anos, mas ainda é muito relevante.

Answer 3

Um papel útil que irá dizer-lhe mais do que você sempre quis saber sobre caches é O que cada programador deve saber sobre memória por Ulrich Drepper. Hennessey cobre muito bem. Christer e Mike Acton ter escrito um monte de coisas boas sobre isso também.

Eu acho que você deveria se preocupar mais com cache de dados do cache de instruções - na minha experiência, dcache acidentes são mais frequentes, mais doloroso e mais útil fixo.

Answer 4

UPDATE: 2014/01/13 De acordo com esta designer de chips sênior, erros de cache são agora o fator esmagadoramente dominante no desempenho do código, então estamos basicamente todo o caminho de volta para meados da década de 80 e rápidos 286 fichas em termos dos gargalos de desempenho relativas de carga, armazenamento, integer acidentes aritmética e cache.

Um Bater Curso Em Modern Hardware por Cliff Clique @ Azul . . . . .

--- nós agora voltar para o seu programa regularmente agendado ---

Às vezes, um exemplo é melhor do que uma descrição de como fazer alguma coisa. Nesse espírito, aqui está um exemplo particularmente bem sucedido de como eu mudei alguns códigos para uma melhor utilização de caches de chips. Isso foi feito há algum tempo em uma CPU 486 e último migrou para uma 1ª Geração Pentium CPU. O efeito sobre o desempenho foi semelhante.

Exemplo: Subscrito Mapeamento

Aqui está um exemplo de uma técnica que eu usei para ajustar os dados em cache do chip que tem utilidade para fins gerais.

Eu tinha um vector flutuador duplo que foi 1.250 elementos de comprimento, que era uma curva de epidemiologia com muito longas caudas. A parte "interessante" da curva só tinha cerca de 200 valores únicos, mas eu não queria que a 2-sided if () teste para fazer uma bagunça de gasoduto da CPU (assim as caudas longas, o que poderia usar como subscritos a mais extremas os valores do código de Monte Carlo iria cuspir), e eu precisava a lógica de previsão de desvio para uma dúzia de outros testes condicionais dentro do "hot-spot" no código.

I em um regime onde utilizado um vector de inteiros de 8 bits como um índice para o vector dupla, que I reduzido para 256 elementos. As pequenas ints todos tinham os mesmos valores antes 128 à frente do zero, e 128 depois de zero, portanto, exceto para os 256 valores médios, todos eles apontaram para o primeiro ou o último valor na dupla vetor.

Este encolheu o requisito de armazenamento de 2k para as duplas e 1.250 bytes para os subscritos de 8 bits. Este encolhido 10.000 bytes para baixo para 3.298. Desde que o programa passou de 90% ou mais de seu tempo neste inner-loop, os 2 vetores nunca foi empurrado para fora do cache de dados de 8k. O programa imediatamente dobrou sua performance. Este código foi atingido ~ 100 bilhões de vezes no processo de computar um valor OEA para 1+ milhões de empréstimos hipotecários.

Uma vez que as caudas da curva foram raramente tocado, é muito possível que apenas os 200-300 elementos do meio da pequena vetor int foram realmente mantidos em cache, juntamente com 160-240 duplos médias representando 1 / 8ths de porcentagens de interesse . Foi um notável aumento no desempenho, realizado em uma tarde, em um programa que eu passei mais de uma otimização ano.

Eu concordo com Jerry, como tem sido a minha experiência também, que a inclinação do código para o cache de instrução não é tão bem sucedido como otimizar para os dados de cache / s. Esta é uma razão que eu acho que caches comuns da AMD não são tão úteis como caches de dados e instruções separados da Intel. IE: você não quer instruções monopolizando o cache, como ele simplesmente não é muito útil. Em parte, isso ocorre porque conjuntos de instruções CISC foram originalmente criados para compensar a grande diferença entre as velocidades de CPU e memória, e com exceção de uma aberração no final dos anos 80, que é muito bonito sempre foi verdade.

Outra técnica favorita eu uso para favorecer o cache de dados, e selvagem do cache de instruções, é usando um monte de bit-ints em definições de estrutura, e os menores tamanhos possíveis dados em geral. Para mascarar um int 4-bit para segurar o mês do ano, ou 9 bits para segurar o dia do ano, etc, etc, requer as máscaras de uso da CPU para mascarar os números inteiros de acolhimento os bits estão usando, o que reduz o dados, efetivamente aumenta tamanhos de cache e de autocarros, mas exige mais instruções. Embora esta técnica produz código que não funcionar tão bem com dados de referência sintéticos, em sistemas onde o uso ocupadors e processos estão competindo por recursos, ele funciona maravilhosamente.

Answer 5

Na maior parte isso vai servir como um espaço reservado até eu conseguir tempo para fazer este tema justiça, mas eu queria compartilhar o que eu considero ser um marco verdadeiramente inovador - a introdução de instruções de manipulação de bits dedicados no novo microprocessador Intel Hazwell.

Ele tornou-se dolorosamente óbvio quando escrevi algum código aqui na StackOverflow para reverter os bits em uma matriz de 4096 bits que mais de 30 anos após a introdução do PC, microprocessadores só não dedicar muita atenção ou recursos em pedaços, e que espero vai mudar. Em particular, eu gostaria de ver, para começar, o tipo bool tornar-se um tipo de dados bit real em C / C ++, em vez do byte ridiculamente desperdício é atualmente.

UPDATE: 2013/12/29

Recentemente, tive a oportunidade de otimizar um buffer de anel que mantém o controle de demandas 512 dos usuários de recursos diferentes em um sistema de granularidade milissegundo. Há um temporizador que dispara a cada milissegundo que somados a soma de solicitações de recursos da fatia mais atual e subtraído os pedidos do 1000 época de fatia, compreendendo solicitações de recursos agora 1.000 milissegundos de idade.

O Chefe, vetores da cauda eram bem próximas umas das outras na memória, exceto quando pela primeira vez a cabeça, em seguida, a cauda enrolada e começou a voltar no início da matriz. A fatia (rolamento) Resumo no entanto estava na, uma matriz fixa estaticamente alocada que não era particularmente perto de qualquer daqueles, e não foi ainda atribuída a partir da pilha.

Pensando nisso, e estudar o código de algumas particularidades me chamou a atenção.

1. As demandas que foram chegando foram adicionados ao Chefe ea fatia Resumo, ao mesmo tempo, ao lado uns dos outros em linhas adjacentes de código.

2. Quando o cronômetro acionado, a cauda foi subtraído para fora da fatia Resumo, e os resultados foram deixados na fatia Resumo, como seria de esperar

3. A segunda função chamada quando o temporizador disparou avançado todos os ponteiros atendendo o anel. Em particular.... O Chefe substituiu a cauda, ??ocupando assim a mesma posição de memória A nova cauda ocuparam as 512 posições de memória próximos, ou envolto

4. O usuário queria mais flexibilidade no número de demandas a ser gerido, 512-4098, ou talvez mais. Senti a forma mais robusta, à prova de idiota para fazer isso foi para alocar ambos os 1.000 fatias de tempo e a fatia resumo todos juntos como um bloco contíguo de memória de forma que seria impossível para a fatia Resumo acabar sendo um comprimento diferente do que as outras 1.000 fatias de tempo.

5. Face ao exposto, comecei a me perguntar se eu poderia obter mais desempenho, se, em vez de ter a fatia Resumo permanecem em um local, eu tinha "roam" entre a cabeça e a cauda, ??por isso foi sempre ao lado da cabeça para a adição de novas demandas, e ao lado da cauda quando o temporizador disparou e os valores da cauda tiveram que ser subtraído do Resumo.

Eu fiz exatamente isso, mas, em seguida, encontrei um par de otimizações adicionais no processo. Mudei o código que calculou o Resumo de rolamento para que ele deixou os resultados in the Tail, em vez da fatia Resumo. Por quê? Porque a própria função seguinte estava realizando um memcpy () para mover a fatia Resumo na memória apenas ocupado pela cauda. (Estranho, mas é verdade, a cauda leva a cabeça até o final do anel quando se envolve). Ao deixar os resultados do somatório in the Tail, eu não tinha para executar a memcpy (), eu só tinha para atribuir pTail para pSummary.

De maneira semelhante, o novo Chefe ocupado posição de memória velho Resumo agora obsoleto da fatia, por isso novamente, eu só atribuído pSummary para pHead, e zerou todos os seus valores com um memset para zero.

Liderando o caminho até o final do anel (realmente um tambor, 512 faixas de largura) foi a cauda, ??mas eu só tive quecomparar o ponteiro contra um ponteiro pEndOfRing constante para detectar essa condição. Todos os outros ponteiros poderia ser atribuído o valor do ponteiro do vetor logo à frente dele. IE: Eu só precisava de um teste condicional para 1: 3 dos ponteiros para envolvê-los corretamente.

O projeto inicial tinha usado ints byte para maximizar o uso de cache, no entanto, eu era capaz de relaxar essa restrição - satisfazer os usuários solicitar para lidar com as contagens de recursos mais elevados por usuário por milissegundo - para usar calções não assinados e ainda desempenho dupla , porque mesmo com 3 vetores adjacentes de 512 calções não assinados, cache de dados de 32K do cache L1 poderia facilmente segurar o exigido 3.720 bytes, 2 / 3rds de que estavam em locais pouco utilizados. Apenas quando a cauda, ??Resumo, ou cabeça enrolada eram um do três separados por qualquer "passo" significativo no 8MB L3cache.

O consumo de memória de tempo de execução total para este código está sob 2MB, então ele é executado inteiramente fora de caches on-chip, e até mesmo em um chip i7 com 4 núcleos, 4 instâncias desse processo pode ser executado sem qualquer degradação na o desempenho de todo, e de transferência total sobe ligeiramente com 5 processos de execução. É uma Opus Magnum no uso de cache.

Answer 6

compiladores maioria C / C ++ preferem otimizar para tamanho ao invés de "velocidade". Ou seja, código menor geralmente executa mais rapidamente do que o código desenrolado por causa dos efeitos de cache.

Answer 7

Se eu fosse você, eu teria certeza eu sei que partes do código são hotspots, que defino como

• um loop que não contenham quaisquer chamadas de função, porque se chama qualquer função, em seguida, o PC estará gastando mais de seu tempo nessa função,
• que representa uma fração significativa do tempo de execução (como> = 10%), que você pode determinar a partir de um profiler. (Eu só provar a pilha manualmente.)

Se você tem um tal hotspot, então ele deve caber no cache. Eu não sei como você diga a ele para fazer isso, mas eu suspeito que é automático.