Hispanopedia WikiEn ciencias de la computación , 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 repetidamente 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 una duración de tiempo relativamente pequeña. 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 están organizados y se accede a ellos linealmente, como recorrer los elementos en una matriz unidimensional .
La localidad es un tipo de comportamiento predecible que se da en los sistemas informáticos. Los sistemas que presentan una fuerte localidad de referencia son buenos 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 bifurcación avanzados del núcleo del procesador.
Tipos de localidad
Existen varios tipos diferentes de localidad de referencia:
- Localidad temporal : Si en un momento dado se hace referencia a una ubicación de memoria específica, es probable que se vuelva a hacer referencia a la misma ubicación en un futuro próximo. Existe proximidad temporal entre referencias consecutivas a la misma ubicación de memoria. En este caso, es común intentar almacenar una copia de los datos referenciados en una memoria más rápida para reducir la latencia de las referencias posteriores. La localidad temporal es un caso especial de localidad espacial (véase más adelante), concretamente cuando la ubicación futura es idéntica a la ubicación actual.
- Localidad espacial : Si se accede a una ubicación de almacenamiento específica en un momento dado, es probable que se acceda a ubicaciones de memoria cercanas en un futuro próximo. En este caso, es común intentar estimar el tamaño y la forma del área que rodea la ubicación actual, para así preparar un acceso más rápido para futuras referencias.
- Localidad espacial en el recorrido de matrices: En estructuras bidimensionales como las matrices, la localidad espacial tiene un impacto directo en el rendimiento computacional. En lenguajes de programación como C, las matrices se almacenan en memoria utilizando el orden de filas, lo que significa que el acceso secuencial a elementos contiguos mejora la utilización de la caché y reduce los fallos de caché.
Cuando el tamaño de la matriz es pequeño, las diferencias de rendimiento entre los métodos de recorrido pueden parecer mínimas, ya que todo el conjunto de datos cabe en la caché del procesador. Sin embargo, a medida que aumentan las dimensiones de la matriz, el patrón de acceso se convierte en un factor crítico, puesto que los recorridos no secuenciales generan muchos más fallos de caché y accesos a la RAM, lo que reduce la eficiencia computacional general.
- Localidad de memoria (o localidad de datos [ 3 ] ): Localidad espacial relacionada explícitamente con la memoria .
- Localidad de rama : Se refiere a la existencia de pocas alternativas posibles para la parte prospectiva de la ruta en el espacio de coordenadas espacio-temporales. Esto ocurre cuando un bucle de instrucciones tiene una estructura simple o cuando el resultado posible de un pequeño sistema de instrucciones de ramificación condicional se limita a un conjunto reducido de posibilidades. La localidad de rama no suele coincidir con la localidad espacial, ya que las pocas posibilidades pueden estar muy alejadas entre sí.
- Localidad equidistante : A medio camino entre la localidad espacial y la localidad de rama. Consideremos un bucle que accede a ubicaciones siguiendo un patrón equidistante; es decir, la trayectoria en el espacio de coordenadas espacio-temporales es una línea punteada. En este caso, una función lineal simple puede predecir a qué ubicación se accederá próximamente.
Para aprovechar la localidad temporal y espacial, que se presenta con frecuencia, la mayoría de los sistemas de almacenamiento de información son jerárquicos . La localidad equidistante suele estar respaldada por las diversas instrucciones de incremento no triviales del procesador. En cuanto a la localidad de bifurcación, los procesadores actuales cuentan con sofisticados predictores de bifurcación, y basándose en esta predicción, el gestor de memoria del procesador intenta recopilar y preprocesar los datos de las alternativas plausibles.
Pertinencia
Existen diversas razones para la localización. Estas razones pueden ser objetivos a alcanzar o circunstancias a aceptar, según el caso. Las razones que se enumeran a continuación no son aisladas ; de hecho, la lista va desde el caso más general hasta casos particulares:
- Previsibilidad : La localidad es simplemente un tipo de comportamiento predecible en los sistemas informáticos.
- Estructura del programa : La localidad se produce con frecuencia debido a la forma en que se crean los programas informáticos para resolver problemas decidibles. Generalmente, los datos relacionados se almacenan en ubicaciones cercanas en la memoria. Un patrón común en la informática implica el procesamiento de varios elementos, uno a la vez. Esto significa que, si se realiza un procesamiento intensivo, se accederá al mismo elemento más de una vez, lo que genera localidad de referencia temporal. Además, pasar al siguiente elemento implica que este se leerá, lo que genera localidad de referencia espacial, ya que las ubicaciones de memoria se leen normalmente en lotes.
- Estructuras de datos lineales : La localidad suele ocurrir porque el código contiene bucles que tienden a referenciar 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 acceden linealmente. 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 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 : Si bien la memoria de acceso aleatorio (RAM) 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 caché , que se mejora aumentando la localidad de referencia. Una localidad de referencia deficiente provoca saturación y contaminación de la caché , y para evitarlo, los elementos de datos con baja localidad pueden omitirse de la caché.
Uso general
Si la mayor parte del tiempo una porción sustancial de las referencias se agrupa en clústeres, y si la forma de este sistema de clústeres se puede predecir con precisión, entonces se puede utilizar para la optimización del rendimiento. Existen varias maneras de aprovechar la localidad mediante técnicas de optimización . Las técnicas comunes son:
- Aumentar la localidad de las referencias (generalmente en el ámbito del software).
- Aprovechamiento de la localidad de referencias: Generalmente lograda a nivel de 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 adecuadas de los procesadores; esta posibilidad no solo depende del hardware, sino también del software, siempre que su estructura sea adecuada para compilar un programa binario que llame a las instrucciones especializadas en cuestión. La localidad de bifurcación es una posibilidad más compleja, por lo que requiere un mayor esfuerzo de desarrollo, pero ofrece un margen mucho mayor para la exploración futura que las demás.
Uso de la localidad espacial y temporal
memoria jerárquica
La memoria jerárquica es una optimización de hardware que aprovecha las ventajas de la localidad espacial y temporal, y puede utilizarse en varios niveles de la jerarquía de memoria. La paginación, por ejemplo, se beneficia de la localidad temporal y espacial. Una caché es un ejemplo sencillo de cómo se aprovecha la localidad temporal, ya que se trata de un área de memoria especialmente diseñada, más rápida pero más pequeña, que generalmente se utiliza para almacenar datos consultados recientemente y datos cercanos a estos, lo que puede generar mejoras potenciales en el rendimiento.
Los elementos de datos en una caché no necesariamente corresponden a elementos de datos espacialmente cercanos en la memoria principal; sin embargo, los elementos de datos se cargan en la caché de uno en uno. Esto significa que la localidad espacial vuelve a ser importante: si se hace referencia a un elemento, algunos elementos vecinos también se cargará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 próximamente pueden almacenarse en los registros de la máquina . Algunos lenguajes de programación (como C ) permiten al programador sugerir que ciertas variables se almacenen en registros.
La localidad de datos es una característica típica de las referencias a memoria en los programas regulares (aunque existen muchos patrones de acceso a memoria irregulares). Esto hace que la organización jerárquica de la memoria sea ventajosa. 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 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 y evita cargar otros datos en los niveles superiores que desplacen datos que se utilizarán en breve. Este es un ideal, pero a veces no se puede alcanzar.
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).(A efectos de debate; los valores reales y el número real 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 L1 de la CPU (de 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 L2 de la CPU (de 128 KB a 24 MB ) : acceso ligeramente más lento, ya que la velocidad del bus de memoria se comparte entre los núcleos gemelos.
- Cachés L3 de la CPU (de 2 MB hasta un máximo de 64 MB ) : acceso aún más lento, con la velocidad del bus de memoria compartida entre aún más núcleos del mismo procesador.
- Memoria física principal ( RAM ) (de 256 MB a 64 GB ) : acceso lento, cuya velocidad está limitada por las distancias físicas y las interfaces de hardware generales entre el procesador y los módulos de memoria en la placa base.
- Disco ( memoria virtual , sistema de archivos ) (de 1 GB a 256 TB ) : muy lento, debido al canal de datos más estrecho (en ancho de bits) y físicamente mucho más largo entre la placa base del ordenador y los dispositivos de disco, y debido al protocolo de software externo necesario sobre la lenta interfaz de hardware.
- Memoria remota (otros ordenadores 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 de nivel inferior en el siguiente nivel de la jerarquía de memoria. Si esto desplaza memoria ya utilizada, el sistema operativo intenta predecir qué datos se accederán con menos frecuencia (o más tarde) y los mueve hacia abajo en la jerarquía de memoria. Los algoritmos de predicción suelen ser sencillos para reducir la complejidad del hardware, aunque cada vez son más complejos.
multiplicación de matrices
Un ejemplo común es la multiplicación de matrices :
para i en 0 .. npara j en 0 .. mpara k en 0 .. pC [ i ][ j ] = C [ i ][ j ] + A [ i ][ k ] * B [ k ][ j ] ;Al invertir el orden de iteración de jlos bucles k, la aceleración en las multiplicaciones de matrices grandes se vuelve drástica, al menos para lenguajes que colocan los elementos contiguos de la matriz en la última dimensión. Esto no modificará 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 .. npara k en 0 .. ppara j en 0 .. mC [ 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 dimensión contigua y última), pero B[k][j]no lo está, por lo que hay una penalización por fallo 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 .. npara j en 0 .. mtemp = C [ i ][ j ]para k en 0 .. ptemp = temp + A [ i ][ k ] * B [ k ][ j ] ;C [ i ][ j ] = temperaturaEn 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 elevar fuera del bucle interno.
para i en 0 .. npara k en 0 .. ptemp = A [ i ][ k ]para j en 0 .. mC [ i ][ j ] = C [ i ][ j ] + temp * B [ k ][ j ] ;Por lo tanto, el segundo ejemplo no tiene penalización por fallo de caché en el bucle interno, mientras que el primer ejemplo sí la tiene.
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 minucioso 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 de SIMD).
En el ejemplo anterior, la localidad temporal también puede mejorarse mediante una técnica denominada bloqueo . La matriz más grande puede dividirse en submatrices de igual tamaño, de modo que los bloques más pequeños puedan consultarse (multiplicarse) varias veces mientras se encuentran en memoria. Cabe destacar que este ejemplo funciona para matrices cuadradas de dimensiones SIZE x SIZE, pero puede extenderse fácilmente a matrices arbitrarias sustituyendo SIZE_I, SIZE_J y SIZE_K según corresponda.
para ( ii = 0 ; ii < SIZE ; ii += BLOCK_SIZE )para ( kk = 0 ; kk < SIZE ; kk += BLOCK_SIZE )para ( jj = 0 ; jj < SIZE ; jj += BLOCK_SIZE )maxi = min ( ii + BLOCK_SIZE , SIZE ) ;para ( i = ii ; i < maxi ; i ++ )maxk = min ( kk + BLOCK_SIZE , SIZE ) ;para ( k = kk ; k < maxk ; k ++ )maxj = min ( jj + BLOCK_SIZE , SIZE ) ;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 debe a que un bloque puede usarse varias veces antes de pasar al siguiente, lo que reduce la frecuencia de entrada y salida de memoria . La localidad espacial mejora porque los elementos con direcciones de memoria consecutivas tienden a ascender juntos en la jerarquía de memoria.
Véase también
Referencias
- ↑ No confundir con el principio de localidad o=s*v=411##sts en física.
- ↑ William Stallings (2010). Organización y arquitectura de computadoras : diseño para el rendimiento (8.ª ed.). Upper Saddle River, NJ: Prentice Hall. ISBN 9780136073734OCLC 268788976
- 1 2 "Marco de interoperabilidad de macrodatos del NIST: Volumen 1", [ https://doi.org/10.6028/NIST.SP.1500-1r2 urn:doi:10.6028/NIST.SP.1500-1r2
- ↑ Aho, Lam, Sethi y Ullman. "Compiladores: Principios, técnicas y herramientas", 2.ª ed. Pearson Education, Inc., 2007.
Bibliografía
- 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
- Memoria de computadora
- Caché (informática)
- Optimización de software
