Organización Informática | Código amigable de localidad y caché

Los cachés son las memorias más rápidas que se construyen para lidiar con la brecha entre el procesador y la memoria en la operación de lectura de datos, es decir, la diferencia de tiempo en una operación de lectura de datos en un registro de la CPU y en la memoria principal. La operación de lectura de datos en los registros es generalmente 100 veces más rápida que en la memoria principal y continúa aumentando sustancialmente a medida que descendemos en la jerarquía de la memoria. 

Los cachés se instalan en medio de los registros de la CPU y la memoria principal para salvar este intervalo de tiempo en la lectura de datos. Los cachés sirven como área de preparación temporal para un subconjunto de datos e instrucciones almacenados en una memoria principal relativamente lenta. Dado que el tamaño de la memoria caché es pequeño, solo los datos que el procesador utiliza con frecuencia durante la ejecución de un programa se almacenan en la memoria caché. El almacenamiento en caché de estos datos de uso frecuente por parte de la CPU elimina la necesidad de traer los datos de la memoria principal más lenta una y otra vez, lo que requiere cientos de ciclos de CPU. 

La idea de almacenar en caché los datos útiles se centra en una propiedad fundamental de los programas informáticos conocida como localidad . Los programas con buena localidad tienden a acceder al mismo conjunto de elementos de datos una y otra vez desde los niveles superiores de la jerarquía de memoria (es decir, caché) y, por lo tanto, se ejecutan más rápido. 

Ejemplo: ¡El tiempo de ejecución de diferentes núcleos de multiplicación de arrays que realizan el mismo número de operaciones aritméticas, pero tienen diferentes grados de localidad, puede variar por un factor de 20! 

Tipos de localidad: 

• Localidad temporal: la localidad 
  temporal establece que es probable que la CPU reutilice los mismos objetos de datos varias veces durante la ejecución de un programa. Una vez que un objeto de datos se ha escrito en la memoria caché en el primer error, se puede esperar una serie de aciertos posteriores en ese objeto. Dado que la memoria caché es más rápida que el almacenamiento en el siguiente nivel inferior, como la memoria principal, estos aciertos posteriores se pueden atender mucho más rápido que el error original.
• Localidad espacial: 
  establece que si se hace referencia a un objeto de datos una vez, existe una alta probabilidad de que también se haga referencia a sus objetos de datos vecinos en un futuro próximo. Los bloques de memoria suelen contener varios objetos de datos. Debido a la localidad espacial, podemos esperar que el costo de copiar un bloque después de un error se amortice con las referencias posteriores a otros objetos dentro de ese bloque.

Importancia de la localidad: 
la localidad en los programas tiene un enorme impacto en el diseño y el rendimiento de los sistemas de hardware y software. En los sistemas informáticos modernos, las ventajas basadas en la localidad no solo se limitan a la arquitectura, sino que también los sistemas operativos y los programas de aplicación se construyen de manera que puedan explotar la localidad en toda su extensión. 

En los sistemas operativos, el principio de localidad permite que el sistema use la memoria principal como un caché de la porción de espacio de direcciones virtual a la que se hace referencia más recientemente y también en el caso de bloques de disco usados ​​recientemente en sistemas de archivos de disco. 

De manera similar, los programas de aplicación, como los navegadores web, explotan la localidad temporal al almacenar en caché los documentos a los que se hace referencia recientemente en un disco local. Los servidores web de gran volumen mantienen los documentos solicitados recientemente en la memoria caché del disco front-end que satisfacen las requests de estos documentos sin ninguna intervención del servidor. 

Código compatible con caché: 
los programas con una buena ubicación generalmente se ejecutan más rápido, ya que tienen una tasa de pérdida de caché más baja en comparación con los que tienen una mala ubicación. En una buena práctica de programación, el rendimiento de la memoria caché siempre se cuenta como uno de los factores importantes cuando se trata del análisis del rendimiento de un programa. El enfoque básico sobre cómo un código puede ser compatible con caché es: 

• Los casos de uso frecuente deben ser más rápidos: los programas a menudo invierten la mayor parte del tiempo en unas pocas funciones básicas y, a cambio, estas funciones tienen más que ver con los bucles. Por lo tanto, estos bucles deben diseñarse de manera que posean una buena localidad.
• Múltiples bucles: si un programa se compone de múltiples bucles, minimice las fallas de caché en el bucle interno para aliviar el rendimiento del código.

Ejemplo-1: El contexto anterior se puede entender siguiendo los ejemplos simples de código de array multidimensional. Considere la función sum_array() que suma los elementos de una array de dos dimensiones en orden de fila principal: 

int sumarrayrows(int a[8][4])
{
 int i, j, sum = 0;
 for (i = 0; i < 8; i++)
    for (j = 0; j < 4; j++)
     sum += a[i][j];
 return sum;
}

Suponiendo que la memoria caché tiene un tamaño de bloque de 4 palabras cada una, siendo el tamaño de palabra de 4 bytes. Inicialmente está vacío y, desde entonces, C almacena arrays en orden de fila principal, por lo que las referencias darán como resultado el siguiente patrón de aciertos y errores, independientemente de la organización de la memoria caché. 

El bloque que contiene w[0]–w[3] se carga en la caché desde la memoria y la referencia a w[0] es un error, pero las siguientes tres referencias son todas aciertos. La referencia a v[4] provoca otro error cuando se carga un nuevo bloque en la memoria caché, las siguientes tres referencias son aciertos, y así sucesivamente. En general, se acertarán tres de cada cuatro referencias, que es lo mejor que se puede hacer con un caché frío. Por lo tanto, la proporción de aciertos es 3/4*100 = 75 % 

Ejemplo-2: Ahora, la función sum_array() suma los elementos de una array de dos dimensiones en orden de columna principal. 
 

int sum_array(int a[8][8])
{
 int i, j, sum = 0;
 for (j = 0; j < 8; j++)
   for (i = 0; i < 8; i++)
   sum += a[i][j];
 return sum;
}

El diseño de caché del programa será como se muestra en la figura: 

Como C almacena arrays en orden de fila principal, pero en este caso se accede a la array en orden de columna principal, por lo que la localidad se estropea en este caso. las referencias se harán en orden: a[0][0], a[1][0], a[2][0] y así sucesivamente. Como el tamaño de la memoria caché es más pequeño, con cada referencia habrá un error debido a la mala ubicación del programa. Por lo tanto, la tasa de aciertos será 0. Una tasa de aciertos deficiente eventualmente disminuirá el rendimiento de un programa y conducirá a una ejecución más lenta. En la programación se deben evitar este tipo de prácticas. 

Conclusión: 
cuando se habla de programas de aplicación de la vida real y dominios de programación, el rendimiento optimizado de la caché brinda una buena aceleración a un programa, incluso si la complejidad del tiempo de ejecución del programa es alta. Un buen ejemplo es Ordenación rápida. Aunque tiene una complejidad en el peor de los casos de O(n ² ), es el algoritmo de clasificación más popular y uno de los factores importantes es el mejor rendimiento de caché que muchos otros algoritmos de clasificación. Los códigos deben escribirse de manera que puedan explotar el caché al máximo para una ejecución más rápida.