Blocking es una técnica que aprovecha la localidad temporal y espacial mediante el uso de algoritmos que organizan la estructura de datos en bloques. La idea principal es insertar una cantidad de datos (chunk) en la memoria caché, trabajar lo más que se pueda con dicha información y luego avanzar al siguiente bloque. De esta forma, los accesos a los datos que se encuentren dentro de nuestro bloque y, por ende, dentro de la memoria caché tendrán una mayor tasa de aciertos; así el programa estará optimizado. Previo a la explicación de la técnica de blocking debemos conocer dos operaciones básicas de algebra lineal. ↑

Sea A una matriz de n filas y m columnas (n x m), y B una matriz de m filas y p columnas (m x p), entonces el producto de ambas matrices, C = A*B, es una matriz de n filas y p columnas (n x p). Cada elemento se calcula de la siguiente manera:

Ejemplo:

Se verifica que el número de columnas de la matriz A es igual al número de filas de la matriz B y que el producto, denotado como matriz C, tiene la cantidad de filas de la matriz A y la cantidad de columnas de la matriz B. ↑

Sea A una matriz de tamaño n x m, la transpuesta será una matriz de tamaño m x n y se obtiene mediante el cambio de filas por columnas (o viceversa). Cada elemento será calculado de la siguiente manera:

Ejemplo:

Se verifica que esta operación realiza un giro de la matriz y considera como eje la diagonal de la matriz. ↑

El objetivo principal de trabajar por bloques es mejorar el tiempo de procesamiento debido a la existencia de localidad temporal y espacial. Por ejemplo, si se tuviesen dos matrices cuadradas de igual tamaño que deseamos multiplicar, estas se pueden dividir en submatrices y luego explotar el hecho matemático de que estas submatrices pueden manipularse como escalares. Supongamos que queremos calcular C = AB, donde A, B y C son cada una matrices de 8 x 8. Podemos dividir cada matriz en cuatro submatrices de 4 x 4 de la siguiente forma:

Luego:

Note que se definió un tamaño de bloque igual a la mitad de la matriz; sin embargo, no siempre tiene que ser así; es recomendable usar tamaños de bloques de tal manera que todos los datos puedan ser localizados dentro de la memoria caché. Si el bloque es muy grande, ciertos datos se perderán y serán guardados fuera de la caché (al siguiente nivel de la jerarquía de memoria).

Una forma de resolver la multiplicación C = AB usando blocking es de la siguiente manera:

• Definir un tamaño de bloque 1 x bsize (block size) para la matriz A. La matriz A disfruta de una buena localidad espacial porque cada bloque es accedido en fila unitaria (1 x bsize). Además, existe una buena localidad temporal porque el bloque es accedido bsize veces seguidas.

• Realizar particiones de la matriz B en bloques de tamaño bsize x bsize. La intención es almacenar bloques de dicha matriz en la memoria caché, usar toda esa información y luego descartarla para cargar un nuevo bloque. El acceso a la matriz B disfruta de una buena localidad temporal porque se accede al bloque bsize x bsize completo n veces consecutivas.

• La matriz resultante C presenta una buena localidad espacial porque cada elemento del bloque está fijado en sucesión. Sin embargo, no presenta una buena localidad temporal porque cada bloque es accedido solo una vez.

En la siguiente figura se muestra una explicación gráfica de lo señalado anteriormente, donde n es el tamaño de las matrices cuadradas. Para el presente laboratorio se considera a bsize como un divisor exacto de n. ↑

De igual forma que en el algoritmo anterior, obtendremos la transpuesta de una matriz mediante la técnica blocking. La idea principal se puede observar en la siguiente ecuación:

Cada matriz es un bloque que pertenece a la matriz principal A. De forma análoga a la multiplicación por bloques, aprovecharemos la buena localidad espacial y temporal así como también los aciertos a la memoria caché, los cuales se traducen a una ejecución del algoritmo en menor tiempo.