En informática , la localidad de referencia , también conocida como principio de localidad , [1] es la tendencia de un procesador a acceder al mismo conjunto de ubicaciones de memoria de forma repetitiva durante un corto período de tiempo. [2] Hay dos tipos básicos de localidad de referencia: localidad temporal y localidad espacial. La localidad temporal se refiere a la reutilización de datos y/o recursos específicos dentro de un período de tiempo relativamente pequeño. La localidad espacial (también denominada localidad de datos [3] ) 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 al recorrer los elementos en una matriz unidimensional .
La localidad es un tipo de comportamiento predecible que se produce en los sistemas informáticos. Los sistemas que presentan una fuerte localidad de referencia son grandes candidatos para la optimización del rendimiento mediante el uso de técnicas como el almacenamiento en caché , la precarga de memoria y los predictores de ramificación avanzados de un núcleo de procesador.
Existen varios tipos diferentes de localidad de referencia:
Para aprovechar la localidad temporal y espacial, que se da con frecuencia, la mayoría de los sistemas de almacenamiento de información son jerárquicos . La localidad equidistante suele estar respaldada por diversas instrucciones de incremento no triviales de un procesador. Para la localidad de ramificación, los procesadores contemporáneos tienen predictores de ramificación sofisticados y, sobre la base de esta predicción, el administrador de memoria del procesador intenta recopilar y preprocesar los datos de alternativas plausibles.
Existen varias razones para la localidad. Estas razones son objetivos que se deben alcanzar o circunstancias que se deben aceptar, según el aspecto. Las razones que se indican a continuación no son inconexas ; de hecho, la lista que figura a continuación va desde el caso más general hasta los casos especiales:
Si la mayor parte del tiempo la parte sustancial de las referencias se agrupan en grupos, y si la forma de este sistema de grupos se puede predecir bien, entonces se puede utilizar para optimizar el rendimiento. Existen varias formas de aprovechar la localidad mediante técnicas de optimización . Las técnicas más comunes son:
La memoria jerárquica es una optimización de hardware que aprovecha los beneficios de la localidad espacial y temporal y se puede utilizar en varios niveles de la jerarquía de memoria. La paginación obviamente se beneficia de la localidad temporal y espacial. Una 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, que generalmente se utiliza para mantener datos a los que se hizo referencia recientemente y datos cerca de los datos a los que se hizo referencia recientemente, lo que puede generar posibles aumentos de rendimiento.
Los elementos de datos en una caché no necesariamente corresponden a elementos de datos que están espacialmente cercanos en la memoria principal; sin embargo, los elementos de datos se llevan a la caché una línea de caché a la vez. Esto significa que la localidad espacial es nuevamente importante: si se hace referencia a un elemento, algunos elementos vecinos también se llevarán a la caché. Finalmente, la localidad temporal juega un papel en el nivel más bajo, ya que los resultados que se referencian muy cerca entre sí se pueden mantener 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 localización de los datos es una característica típica de referencia de memoria de los programas regulares (aunque existen muchos patrones de acceso a la memoria irregulares). Hace que la disposición jerárquica de la memoria sea rentable. En las computadoras, la memoria se divide en una jerarquía para acelerar los accesos a los datos. Los niveles inferiores 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 memoria mientras está almacenada en caché en los niveles superiores de la jerarquía de memoria y evita llevar otros datos a los niveles superiores de la jerarquía que desplazarán datos que se utilizarán en breve en el futuro. Esto es un ideal y, a veces, no se puede lograr.
Jerarquía de memoria típica (los tiempos de acceso y los tamaños de caché son aproximaciones de valores típicos utilizados a partir de 2013 [actualizar]para fines de discusión; los valores reales y los números reales de niveles en la jerarquía varían):
Las máquinas modernas tienden a leer bloques de memoria inferior en el siguiente nivel de la jerarquía de memoria. Si esto desplaza memoria usada, el sistema operativo intenta predecir qué datos serán los que menos se accederán (o los últimos) y los mueve hacia abajo en la jerarquía de memoria. Los algoritmos de predicción tienden a ser simples para reducir la complejidad del hardware, aunque se están volviendo algo más complicados.
Un ejemplo común es la multiplicación de matrices :
para i en 0 .. n para j en 0 .. m para k en 0 .. p C [ i ][ j ] = C [ i ][ j ] + A [ i ][ k ] * B [ k ][ j ] ; Al cambiar el orden de repetición de jy k, la aceleración en las multiplicaciones de matrices grandes se vuelve dramática, al menos para 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 en 0 .. n para k en 0 .. p para j en 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é (ya que el kíndice es la última dimensión contigua), pero B[k][j]no es así, por lo que hay una penalización por error de caché en B[k][j]. C[i][j]es irrelevante, porque se puede sacar del bucle interno: la variable del bucle allí es k.
para i en 0 .. n para j en 0 .. m temperatura = C [ i ][ j ] para k en 0 .. p temperatura = temperatura + A [ i ][ k ] * B [ k ][ j ] ; C [ i ][ j ] = temperatura 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 las lecturas de A[i][k]pueden sacarse del bucle interno.
para i en 0 .. n para k en 0 .. p temperatura = A [ i ][ k ] para j en 0 .. m C [ i ][ j ] = C [ i ][ j ] + temperatura * B [ k ][ j ] ; Por lo tanto, el segundo ejemplo no tiene penalización por falta de caché en el bucle interno, mientras que el primer ejemplo tiene una penalización de caché.
En un procesador del año 2014, el segundo caso es aproximadamente cinco veces más rápido que el primero, cuando está escrito en C y compilado con gcc -O3. (Un examen cuidadoso del código desensamblado muestra que en el primer caso, GCC usa instrucciones SIMD y en el segundo caso no, pero la penalización de caché es mucho peor que la ganancia de SIMD). [ cita requerida ]
La localidad temporal también se puede mejorar en el ejemplo anterior mediante el uso de 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 puedan referenciar (multiplicar) varias veces mientras están en la memoria. Tenga en cuenta que este ejemplo funciona para matrices cuadradas de dimensiones SIZE x SIZE, pero se puede extender fácilmente para matrices arbitrarias sustituyendo SIZE_I, SIZE_J y SIZE_K cuando sea apropiado.
para ( ii = 0 ; ii < TAMAÑO ; ii += TAMAÑO_DE_BLOQUE ) para ( kk = 0 ; kk < TAMAÑO ; kk += TAMAÑO_DE_BLOQUE ) para ( jj = 0 ; jj < TAMAÑO ; jj += TAMAÑO_DE_BLOQUE ) maxi = min ( ii + TAMAÑO_DE_BLOQUE , TAMAÑO ) ; para ( i = ii ; i < maxi ; i ++ ) maxk = min ( kk + TAMAÑO_DE_BLOQUE , TAMAÑO ) ; para ( k = kk ; k < maxk ; k ++ ) maxj = min ( jj + TAMAÑO_DE_BLOQUE , 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 logra porque un bloque se puede usar varias veces antes de continuar, de modo que se lo 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.
