Localidad de referencia

En informática, la localidad de referencia, también conocida como el principio de localidad, es la tendencia de un procesador a acceder al mismo conjunto de ubicaciones de memoria de forma repetitiva durante un corto periodo de tiempo. Hay dos tipos básicos de localidad de referencia: localidad temporal y espacial. La localidad temporal se refiere a la reutilización de datos y/o recursos específicos dentro de una duración de tiempo relativamente pequeña. La localidad espacial (también denominada localidad de datos) se refiere al uso de elementos de datos dentro de ubicaciones de almacenamiento relativamente cercanas. La localidad secuencial, un caso especial de localidad espacial, ocurre cuando los elementos de datos se organizan y se accede a ellos de forma lineal, como atravesar los elementos en una matriz unidimensional.

La localidad es un tipo de comportamiento predecible que ocurre en los sistemas informáticos. Los sistemas que muestran una fuerte localidad de referencia son excelentes candidatos para la optimización del rendimiento mediante el uso de técnicas como el almacenamiento en caché, la captación previa de memoria y predictores de bifurcación avanzados en la etapa de canalización de un núcleo de procesador.

Tipos de localidad

Hay varios tipos diferentes de localidad de referencia:

• Localidad temporal: Si en un momento se hace referencia a una ubicación de memoria particular, entonces es probable que la misma ubicación se refiera de nuevo en un futuro próximo. Hay proximidad temporal entre referencias adyacentes a la misma ubicación de memoria. En este caso es común hacer esfuerzos para almacenar una copia de los datos referenciados en un almacenamiento de memoria más rápido, para reducir la latencia de referencias posteriores. La localidad temporal es un caso especial de localización espacial (ver más abajo), es decir, cuando la ubicación prospectiva es idéntica a la ubicación actual.
• Localidad espacial: Si una ubicación de almacenamiento particular se hace referencia en un momento determinado, entonces es probable que los lugares de memoria cercanos se refieran en un futuro próximo. En este caso es común intentar adivinar el tamaño y la forma de la zona alrededor de la referencia actual para la que vale la pena preparar un acceso más rápido para la referencia posterior.
  • Localidad de memoria (o Localidad de datos): Localidad espacial explícitamente relacionada con la memoria.
• Localidad de la subdivisión: Si sólo hay algunas alternativas posibles para la parte prospectiva del camino en el espacio de coordinación espacial-temporal. Este es el caso cuando un bucle de instrucción tiene una estructura simple, o el posible resultado de un pequeño sistema de instrucciones de ramificación condicional se limita a un pequeño conjunto de posibilidades. Localidad de la rama no es típicamente localidad espacial ya que las pocas posibilidades pueden estar situadas lejos unos de otros.
• Localidad equitativa: Medio camino entre la localidad espacial y la localidad de rama. Considere un bucle que accede a lugares en un patrón equidistante, es decir, el camino en el espacio de coordenadas espacio-temporal es una línea punteada. En este caso, una simple función lineal puede predecir qué ubicación se accederá en un futuro próximo.

Para beneficiarse de la localidad temporal y espacial, que ocurre con frecuencia, la mayoría de los sistemas de almacenamiento de información son jerárquicos. La localidad equidistante generalmente es compatible con las diversas instrucciones de incremento no triviales de un procesador. Para la ubicación de sucursales, los procesadores contemporáneos tienen predictores de sucursales sofisticados y, sobre la base de esta predicción, el administrador de memoria del procesador intenta recopilar y preprocesar los datos de alternativas plausibles.

Relevancia

Hay varias razones para la localidad. Estas razones son objetivos a alcanzar o circunstancias a aceptar, dependiendo del aspecto. Las razones a continuación no son inconexas; de hecho, la siguiente lista va desde el caso más general hasta casos especiales:

• Predecibilidad: La localidad es simplemente un tipo de comportamiento predecible en los sistemas informáticos.
• Estructura del programa: Localidad ocurre a menudo debido a la forma en que se crean programas informáticos, para el manejo de problemas decisorios. Generalmente, los datos relacionados se almacenan en lugares cercanos en almacenamiento. Un patrón común en el cálculo implica el procesamiento de varios artículos, uno a la vez. Esto significa que si se hace un montón de procesamiento, el único artículo será accedido más de una vez, lo que llevará a la localidad temporal de referencia. Además, pasar al siguiente tema implica que se leerá el siguiente tema, por lo que la localización espacial de referencia, ya que los lugares de memoria suelen leerse en lotes.
• Estructuras de datos lineales: Localidad a menudo ocurre porque el código contiene bucles que tienden a referenciar arrays u otras estructuras de datos por índices. La localidad secuencial, un caso especial de localización espacial, ocurre cuando se organizan y acceden los elementos de datos pertinentes de forma lineal. Por ejemplo, la simple traversal de elementos en una matriz unidimensional, desde la dirección base hasta el elemento más alto explotaría la localidad secuencial de la matriz en memoria. Localidad equidistante ocurre cuando la traversal lineal está sobre un área más larga de estructuras de datos adyacentes con estructura y tamaño idénticos, accediendo a elementos mutuamente correspondientes de cada estructura en lugar de cada estructura entera. Este es el caso cuando una matriz está representada como una matriz secuencial de filas y el requisito es acceder a una sola columna de la matriz.
• Eficiencia del uso de la jerarquía de memoria: Aunque la memoria de acceso aleatorio presenta al programador con la capacidad de leer o escribir en cualquier lugar en cualquier momento, en la práctica latencia y el rendimiento se ven afectados por la eficiencia del caché, que se mejora aumentando la localidad de referencia. La mala localización de los resultados de referencia en la contaminación de caché y caché y para evitarlo, los elementos de datos con mala localidad pueden ser evitados de caché.

Uso general

Si la mayor parte del tiempo, la parte sustancial de las referencias se agregan en grupos, y si la forma de este sistema de grupos se puede predecir bien, entonces se puede usar para optimizar el rendimiento. Hay varias formas de beneficiarse de la localidad utilizando técnicas de optimización. Las técnicas comunes son:

• Aumentar la localidad de referencias (generalmente en el lado del software)
• Explorando la localidad de referencias: Generalmente logrado en el lado del hardware, la localidad temporal y espacial puede ser capitalizada por hardware de almacenamiento jerárquico. La localidad equidistante puede ser utilizada por las instrucciones adecuadamente especializadas de los procesadores, esta posibilidad no es sólo la responsabilidad del hardware, sino también el software, si su estructura es adecuada para compilar un programa binario que llama las instrucciones especializadas en cuestión. La localidad ramera es una posibilidad más elaborada, por lo que se necesita más esfuerzo en desarrollo, pero hay una reserva mucho mayor para la exploración futura en este tipo de localidad que en todos los restantes.

Uso de localidad espacial y temporal

Memoria jerárquica

La memoria jerárquica es una optimización de hardware que aprovecha los beneficios de la localidad espacial y temporal y se puede usar en varios niveles de la jerarquía de la memoria. La paginación obviamente se beneficia de la localidad temporal y espacial. Un caché es un ejemplo simple de explotación de la localidad temporal, porque es un área de memoria especialmente diseñada, más rápida pero más pequeña, generalmente utilizada para mantener los datos a los que se hace referencia recientemente y los datos cerca de los datos a los que se hace referencia recientemente, lo que puede generar aumentos potenciales en el rendimiento.

Los elementos de datos en un caché no necesariamente corresponden a elementos de datos que están espacialmente cerca en la memoria principal; sin embargo, los elementos de datos se introducen en la caché una línea de caché a la vez. Esto significa que la localidad espacial vuelve a ser importante: si se hace referencia a un elemento, algunos elementos vecinos también se incluirán en la memoria caché. Finalmente, la localidad temporal juega un papel en el nivel más bajo, ya que los resultados que están referenciados muy de cerca pueden guardarse en los registros de la máquina. Algunos lenguajes de programación (como C) permiten al programador sugerir que ciertas variables se mantengan en registros.

La localidad de datos es una característica de referencia de memoria típica de los programas regulares (aunque existen muchos patrones irregulares de acceso a la memoria). Hace que el diseño de memoria jerárquica sea rentable. En las computadoras, la memoria se divide en una jerarquía para acelerar el acceso a los datos. Los niveles más bajos de la jerarquía de memoria tienden a ser más lentos, pero más grandes. Por lo tanto, un programa logrará un mayor rendimiento si utiliza la memoria mientras está almacenada en caché en los niveles superiores de la jerarquía de la memoria y evita llevar otros datos a los niveles superiores de la jerarquía que desplazarán los datos que se utilizarán en breve en el futuro. Este es un ideal, ya veces no se puede lograr.

Jerarquía de memoria típica (los tiempos de acceso y los tamaños de caché son aproximaciones de los valores típicos utilizados a partir de 2013 con fines de discusión; los valores reales y la cantidad real de niveles en la jerarquía varían):

• CPU registra (8-256 registros) – acceso inmediato, con la velocidad del núcleo más interior del procesador
• L1 CPU caches (32 KB a 512 KB) – acceso rápido, con la velocidad del bus de memoria más interior propiedad exclusiva de cada núcleo
• L2 CPU caches (128 KB a 24 MB) – acceso ligeramente más lento, con la velocidad del autobús de memoria compartido entre gemelos de núcleos
• L3 CPU caches (2 MB hasta un máximo de 64 MB) – incluso un acceso más lento, con la velocidad del autobús de memoria compartido entre más núcleos del mismo procesador
• Memoria física principal (RAM) (256 MB a 64 GB) – acceso lento, cuya velocidad se ve limitada por las distancias espaciales y las interfaces generales de hardware entre el procesador y los módulos de memoria en el tablero
• Disco (memoria virtual, sistema de archivos) (1 GB a 256 TB) – muy lento, debido al más estrecho (en ancho de bit), físicamente mucho más largo canal de datos entre la placa principal del equipo y los dispositivos de disco, y debido al protocolo de software extraneoso necesario en la parte superior de la interfaz de hardware lenta
• Memoria remota (otros ordenadores o la nube) (prácticamente ilimitada) – la velocidad varía de muy lento a extremadamente lento

Las máquinas modernas tienden a leer bloques de memoria inferior al siguiente nivel de la jerarquía de memoria. Si esto desplaza la memoria usada, el sistema operativo intenta predecir qué datos se accederán menos (o los últimos) y los moverá hacia abajo en la jerarquía de la memoria. Los algoritmos de predicción tienden a ser simples para reducir la complejidad del hardware, aunque cada vez son más complicados.

Multiplicación de matrices

Un ejemplo común es la multiplicación de matrices:

para i dentro 0..n para j dentro 0..m para k dentro 0..p C[i[ ]j] = C[i[ ]j] + A[i[ ]k] * B[k[ ]j];

Al cambiar el orden de bucle para j y k, la aceleración en las multiplicaciones de matrices grandes se vuelve dramática, al menos para los lenguajes que colocan elementos de matriz contiguos en la última dimensión. Esto no cambiará el resultado matemático, pero mejora la eficiencia. En este caso, "grande" significa, aproximadamente, más de 100.000 elementos en cada matriz, o suficiente memoria direccionable para que las matrices no quepan en las cachés L1 y L2.

para i dentro 0..n para k dentro 0..p para j dentro 0..m C[i[ ]j] = C[i[ ]j] + A[i[ ]k] * B[k[ ]j];

La razón de esta aceleración es que en el primer caso, las lecturas de A[i][k] están en caché (dado que el índice k es el índice contiguo, última dimensión), pero B[k][j] no lo es, por lo que hay una penalización por pérdida de caché en B[k][j]. C[i][j] es irrelevante, porque se puede sacar del bucle interno; la variable de bucle allí es k.

para i dentro 0..n para j dentro 0..m tempestad = C[i[ ]j] para k dentro 0..p tempestad = tempestad + A[i[ ]k] * B[k[ ]j]; C[i[ ]j] = tempestad

En el segundo caso, las lecturas y escrituras de C[i][j] están ambas en caché, las lecturas de B[k][j] están en caché, y la lectura de A[i][k] se puede sacar del bucle interno.

para i dentro 0..n para k dentro 0..p tempestad = A[i[ ]k] para j dentro 0..m C[i[ ]j] = C[i[ ]j] + tempestad * B[k[ ]j];

Por lo tanto, el segundo ejemplo no tiene penalización por pérdida de caché en el bucle interno, mientras que el primer ejemplo tiene una penalización por caché.

En un procesador del año 2014, el segundo caso es aproximadamente cinco veces más rápido que el primero, cuando se escribe en C y se compila con gcc -O3. (Un examen cuidadoso del código desensamblado muestra que en el primer caso, GCC usa instrucciones SIMD y en el segundo no, pero la penalización de caché es mucho peor que la ganancia SIMD).

La localidad temporal también se puede mejorar en el ejemplo anterior usando una técnica llamada bloqueo. La matriz más grande se puede dividir en submatrices de tamaño uniforme, de modo que los bloques más pequeños se pueden referenciar (multiplicar) varias veces mientras están en la memoria. Tenga en cuenta que este ejemplo funciona para matrices cuadradas de dimensiones TAMAÑO x TAMAÑO, pero se puede ampliar fácilmente para matrices arbitrarias sustituyendo TAMAÑO_I, TAMAÑO_J y TAMAÑO_K cuando corresponda.

para ()ii = 0; ii . TAMAÑO; ii += BLOCK_SIZE) para ()kk = 0; kk . TAMAÑO; kk += BLOCK_SIZE) para ()jj = 0; jj . TAMAÑO; jj += BLOCK_SIZE) maxi = min()ii + BLOCK_SIZE, TAMAÑO); para ()i = ii; i . maxi; i++) maxk = min()kk + BLOCK_SIZE, TAMAÑO); para ()k = kk; k . maxk; k++) maxj = min()jj + BLOCK_SIZE, TAMAÑO); para ()j = jj; j . maxj; j++) C[i[ ]j] = C[i[ ]j] + A[i[ ]k] * B[k[ ]j];

La localidad temporal de la solución anterior se proporciona porque un bloque se puede usar varias veces antes de continuar, por lo que se mueve dentro y fuera de la memoria con menos frecuencia. La localidad espacial se mejora porque los elementos con direcciones de memoria consecutivas tienden a subir juntos en la jerarquía de memoria.