En informática , 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 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 corto. 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 manera lineal, como cuando se atraviesan los elementos en una matriz unidimensional .
La localidad es un tipo de comportamiento predecible que ocurre en los sistemas informáticos. Los sistemas que exhiben 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 rama avanzados de un núcleo de procesador.
Existen varios tipos diferentes de localidad de referencia:
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 suele estar respaldada por diversas instrucciones de incremento no triviales de un procesador. Para la localidad de sucursal, los procesadores contemporáneos tienen predictores de sucursal sofisticados y, basándose en esta predicción, el administrador de memoria del procesador intenta recopilar y preprocesar los datos de alternativas plausibles.
Hay varias razones para la localidad. Estas razones son objetivos a alcanzar o circunstancias a aceptar, según el aspecto. Las razones siguientes no son inconexas ; de hecho, la lista a continuación va desde el caso más general hasta casos especiales:
Si la mayor parte del tiempo la porción sustancial de las referencias se agrega en grupos, y si la forma de este sistema de grupos se puede predecir bien, entonces se puede utilizar para optimizar el rendimiento. Hay varias formas de beneficiarse de la localidad utilizando técnicas de optimización . Las técnicas 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 sencillo 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 hace referencia recientemente y datos cerca de datos a los que se hace referencia recientemente, lo que puede conducir a posibles aumentos de rendimiento.
Los elementos de datos en una 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 guardarán en la caché. Finalmente, la localidad temporal juega un papel en el nivel más bajo, ya que los resultados a los que se hace referencia muy estrechamente 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 localidad de datos es una característica típica de referencia de memoria de los programas normales (aunque existen muchos patrones irregulares de acceso a la memoria). Hace que el diseño jerárquico de la memoria sea rentable. En las computadoras, la memoria se divide en una jerarquía para acelerar el acceso a los datos. Los niveles inferiores de la jerarquía de la memoria tienden a ser más lentos, pero más grandes. Por lo tanto, un programa logrará un mayor rendimiento si usa 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. Este 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 los valores típicos utilizados a partir de 2013 [actualizar]con 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 la memoria usada, el sistema operativo intenta predecir a qué datos se accederá menos (o más recientemente) y moverlos 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 del bucle para jy k, la aceleración en 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 como 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 lo está, 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 que existe 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 en caché, las lecturas de B[k][j]están en caché y la lectura de A[i][k]puede extraerse 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 error de caché en el bucle interno, mientras que el primer ejemplo tiene una penalización por error 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 la memoria caché es mucho peor que la ganancia SIMD ) .
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 se pueda hacer referencia a los bloques más pequeños (multiplicarlos) 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 += TAMAÑO_BLOQUE ) para ( kk = 0 ; kk < TAMAÑO ; kk += BLOQUE_TAMAÑO ) para ( jj = 0 ; jj < TAMAÑO ; jj += BLOQUE_TAMAÑO ) maxi = min ( ii + TAMAÑO_BLOQUE , TAMAÑO ) ; para ( i = ii ; i < maxi ; i ++ ) maxk = mínimo ( kk + TAMAÑO_BLOQUE , TAMAÑO ) ; para ( k = kk ; k < maxk ; k ++ ) maxj = min ( jj + TAMAÑO_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 proporciona porque un bloque se puede usar varias veces antes de continuar, de modo que entra y sale de la memoria con menos frecuencia. La localidad espacial mejora porque los elementos con direcciones de memoria consecutivas tienden a agruparse en la jerarquía de memoria.
