Uso de formatos de almacenamiento y algoritmos a bloques en álgebra dispersa en dispositivos masivamente paralelos.
La notoria evolución de disciplinas como la ciencia de datos y el aprendizaje automático en los últimos años ha despertado un gran interés en operaciones del álgebra lineal dispersa tales como la multiplicación de matrices dispersas generales (SpGeMM). Esta operación anteriormente no gozaban de la m...
Uloženo v:
| Hlavní autor: | |
|---|---|
| Médium: | masterThesis |
| Jazyk: | španělština |
| Vydáno: |
2024
|
| Témata: | |
| On-line přístup: | https://hdl.handle.net/20.500.12008/46179 |
| Tagy: |
Žádné tagy, Buďte první, kdo vytvoří štítek k tomuto záznamu!
|
| _version_ | 1868889971345063936 |
|---|---|
| author | Berger Álvarez, Gonzalo |
| author_browse | Berger Álvarez, Gonzalo |
| author_facet | Berger Álvarez, Gonzalo |
| author_role | author |
| collection | COLIBRI |
| dc.contributor.none.fl_str_mv | Berger Álvarez Gonzalo, Universidad de la República (Uruguay). Facultad de Ingeniería. |
| dc.creator.none.fl_str_mv | Berger Álvarez, Gonzalo |
| dc.date.none.fl_str_mv | 2024-10-07T15:23:17Z 2024-10-07T15:23:17Z 2024 |
| dc.format.none.fl_str_mv | 112 p. application/pdf |
| dc.identifier.none.fl_str_mv | Berger Álvarez, G. Uso de formatos de almacenamiento y algoritmos a bloques en álgebra dispersa en dispositivos masivamente paralelos [en línea] Tesis de maestría. Montevideo : Udelar. FI. INCO : PEDECIBA. Área Informática, 2024. 1688-2792 https://hdl.handle.net/20.500.12008/46179 |
| dc.language.none.fl_str_mv | es spa |
| dc.publisher.none.fl_str_mv | Udelar. FI. |
| dc.rights.none.fl_str_mv | info:eu-repo/semantics/openAccess Licencia Creative Commons Atribución - No Comercial - Sin Derivadas (CC - By-NC-ND 4.0) |
| dc.source.none.fl_str_mv | reponame:COLIBRI instname:Universidad de la República instacron:Universidad de la República |
| dc.subject.none.fl_str_mv | Álgebra dispersa Almacenamiento a bloques Computación de alta performance CUDA GPU |
| dc.title.none.fl_str_mv | Uso de formatos de almacenamiento y algoritmos a bloques en álgebra dispersa en dispositivos masivamente paralelos. |
| dc.type.none.fl_str_mv | Tesis de maestría info:eu-repo/semantics/masterThesis info:eu-repo/semantics/acceptedVersion |
| description | La notoria evolución de disciplinas como la ciencia de datos y el aprendizaje automático en los últimos años ha despertado un gran interés en operaciones del álgebra lineal dispersa tales como la multiplicación de matrices dispersas generales (SpGeMM). Esta operación anteriormente no gozaban de la misma atención dedicada como por ejemplo a la multiplicación de matriz dispersavector (SpMV) por parte de la comunidad científica. Consecuentemente, hoy día son comunes los esfuerzos de investigación volcados al desarrollo eficiente de ambas rutinas en plataformas paralelas. La mayoría de las operaciones sobre matrices dispersas son caracterizadas por implicar una cantidad baja de cómputo en relación a los accesos a memoria, algo que dificulta explotar la gran capacidad de cómputo que tienen dispositivos masivamente paralelos como las GPUs. Estos accesos, además, son altamente irregulares, dado que dependen de la distribución de los valores no nulos y, en el caso de SpGeMM, dependen también de como se vinculen los elementos no nulos de las dos matrices de entrada. Para mitigar esta irregularidad, una posibilidad es el uso de formatos a bloques para el almacenamiento de las matrices dispersas. En este trabajo se explora el uso de formatos de almacenamiento a bloques para las operaciones SpGeMM y SpMV. En este sentido, se profundiza en el formato bmSparse, que permite potenciales ahorros importantes tanto en espacio de almacenamiento como en accesos a memoria. En primera instancia, se busca atacar distintos cuellos de botella de una implementación base de la operación SpGeMM a través de distintas propuestas, que incluyen cambios en la representación del formato, mejoras en el paso de ordenamiento y el uso de Tensor Cores para la multiplicación de bloques. Por otro lado, se implementa una rutina para la operación SpMV con el fin de explorar el potencial del formato más allá del producto de matrices dispersas. Los resultados obtenidos al evaluar estas dos implementaciones en matrices de distintos tamaños de la Suite Sparse Matrix Collection muestran importantes mejoras del tiempo de ejecución para varias matrices. En el caso de SpGeMM, la implementación propuesta obtiene resultados considerablemente mejores que las variantes para CSR presentes en bibliotecas conocidas como cuSPARSE de NVIDIA y MKL de Intel, y es competitiva con la implementación para BCSR de esta última. En el caso de SpMV, se alcanzan speedups de más de 4× en algunas matrices en comparación con la implementación de cuSPARSE para CSR, lo que sugiere que el formato es una alternativa interesante para distintas aplicaciones que involucran el uso de matrices dispersas. |
| eu_rights_str_mv | openAccess |
| format | masterThesis |
| id | anni_1a4cc039fa12e9af679bf8a72a17103e |
| identifier_str_mv | Berger Álvarez, G. Uso de formatos de almacenamiento y algoritmos a bloques en álgebra dispersa en dispositivos masivamente paralelos [en línea] Tesis de maestría. Montevideo : Udelar. FI. INCO : PEDECIBA. Área Informática, 2024. 1688-2792 |
| instacron_str | Universidad de la República |
| institution | Universidad de la República |
| instname_str | Universidad de la República |
| language | spa |
| language_invalid_str_mv | es |
| network_acronym_str | anni |
| network_name_str | oai-lr-anni |
| oai_identifier_str | oai:colibri.udelar.edu.uy:20.500.12008/46179 |
| publishDate | 2024 |
| publishDateSort | 2024 |
| publisher.none.fl_str_mv | Udelar. FI. |
| reponame_str | COLIBRI |
| repository.mail.fl_str_mv | |
| repository.name.fl_str_mv | |
| repository_id_str | |
| rights_invalid_str_mv | Licencia Creative Commons Atribución - No Comercial - Sin Derivadas (CC - By-NC-ND 4.0) |
| spelling | Uso de formatos de almacenamiento y algoritmos a bloques en álgebra dispersa en dispositivos masivamente paralelos.Berger Álvarez, GonzaloÁlgebra dispersaAlmacenamiento a bloquesComputación de alta performanceCUDAGPULa notoria evolución de disciplinas como la ciencia de datos y el aprendizaje automático en los últimos años ha despertado un gran interés en operaciones del álgebra lineal dispersa tales como la multiplicación de matrices dispersas generales (SpGeMM). Esta operación anteriormente no gozaban de la misma atención dedicada como por ejemplo a la multiplicación de matriz dispersavector (SpMV) por parte de la comunidad científica. Consecuentemente, hoy día son comunes los esfuerzos de investigación volcados al desarrollo eficiente de ambas rutinas en plataformas paralelas. La mayoría de las operaciones sobre matrices dispersas son caracterizadas por implicar una cantidad baja de cómputo en relación a los accesos a memoria, algo que dificulta explotar la gran capacidad de cómputo que tienen dispositivos masivamente paralelos como las GPUs. Estos accesos, además, son altamente irregulares, dado que dependen de la distribución de los valores no nulos y, en el caso de SpGeMM, dependen también de como se vinculen los elementos no nulos de las dos matrices de entrada. Para mitigar esta irregularidad, una posibilidad es el uso de formatos a bloques para el almacenamiento de las matrices dispersas. En este trabajo se explora el uso de formatos de almacenamiento a bloques para las operaciones SpGeMM y SpMV. En este sentido, se profundiza en el formato bmSparse, que permite potenciales ahorros importantes tanto en espacio de almacenamiento como en accesos a memoria. En primera instancia, se busca atacar distintos cuellos de botella de una implementación base de la operación SpGeMM a través de distintas propuestas, que incluyen cambios en la representación del formato, mejoras en el paso de ordenamiento y el uso de Tensor Cores para la multiplicación de bloques. Por otro lado, se implementa una rutina para la operación SpMV con el fin de explorar el potencial del formato más allá del producto de matrices dispersas. Los resultados obtenidos al evaluar estas dos implementaciones en matrices de distintos tamaños de la Suite Sparse Matrix Collection muestran importantes mejoras del tiempo de ejecución para varias matrices. En el caso de SpGeMM, la implementación propuesta obtiene resultados considerablemente mejores que las variantes para CSR presentes en bibliotecas conocidas como cuSPARSE de NVIDIA y MKL de Intel, y es competitiva con la implementación para BCSR de esta última. En el caso de SpMV, se alcanzan speedups de más de 4× en algunas matrices en comparación con la implementación de cuSPARSE para CSR, lo que sugiere que el formato es una alternativa interesante para distintas aplicaciones que involucran el uso de matrices dispersas.Udelar. FI.Berger Álvarez Gonzalo, Universidad de la República (Uruguay). Facultad de Ingeniería.2024-10-07T15:23:17Z2024-10-07T15:23:17Z2024Tesis de maestríainfo:eu-repo/semantics/masterThesisinfo:eu-repo/semantics/acceptedVersion112 p.application/pdfBerger Álvarez, G. Uso de formatos de almacenamiento y algoritmos a bloques en álgebra dispersa en dispositivos masivamente paralelos [en línea] Tesis de maestría. Montevideo : Udelar. FI. INCO : PEDECIBA. Área Informática, 2024.1688-2792https://hdl.handle.net/20.500.12008/46179reponame:COLIBRIinstname:Universidad de la Repúblicainstacron:Universidad de la RepúblicaesspaLas obras depositadas en el Repositorio se rigen por la Ordenanza de los Derechos de la Propiedad Intelectual de la Universidad de la República.(Res. Nº 91 de C.D.C. de 8/III/1994 – D.O. 7/IV/1994) y por la Ordenanza del Repositorio Abierto de la Universidad de la República (Res. Nº 16 de C.D.C. de 07/10/2014)info:eu-repo/semantics/openAccessLicencia Creative Commons Atribución - No Comercial - Sin Derivadas (CC - By-NC-ND 4.0)oai:colibri.udelar.edu.uy:20.500.12008/461792026-04-14T10:27:58Z |
| spellingShingle | Uso de formatos de almacenamiento y algoritmos a bloques en álgebra dispersa en dispositivos masivamente paralelos. Berger Álvarez, Gonzalo Álgebra dispersa Almacenamiento a bloques Computación de alta performance CUDA GPU |
| status_str | acceptedVersion |
| title | Uso de formatos de almacenamiento y algoritmos a bloques en álgebra dispersa en dispositivos masivamente paralelos. |
| title_full | Uso de formatos de almacenamiento y algoritmos a bloques en álgebra dispersa en dispositivos masivamente paralelos. |
| title_fullStr | Uso de formatos de almacenamiento y algoritmos a bloques en álgebra dispersa en dispositivos masivamente paralelos. |
| title_full_unstemmed | Uso de formatos de almacenamiento y algoritmos a bloques en álgebra dispersa en dispositivos masivamente paralelos. |
| title_short | Uso de formatos de almacenamiento y algoritmos a bloques en álgebra dispersa en dispositivos masivamente paralelos. |
| title_sort | Uso de formatos de almacenamiento y algoritmos a bloques en álgebra dispersa en dispositivos masivamente paralelos. |
| topic | Álgebra dispersa Almacenamiento a bloques Computación de alta performance CUDA GPU |
| url | https://hdl.handle.net/20.500.12008/46179 |