Memória hierárquicaEditar

A memória hierárquica é uma otimização de hardware que tira os benefícios da localização espacial e temporal e pode ser usada em vários níveis da hierarquia da memória. Paging obviamente beneficia da localidade espacial e temporal. Um cache é um exemplo simples de exploração da localidade temporal, porque é uma área de memória especialmente projetada, mais rápida mas menor, geralmente usada para manter dados referenciados recentemente e dados próximos a dados referenciados recentemente, o que pode levar a potenciais aumentos de desempenho.

Elementos de dados em um cache não correspondem necessariamente a elementos de dados que estão espacialmente próximos na memória principal; no entanto, elementos de dados são trazidos para o cache uma linha de cache de cada vez. Isso significa que a localidade espacial é novamente importante: se um elemento for referenciado, alguns elementos vizinhos também serão trazidos para o cache. Finalmente, a localidade temporal desempenha um papel no nível mais baixo, uma vez que os resultados que são referenciados muito próximos entre si podem ser mantidos nos registos da máquina. Algumas linguagens de programação (como C) permitem ao programador sugerir que certas variáveis sejam mantidas em registros.

Localidade de dados é uma característica típica de referência de memória de programas regulares (embora existam muitos padrões irregulares de acesso à memória). Ela torna o layout hierárquico da memória rentável. Em computadores, a memória é dividida em uma hierarquia a fim de acelerar os acessos aos dados. Os níveis inferiores da hierarquia da memória tendem a ser mais lentos, mas maiores. Assim, um programa alcançará maior desempenho se usar memória enquanto estiver em cache nos níveis superiores da hierarquia de memória e evitará trazer outros dados para os níveis superiores da hierarquia que deslocarão os dados que serão usados no futuro próximo. Este é um ideal, e às vezes não pode ser alcançado.

Hierarquia de memória típica (tempos de acesso e tamanhos de cache são aproximações de valores típicos usados a partir de 2013 para fins de discussão; valores reais e números reais de níveis na hierarquia variam):

• Registros de CPU (8-256 registros) – acesso imediato, com a velocidade do núcleo mais interno do processador
• Caches de CPU L1 (32 KiB a 512 KiB) – acesso rápido, com a velocidade do barramento de memória mais interno de cada núcleo
• Caches de CPU L2 (128 KiB a 24 MiB) – acesso ligeiramente mais lento, com a velocidade do bus de memória partilhada entre gémeos de núcleos
• Caches de CPU L3 (2 MiB a 32 MiB) – acesso ainda mais lento, com a velocidade do bus de memória partilhada entre ainda mais núcleos do mesmo processador
• Maior memória física (RAM) (256 MiB a 64 GiB) – acesso lento, cuja velocidade é limitada pelas distâncias espaciais e interfaces de hardware gerais entre o processador e os módulos de memória na placa mãe
• Disk (memória virtual, sistema de arquivos) (1 GiB a 256 TiB) – muito lento, devido ao canal de dados mais estreito (em largura de bit), fisicamente muito mais longo entre a placa principal do computador e os dispositivos de disco, e devido ao protocolo de software externo necessário no topo da interface de hardware lento
• Memória memorizada (outros computadores ou a nuvem) (praticamente ilimitada) – a velocidade varia de muito lenta a extremamente lenta

Máquinas modernas tendem a ler blocos de memória inferior para o próximo nível da hierarquia da memória. Se isso deslocar a memória utilizada, o sistema operacional tenta prever quais dados serão menos acessados (ou mais recentes) e movê-los para baixo na hierarquia da memória. Algoritmos de previsão tendem a ser simples para reduzir a complexidade do hardware, embora eles estejam se tornando um pouco mais complicados.

Matrix multiplicationEdit

Um exemplo comum é a multiplicação de matrizes:

for i in 0..n for j in 0..m for k in 0..p C = C + A * B;

Alternando a ordem de looping para j e k, a velocidade em grandes multiplicações de matrizes torna-se dramática, pelo menos para linguagens que colocam elementos contíguos de matrizes na última dimensão. Isto não vai alterar o resultado matemático, mas melhora a eficiência. Neste caso, “grande” significa, aproximadamente, mais de 100.000 elementos em cada matriz, ou memória endereçável suficiente para que as matrizes não caibam em caches L1 e L2.

for i in 0..n for k in 0..p for j in 0..m C = C + A * B;

A razão para esta velocidade é que no primeiro caso, as leituras de A estão em cache (já que o índice k é o contíguo, última dimensão), mas B não está, portanto há uma penalização de falta de cache em B. C é irrelevante, porque pode ser içada para fora do loop interno — a variável de loop lá é k.

for i in 0..n for j in 0..m temp = C for k in 0..p temp = temp + A * B; C = temp

No segundo caso, as leituras e escritas de C estão ambas em cache, as leituras de B estão em cache, e a leitura de A pode ser içada para fora do loop interno.

for i in 0..n for k in 0..p temp = A for j in 0..m C = C + temp * B;

Assim, o segundo exemplo não tem penalidade de falta de cache no loop interno enquanto que o primeiro exemplo tem uma penalidade de cache.

Em um processador do ano 2014, o segundo caso é aproximadamente cinco vezes mais rápido que o primeiro, quando escrito em C e compilado com gcc -O3. (Um exame cuidadoso do código desmontado mostra que no primeiro caso, o GCC usa instruções SIMD e no segundo caso não, mas a penalidade de cache é muito pior do que o ganho SIMD.)

Localidade temporal também pode ser melhorada no exemplo acima, usando uma técnica chamada bloqueio. A matriz maior pode ser dividida em sub-matriz de tamanho uniforme, para que os blocos menores possam ser referenciados (multiplicados) várias vezes enquanto na memória.

for (ii = 0; ii < SIZE; ii += BLOCK_SIZE) for (kk = 0; kk < SIZE; kk += BLOCK_SIZE) for (jj = 0; jj < SIZE; jj += BLOCK_SIZE) maxi = min(ii + BLOCK_SIZE, SIZE); for (i = ii; i < maxi; i++) maxk = min(kk + BLOCK_SIZE, SIZE); for (k = kk; k < maxk; k++) maxj = min(jj + BLOCK_SIZE, SIZE); for (j = jj; j < maxj; j++) C = C + A * B;

A localização temporal da solução acima é fornecida porque um bloco pode ser usado várias vezes antes de seguir em frente, para que ele seja movido para dentro e para fora da memória com menos freqüência. A localização espacial é melhorada porque elementos com endereços de memória consecutivos tendem a ser puxados para cima na hierarquia da memória.