¿Qué técnicas utiliza el marco petsc para la multiplicación de matriz dispersa?

Answer 1

PETSc es una buena biblioteca si desea mejorar el rendimiento de SpMV en serie o en paralelo sin ajustar manualmente su propio código o usar instrucciones SSE o una serie de bibliotecas sintonizadas más pequeñas. PETSc se optimiza para SpMV directamente desde la carga de la matriz en un formato binario (leer el archivo .mtx es una gran sobrecarga) para ofrecer una variedad de estructuras de datos de matriz apropiadas (en serie y en paralelo) para proporcionar varias configuraciones de tiempo de ejecución para ajustar el rendimiento , como el tamaño del bloque.

PETSc implementa diferentes algoritmos de SpMV para diferentes tipos de matriz, a saber, casos simétricos y no simétricos. El diseño de datos y los accesos vectoriales se planifican cuidadosamente para maximizar la reutilización de datos durante el cálculo, particularmente para los tamaños de bloque 1-7 u 8. Desde mi experiencia, la asignación previa para la matriz (dependiendo de la estructura de dispersión de la matriz) y la elección de la estructura de datos + bloque apropiado El tamaño de su matriz dispersa son perillas críticas que desea ajustar para mejorar el rendimiento de su SpMV.

Answer 2

PETSc tiene varios formatos de matriz, pero el formato disperso principal es una variante en el almacenamiento de filas comprimidas. Si ejecuta en un solo procesador, es exactamente CRS. Para hacer un producto paralelo, hicieron algo bastante ingenioso.

Primero debe saber que se distribuye una matriz dispersa paralela (formato MPIAIJ) con cada procesador que tiene un blockrow: un número consecutivo de filas. Esto podría almacenarse como una matriz dispersa única, con alguna anotación sobre qué subconjunto de la matriz global es.

En su lugar, almacenan la parte en cada procesador como * dos * matrices, una parte que contiene el bloque diagonal cuadrado (es decir, aquellos elementos cuyos índices de columna están en el rango de filas que almacena el procesador) y una para todo lo demás. Esto le permite implementar el producto de matriz dispersa de la siguiente manera:

1. Publique un montón de solicitudes de Isend e Irecv para los datos de otros procesadores
2. Multiplica por la parte diagonal de la matriz
3. Espere a que se completen las llamadas Isend / Irecv
4. Multiplica por la parte fuera de la diagonal.

Almacenar la parte en el procesador como dos matrices CRS es bastante elegante.