Localidad escalable

Se dice que el software de computadora exhibe localidad escalable ^[1] si puede continuar haciendo uso de procesadores que superan a sus sistemas de memoria para resolver problemas cada vez más grandes. Este término es un análogo de un solo procesador de alto rendimiento del uso de paralelismo escalable para referirse al software para el cual se pueden emplear cantidades cada vez mayores de procesadores para problemas más grandes.

Considere los patrones de uso de memoria del siguiente nido de bucles (un cálculo iterativo de plantilla bidimensional ):

para t := 0 a T hacer para i := 1 a N - 1 hacer para j := 1 a N - 1 hacer nuevo ( i , j ) := ( A ( i - 1 , j ) + A ( i , j - 1 ) + A ( i , j ) + A ( i , j + 1 ) + A ( i + 1 , j )) * . 2 fin fin      
          
              
                        
        
    

    para i := 1 a N - 1 hacer para j := 1 a N - 1 hacer A ( i , j ) := nuevo ( i , j ) fin fin fin      
              
              
        
    

Todo el bucle anidado toca aproximadamente 2*N**2 elementos de matriz y realiza aproximadamente 5*T*N**2 operaciones de punto flotante. Por lo tanto, el balance computacional general (relación entre los cálculos de punto flotante y las celdas de memoria de punto flotante utilizadas) de todo este bucle anidado es de aproximadamente 5T/2. Cuando el balance computacional es una función del tamaño del problema, como en este caso, se dice que el código tiene un balance computacional escalable . Aquí, podríamos lograr cualquier balance computacional que deseemos simplemente eligiendo un T lo suficientemente grande .

Sin embargo, cuando N es grande, este código aún no exhibirá una buena reutilización de caché, debido a la mala localidad de referencia : para cuando se necesite new(1,1) en la segunda asignación, o en la ejecución del segundo paso de tiempo de la primera asignación, la línea de caché que contiene new(1,1) se habrá sobrescrito con alguna otra parte de una de las matrices.

El agrupamiento en mosaicos del primer bucle i/j puede mejorar el rendimiento de la memoria caché, pero solo por un factor limitado, ya que ese bucle tiene un equilibrio de cálculo de aproximadamente 5/2. Para producir un grado de localidad muy alto, por ejemplo 500 (para ejecutar este código de manera eficiente con una matriz que no cabe en la RAM y está relegada a la memoria virtual), debemos reutilizar los valores en los intervalos de tiempo.

La optimización a lo largo de pasos de tiempo se ha explorado en varios compiladores de investigación; consulte el trabajo de Wonnacott, ^{[1] [2]} de Song y Li, ^[3] o de Sadayappan et al. ^[4] para obtener detalles de algunos enfoques de mosaico temporal . Wonnacott ^[1] demostró que el mosaico temporal podría usarse para optimizar conjuntos de datos fuera del núcleo; en principio, cualquiera de estos enfoques ^{[2] [3] [4]} debería poder lograr una localidad de memoria arbitrariamente alta sin requerir que toda la matriz quepa en la caché (el requisito de caché, sin embargo, crece con la localidad requerida). Las técnicas de multiprocesador citadas anteriormente ^{[2] [4]} deberían, en principio, producir simultáneamente localidad escalable y paralelismo escalable .