Precarga de caché

La precarga de caché es una técnica utilizada por los procesadores de computadoras para aumentar el rendimiento de 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 'precarga'). ^[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 precargados hasta que se necesitan. La fuente para la operación de precarga 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 precarga 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 precarga se puede realizar con instrucciones de control de caché no bloqueantes .

Precarga de caché de datos frente a caché de instrucciones

La precarga de caché puede recuperar datos o instrucciones en la caché.

La precarga 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 instrucciones, la precarga de datos precisa suele ser más difícil que la precarga de instrucciones.
La precarga de instrucciones permite obtener instrucciones antes de que sea necesario ejecutarlas. Los primeros microprocesadores convencionales que utilizaron alguna forma de precarga 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 precarga.

Precarga de caché de hardware y de software

La precarga de caché se puede realizar mediante hardware o software. ^[3]

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

Métodos de precarga de hardware

Buffers de transmisión

Los buffers de flujo se desarrollaron basándose en el concepto de "esquema de mirada hacia adelante de un bloque (OBL)" propuesto por Alan Jay Smith . ^[1]
Los buffers de flujo son una de las técnicas de precarga basadas en hardware más comunes en uso. 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 de error de caché (y las direcciones posteriores) se recuperan en un buffer separado de profundidad . Este buffer se denomina buffer de flujo y está separado de la caché. Luego, el procesador consume datos/instrucciones del buffer 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: ${\estilo de visualización k}$ ${\estilo de visualización k}$

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

Precarga con zancadas

Este tipo de precarga monitorea la diferencia entre las direcciones de los accesos a la memoria y busca patrones dentro de ella.

Pasos regulares

En este patrón, se realizan accesos consecutivos a la memoria de bloques que están separados por direcciones. ^[3]^[12] En este caso, el prefetcher calcula y lo utiliza para calcular la dirección de memoria para la precarga. Por ejemplo: si es 4, la dirección que se va a precargar sería A+4. ${\estilo de visualización s}$ ${\estilo de visualización s}$ ${\estilo de visualización s}$

Zancadas espaciales irregulares

En este caso, la diferencia entre las direcciones de accesos consecutivos a la memoria es variable, pero sigue un patrón. Algunos diseños de prefetchers ^[9]^[13]^[14] aprovechan esta propiedad para predecir y prefetchear futuros accesos.

Precarga temporal irregular

Esta clase de prefetchers busca secuencias de acceso a memoria que se repiten en el tiempo. ^[15]^[16] Por ejemplo, en esta secuencia 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, ...; la secuencia A, B, C se repite en el tiempo. Otras variaciones de diseño han intentado proporcionar implementaciones más eficientes y de mayor rendimiento. ^[17]^[18]

Precarga colaborativa

Las aplicaciones informáticas generan una variedad de patrones de acceso. Las arquitecturas del subsistema de memoria y del procesador que se utilizan 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 eficacia y la eficiencia de los esquemas de precarga suelen depender de la aplicación y de las arquitecturas que se utilizan para ejecutarlas. ^[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 precarga para lograr una mejor cobertura y precisión de la precarga.

Métodos de precarga de software

Precarga dirigida por el compilador

La precarga dirigida por el compilador se utiliza 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 precarga en función de la penalización por error y el tiempo de ejecución de las instrucciones.

Estas precapturas son operaciones de memoria no bloqueantes, es decir, estos accesos a la memoria no interfieren con los accesos reales a la memoria. No modifican el estado del procesador ni provocan fallos de página.

Una ventaja principal de la precarga 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 precarga al código para mejorar el rendimiento de la caché .

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

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

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

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

Aquí, el paso de precarga 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 haber - lo que significa que el sistema debería precargar 7 elementos por adelantado. Con la primera iteración, i será 0, por lo que el sistema precarga el séptimo elemento. Ahora, con esta disposición, los primeros 7 accesos (i=0->6) seguirán siendo errores (bajo la suposición simplificadora de que cada elemento de array1 está en una línea de caché separada propia). ${\estilo de visualización k}$ $k=49/7=7$

Comparación de precarga de hardware y software

Mientras que la precarga de software requiere la intervención de un programador o compilador , la precarga de hardware requiere mecanismos de hardware especiales. ^[3]
La precarga de software funciona bien sólo con bucles donde hay acceso regular a la matriz, ya que el programador tiene que codificar manualmente las instrucciones de precarga, mientras que los precargadores de hardware funcionan dinámicamente en función del comportamiento del programa en tiempo de ejecución . ^[3]
La precarga de hardware también tiene menos sobrecarga de CPU en comparación con la precarga de software. ^[22] Sin embargo, la precarga de software puede mitigar ciertas limitaciones de la precarga de hardware, lo que lleva a mejoras en el rendimiento. ^[23]

Métricas de precarga de caché

Hay tres métricas principales para evaluar la precarga de caché ^[3]

Cobertura

La cobertura es la fracción de errores totales que se eliminan debido a la precarga, es decir,

$Cobertura={\frac {\text{Errores de caché eliminados mediante precarga}}{\text{Errores de caché totales}}}$ ,

dónde, ${\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 prefetches que fueron útiles, es decir, la relación entre el número de direcciones de memoria prefetches que fueron realmente referenciadas por el programa y el total de prefetches realizados.

${\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 precapturas en sí mismas podrían generar nuevos errores si los bloques precapturados se colocan directamente en la memoria caché. Si bien estos pueden ser una pequeña fracción del número total de errores observados sin ninguna precaptura, este es un número de errores distinto de cero.

Oportunidad

La definición cualitativa de puntualidad es la anticipación con la que se obtiene un bloque en comparación con el momento en que se hace referencia a él. A continuación, se ofrece un ejemplo para explicar con más detalle la puntualidad:

Considere un bucle for en el que cada iteración tarda 3 ciclos en ejecutarse y la operación de "precarga" tarda 12 ciclos. Esto implica que para que los datos precargados sean útiles, el sistema debe iniciar las iteraciones de precarga antes de su uso para mantener la puntualidad. $12/3=4$

Véase también

Referencias

^ ab Smith, Alan Jay (1 de septiembre de 1982). "Memorias caché". ACM Comput. Surv . 14 (3): 473–530. doi :10.1145/356887.356892. ISSN 0360-0300. S2CID 6023466.
^ Li, Chunlin; Song, Mingyang; Du, Shaofeng; Wang, Xiaohai; Zhang, Min; Luo, Youlong (1 de septiembre de 2020). "Reemplazo de caché basado en prioridad adaptativo y precarga de caché basada en predicción en un entorno de computación de borde". Revista de aplicaciones informáticas y de redes . 165 : 102715. doi :10.1016/j.jnca.2020.102715. S2CID 219506427.
^ abcdef Solihin, Yan (2016). Fundamentos de la arquitectura multinúcleo paralela . Boca Raton, Florida: CRC Press, Taylor & Francis Group. p. 163. ISBN 978-1482211184.
^ Baer, Jean-Loup; Chen, Tien-Fu (1 de enero de 1991). Un esquema eficaz de precarga en chip para reducir la penalización por acceso a datos . Conferencia ACM/IEEE sobre supercomputación de 1991. Albuquerque, Nuevo México, EE. UU.: Association for Computing Machinery. pp. 176–186. CiteSeerX 10.1.1.642.703 . doi :10.1145/125826.125932. ISBN . 978-0897914598.
^ Kennedy, Porterfield, Allan (1 de enero de 1989). Métodos de software para mejorar el rendimiento de la memoria caché en aplicaciones de supercomputadoras (Tesis). Universidad Rice. hdl :1911/19069.{{cite thesis}}: CS1 maint: multiple names: authors list (link)
^ abc Jouppi, Norman P. (1990). "Mejora del rendimiento de la caché de mapeo directo mediante la adición de una pequeña caché totalmente asociativa y búferes de precarga". Actas del 17.º simposio internacional anual sobre arquitectura informática – ISCA 1990. 17.º simposio internacional anual sobre arquitectura informática – ISCA 1990. Nueva York, Nueva York, EE. UU.: 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.
^ Chen, Tien-Fu; Baer, Jean-Loup (1995-05-01). "Precarga de datos basada en hardware eficaz para procesadores de alto rendimiento". IEEE Transactions on Computers . 44 (5): 609–623. doi :10.1109/12.381947. ISSN 0018-9340. S2CID 1450745.
^ Palacharla, S.; Kessler, RE (1994-01-01). Evaluación de los buffers de flujo como reemplazo de caché secundaria . 21.° Simposio internacional anual sobre arquitectura informática. Chicago, Illinois, EE. UU.: IEEE Computer Society Press. pp. 24–33. CiteSeerX 10.1.1.92.3031 . doi :10.1109/ISCA.1994.288164. ISBN . 978-0818655104.
^ ab Grannaes, Marius; Jahre, Magnus; Natvig, Lasse (2011). "Precarga de hardware con almacenamiento eficiente mediante tablas de predicción de correlación delta". Journal of Instruction-Level Parallelism (13): 1–16. CiteSeerX 10.1.1.229.3483 .
^ Ishii, Yasuo; Inaba, Mary; Hiraki, Kei (8 de junio de 2009). "Access map pattern matching for data cache prefetch". Actas de la 23.ª Conferencia Internacional sobre Supercomputación . ICS 2009. Nueva York, Nueva York, EE. UU.: Association for Computing Machinery. págs. 499–500. doi :10.1145/1542275.1542349. ISBN 978-1-60558-498-0. Número de identificación del sujeto 37841036.
^ Srinath, Santhosh; Mutlu, Onur; Kim, Hyesoon ; Patt, Yale N. (febrero de 2007). Prefetching dirigido por retroalimentación: mejora del rendimiento y la eficiencia del ancho de banda de los prefetchers de hardware. 2007 IEEE 13th International Symposium on High Performance Computer Architecture. págs. 63–74. doi :10.1109/HPCA.2007.346185. ISBN 978-1-4244-0804-7.S2CID6909725 .
^ Kondguli, Sushant; Huang, Michael (noviembre de 2017). T2: Un precargador de pasos de alta precisión y eficiencia energética. Conferencia internacional IEEE sobre diseño informático (ICCD) de 2017. págs. 373–376. doi :10.1109/ICCD.2017.64. ISBN 978-1-5386-2254-4.S2CID11055312 .
^ Shevgoor, Manjunath; Koladiya, Sahil; Balasubramonian, Rajeev; Wilkerson, Chris; Pugsley, Seth H.; Chishti, Zeshan (diciembre de 2015). Precarga eficiente de patrones de direcciones complejos. 48.° Simposio internacional anual IEEE/ACM sobre microarquitectura (MICRO) de 2015. págs. 141–152. doi :10.1145/2830772.2830793. ISBN 9781450340342.S2CID 15294463 .
^ Kim, Jinchun; Pugsley, Seth H.; Gratz, Paul V.; Reddy, AL Narasimha; Wilkerson, Chris; Chishti, Zeshan (octubre de 2016). Búsqueda anticipada basada en confianza de ruta. 49.° Simposio internacional anual IEEE/ACM sobre microarquitectura (MICRO) de 2016. págs. 1–12. doi :10.1109/MICRO.2016.7783763. ISBN 978-1-5090-3508-3.S2CID1097472 .
^ Joseph, Doug; Grunwald, Dirk (1997-05-01). "Prefetching using Markov predictors". Actas del 24º Simposio Internacional Anual sobre Arquitectura de Computadores . ISCA 1997. ISCA 1997. Nueva York, Nueva York, EE. UU.: Association for Computing Machinery. págs. 252–263. doi :10.1145/264107.264207. ISBN 978-0-89791-901-2.S2CID 434419 .
^ Collins, J.; Sair, S.; Calder, B.; Tullsen, DM (noviembre de 2002). Precarga asistida por caché de punteros. 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. Número de identificación del sujeto 5608519.
^ Jain, Akanksha; Lin, Calvin (7 de diciembre de 2013). "Linearización de accesos irregulares a memoria para mejorar la precarga correlacionada". Actas del 46.º Simposio Internacional Anual IEEE/ACM sobre Microarquitectura . MICRO-46. Nueva York, Nueva York, EE. UU.: Association for Computing Machinery. págs. 247–259. doi :10.1145/2540708.2540730. ISBN . 978-1-4503-2638-4.S2CID 196831 .
^ "Cómo hacer prácticos los prefetchers temporales: el prefetcher MISB – Artículos de investigación – Investigación de Arm – Comunidad de Arm". community.arm.com . 24 de junio de 2019 . Consultado el 16 de marzo de 2022 .
^ Kim, Jinchun; Teran, Elvira; Gratz, Paul V.; Jiménez, Daniel A.; Pugsley, Seth H.; Wilkerson, Chris (12 de mayo de 2017). "Eliminar el contador de programa: reconstrucción del comportamiento del programa en la jerarquía de caché del procesador". Avisos SIGPLAN de ACM . 52 (4): 737–749. doi : 10.1145/3093336.3037701 . ISSN 0362-1340.
^ Kondguli, Sushant; Huang, Michael (2 de junio de 2018). "División del trabajo: un enfoque más eficaz para la precarga". Actas del 45.º Simposio internacional anual sobre arquitectura informática . ISCA '18. Los Ángeles, California: IEEE Press. págs. 83–95. doi :10.1109/ISCA.2018.00018. ISBN . 978-1-5386-5984-7. Número de identificación del sujeto 50777324.
^ Pakalapati, Samuel; Panda, Biswabandan (mayo de 2020). Ramo de punteros de instrucción: precarga de hardware espacial basada en clasificadores de punteros de instrucción. 47.° Simposio internacional anual sobre arquitectura informática (ISCA) de la ACM/IEEE de 2020. págs. 118-131. doi :10.1109/ISCA45697.2020.00021. ISBN 978-1-7281-4661-4. Número de identificación del sujeto 218683672.
^ 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.: Association for Computing Machinery. págs. 40–52. doi :10.1145/106972.106979. ISBN 978-0897913805.
^ Lee, Jaekyu y Kim, Hyesoon y Vuduc, Richard (2012), "Cuándo funciona la precarga, cuándo no y por qué" (PDF) , ACM Trans. Archit. Code Optim. , 9 : 1–29, doi :10.1145/2133382.2133384{{citation}}: CS1 maint: multiple names: authors list (link)