Design e codificação para uso efetivo de caches

O uso efetivo do armazenamento significa mantê-lo cheio de instruções e dados que provavelmente serão utilizados.

Os processadores possuem uma hierarquia de memória multinível:

Pipeline de instrução e os registros da CPU
Instrução e cache de dados (s) e os buffers de lookaside de tradução correspondentes
RAM
Disco

Como instruções e dados movem a hierarquia, eles se movem para o armazenamento que é mais rápido do que o nível abaixo dele, mas também menor e mais caro. Para obter o máximo de desempenho possível a partir de uma determinada máquina, portanto, o programador deve fazer o uso mais eficaz do armazenamento disponível em cada nível.

Um obstáculo para alcançar um armazenamento eficiente é o fato de que o armazenamento é alocado em blocos de comprimento fixo, como linhas de cache e páginas de memória reais que geralmente não correspondem a limites dentro de programas ou estruturas de dados. Programas e estruturas de dados que são projetados sem considerar a hierarquia de armazenamento muitas vezes fazem uso ineficiente do armazenamento alocado a eles, com efeitos de desempenho adversos em sistemas pequenos ou fortemente carregados.

Levar em conta a hierarquia de armazenamento significa entender e se adaptar aos princípios gerais de uma programação eficiente em um ambiente de memória cache ou virtual. As técnicas de reembalagem podem render melhorias significativas sem recodificação, e qualquer novo código deve ser projetado com um uso eficiente de armazenamento em mente.

Dois termos são essenciais para qualquer discussão sobre o uso eficiente do armazenamento hierárquico: localidade de referência e conjunto de trabalho.

A localidade de referência de um programa é o grau em que seus endereços de execução de instrução e referências de dados são agrupados em uma pequena área de armazenamento durante um determinado intervalo de tempo.
O conjunto de trabalhos de um programa durante esse mesmo intervalo é o conjunto de blocos de armazenamento que estão em uso, ou, mais precisamente, o código ou os dados que ocupam esses blocos.

Um programa com boa localidade de referência possui um conjunto de trabalhos mínimo, pois os blocos que estão em uso são fortemente embalados com o código ou dados de execução. Um programa funcionalmente equivalente com má localidade de referência tem um conjunto de trabalhos maior, porque mais blocos são necessários para acomodar a gama mais ampla de endereços que estão sendo acessados.

Como cada bloco leva um tempo significativo para carregar em um determinado nível da hierarquia, o objetivo de uma programação eficiente para um sistema hierárquico de armazenamento é projetar e empacotar código de tal forma que o conjunto de trabalhos permaneça tão pequeno quanto prático.

A figura a seguir ilustra a boa e a má prática em um nível subroutine. A primeira versão do programa é embalada na sequência em que provavelmente foi escrita. A primeira subroutine PriSub1 contém o ponto de entrada do programa. Ele sempre usa subroutines primárias PriSub2 e PriSub3. Algumas funções pouco utilizadas do programa requerem subroutines secundários SecSub1 e SecSub2. Em raras ocasiões, as subroutines de erro ErrSub1 e ErrSub2 são necessárias.

Figura 1. Localidade de Referência. A metade superior da figura descreve como um programa binário é empacotado o que mostra baixa localidade de referência. As instruções para **PriSub1** estão no executável binário primeiro, seguido das instruções para **SecSub1**, **ErrSub1**, **PriSub2**, **SecSub2**, **ErrSub2**e **PriSub3**. Neste executável, as instruções para **PriSub1**, **SecSub1**, e **ErrSub1** ocupam na primeira página da memória. As instruções paraPriSub2, **SecSub2**, **ErrSub2** ocupam a segunda página da memória, e as instruções para **PriSub3** ocupam a terceira página da memória. **SecSub1** e **SecSub2** são usados com frequência; também **ErrSub1** e **ErrSub2** raramente são usados, se sempre. Por isso, a embalagem deste programa exibe má localidade de referência e pode usar mais memória do que o necessário. Na segunda metade da figura, **PriSub1**, **PriSub2**, e **PriSub3** estão localizados próximos uns dos outros e ocupam a primeira página da memória. A seguir **PriSub3** é **SecSub1**, **SecSub2**, e **ErrSub1** que todos ocupam a segunda página da memória. Por fim, **ErrSub2** está no final e ocupa a terceira página da memória. Como **ErrSub2** pode nunca ser necessário, ele reduziria os requisitos de memória por uma página neste caso.

A versão inicial do programa tem uma localidade pobre de referência porque leva três páginas de memória para correr no caso normal. As subroutines secundárias e de erro separam o caminho principal do programa em três seções, fisicamente distantes.

A versão melhorada do programa coloca as subroutines primárias adjacentes a uma outra e coloca a função de baixa frequência depois disso. As subroutines de erro necessárias (que raramente-usadas) são deixadas no final do programa executável. As funções mais comuns do programa agora podem ser tratadas com apenas um disco de leitura e uma página de memória em vez dos três previamente exigidos.

Lembre-se que localidade de referência e conjunto de trabalhos são definidos com relação ao tempo. Se um programa funciona em estágios, cada um dos quais leva um tempo significativo e usa um conjunto diferente de subroutines, tente minimizar o conjunto de trabalhos de cada etapa.