<  Retour au portail Polytechnique Montréal

Modélisation des accès mémoire lors de la multiplication d'une matrice creuse par un vecteur sur processeur graphique

Thalie Léna Keklikian

Mémoire de maîtrise (2014)

[img]
Affichage préliminaire
Télécharger (2MB)
Citer ce document: Keklikian, T. L. (2014). Modélisation des accès mémoire lors de la multiplication d'une matrice creuse par un vecteur sur processeur graphique (Mémoire de maîtrise, École Polytechnique de Montréal). Tiré de https://publications.polymtl.ca/1644/
Afficher le résumé Cacher le résumé

Résumé

RÉSUMÉ : Une matrice creuse est une matrice dont une grande proportion des éléments sont nuls. Il est sou-vent avantageux de ne pas tenir compte des éléments nuls lors d’une opération utilisant une ma-trice creuse. Plusieurs formats de représentation réduisent l’espace nécessaire pour représenter une matrice creuse. Dans la résolution de systèmes linéaires creux, la matrice creuse est souvent multi-pliée par un vecteur dense. Cette opération est fréquemment utilisée dans des domaines comme l’électromagnétique, le classement de pages web ou des problèmes de transport et de livraison.Depuis quelques années, les processeurs graphiques (GPU) deviennent de plus en plus perfor-mants et s’intègrent aux superordinateurs. La multiplication entre une matrice creuse et un vecteur (SpMV – Sparse Matrix-Vector Multiplication) peut être implémentée sur un GPU, puisque l’opération peut se diviser en une série de produits scalaires indépendants. Par contre, c’est une opération difficile à optimiser. Plusieurs travaux ont été réalisés sur son accélération et les auteurs s’entendent pour dire que son exécution est ralentie par les accès à la mémoire irréguliers et diffi-ciles à prévoir.Dans ce mémoire, nous présentons un modèle permettant de calculer le nombre d’accès à la mé-moire de la SpMV implémentée sur GPU pour quatre formats de représentation : le format de compression de ligne (CSR), le format ELLPACK (ELL), le format de coordonnées (COO) et un format hybride entre ELL et COO abrégé à HYB. Le modèle permet de prédire la performance d’une SpMV selon la matrice utilisée, son format et le GPU sur lequel elle est implémentée. Une SpMV ayant moins d’accès à la mémoire aura une meilleure performance. Le modèle calcule le nombre de requêtes à la mémoire et le nombre de transactions à la mémoire. Une requête repré-sente une demande de lecture ou d’écriture et une transaction représente le nombre de transferts de données déclenchés par une requête. Pour valider le modèle, des implémentations de la SpMV ont été exécutées sur deux cartes GPU récentes, la NVIDIA GeForce GTX 670 et la NVIDIA Tesla K20c. Les matrices utilisées pour les tests sont de tailles différentes et de structures irrégulières. Les résultats montrent que dans le meilleur des cas, le modèle estime parfaitement le nombre de transactions ou de requêtes. Les moyennes des erreurs entre les nombres de transactions estimés et mesurés pour deux implémenta-tions du format CSR, le format ELL, le format COO et le format HYB sont de 1.1 %, 2.6 %, 0 %, 0.7 % et 0.3 % respectivement. De plus, le meilleur format pour la grande majorité des ma-trices testées est le format HYB, puisqu’il a requis le moins de transactions et de requêtes. ----------ABSTRACT A sparse matrix is a matrix in which the majority of elements are zeroes. It is almost always bene-ficial to avoid calculations on the zero elements when using sparse matrices. For this purpose, sev-eral formats have been created to compress sparse matrices by storing only the nonzero elements. An important operation involving a sparse matrix is the sparse matrix-vector multiplication (SpMV) that can be found in many sparse linear solvers. The SpMV is used in many high perfor-mance computing applications in fields such as electromagnetics, ranking of web pages or trans-portation problems.Graphics processing units have become more powerful over the past few years and are now inte-grated to supercomputers. The SpMV can be implemented on a GPU since the operation can be divided in multiple dot products between a row of the matrix and the vector. However, the SpMV is difficult to optimize and its acceleration has been studied by several authors. It mostly suffers from poor memory access performance which is difficult to anticipate.In this project, we propose a model predicting the number of requests and transactions to the memory of the SpMV implemented on GPU. The four formats that were explored are the com-pressed sparse row format (CSR), the ELLPACK format (ELL), the coordinated format (COO) and a format that is a hybrid between ELL and COO called HYB. Our model can help predict the performance of a SpMV depending on the sparse matrix, the format and the GPU used. When a memory access is requested, it can cause one or multiple data transactions depending of the transfer size. A SpMV implementation has a better performance when the number of memory transactions that it requires is less than with another one.Our model is validated on two recent GPU boards: the NVIDIA GeForce GTX 670 and the NVIDIA Tesla K20c. Sparse matrices used are chosen from different fields and are unstructured so that the results apply to a larger range of matrices. The results show that, in the best case sce-nario, the estimated number of transactions and requests exactly match the profiled ones. With respect to the number of memory transactions, the average errors between the estimated numbers and the profiled ones are 1.1 %, 2.6 %, 0 %, 0.7 % and 0.3 % for two implementation of the CSR format, the ELL format, the COO format and the HYB format respectively. Also, the HYB for-mat shows the best performance, since it requires the smallest number of memory transactions and requests.

Document en libre accès dans PolyPublie
Département: Département de génie électrique
Directeur de mémoire/thèse: Yvon Savaria et J.M. Pierre Langlois
Date du dépôt: 01 avr. 2015 15:08
Dernière modification: 24 oct. 2018 16:11
Adresse URL de PolyPublie: https://publications.polymtl.ca/1644/

Statistiques

Total des téléchargements à partir de PolyPublie

Téléchargements par année

Provenance des téléchargements

Actions réservées au personnel