A precarga da memoria caché (en inglés: cache prefetching) é 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[1][2]. 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.
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.
A precarga da caché pode ser lograda mediante hardware ou software[3].
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[4].
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[5].
Os buffers de fluxo (stream buffers) foron desenvolvidos baseándose no concepto do esquema OBL (One Block Lookahead) proposto por Alan Jay Smith[1].
Un configuración típica dos buffers de fluxo tal e como foron propostos por Norman Jouppi en 1990Os buffers de fluxo son unha das principais técnicas de precarga por hardware en uso. Esta técnica foi proposta inicialmente por Norman Jouppi en 1990[6] e múltiples variacións deste método foron desenvolvidas dende aquela[7][8][9]. 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[10]. 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[6] e, ademais, depende do resto da microarquitectura implicada[11].
Neste patrón, os accesos a memoria consecutivos realízanse a bloques que están a s enderezos de distancia uns de outros[3][12]. 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.
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[9][13][14] explotan esta propiedade para predicir e precargar accesos futuros.
Este tipo de mecanismos de precarga buscan fluxos de acceso a memoria que se repiten ao longo do tempo[15][16]. 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[17][18].
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[19]. Investigacións recentes[20][21] centráronse na creación de mecanismos colaborativos para utilizar sinerxicamente múltiples esquemas de precarga e lograr unha mellor cobertura e precisión.
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[3].
O seguinte exemplo amosa como a precarga dunha instrución sería engadida ao código para mellorar o rendemento da caché.
Consideremos un bucle coma o inferior:
En cada iteración, o i-ésimo elemento do vector "array1" é accedido. Por iso, o sistema pode precargar os elementos que van ser accedidos en iteracións futuras inserindo unha instrución de precarga como se amosa no recadro inferior:
Aquí, o salto da precarga, k, depende de dous factores: a penalización polo fallo caché e o tempo que se tarda en executar unha soa iteración do bucle for. Por exemplo, se unha iteración do bucle tarda 7 ciclos en executarse e a penalización por fallo caché é de 49 ciclos, debería tomarse , é dicir, o sistema debe precargar 7 elementos por adiantado. Na primeira iteración, i será 0, polo que o sistema precarga o sétimo elemento. Con este enfoque, os 7 primeiros accesos seguirán sendo fallos (baixo a suposición de que cada elemento do vector está nunha liña caché distinta).
Comparación entre as precargas por hardware e software
Mentres que a precarga por software require a intervención do programador ou o compilador, a precarga por hardware require mecanismos hardware especiais[3].
A precarga por software funciona ben só en bucles onde hai un acceso regular a vectores de datos xa que se teñen que codificar manualmente as instrucións de precarga, mentres que os mecanismos de precarga por hardware traballan dinamicamente baseándose no comportamento do programa durante a execución[3].
A precarga por hardware tamén ten menos sobrecarga da CPU en comparación coa precarga por software[22]. Porén, a precarga por software pode mitigar certas limitacións da precarga por hardware, o que leva a melloras no rendemento[23].
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.
,
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.
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 iteracións antes do seu uso para manter a puntualidade.
↑Li, Chunlin; Song, Mingyang; Du, Shaofeng; Wang, Xiaohai; Zhang, Min; Luo, Youlong (2020-09-01). "Adaptive priority-based cache replacement and prediction-based cache prefetching in edge computing environment". Journal of Network and Computer Applications165. doi:10.1016/j.jnca.2020.102715.
↑ 3,03,13,23,33,43,5Solihin, Yan (2016). Fundamentals of parallel multicore architecture. CRC Press, Taylor & Francis Group. ISBN978-1482211184.
↑Baer, Jean-Loup; Chen, Tien-Fu (1991-01-01). "An Effective On-chip Preloading Scheme to Reduce Data Access Penalty". doi:10.1145/125826.125932.
↑Kennedy, Porterfield, Allan (1989-01-01). Software methods for improvement of cache performance on supercomputer applications (Tese). Rice University. hdl:1911/19069.
↑ 6,06,1Jouppi, Norman P. (1990). "Improving direct-mapped cache performance by the addition of a small fully-associative cache and prefetch buffers". 17th annual international symposium on Computer Architecture – ISCA 1990.
↑Chen, Tien-Fu; Baer, Jean-Loup (1995-05-01). "Effective hardware-based data prefetching for high-performance processors". IEEE Transactions on Computers44: 609–623. doi:10.1109/12.381947.
↑Palacharla, S.; Kessler, R. E. (1994-01-01). "Evaluating Stream Buffers As a Secondary Cache Replacement". 21st Annual International Symposium on Computer Architecture.
↑ 9,09,1Grannaes, Marius; Jahre, Magnus; Natvig, Lasse (2011). "Storage Efficient Hardware Prefetching using Delta-Correlating Prediction Tables". Journal of Instruction-Level Parallelism (13): 1–16.
↑Ishii, Yasuo; Inaba, Mary; Hiraki, Kei (2009-06-08). "Access map pattern matching for data cache prefetch". ICS 2009. doi:10.1145/1542275.1542349.
↑Srinath, Santhosh; Mutlu, Onur; Kim, Hyesoon; Patt, Yale N. (February 2007). "Feedback Directed Prefetching: Improving the Performance and Bandwidth-Efficiency of Hardware Prefetchers". 2007 IEEE 13th International Symposium on High Performance Computer Architecture. doi:10.1109/HPCA.2007.346185.
↑Kondguli, Sushant; Huang, Michael (Novembro 2017). "T2: A Highly Accurate and Energy Efficient Stride Prefetcher". 2017 IEEE International Conference on Computer Design (ICCD): 373–376. doi:10.1109/ICCD.2017.64.
↑Kim, Jinchun; Teran, Elvira; Gratz, Paul V.; Jiménez, Daniel A.; Pugsley, Seth H.; Wilkerson, Chris (2017-05-12). "Kill the Program Counter: Reconstructing Program Behavior in the Processor Cache Hierarchy". ACM SIGPLAN Notices52 (4).
↑Kondguli, Sushant; Huang, Michael (2018-06-02). "Division of labor: a more effective approach to prefetching". ISCA '18: 83–95. doi:10.1109/ISCA.2018.00018.
↑Pakalapati, Samuel; Panda, Biswabandan (Maio 2020). "Bouquet of Instruction Pointers: Instruction Pointer Classifier-based Spatial Hardware Prefetching". 2020 ACM/IEEE 47th Annual International Symposium on Computer Architecture (ISCA): 118–131. doi:10.1109/ISCA45697.2020.00021.
↑Callahan, David; Kennedy, Ken; Porterfield, Allan (1991-01-01). Software Prefetching. Fourth International Conference on Architectural Support for Programming Languages and Operating Systems. Santa Clara, California, USA: Association for Computing Machinery. pp. 40–52. ISBN978-0897913805. doi:10.1145/106972.106979.
