Romper el bucle en bloques

Mosaico de bucles (mosaico [1] , dividir el bucle en bloques ) es una transformación de optimización diseñada para hacer que la ejecución de ciertos tipos de bucles sea más eficiente.

Este método de optimización consiste en dividir el espacio de iteración del bucle original (que se puede realizar sobre varias variables) en pequeños bloques de menor tamaño, lo que permite almacenar los datos utilizados en estos pequeños bloques en la caché por completo para su repetición. uso durante la ejecución del bloque. Dividir el espacio de iteración del bucle hace que la matriz se divida en bloques más pequeños que caben en la caché, lo que da como resultado una mejor utilización de la caché, menos errores y requisitos de tamaño de caché más bajos.

Ejemplo: multiplicación matriz-vector

para ( yo = 0 ; yo < N ; yo ++ ) para ( j = 0 ; j < N ; j ++ ) c [ yo ] = c [ yo ] + un [ yo , j ] * segundo [ j ];

Después de dividir el bucle en bloques de 2 × 2

para ( yo = 0 ; yo < norte ; yo += 2 ) para ( j = 0 ; j < norte ; j += 2 ) para ( ii = i ; ii < min ( i + 2 , N ); ii ++ ) para ( jj = j ; jj < min ( j + 2 , N ); jj ++ ) c [ ii ] = c [ ii ] + a [ ii , jj ] * b [ ii ];

Inicialmente, el espacio de iteración tiene un tamaño de N × N. El bloque de matriz a[i, j] al que se debe acceder también tiene un tamaño de N × N. , luego los elementos que se usan dentro de una iteración (por ejemplo, cuando i = 1, j cambia de 1 a N), luego se producen errores de caché, se deben descargar diferentes partes de la matriz, lo que reduce en gran medida el rendimiento.

Ejemplo: multiplicación de matrices

Otro ejemplo del uso de esta transformación de optimización es la multiplicación de matrices.

Fuente:

para ( yo = 0 ; yo < N ; yo ++ ) para ( k = 0 ; k < norte ; k ++ ) para ( j = 0 ; j < N ; j ++ ) z [ yo , j ] = z [ yo , j ] + x [ yo , k ] * y [ k , j ]

Después de dividir en bloques B × B:

para ( k2 = 0 ; k2 < norte ; yo += segundo ) para ( j2 = 0 ; j2 < norte ; j += segundo ) para ( yo = 0 ; yo < N ; yo ++ ) para ( k1 = k2 ; k1 < min ( k2 + B , N ); k1 ++ ) para ( j1 = j2 ; k2 < min ( j2 + B , N ); j1 ++ ) z [ yo , j1 ] = z [ yo , j1 ] + x [ yo , k1 ] * y [ k1 , j1 ];

Selección de tamaño de bloque

No siempre es fácil determinar qué tamaño de bloque es óptimo para un ciclo en particular, ya que depende de la precisión del cálculo de las áreas de las matrices a las que se accede. El orden de anidamiento de los bucles también juega un papel importante para lograr un mejor rendimiento.

Notas

  1. ↑ Mosaico generalizado  // Informes de la Academia Nacional de Ciencias de Bielorrusia: revista. - 2011. - T. 55 . - S. 16-22 . Archivado desde el original el 4 de febrero de 2017.

Literatura

  1.  (Inglés) Wolfe, M. More Mosaico espacial de iteración . Supercomputing'89, páginas 655-664, 1989.
  2.  (Inglés) Wolf, M.E. y Lam, M. Un algoritmo de optimización de localidad de datos . PLDI '91, páginas 30-44, 1991.
  3.  (Inglés) Irigoin, F. y Triolet, R. Supernode Partitioning . POPL '88, páginas 319-329, 1988.
  4.  (Inglés) Xue, J. Loop Tiling for Parallelism . Editores académicos de Kluwer. 2000.
  5.  (Inglés) MS Lam, EE Rothberg y ME Wolf. El rendimiento de la memoria caché y las optimizaciones de los algoritmos bloqueados. En Actas de la 4ª Conferencia Internacional sobre Soporte Arquitectónico para Lenguajes de Programación y Sistemas Operativos, páginas 63–74, abril de 1991.