Localidad de referencia

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:

• Localidad temporal : si en un momento dado se hace referencia a una ubicación de memoria en particular, es probable que se haga referencia a la misma ubicación nuevamente en un futuro cercano. Existe 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 localidad espacial (ver más abajo), es decir, cuando la ubicación prospectiva es idéntica a la ubicación actual.
• Localidad espacial : si se hace referencia a una ubicación de almacenamiento en particular en un momento determinado, es probable que se haga referencia a ubicaciones de memoria cercanas en el futuro cercano. En este caso, es común intentar adivinar el tamaño y la forma del área alrededor de la referencia actual para la cual vale la pena preparar un acceso más rápido para referencias posteriores.
  • Localidad de memoria (o localidad de datos ^[3] ): Localidad espacial relacionada explícitamente con la memoria .
• Localidad de ramificación : si solo hay unas pocas alternativas posibles para la parte prospectiva de la ruta en el espacio de coordenadas espacio-temporales. Este es el caso cuando un bucle de instrucciones tiene una estructura simple o el posible resultado de un pequeño sistema de instrucciones de ramificación condicional está restringido a un pequeño conjunto de posibilidades. La localidad de ramificación normalmente no es una localidad espacial, ya que las pocas posibilidades pueden estar ubicadas muy alejadas entre sí.
• Localidad equidistante : A medio camino entre la localidad espacial y la localidad de ramificación. Considere un bucle que accede a ubicaciones en un patrón equidistante, es decir, la ruta en el espacio de coordenadas espacio-temporales es una línea de puntos. En este caso, una función lineal simple puede predecir a qué ubicación se accederá en el futuro cercano.

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:

• Predictibilidad : la localidad es simplemente un tipo de comportamiento predecible en los sistemas informáticos.
• Estructura del programa : La localidad se produce a menudo debido a la forma en que se crean los programas informáticos para gestionar problemas decidibles. Generalmente, los datos relacionados se almacenan en ubicaciones cercanas en la memoria. Un patrón común en informática implica el procesamiento de varios elementos, uno a la vez. Esto significa que si se realiza mucho procesamiento, se accederá al elemento único más de una vez, lo que conduce a la localidad de referencia temporal. Además, pasar al siguiente elemento implica que se leerá el siguiente elemento, de ahí la localidad de referencia espacial, ya que las ubicaciones de memoria normalmente se leen en lotes.
• Estructuras de datos lineales : la localidad ocurre a menudo porque el código contiene bucles que tienden a hacer referencia a matrices u otras estructuras de datos por índices. La localidad secuencial, un caso especial de localidad espacial, ocurre cuando los elementos de datos relevantes se organizan y se accede a ellos de forma lineal. Por ejemplo, el simple recorrido 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 la memoria. ^[4] La localidad equidistante ocurre cuando el recorrido lineal se realiza 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 a cada estructura completa. Este es el caso cuando una matriz se representa como una matriz secuencial de filas y el requisito es acceder a una sola columna de la matriz.
• Eficiencia en el uso de la jerarquía de memoria : aunque la memoria de acceso aleatorio ofrece al programador la posibilidad de leer o escribir en cualquier lugar y en cualquier momento, en la práctica la latencia y el rendimiento se ven afectados por la eficiencia de la memoria caché , que se mejora al aumentar la localidad de referencia. Una localidad de referencia deficiente da como resultado la destrucción y la contaminación de la memoria caché y, para evitarlo, los elementos de datos con una localidad deficiente se pueden omitir de la memoria caché.

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:

• Aumentar la localidad de las referencias (generalmente en el lado del software)
• Explotación de la localidad de referencias: Generalmente lograda 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 especializadas apropiadas de los procesadores, esta posibilidad no es solo responsabilidad del hardware, sino también del software, si su estructura es adecuada para compilar un programa binario que llame a las instrucciones especializadas en cuestión. La localidad de ramificación es una posibilidad más elaborada, por lo tanto se necesita un mayor esfuerzo de desarrollo, pero hay una reserva mucho mayor para la exploración futura en este tipo de localidad que en todas las restantes.

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):

• Registros de la CPU (8–256 registros): acceso inmediato, con la velocidad del núcleo más interno del procesador
• Cachés de CPU L1 (32 KB a 512  KB ): acceso rápido, con la velocidad del bus de memoria más interno propiedad exclusiva de cada núcleo
• Cachés de CPU L2 (128 KB a 24  MB ): acceso ligeramente más lento, con la velocidad del bus de memoria compartida entre núcleos gemelos
• Cachés de CPU L3 (2 MB hasta un máximo de 64  MB ): acceso aún más lento, con la velocidad del bus de memoria compartida entre incluso más núcleos del mismo procesador
• Memoria física principal ( RAM ) (256 MB a 64  GB ): acceso lento, cuya velocidad está limitada por las distancias espaciales y las interfaces generales de hardware entre el procesador y los módulos de memoria en la placa base
• Disco ( memoria virtual , sistema de archivos ) (1 GB a 256  TB ): muy lento, debido al canal de datos más angosto (en ancho de bits), físicamente mucho más largo entre la placa principal de la computadora y los dispositivos de disco, y debido al protocolo de software extraño necesario en la parte superior de la interfaz de hardware lenta
• Memoria remota (otras computadoras o la nube) (prácticamente ilimitada): la velocidad varía de muy lenta a extremadamente lenta

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.

• Algoritmo que ignora el caché
• Algoritmo para evitar la comunicación
• Fragmentación del sistema de archivos
• Espacio de direcciones global particionado
• Orden principal de filas y columnas
• Localidad escalable
• Memoria de bloc de notas
• Conjunto de trabajo
• Heurístico

• Peter J. Denning , "El principio de localidad", Communications of the ACM , Volumen 48, Número 7, (2005), páginas 19-24
• Peter J. Denning, Stuart C. Schwartz, "Propiedades del modelo de conjunto de trabajo", Communications of the ACM , volumen 15, número 3 (marzo de 1972), páginas 191-198