Se dice que el software de computadora exhibe una localidad escalable [1] si puede continuar utilizando procesadores que superan el ritmo de sus sistemas de memoria , para resolver problemas cada vez mayores. Este término es un monoprocesador de alto rendimiento análogo al uso del paralelismo escalable para referirse al software para el cual se puede emplear un número creciente de procesadores para problemas mayores.
Descripción general
Considere los patrones de uso de memoria del siguiente nido de bucles (un cálculo de esténcil bidimensional iterativo ):
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 ( yo , j ) + A ( yo , j + 1 ) + A ( yo + 1 , j )) * . 2 fin fin para i : = 1 a N - 1 hacer para j : = 1 a N - 1 hacer A ( i , j ) : = new ( i , j ) end end end
El nido de bucle completo toca aproximadamente 2 * N ** 2 elementos de la matriz y realiza aproximadamente 5 * T * N ** 2 operaciones de punto flotante. Por lo tanto, el balance de cálculo general (relación de cálculos de punto flotante a celdas de memoria de punto flotante utilizadas) de este nido de bucle completo es de aproximadamente 5T / 2. Cuando el equilibrio de cálculo es una función del tamaño del problema, como aquí, se dice que el código tiene un equilibrio de cálculo escalable . Aquí, podríamos lograr cualquier equilibrio de cálculo que deseemos simplemente eligiendo una T lo suficientemente grande .
Sin embargo, cuando N es grande, este código aún no exhibirá una buena reutilización de la caché, debido a una localidad de referencia deficiente : para cuando se necesite new (1,1) en la segunda asignación, o en el segundo paso de tiempo para la ejecución 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 mosaico del primer nido de bucle i / j puede mejorar el rendimiento de la caché, pero solo por un factor limitado, ya que ese nido tiene un balance de cálculo de aproximadamente 5/2. Para producir un grado muy alto de localidad, 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 a lo largo de los pasos de tiempo.
La optimización a lo largo de los pasos de tiempo se ha explorado en varios compiladores de investigación; véase el trabajo de Wonnacott, [1] [2] de Song y Li, [3] o de Sadayappan et al. [4] para obtener detalles de algunos enfoques de ordenamiento temporal . Wonnacott [1] demostró que el mosaico de tiempo se puede utilizar 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 todo el arreglo 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 una localidad escalable y un paralelismo escalable .
Referencias
- ^ a b c David Wonnacott. Lograr una localidad escalable con sesgo de tiempo. Revista Internacional de Programación Paralela 30.3 (2002)
- ^ a b c David Wonnacott. Uso de Time Skewing para eliminar el tiempo de inactividad debido al ancho de banda de la memoria y las limitaciones de la red. Simposio internacional de procesamiento paralelo y distribuido 2000
- ^ a b Yonghong Song y Zhiyuan Li. Nuevas técnicas de ordenamiento en teselas para mejorar la localidad temporal de la caché. PLDI '99
- ^ a b c Sriram Krishnamoorthy y Muthu Baskaran y Uday Bondhugula y J. Ramanujam y Atanas Rountev y P. Sadayappan. Paralelización automática efectiva de cálculos de esténcil. PLDI '07