Producto de dos Matrices Almacenadas en Formato Comprimido.
Profesor: Ignacio Blanquer, email iblanque en dsic.upv.es, hasta 1 punto
Alumno: Carlos Ballesteros Velasco - carbalve en fiv.upv.es
Enunciado:
Los formatos CSR (Compress Sparse Row) y CSC (Compress Sparse Column) permiten almacenar Únicamente los valores no nulos de una matriz. De esta forma se reduce el número de operaciones inútiles y el espacio en memoria. Se deberá implementar un conjunto de funciones en "C" para almacenar e imprimir matrices en formato CSR y CSC y para realizar el producto de una matriz CSR por una CSC. El ejercicio requerirá la implementación para la conversión entre el formato convencional y CSR / CSC, la visualización de matrices densas o dispersas en CSR / CSC y el producto de una matriz CSR por una matriz CSC. Deberá además contabilizarse el tiempo de ejecución y el número de flops requeridos en el producto, utilizando matrices aleatorias de dimensiones 128, 256, 512 y 1024, y con un porcentajes de ceros de 95%, 99% y 99,99% en cada caso.
Objetivos:
Este ejercicio pretende analizar la mejora en prestaciones que supone aprovechar la estructura de elementos no nulos en matrices dispersas, utilizando para ello la codificación de fila comprimida e implementando la operación del producto matriz por vector. Las acciones que deberán realizarse en este trabajo son:
- Generación de matrices dispersas con un gran porcentaje de elementos nulos.
- Almacenamiento de estas matrices en formatos CSR / CSC.
- Implementación del producto matriz por matriz para matrices con almacenamiento completo (incluyendo los ceros) y con almacenamiento CSR (la primera) y CSC (la segunda).
- Verificación de resultados y comparativa de prestaciones.
Para la primera opción, se pretende que el alumno genere matrices aleatorias que tengan, aproximadamente un porcentaje de elementos nulos prefijados. Por ejemplo, si se indica un porcentaje del 95% de elementos nulos, la probabilidad de que un elemento sea 0 es del 95%, pudiéndose obtener este valor mediante un número aleatorio entre 0 y 100, considerando que es nulo si es menor que el porcentaje. El ratio final de elementos nulos versus elementos no nulos deberá calcularse al final de la generación.
Para la segunda opción se propone utilizar el formato de fila y columna comprimida, descrito en http://www-users.cs.umn.edu/
Para la tercera opción, la versión de almacenamiento completo será la versión general del producto matriz por matriz, y la versión que aprovecha el formato comprimido deberá garantizar que sólo se realizan los productos de los elementos que no son nulos. Se destaca que se ha escogido un almacenamiento CSR para la primera matriz y uno CSC para la segunda ya que éstas son las direcciones en que se recorren cada una de las matrices.
Finalmente, se deberá mostrar los resultados por pantalla de forma opcional para comprobar su corrección y se evaluarán las prestaciones con matrices de dimensiones 128, 256, 512 y 1024, y con un porcentajes de ceros de 95%, 99% y 99,99% en cada caso, calculando los flops y comparando con la versión densa.
Desarrollo:
SinopsisLos formatos CSR (Compress Sparse Row) y CSC (Compress Sparse Column) permiten almacenar únicamente los valores no nulos de una matriz. De esta forma se reduce el número de operaciones inútiles y el espacio en memoria. Se deberá implementar un conjunto de funciones en "C" para almacenar e imprimir matrices en formato CSR y CSC y para realizar el producto de una matriz CSR por una CSC.
Formatos comprimidos de matrices
Ambos formatos CSR y CSC, almacenan información sobre los elementos no nulos de las matrices.
Estos formatos almacenan tres vectores: {valores, posiciones, inicios}
El vector de valores es de tipo <el tipo de elementos de la matriz>, generalmente int, float (32 bits) o double (64 bits).
Los vectores de posiciones e inicios son vectores de enteros sin signo Vi € [0, 2^32-1] (para arquitecturas de 32 bits)
Almacenamiento:
El formato CSR almacena la información por filas.
Vector de valores:
- El vector de valores es un vector que contiene los elementos no nulos de la matriz, ordenados de izquierda a derecha y de arriba a abajo: primero los de la primera fila, (de izquierda a derecha), luego los de la segunda...
Vector de posiciones (columna, fila):
- El vector de posiciones indica la columna de cada elemento del vector de valores. Así pues la longitud del vector de posiciones es la misma a la del vector de valores y es la cantidad de elementos no nulos de la matriz original.
Vector de inicios:
- El vector de inicios es un vector de longitud el número de filas de la matriz. Este vector indica la posición en los vectores de valores y posiciones en los cuales empieza cada fila.
NOTA: Los vectores de valores y posiciones se podrían considerar como un único vector de pares, estructura (valor, columna)
Declaración de estructuras
typedef double mtype; // Tipo que usaremos para los valores de la matriz
typedef struct {
uint nrows, ncols; // Número de filas y de columnas de la matriz
mtype *values; // Valores de la matriz (del tipo mtype declarado arriba)
uint *positions; // Posiciones (filas o columnas) de cada valor (CSR: columnas, CSC:filas)
uint *linestarts; // Posiciones en el vector de valores (CSR: filas, CSC: columnas)
} *CSR, *CSC, *CS;
// Estructura para almacenar matrices completas
typedef struct {
mtype *values;
int rows, cols;
} *Matrix;
Coste espacial
La memoria requerida por los formatos de matrices comprimidas oscila (para matrices cuadradas siendo N el orden de la matriz) entre [N+2, 2·N2+N+2]
[(N+2)*sizeof(unsigned int), (N^2)*sizeof(mtype)+(N^2)*sizeof(unsigned int)+(N+2)*sizeof(unsigned int)]
Sin la compresión, la cantidad de memoria requerida es constante: N2+2
(N^2)*sizeof(mtype)+2*sizeof(unsigned int)
Coste temporal
SIN NODOS (usando vectores estáticos o dinámicos)
- Creación a partir de una matriz completa:
- Inserción de elementos (costoso):
- Eliminación de elementos (costoso):
- Mostrar la matriz (rápido para CSR y algo costoso para CSC):
- Multiplicar dos matrices CSR*CSC (crítico) -> Matriz
Implementación
Descargar ZIP con codigo fuente y ejecutable.
Resultados:
Tiene un precisión de mcirosegundos. Sin embargo, por ejecutarse en un entorno multitarea, hay algunos desajustes.
Las pruebas han sido realizadas con doubles como componentes de la matriz. Los FLOPS indicados son operaciones de coma flotante de doble precisión.
Procesador: AMD Athlon(tm) 64 Processor 3200+ 2.00 Ghz
RAM: 1,00 GB DDR
UNITTEST simple de 8x8 ~50%.
Matriz izquierda:
+----------------------------------------------------------------+
| 0.0, 0.0, 14.4, 15.3, 0.0, 0.0, 0.0, 1.9 |
| 0.0, 9.3, 19.8, 0.0, 20.2, 0.0, 4.0, 4.7 |
| 29.7, 0.9, 0.0, 0.2, 31.2, 0.0, 14.3, 8.9 |
| 0.0, 0.7, 4.3, 1.0, 0.0, 32.7, 0.0, 0.0 |
| 25.0, 21.1, 0.0, 5.2, 0.0, 0.0, 0.0, 29.2 |
| 4.6, 0.0, 0.0, 20.3, 0.0, 0.0, 0.0, 0.0 |
| 26.4, 0.0, 0.0, 28.2, 0.0, 6.0, 0.0, 0.0 |
| 13.7, 0.0, 0.0, 0.0, 0.0, 10.1, 10.2, 14.1 |
+----------------------------------------------------------------+
Matriz derecha:
+----------------------------------------------------------------+
| 28.0, 0.0, 20.4, 0.0, 0.0, 0.0, 20.8, 5.7 |
| 0.0, 31.5, 0.0, 29.9, 25.1, 30.4, 7.6, 11.6 |
| 14.1, 0.0, 0.0, 5.0, 2.5, 0.0, 0.0, 0.0 |
| 2.7, 0.0, 19.7, 27.2, 5.6, 0.0, 0.0, 0.0 |
| 0.0, 0.0, 0.0, 0.0, 2.7, 28.6, 18.6, 32.3 |
| 0.0, 3.4, 16.3, 32.3, 0.0, 0.0, 8.1, 0.0 |
| 0.0, 0.0, 29.5, 0.0, 0.0, 5.8, 4.5, 18.2 |
| 15.4, 23.5, 0.0, 0.0, 1.6, 21.4, 10.9, 18.9 |
+----------------------------------------------------------------+
Multiplicación usando CS | FLOPS(278) MEMORIA(920):
+----------------------------------------------------------------+
| 273.6, 44.4, 301.7, 487.4, 124.3, 40.5, 20.6, 35.7 |
| 352.0, 402.0, 117.5, 376.9, 343.9, 983.4, 514.9, 920.8 |
| 971.3, 237.6, 1032.9, 31.3, 120.1, 1193.1, 1365.7, 1615.8 |
| 63.3, 131.7, 549.9, 1123.2, 33.1, 20.5, 270.0, 7.8 |
| 1161.8, 1349.2, 611.0, 771.8, 603.8, 1267.0, 997.8, 937.4 |
| 183.9, 0.0, 495.8, 552.9, 113.3, 0.0, 96.2, 26.3 |
| 816.2, 20.3, 1192.8, 960.2, 157.0, 0.0, 597.9, 149.9 |
| 599.7, 365.8, 741.6, 325.2, 22.2, 361.2, 565.0, 528.9 |
+----------------------------------------------------------------+
Multiplicación completa | FLOPS(1024) MEMORIA(1048):
+----------------------------------------------------------------+
| 273.6, 44.4, 301.7, 487.4, 124.3, 40.5, 20.6, 35.7 |
| 352.0, 402.0, 117.5, 376.9, 343.9, 983.4, 514.9, 920.8 |
| 971.3, 237.6, 1032.9, 31.3, 120.1, 1193.1, 1365.7, 1615.8 |
| 63.3, 131.7, 549.9, 1123.2, 33.1, 20.5, 270.0, 7.8 |
| 1161.8, 1349.2, 611.0, 771.8, 603.8, 1267.0, 997.8, 937.4 |
| 183.9, 0.0, 495.8, 552.9, 113.3, 0.0, 96.2, 26.3 |
| 816.2, 20.3, 1192.8, 960.2, 157.0, 0.0, 597.9, 149.9 |
| 599.7, 365.8, 741.6, 325.2, 22.2, 361.2, 565.0, 528.9 |
+----------------------------------------------------------------+
(128x128) ~95.00% {
CON CS FLOPS ( 9288) TIEMPO ( 0.0020142225) MEMORIA( 19556)
SIN CS FLOPS ( 4194304) TIEMPO ( 0.0250970445) MEMORIA( 262168)
}
(128x128) ~99.00% {
CON CS FLOPS ( 382) TIEMPO ( 0.0007920001) MEMORIA( 4676)
SIN CS FLOPS ( 4194304) TIEMPO ( 0.0237046887) MEMORIA( 262168)
}
(128x128) ~99.99% {
CON CS FLOPS ( 0) TIEMPO ( 0.0007084699) MEMORIA( 1136)
SIN CS FLOPS ( 4194304) TIEMPO ( 0.0260801303) MEMORIA( 262168)
}
(256x256) ~95.00% {
CON CS FLOPS ( 68970) TIEMPO ( 0.0139065161) MEMORIA( 73068)
SIN CS FLOPS ( 33554432) TIEMPO ( 0.2116280142) MEMORIA( 1048600)
}
(256x256) ~99.00% {
CON CS FLOPS ( 2416) TIEMPO ( 0.0045944387) MEMORIA( 15684)
SIN CS FLOPS ( 33554432) TIEMPO ( 0.2197790501) MEMORIA( 1048600)
}
(256x256) ~99.99% {
CON CS FLOPS ( 2) TIEMPO ( 0.0030121147) MEMORIA( 2232)
SIN CS FLOPS ( 33554432) TIEMPO ( 0.2185883960) MEMORIA( 1048600)
}
(512x512) ~95.00% {
CON CS FLOPS ( 563786) TIEMPO ( 0.1193168405) MEMORIA( 292400)
SIN CS FLOPS ( 268435456) TIEMPO ( 8.0019753907) MEMORIA( 4194328)
}
(512x512) ~99.00% {
CON CS FLOPS ( 22692) TIEMPO ( 0.0393312558) MEMORIA( 62060)
SIN CS FLOPS ( 268435456) TIEMPO ( 8.0279177940) MEMORIA( 4194328)
}
(512x512) ~99.99% {
CON CS FLOPS ( 0) TIEMPO ( 0.0599517536) MEMORIA( 4784)
SIN CS FLOPS ( 268435456) TIEMPO ( 8.4407976433) MEMORIA( 4194328)
}
(1024x1024) ~95.00% {
CON CS FLOPS ( 4468796) TIEMPO ( 0.9223985171) MEMORIA( 1156116)
SIN CS FLOPS (2147483648) TIEMPO ( 65.0101345283) MEMORIA( 16777240)
}
(1024x1024) ~99.00% {
CON CS FLOPS ( 176254) TIEMPO ( 0.2427207927) MEMORIA( 235908)
SIN CS FLOPS (2147483648) TIEMPO ( 67.3218886758) MEMORIA( 16777240)
}
(1024x1024) ~99.99% {
CON CS FLOPS ( 16) TIEMPO ( 0.1075882549) MEMORIA( 10572)
SIN CS FLOPS (2147483648) TIEMPO ( 67.0303868229) MEMORIA( 16777240)
}
Conclusiones:
- La multiplicación de matrices usando formatos CS, reduce enormemente el coste temporal y espacial en matrices dispersas.
- En las multiplicaciones de matrices completas, la dispersión de elementos no nulos no afecta al rendimiento (que solo depende de las dimensiones de las matrices a multiplicar).
- En las multiplicaciones con compresión, el tiempo depende del tamaño de la matriz y de la dispersión.
