Cache prefetching

A **precarga da memoria caché** (en ) é unha técnica empregada polos procesadores para mellorar o rendemento dos programas buscando instrucións ou datos dende niveis máis baixos da xerarquía de memoria (onde están almacenados) a niveis máis altos (onde o acceso é máis rápido) antes de que o programa os necesite. A meirande parte dos procesadores modernos posúen unha memoria caché rápida e local na que se almacenan os datos obtidos mediante precarga ata que se requiran. Habitualmente, o lugar de onde proceden os datos é a memoria principal. Polo seu deseño, acceder á memoria caché é tipicamente máis rápido que acceder á memoria principal, polo que recuperar previamente os datos e logo accedelos dende a caché é normalmente varias ordes de magnitude máis veloz que acceder aos datos directamente dende a memoria principal. Cómpre salientar que a precarga pode facerse con instrucións de control de memoria caché non bloqueantes.

## Precarga de datos vs. precarga de instrucións 
A precarga da memoria caché pode consistir en traer con antelación datos ou instrucións á memoria caché.

* A **precarga de datos** (*data prefetching*) busca datos antes de precisalos. Dado que os patróns de acceso a datos adoitan ser menos regulares que os de acceso a instrucións, lograr unha precarga de datos precisa é máis desafiante.
* A **precarga de instrucións** (*instruction prefetching*) busca instrucións antes de precisalas. Os primeiros microprocesadores en usar algún tipo de precarga de instrucións foron o Intel 8086 (seis bytes) e o Motorola 68000 (catro bytes). Nos últimos anos, todos os procesadores de alto rendemento usan técnicas de precarga.

## Precarga por hardware vs precarga por software 
A precarga da caché pode ser lograda mediante hardware ou software.

* A **precarga baseada en hardware** acádase habitualmente tendo unha unidade hardware no procesador que vixía o fluxo de instrucións ou datos que solicita o programa en execución. Segundo estes patróns de acceso, recoñece os seguintes elementos que o programa podería necesitar e precárgaos na caché local do procesador.
* A **precarga baseada en software** acádase habitualmente posuíndo un compilador analizando o código e inserindo, durante a compilación, instrucións no programa que ordenan realizar a precarga.

## Métodos de precarga por hardware 
### Buffers de fluxo 
* Os buffers de fluxo (*stream buffers*) foron desenvolvidos baseándose no concepto do esquema OBL (*One Block Lookahead*) proposto por Alan Jay Smith e múltiples variacións deste método foron desenvolvidas dende aquela. A idea básica é que o enderezo do fallo caché (e os *k* subseguintes enderezos) son buscados e almacenados nun buffer separado de tamaño *k*. Este buffer denomínase buffer de fluxo e está separado da memoria caché. Logo, o procesador toma datos ou instrucións do buffer de fluxo se o enderezo asociado cos bloques precargados coincide co enderezo solicitado polo programa en execución no procesador. Esta configuración pode observarse na figura que acompaña o texto.
* Sempre que o mecanismo de precarga detecta un fallo nun bloque de memoria (chamémoslle A) asigna un fluxo para comezar a precargar os bloques que seguen ao bloque no que se produciu o fallo caché. Se o buffer de fluxo ten espazo para 4 bloques, entón o procesador precargaría A+1, A+2, A+3 e A+4 e manteríaos no buffer de fluxo asignado. Se o procesador solicita o bloque A+1 a continuación, debe moverse "enriba" da memoria intermedia de fluxo á caché do procesador. Entón, a primeira entrada do buffer de fluxo sería agora A+2 e así sucesivamente. Este patrón de precargar sucesivos bloques denomínase **precarga secuencial**. Maioritariamente, úsase cando se deben precargar localizacións contiguas, como é o caso da precarga de instrucións.
* Este mecanismo pode escalarse engadindo múltiples buffers de fluxo, mantendo cada un deles un fluxo de precarga separado. Para cada novo fallo caché, habería un novo buffer de fluxo asignado e operaría dun xeito similar ao descrito con anterioridade.
* O tamaño ideal do buffer de fluxo é un tema que está suxeito a experimentación usando *benchmarks*.

### Precarga por saltos 
A precarga por saltos (*strided prefetching*) monitorea a diferenza (*delta*) entre os enderezos de acceso a memoria e busca patróns nesa variación.

#### Saltos regulares 
Neste patrón, os accesos a memoria consecutivos realízanse a bloques que están a *s* enderezos de distancia uns de outros. Neste caso, o mecanismo de precarga calcula este valor *s* e úsao para computar o enderezo de memoria que se debe precargar. Por exemplo, se o valor de *s* é 4, o enderezo que se precargará é A+4.

#### Saltos espazados irregulares 
Neste caso, a diferenza entre os accesos a memoria consecutivos é variable pero aínda segue algún patrón. Algúns deseños de mecanismos de precarga explotan esta propiedade para predicir e precargar accesos futuros.

#### Precarga temporal irregular 
Este tipo de mecanismos de precarga buscan fluxos de acceso a memoria que se repiten ao longo do tempo. Por exemplo, neste fluxo de accesos a memoria: N, A, B, C, E, G, H, A, B, C, I, J, K, A, B, C, L, M, N, O, A, B, C, ..., o fluxo A, B, C repítese ao longo do tempo.

### Precarga colaborativa 
As aplicacións dun computador xeran unha gran variedade de patróns de acceso. A arquitectura do procesador e do subsistema de memoria para executar estas aplicacións desambiguan aínda máis os patróns de acceso a memoria que xeran. Polo tanto, a eficacia e eficiencia dos esquemas de precarga adoitan depender da aplicación e das arquitecturas usadas para executalos. Investigacións recentes centráronse na creación de mecanismos colaborativos para utilizar sinerxicamente múltiples esquemas de precarga e lograr unha mellor cobertura e precisión.

## Métodos de precarga por software 
### Precarga dirixida por compilador 
A precarga dirixida por compilador é moi usada en bucles con un gran número de iteracións. Nesta técnica, o compilador predí futuros fallos de caché e inserta unha instrución de precarga baseada na penalización por fallo e no tempo de execución das instrucións.

Estas precargas son operacións de memoria non bloqueantes, i.e. estes accesos a memoria non interfiren cos accesos a memoria actuais. Non cambian o estado do procesador nin causan fallos de páxina.

Unha das principais vantaxes deste tipo de precarga é que reduce o número de fallos de caché obrigatorios. Porén, a precarga por software pode mitigar certas limitacións da precarga por hardware, o que leva a melloras no rendemento.

## Métricas da precarga caché 
Existen tres métricas principais para avaliar a precarga caché.

### Cobertura 
A cobertura é a fracción de fallos totais que son evitados grazas á precarga, i.e.

Cobertura = \frac{\text{fallos caché eliminados mediante precarga}}{\text{fallos caché totais}},

onde\text{fallos caché totais} = (\text{fallos caché eliminados mediante precarga}) + (\text{fallos caché non eliminados mediante precarga})

### Precisión 
A precisión é a fracción do total de precargas que foron útiles, é dicir, a proporción do número de enderezos de memoria precargados que foron referenciados polo programa sobre o total de precargas feitas.

\text{Precisión} = \frac{\text{fallos caché eliminados mediante precarga}}{\text{(precargas de caché inútiles)+(fallos caché eliminados mediante precarga)}},

Mentres que aparenta que unha perfecta precisión puidese implicar que non hai fallos, este non é o caso. As precargas por si mesmas poden levar en novos fallos se os bloques precargados se sitúan directamente na caché. Aínda que isto pode ser unha pequena fracción do número total de fallos observados sen ningún tipo de precargas, este é un número non nulo de fallos.

### Puntualidade 
Unha definición cualitativa da puntualidade (*timeliness*) é que pronto un bloque é precargado versus cando é realmente referenciado. Un exemplo para explicar mellor a puntualidade é o seguinte:

Considere un bucle for onde cada iteración tarda tres ciclos en executarse e a operación de precarga, 12 ciclos. Isto supón que, para que os datos precargados sexan útiles, o sistema debe iniciar a precarga 12 / 3 = 4 iteracións antes do seu uso para manter a puntualidade.

## Notas