Precarga de caché

Técnica de procesamiento informático para aumentar el rendimiento de la memoria

La captación previa de caché es una técnica utilizada por los procesadores de las computadoras para aumentar el rendimiento de la ejecución al recuperar instrucciones o datos de su almacenamiento original en una memoria más lenta a una memoria local más rápida antes de que realmente se necesiten (de ahí el término "búsqueda previa"). ^{[1] [2]} La mayoría de los procesadores de computadoras modernos tienen una memoria caché local y rápida en la que se guardan los datos captados previamente hasta que se necesitan. La fuente de la operación de captación previa suele ser la memoria principal . Debido a su diseño, acceder a las memorias caché suele ser mucho más rápido que acceder a la memoria principal , por lo que la búsqueda previa de datos y luego acceder a ellos desde las cachés suele ser muchos órdenes de magnitud más rápido que acceder a ellos directamente desde la memoria principal. La captación previa se puede realizar con instrucciones de control de caché sin bloqueo .

Captación previa de caché de datos versus instrucciones

La captura previa de caché puede recuperar datos o instrucciones en el caché.

• La captación previa de datos recupera los datos antes de que sean necesarios. Debido a que los patrones de acceso a datos muestran menos regularidad que los patrones de instrucción, la captación previa de datos precisa generalmente es más desafiante que la captación previa de instrucciones.
• La captación previa de instrucciones recupera instrucciones antes de que sea necesario ejecutarlas. Los primeros microprocesadores convencionales que utilizaron algún tipo de captación previa de instrucciones fueron el Intel 8086 (seis bytes) y el Motorola 68000 (cuatro bytes). En los últimos años, todos los procesadores de alto rendimiento utilizan técnicas de captación previa.

Precarga de caché de hardware versus software

La captación previa de caché se puede realizar mediante hardware o software. ^[3]

• La captación previa basada en hardware generalmente se logra al tener un mecanismo de hardware dedicado en el procesador que observa el flujo de instrucciones o datos solicitados por el programa en ejecución, reconoce los siguientes elementos que el programa podría necesitar en función de este flujo y realiza la captación previa en la memoria caché del procesador. . ^[4]
• La captación previa basada en software generalmente se logra haciendo que el compilador analice el código e inserte instrucciones de "captación previa" adicionales en el programa durante la compilación misma. ^[5]

Métodos de captación previa de hardware

Búfers de flujo

• Los buffers de flujo se desarrollaron basándose en el concepto de "esquema de anticipación de un bloque (OBL)" propuesto por Alan Jay Smith . ^[1]
• Los buffers de flujo son una de las técnicas de captación previa basadas en hardware más comunes que se utilizan. Esta técnica fue propuesta originalmente por Norman Jouppi en 1990 ^[6] y desde entonces se han desarrollado muchas variaciones de este método. ^{[7] [8] [9]} La idea básica es que la dirección perdida de caché (y las direcciones posteriores) se recuperan en un búfer de profundidad separado . Este búfer se denomina búfer de flujo y está separado del caché. Luego, el procesador consume datos/instrucciones del búfer de flujo si la dirección asociada con los bloques precargados coincide con la dirección solicitada generada por el programa que se ejecuta en el procesador. La siguiente figura ilustra esta configuración: ${\displaystyle k}$ ${\displaystyle k}$

Una configuración típica de buffer de flujo propuesta originalmente por Norman Jouppi en 1990 ^[6]

• Siempre que el mecanismo de captación previa detecta una falta en un bloque de memoria, digamos A, asigna una secuencia para comenzar a buscar previamente bloques sucesivos desde el bloque faltante en adelante. Si el búfer de flujo puede contener 4 bloques, entonces el procesador buscará previamente A+1, A+2, A+3, A+4 y los mantendrá en el búfer de flujo asignado. Si el procesador consume A+1 a continuación, se moverá "hacia arriba" desde el búfer de flujo al caché del procesador. La primera entrada del buffer de flujo ahora sería A+2 y así sucesivamente. Este patrón de captación previa de bloques sucesivos se denomina captación previa secuencial . Se utiliza principalmente cuando se deben buscar previamente ubicaciones contiguas. Por ejemplo, se utiliza al buscar previamente instrucciones.
• Este mecanismo se puede ampliar agregando múltiples 'búferes de flujo', cada uno de los cuales mantendría un flujo de captación previa separado. ^[10] Para cada nuevo error, se asignará un nuevo búfer de flujo y funcionará de manera similar a la descrita anteriormente.
• La profundidad ideal del buffer de flujo es algo que está sujeto a experimentación con varios puntos de referencia ^[6] y depende del resto de la microarquitectura involucrada. ^[11]

Captación previa a pasos agigantados

Este tipo de captación previa monitorea el delta entre las direcciones de los accesos a la memoria y busca patrones dentro de él.

Pasos regulares

En este patrón, se realizan accesos consecutivos a la memoria a bloques que están separados por direcciones. ^{[3] [12]} En este caso, el captador previo calcula y lo utiliza para calcular la dirección de memoria para la captación previa. Por ejemplo: si es 4, la dirección que se buscará previamente sería A+4. ${\displaystyle s}$ ${\displaystyle s}$ ${\displaystyle s}$

Pasos espaciales irregulares

En este caso, el delta entre las direcciones de accesos consecutivos a la memoria es variable pero aún sigue un patrón. Algunos diseños de captadores previos ^{[9] [13] [14]} explotan esta propiedad para predecir y captar previamente accesos futuros.

Captura previa temporal irregular

Esta clase de captadores previos busca flujos de acceso a la memoria que se repiten con el tiempo. ^{[15] [16]} Ej. En este flujo de memoria se accede a: N, A, B, C, E, G, H, A, B, C, I, J, K, A, B, C, L, M, N, O, A, B, C, ...; la corriente A, B, C se repite en el tiempo. Otras variaciones de diseño han intentado proporcionar implementaciones más eficientes y con mayor rendimiento. ^{[17] [18]}

Captura previa colaborativa

Las aplicaciones informáticas generan una variedad de patrones de acceso. Las arquitecturas de procesador y subsistema de memoria utilizadas para ejecutar estas aplicaciones eliminan aún más la ambigüedad de los patrones de acceso a la memoria que generan. Por lo tanto, la efectividad y eficiencia de los esquemas de captación previa a menudo dependen de la aplicación y las arquitecturas utilizadas para ejecutarlos. ^[19] Investigaciones recientes ^{[20] [21]} se han centrado en la creación de mecanismos de colaboración para utilizar de forma sinérgica múltiples esquemas de captación previa para una mejor cobertura y precisión de la captación previa.

Métodos de captación previa de software

Captación previa dirigida por el compilador

La captación previa dirigida por el compilador se usa ampliamente en bucles con una gran cantidad de iteraciones. En esta técnica, el compilador predice futuros errores de caché e inserta una instrucción de captación previa basada en la penalización por error y el tiempo de ejecución de las instrucciones.

Estas captaciones previas son operaciones de memoria sin bloqueo, es decir, estos accesos a la memoria no interfieren con los accesos a la memoria reales. No cambian el estado del procesador ni provocan fallos de página.

Una de las principales ventajas de la captación previa de software es que reduce el número de errores de caché obligatorios. ^[3]

El siguiente ejemplo muestra cómo se agregaría una instrucción de captación previa al código para mejorar el rendimiento de la caché .

Considere un bucle for como se muestra a continuación:

for ( int i = 0 ; i < 1024 ; i ++ ) { matriz1 [ i ] = 2 * matriz1 [ i ]; }          

En cada iteración, se accede al iésimo elemento de la matriz "array1" ^. Por lo tanto, el sistema puede buscar previamente los elementos a los que se accederá en iteraciones futuras insertando una instrucción de "búsqueda previa" como se muestra a continuación:

for ( int i = 0 ; i < 1024 ; i ++ ) { captación previa ( matriz1 [ i + k ]); matriz1 [ yo ] = 2 * matriz1 [ yo ]; }               

Aquí, el paso de captación previa depende de dos factores: la penalización por error de caché y el tiempo que lleva ejecutar una única iteración del bucle for . Por ejemplo, si una iteración del bucle tarda 7 ciclos en ejecutarse y la penalización por error de caché es de 49 ciclos, entonces debería haberla , lo que significa que el sistema debería buscar previamente 7 elementos por delante. Con la primera iteración, seré 0, por lo que el sistema busca previamente el séptimo elemento. Ahora, con esta disposición, los primeros 7 accesos (i=0->6) aún se perderán (bajo el supuesto simplificador de que cada elemento de la matriz1 está en una línea de caché separada). ${\displaystyle k}$ ${\displaystyle k=49/7=7}$

Comparación de captación previa de hardware y software

• Mientras que la captación previa de software requiere la intervención del programador o del compilador , la captación previa de hardware requiere mecanismos de hardware especiales. ^[3]
• La captación previa de software funciona bien solo con bucles donde hay acceso regular a la matriz, ya que el programador tiene que codificar manualmente las instrucciones de captación previa, mientras que los captadores previos de hardware funcionan dinámicamente según el comportamiento del programa en tiempo de ejecución . ^[3]
• La captación previa de hardware también tiene menos sobrecarga de CPU en comparación con la captación previa de software. ^[22]

Métricas de captación previa de caché

Hay tres métricas principales para juzgar la captación previa de caché ^[3]

Cobertura

La cobertura es la fracción del total de errores que se eliminan debido a la captación previa, es decir

${\displaystyle Coverage={\frac {\text{Cache Misses eliminated by Prefetching}}{\text{Total Cache Misses}}}}$,

dónde, ${\displaystyle {\text{Total Cache Misses}}=({\text{Cache misses eliminated by prefetching}})+({\text{Cache misses not eliminated by prefetching}})}$

Exactitud

La precisión es la fracción del total de captaciones previas que fueron útiles, es decir, la proporción entre el número de direcciones de memoria captadas previamente a las que el programa realmente hizo referencia y el total de captaciones previas realizadas.

${\displaystyle {\text{Prefetch Accuracy}}={\frac {\text{Cache Misses eliminated by prefetching}}{({\text{Useless Cache Prefetches}})+({\text{Cache Misses eliminated by prefetching}})}}}$

Si bien parece que tener una precisión perfecta podría implicar que no hay errores, este no es el caso. Las propias captaciones previas pueden provocar nuevos errores si los bloques captados previamente se colocan directamente en la memoria caché. Aunque estos pueden ser una pequeña fracción del número total de errores observados sin ninguna captación previa, se trata de un número de errores distinto de cero.

Oportunidad

La definición cualitativa de puntualidad es qué tan temprano se busca previamente un bloque versus cuándo realmente se hace referencia a él. Un ejemplo para explicar mejor la puntualidad es el siguiente:

Considere un bucle for donde cada iteración requiere 3 ciclos para ejecutarse y la operación de "búsqueda previa" requiere 12 ciclos. Esto implica que para que los datos captados previamente sean útiles, el sistema debe iniciar las iteraciones de captación previa antes de su uso para mantener la puntualidad. ${\displaystyle 12/3=4}$

Ver también

• Cola de entrada de captación previa
• Captación previa de enlaces
• captador previo
• Instrucción de control de caché

Referencias

1. Smith, Alan Jay (1 de septiembre de 1982). "Recuerdos de caché". Computación ACM. Sobrevivir . 14 (3): 473–530. doi :10.1145/356887.356892. ISSN  0360-0300. S2CID  6023466.
2. Li, Chunlin; Canción, Mingyang; Du, Shaofeng; Wang, Xiaohai; Zhang, Min; Luo, Youlong (1 de septiembre de 2020). "Reemplazo de caché adaptativo basado en prioridad y captación previa de caché basada en predicción en un entorno informático de borde". Revista de aplicaciones informáticas y de redes . 165 : 102715. doi : 10.1016/j.jnca.2020.102715. S2CID  219506427.
3. Solihin, Yan (2016). Fundamentos de la arquitectura multinúcleo paralela . Boca Ratón, Florida: CRC Press, Taylor & Francis Group. pag. 163.ISBN _ 978-1482211184.
4. Baer, ​​Jean-Loup; Chen, Tien-Fu (1 de enero de 1991). "Un esquema eficaz de precarga en chip para reducir las penalizaciones por acceso a datos ". 1991 Conferencia ACM/IEEE sobre Supercomputación. Albuquerque, Nuevo México, EE.UU.: Asociación de Maquinaria de Computación. págs. 176–186. CiteSeerX 10.1.1.642.703 . doi :10.1145/125826.125932. ISBN  978-0897914598.
5. Kennedy, Porterfield, Allan (1 de enero de 1989). Métodos de software para mejorar el rendimiento de la caché en aplicaciones de supercomputadoras (Tesis). Universidad de Rice. hdl :1911/19069.{{cite thesis}}: Mantenimiento CS1: varios nombres: lista de autores ( enlace )
6. Jouppi, Norman P. (1990). "Mejora del rendimiento de la caché asignada directamente mediante la adición de una pequeña caché totalmente asociativa y búferes de captación previa". Actas del 17º simposio internacional anual sobre arquitectura de computadoras - ISCA 1990 . 17º simposio internacional anual sobre Arquitectura de Computadores - ISCA 1990. Nueva York, Nueva York, Estados Unidos: Association for Computing Machinery Press. págs. 364–373. CiteSeerX 10.1.1.37.6114 . doi :10.1145/325164.325162. ISBN  0-89791-366-3.
7. Chen, Tien-Fu; Baer, ​​Jean-Loup (1 de mayo de 1995). "Captura previa de datos eficaz basada en hardware para procesadores de alto rendimiento". Transacciones IEEE en computadoras . 44 (5): 609–623. doi : 10.1109/12.381947. ISSN  0018-9340. S2CID  1450745.
8. Palacharla, S.; Kessler, RE (1 de enero de 1994). Evaluación de Stream Buffers como reemplazo de caché secundario . XXI Simposio Internacional Anual sobre Arquitectura de Computadores. Chicago, Illinois, EE.UU.: IEEE Computer Society Press. págs. 24-33. CiteSeerX 10.1.1.92.3031 . doi :10.1109/ISCA.1994.288164. ISBN  978-0818655104.
9. Grannaes, Marius; Jahré, Magnus; Natvig, Lasse (2011). "Captación previa de hardware de almacenamiento eficiente mediante tablas de predicción de correlación delta". Revista de paralelismo a nivel de instrucción (13): 1–16. CiteSeerX 10.1.1.229.3483 . 
10. Ishii, Yasuo; Inaba, María; Hiraki, Kei (8 de junio de 2009). "Acceda a la coincidencia de patrones de mapas para la captación previa de caché de datos". Actas de la 23ª Conferencia Internacional sobre Supercomputación . ICS 2009. Nueva York, Nueva York, Estados Unidos: Association for Computing Machinery. págs. 499–500. doi :10.1145/1542275.1542349. ISBN 978-1-60558-498-0. S2CID  37841036.
11. Srinath, Santhosh; Mutlu, Onur; Kim, Hyesoon ; Patt, Yale N. (febrero de 2007). Captación previa dirigida por retroalimentación: mejora del rendimiento y la eficiencia del ancho de banda de los captadores previos de hardware. 2007 IEEE 13º Simposio Internacional sobre Arquitectura de Computadoras de Alto Rendimiento. págs. 63–74. doi :10.1109/HPCA.2007.346185. ISBN 978-1-4244-0804-7. S2CID  6909725.
12. Kondguli, Sushant; Huang, Michael (noviembre de 2017). T2: un captador previo de zancada altamente preciso y energéticamente eficiente. Conferencia internacional IEEE 2017 sobre diseño informático (ICCD). págs. 373–376. doi :10.1109/ICCD.2017.64. ISBN 978-1-5386-2254-4. S2CID  11055312.
13. Shevgoor, Manjunath; Koladiya, Sahil; Balasubramonian, Rajeev; Wilkerson, Chris; Pugsley, Seth H.; Chishti, Zeshan (diciembre de 2015). Captura previa eficiente de patrones de direcciones complejos. 2015 48º Simposio Internacional Anual IEEE/ACM sobre Microarquitectura (MICRO). págs. 141-152. doi :10.1145/2830772.2830793. ISBN 9781450340342. S2CID  15294463.
14. Kim, Jinchún; Pugsley, Seth H.; Gratz, Paul V.; Reddy, AL Narasimha; Wilkerson, Chris; Chishti, Zeshan (octubre de 2016). Captación previa basada en la confianza de la ruta. 2016 49º Simposio Internacional Anual IEEE/ACM sobre Microarquitectura (MICRO). págs. 1–12. doi :10.1109/MICRO.2016.7783763. ISBN 978-1-5090-3508-3. S2CID  1097472.
15. José, Doug; Grunwald, Dirk (1 de mayo de 1997). "Captación previa utilizando predictores de Markov". Actas del 24º Simposio Internacional Anual sobre Arquitectura de Computadores . ISCA 1997. ISCA 1997. Nueva York, Nueva York, Estados Unidos: Association for Computing Machinery. págs. 252-263. doi :10.1145/264107.264207. ISBN 978-0-89791-901-2. S2CID  434419.
16. Collins, J.; Sair, S.; Calder, B.; Tullsen, DM (noviembre de 2002). Captación previa asistida por caché de puntero. 35º Simposio Internacional Anual IEEE/ACM sobre Microarquitectura, 2002. (MICRO-35). Actas. págs. 62–73. doi :10.1109/MICRO.2002.1176239. ISBN 0-7695-1859-1. S2CID  5608519.
17. Jainista, Akanksha; Lin, Calvin (7 de diciembre de 2013). "Linealización de accesos irregulares a la memoria para mejorar la captación previa correlacionada". Actas del 46º Simposio Internacional Anual IEEE/ACM sobre Microarquitectura . MICRO-46. Nueva York, Nueva York, Estados Unidos: Asociación de Maquinaria de Computación. págs. 247-259. doi :10.1145/2540708.2540730. ISBN 978-1-4503-2638-4. S2CID  196831.
18. "Hacer prácticos los captadores temporales temporales: el captador previo de MISB - artículos de investigación - investigación de Arm - comunidad de Arm". comunidad.arm.com . 24 de junio de 2019 . Consultado el 16 de marzo de 2022 .
19. Kim, Jinchún; Terán, Elvira; Gratz, Paul V.; Jiménez, Daniel A.; Pugsley, Seth H.; Wilkerson, Chris (12 de mayo de 2017). "Eliminar el contador del programa: reconstruir el comportamiento del programa en la jerarquía de caché del procesador". Avisos ACM SIGPLAN . 52 (4): 737–749. doi : 10.1145/3093336.3037701 . ISSN  0362-1340.
20. Kondguli, Sushant; Huang, Michael (2 de junio de 2018). "División del trabajo: un enfoque más eficaz para la captación previa". Actas del 45º Simposio Internacional Anual sobre Arquitectura de Computadores . ISCA '18. Los Ángeles, California: IEEE Press. págs. 83–95. doi :10.1109/ISCA.2018.00018. ISBN 978-1-5386-5984-7. S2CID  50777324.
21. Pakalapati, Samuel; Panda, Biswabandan (mayo de 2020). Conjunto de punteros de instrucción: captación previa de hardware espacial basada en clasificador de puntero de instrucción. 2020 ACM/IEEE 47º Simposio Internacional Anual sobre Arquitectura de Computadores (ISCA). págs. 118-131. doi :10.1109/ISCA45697.2020.00021. ISBN 978-1-7281-4661-4. S2CID  218683672.
22. Callahan, David; Kennedy, Ken; Porterfield, Allan (1 de enero de 1991). Precarga de software . Cuarta Conferencia Internacional sobre Soporte Arquitectónico para Lenguajes de Programación y Sistemas Operativos. Santa Clara, California, EE.UU.: Asociación de Maquinaria de Computación. págs. 40–52. doi :10.1145/106972.106979. ISBN 978-0897913805.