Cache prefetching

La recuperació prèvia de la memòria cau és una tècnica utilitzada pels processadors d'ordinadors per augmentar el rendiment de l'execució mitjançant l'obtenció d'instruccions o dades del seu emmagatzematge original en una memòria més lenta a una memòria local més ràpida abans que sigui realment necessària (d'aquí el terme 'precaptura').^[1]^[2] La majoria dels processadors d'ordinadors moderns tenen memòria cau ràpida i local en la qual es conserven les dades obtingudes prèviament fins que es requereixen. La font per a l'operació de recuperació prèvia sol ser la memòria principal. A causa del seu disseny, l'accés a les memòries cau acostuma a ser molt més ràpid que l'accés a la memòria principal, de manera que l'obtenció prèvia de dades i l'accés a les memòries cau acostuma a ser molts ordres de magnitud més ràpid que accedir-hi directament des de la memòria principal. La recuperació prèvia es pot fer amb instruccions de control de memòria cau que no bloquegen.^[3]

Obtenció prèvia de dades versus memòria cau d'instruccions

L'obtenció prèvia de la memòria cau pot obtenir dades o instruccions a la memòria cau.

Data prefetching fetches data before it is needed. Because data access patterns show less regularity than instruction patterns, accurate data prefetching is generally more challenging than instruction prefetching.
Instruction prefetching fetches instructions before they need to be executed. The first mainstream microprocessors to use some form of instruction prefetch were the Intel 8086 (six bytes) and the Motorola 68000 (four bytes). In recent years, all high-performance processors use prefetching techniques.

Obtenció prèvia de la memòria cau de maquinari i programari

L'obtenció prèvia de la memòria cau es pot fer mitjançant maquinari o programari.^[4]

L'obtenció prèvia basada en maquinari s'aconsegueix normalment tenint un mecanisme de maquinari dedicat al processador que vigila el flux d'instruccions o dades que sol·licita el programa en execució, reconeix els següents elements que el programa podria necessitar en funció d'aquest flux i s'obté prèviament a la memòria cau del processador.
L'obtenció prèvia basada en programari s'aconsegueix normalment fent que el compilador analitzi el codi i insereix instruccions addicionals de "captura prèvia" al programa durant la pròpia compilació.

Mètodes d'obtenció prèvia de maquinari

Buffers de flux

Els buffers de flux es van desenvolupar basant-se en el concepte d'"esquema OBL (One Block Lookahead)" proposat per Alan Jay Smith.
Els buffers de flux són una de les tècniques d'obtenció prèvia basada en maquinari més comunes que s'utilitzen. Aquesta tècnica va ser proposada originalment per Norman Jouppi l'any 1990 i des de llavors s'han desenvolupat moltes variacions d'aquest mètode. La idea bàsica és que l'adreça de memòria cau falta (i adreces posteriors) s'obtenen en un buffer separat de profunditat. Aquest buffer s'anomena buffer de flux i està separat de la memòria cau. Aleshores, el processador consumeix dades/instruccions de la memòria intermèdia de flux si l'adreça associada als blocs recuperats prèviament coincideix amb l'adreça sol·licitada generada pel programa que s'executa al processador. La figura següent il·lustra aquesta configuració:

Sempre que el mecanisme d'obtenció prèvia detecta un error en un bloc de memòria, per exemple A, assigna un flux per començar a recuperar blocs successius a partir del bloc perdut. Si la memòria intermèdia de flux pot contenir 4 blocs, hauríem d'obtenir prèviament A+1, A+2, A+3, A+4 i mantindrem aquells a la memòria intermèdia de flux assignada. Si el processador consumeix A+1 a continuació, s'ha de moure "amunt" de la memòria intermèdia de flux a la memòria cau del processador. La primera entrada del buffer de flux seria ara A+2 i així successivament. Aquest patró d'obtenció prèvia de blocs successius s'anomena Sequential Prefetching. S'utilitza principalment quan s'han de buscar prèviament ubicacions contigües. Per exemple, s'utilitza quan s'obtenen instruccions prèviament.
Aquest mecanisme es pot augmentar afegint diversos "búfers de flux" d'aquest tipus, cadascun dels quals mantindria un flux d'obtenció prèvia independent. Per a cada nou error, hi hauria un nou buffer de flux assignat i funcionaria de la mateixa manera que es descriu anteriorment.
La profunditat ideal del buffer de flux és una cosa que està subjecta a experimentació amb diversos punts de referència i depèn de la resta de la microarquitectura implicada.

Mètodes d'obtenció prèvia de programari

Obtenció prèvia dirigida pel compilador

La recuperació prèvia dirigida al compilador s'utilitza àmpliament dins de bucles amb un gran nombre d'iteracions. En aquesta tècnica, el compilador prediu futures errades de memòria cau i insereix una instrucció d'obtenció prèvia basada en la penalització per error i el temps d'execució de les instruccions.

Comparació de la recuperació prèvia de maquinari i programari

Tot i que l'obtenció prèvia del programari requereix la intervenció del programador o del compilador, la recuperació prèvia del maquinari requereix mecanismes de maquinari especials.
L'obtenció prèvia del programari només funciona bé amb bucles on hi ha accés regular a la matriu, ja que el programador ha de codificar manualment les instruccions d'obtenció prèvia, mentre que els recuperadors de maquinari funcionen de manera dinàmica en funció del comportament del programa en temps d'execució.
La recuperació prèvia de maquinari també té menys sobrecàrrega de CPU en comparació amb la recuperació prèvia de programari.

Referències

↑ Smith, Alan Jay ACM Comput. Surv., 14, 3, 01-09-1982, pàg. 473–530. DOI: 10.1145/356887.356892. ISSN: 0360-0300.
↑ Li, Chunlin; Song, Mingyang; Du, Shaofeng; Wang, Xiaohai; Zhang, Min (en anglès) Journal of Network and Computer Applications, 165, 01-09-2020, pàg. 102715. DOI: 10.1016/j.jnca.2020.102715.
↑ Mittal, Sparsh «A Survey of Recent Prefetching Techniques for Processor Caches» (en anglès). ACM Computing Surveys, 49, 2, 30-06-2017, pàg. 1–35. DOI: 10.1145/2907071. ISSN: 0360-0300.
↑ Solihin, Yan. Fundamentals of parallel multicore architecture (en anglès americà). Boca Raton, Florida: CRC Press, Taylor & Francis Group, 2016, p. 163. ISBN 978-1482211184.

[:3-1] Smith, Alan Jay ACM Comput. Surv., 14, 3, 01-09-1982, pàg. 473–530. DOI: 10.1145/356887.356892. ISSN: 0360-0300.

[2] Li, Chunlin; Song, Mingyang; Du, Shaofeng; Wang, Xiaohai; Zhang, Min (en anglès) Journal of Network and Computer Applications, 165, 01-09-2020, pàg. 102715. DOI: 10.1016/j.jnca.2020.102715.

[3] Mittal, Sparsh «A Survey of Recent Prefetching Techniques for Processor Caches» (en anglès). ACM Computing Surveys, 49, 2, 30-06-2017, pàg. 1–35. DOI: 10.1145/2907071. ISSN: 0360-0300.

[:2-4] Solihin, Yan. Fundamentals of parallel multicore architecture (en anglès americà). Boca Raton, Florida: CRC Press, Taylor & Francis Group, 2016, p. 163. ISBN 978-1482211184.

[1]

[2]

[3]

[4]