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

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.