Resumen

La multiplicación de matrices y vectores dispersos (SpMV) es una operación importante en la ciencia computacional y necesita ser acelerada porque a menudo representa el coste dominante en muchos métodos iterativos y problemas de valores propios ampliamente utilizados. Logramos este objetivo proponiendo un novedoso algoritmo de SpMV basado en la fila dispersa comprimida (CSR) en la GPU. Nuestro método asigna dinámicamente distintos números de filas a cada bloque de hilos y ejecuta distintas implementaciones de optimización en función del número de filas que implique para cada bloque. El proceso de accesos a las matrices CSR está totalmente coalescido y el ancho de banda de la DRAM de la GPU se utiliza de forma eficiente cargando los datos en la memoria compartida, lo que alivia el cuello de botella de muchos algoritmos existentes basados en CSR (es decir, CSR-escalar y CSR-vectorial). Los resultados de las pruebas realizadas en GPUs C2050 y K20c demuestran que nuestro método supera a un algoritmo de CSR perfecta que inspira nuestro trabajo, a los algoritmos CUSPARSE V6.5 y CUSP V0.5.1 ajustados por el fabricante y a tres algoritmos populares clSpMV, CSR5 y CSR-Adaptive.

• Materias:Análisis Matemático Matemáticas Algebra Ingeniería Lógica matemática
• Subjects:Mathematical Analysis mathematics Algebra Engineering Mathematical logic
• Palabras claves:Multiplicación matriz-vectorial dispersa; SpMV; ciencia computacional; acelerado; coste dominante; métodos iterativos; problemas de valores propios; nuevo algoritmo SpMV; fila dispersa comprimida; CSR; GPU; asigna dinámicamente; bloque de hilos; implementaciones de optimización; matrices CSR; coalesced; ancho de banda DRAM; memoria compartida; cuello de botella; algoritmos basados en CSR; resultados de pruebas; GPUs C2050; K20c; algoritmo Perfect-CSR; vendor tuned CUSPARSE V6.5; CUSP V0.5.1; clSpMV; CSR5; CSR-Adaptive.
• Keywords:Sparse matrix-vector multiplication; SpMV; computational science; accelerated; dominant cost; iterative methods; eigenvalue problems; novel SpMV algorithm; compressed sparse row; CSR; GPU; dynamically assigns; thread block; optimization implementations; CSR arrays; coalesced; DRAM bandwidth; shared memory; bottleneck; CSR-based algorithms; test results; C2050; K20c GPUs; perfect-CSR algorithm; vendor tuned CUSPARSE V6.5; CUSP V0.5.1; clSpMV; CSR5; CSR-Adaptive.