Lecture critique et synthèse de: Exploiting Memory Access Patterns to Improve Memory Performance in Data-Parallel Architectures

Jean-François Patenaude

Département de génie logiciel et des technologies de l’information, École de technologie supérieure
1100 rue Notre-Dame Ouest, Montréal (Québec) H3C 1K3 Canada

Abstract—On retrouve une quasi-ubiquité de GPU permettant les calculs en tout genre (GPGPU) sur le marché. Or, il y a encore peu de logiciels qui en prennent avantage. Une de ces raisons est la complexité du développement de logiciels parallèles sur les GPU. C’est en grande partie parce que la gestion de la mémoire est laissée aux soins du développeur. D’ailleurs, une mauvaise gestion de la mémoire peut impacter grandement la performance du logiciel, d’autant plus que les cartes graphiques sont optimisées pour offrir une très large bande passante de mémoire, mais avec des temps de réponse moins rapide. Un article portant sur une méthodologie qui permet de systématiser l’application de techniques d’amélioration de l’accès de la mémoire afin de garantir de bonnes performances a récemment été publié. Selon cette méthodologie, l’optimisation est alors fonction des différents patrons d’accès de la mémoire et de l’architecture sous-jacente : vectorielle comme les GPU d’AMD ou scalaire comme ceux de NVIDIA. Dans le présent article, une synthèse de la méthodologie sera présentée. Puis, une analyse suivra afin de discuter de la méthodologie et de la critiquer.

Index Terms—General-purpose computation on GPUs (GPGPUs), GPU computing, memory optimization, memory access pattern, vectorization, memory selection, memory coalescing, data parallelism, data-parallel architectures.

Introduction Bien que le GPGPU existe depuis plus de trois décennies, les outils de développement étaient jusqu’alors déficients ou tout simplement inexistants [1]. Aujourd’hui, l’offre des deux géants de l’industrie des processeurs graphiques, AMD et NVIDIA, s’est grandement améliorée et les développeurs ont accès à plusieurs outils pour développer leurs programmes parallèles sur les GPU. En effet, il est maintenant très facile de se procurer une carte graphique qui permet de faire du GPGPU. En fait, depuis l’année 2006, la majorité des cartes graphiques vendues contiennent un processeur graphique qui supporte le GPGPU. C’est lors de cette année qu’AMD et NVIDIA, sortaient leurs outils de développement de GPGPU de pair avec leurs nouveaux GPU offrant plus de programmabilité [2], [3]. Or, les programmes parallèles ont un niveau de complexité plus élevé que les programmes séquentiels. En effet, les compilateurs n’étant pas encore assez évolués et matures, il en revient aux développeurs d’optimiser l’utilisation de la mémoire. Quatre chercheurs, Byunghyun Jang, Dana Schaa, Perhaad Mistry et David Kaeli, se sont penchés sur l’étude des patrons d’accès de la mémoire afin d’y déceler des optimisations possibles [4]. Il s’agirait donc de définir une méthodologie qui garantirait de meilleures performances pour certains cas typiques. Deux différentes techniques sont alors présentées et testées selon l’architecture parallèle sous-jacente. Il y a donc la vectorisation obtenue par une transformation sur les données d’entrée pour les architectures vectorielles et la sélection algorithmique de l’espace mémoire pour les architectures scalaires. Voyons si l’application de la méthodologie présentée par ces chercheurs tient la route et si elle parvient à faciliter la tâche des développeurs pour le développement de programmes parallèles.

Background • Architecture scalaire : architecture qui n’est pas vectorielle dans le sens où elle ne fait qu’une opération à la fois, mais avec plusieurs threads. On parle du modèle d’exécution Single Instruction Multiple Threads (SIMT) et il est très utile pour paralléliser les programmes qui ne sont pas vectorisables. • Architecture vectorielle : les opérations mémoire et les calculs sont effectués sur jusqu’à 4 éléments à la fois. La vectorisation des données permet alors de faire jusqu’à 4 fois plus d’opérations en même temps. • Coalescence de la mémoire (Memory Coalescence) : fusion de blocs adjacents de mémoire afin de remplir l’espace libérée par de la mémoire désaffectée. • CPU : Unité de traitement centrale (Central Processing Unit), là où est normalement exécuté le traitement séquentiel. • Foulée non unitaire (non-unit stride) : un saut qui n’est pas unitaire, par exemple un saut de 3 ou de 2*indice. • Fractionnellement vectorisable : lorsque seulement une partie des tableaux peut être mappée directement aux vecteurs. • GPGPU : calcul générique sur un processeur graphique (General Purpose computing on Graphics Processing Units), consiste à utiliser le processeur de la carte graphique pour d’autres fins que les calculs graphiques. • GPU : unité de traitement graphique (Graphic Processing Unit), le processeur graphique. • Intrinsèquement vectorisable : lorsque tous les tableaux peuvent être directement mappés aux vecteurs sans nécessité de transformations. • Loi d’Amdahl : selon cette loi, le temps de calcul est dépendant du traitement séquentiel, puisqu’avec un nombre infini de processeurs pour le traitement parallèle, le temps de calcul du traitement parallèle devient nul. • Mémorisation par bloc : l’organisation de la mémoire dans la mémoire court terme en un ensemble large et gérable de blocs. • Réutilisation temporelle (temporal reuse) : lorsque la même donnée est réutilisée dans plus d’une itération. • Temps système (overhead) : temps supplémentaire requis pour effectuer le pré-traitement. • Vectorisation : linéarisation des données pour permettre le traitement vectoriel.

Analyse de l’article Il faut commencer par présenter le modèle mathématique qui supporte les différents patrons d’accès à la mémoire. Ensuite, ces différents patrons vont être utilisés pour décider des transformations à faire sur les données d’entrées ou pour décider de l’espace mémoire qui sera utilisé pour stocker les données. Finalement, un comparatif est fait entre l’utilisation de la méthodologie et l’utilisation des paramètres par défaut (aucune optimisation).

Modèle mathématique des patrons d’accès de la mémoire Le modèle mathématique qui représente les différents patrons d’accès de la mémoire lors de l’exécution d’une boucle de calcul est basé sur des travaux précédents qui cherchaient à améliorer le principe de localité sur un processeur à un seul cœur [5]. Afin de mieux comprendre le modèle, considérons un tableau de M dimensions qui est accédé par une boucle de calcul de profondeur D. De plus, définissons le vecteur d’accès de la mémoire [pic] qui est de grandeur M. La forme affine de [pic] est alors : [pic] où M est la matrice d’accès mémoire de grandeur M x D, [pic] le vecteur d’itération de grandeur D et [pic] le vecteur de décalage de grandeur M.

Patrons d’accès de la mémoire La figure 1 montre les différents patrons d’accès de la mémoire ainsi que leur matrice d’accès mémoire M et leur vecteur de décalage[pic]Voici la description des différents patrons et un exemple où nous pouvons les retrouver : • Linear et Reverse Linear sont lorsque l’accès d’une dimension d’un tableau est contigu dans une itération (figure 1a et 1b). Ils se retrouvent dans la plupart des Basic Linear Algebra Subprograms (BLAS) de niveau 1 et 2 [6]. • Shifted est un accès linéaire qui est décalé d’une certaine constante (figure 1c). Il se retrouve dans les logiciels multimédias où plusieurs flux de données sont combinés ou transformés. • Overlapping est lorsqu’une dimension d’un tableau est accédée par plus d’une seule itération (figure 1d). Il se retrouve dans les solveurs d’équation linéaire où la décomposition Lower-Upper (LU) est utilisée. • Non-unit Stride est lorsque l’accès d’une dimension d’un tableau est fait avec une foulée non unitaire (non-unit stride) (figure 1e). Il se retrouve dans certaines opérations de multiplications de matrices. • Random est lorsque l’accès d’une dimension d’un tableau est aléatoire (figure 1f). Il se retrouve lorsque les accès mémoires sont indexés par un autre tableau, par exemple avec les tables de hachage. Bien entendu, il s’agit des formes de base des patrons, il est possible de les retrouver combinés.
[pic]

Figure 1 Patrons d'accès de la mémoire et représentation mathématique. Les éléments accédés sont en gris. Un C représente une constante. Un Z représente un nombre aléatoire.

Transformation des données d’entrée pour la vectorisation Pour les architectures vectorielles, comme les GPU d’AMD, il est nécessaire d’appliquer des transformations sur les données pour les vectoriser afin d’optimiser les accès à la mémoire. Avant d’appliquer une transformation, il faut voir si les tableaux sont vectorisables. Pour ce faire, il s’agit de vérifier que tous les tableaux impliqués possèdent le même patron d’accès de la mémoire pour leur dernière dimension. Afin d’arriver à quantifier le niveau de vectorisation d’une boucle de calcul fractionnellement vectorisable, la formule suivante est utilisée :
[pic]
Les boucles de calculs intrinsèquement vectorisables ont un Qv de 100%. Étant donné que les GPU d’AMD font le mappage vectoriel lorsque les données sont transférées du CPU vers le GPU, les transformations sur les données doivent être faites au niveau du CPU. Ainsi, la transformation sera appliquée selon la règle : [pic] où Tm est la matrice de transformation de grandeur D x D (D étant la grandeur du vecteur d’itération) et où [pic]est un vecteur de décalage de grandeur D. On obtient alors un nouveau vecteur d’accès de la mémoire, [pic]. Voici donc les différentes transformations à faire sur les données d’entrée afin d’obtenir des matrices vectorisables : • Les patrons Linear et Reverse Linear nécessitent d’inverser l’ordre des données. Ainsi, on utilisera la matrice de transformation suivante : [pic][pic] • Le patron Shifted ne nécessite qu’un vecteur de décalage afin de réaligner les données. Ainsi, on utilisera le vecteur de décalage suivant : [pic] où C représente une constante. • Le patron Overlapping pouvant apparaître lorsqu’il y a des boucles imbriquées et où les indices sont utilisés conjointement. Les accès se retrouveront alors shifted à chaque itération. Par exemple, la matrice d’accès de la mémoire M suivante nécessite une matrice de transformation Tm tel que : [pic] • Le patron Non-unit Stride nécessite d’être linéarisé en rassemblant un gros bloc de données en mémoire adressable linéaire. Le temps système requis pour accomplir cette tâche peut rapidement devenir assez important compte tenu du niveau de restructuration des données nécessaire. Par exemple, la matrice d’accès de la mémoire M suivante nécessite une matrice de transformation Tm tel que : [pic] • Le patron Random n’a toujours pas de méthode pour être linéarisé et c’est un des points qui limite l’adoption de la vectorisation pour le GPGPU. Bien entendu, il est possible de combiner des transformations lorsque plus d’un patron d’accès de la mémoire est présent. Afin de bien identifier quelles transformations appliquées, toutes les matrices d’accès de la mémoire en entrée sont analysées pour trouver le plus grand groupe de rangées vectorisables ensemble. C’est donc ici que le Qv est utilisé. Par la suite, les patrons d’accès mémoire sont identifiés pour chaque rangée. Puis, la transformation adéquate est finalement appliquée.

Sélection de l’espace mémoire Pour les architectures scalaires, comme les GPU de NVIDIA, l’optimisation de l’accès à la mémoire se fait par le choix judicieux de l’espace mémoire utilisé pour stocker les données d’entrée et de sortie. Le tableau 1 présente les différents espaces mémoire tels que définis par NVIDIA sur leurs GPU ainsi que leurs principales caractéristiques.

TABLE I
Espaces mémoire des GPU de NVIDIA

|Espace |Emplacement |Mise en |Accès |Portée |
|mémoire | |cache | | |
|Global |Mémoire GPU |Non |Lecture/Écriture |Thread Grid|
|Constant |Mémoire GPU |Oui |Lecture |Thread Grid|
|Texture |Mémoire GPU |Oui |Lecture |Thread Grid|
|Shared |Puce du |s.o. |Lecture/Écriture |Thread |
| |processeur | | |Block |
| |graphique | | | |

Voici une brève description des différents espaces mémoires disponibles aux développeurs et les utilisations pour lesquelles ils performent le mieux : • Global Memory est l’espace mémoire par défaut du compilateur puisque c’est le plus flexible. Toutefois, le temps de réponse étant plus lent de deux ordres de grandeur, les accès en série coûtent cher en temps. Il est le mieux utilisé pour les données de sorties et pour les données d’entrée en lecture ou en écriture seule qui sont coalescentes et qui ne sont pas réutilisées temporellement. • Constant Memory est un espace mémoire de petite taille qui est accessible par tous les threads. Il est le mieux utilisé pour les données en lecture seule d’assez petite taille et pour les accès mémoires d’un tableau qui sont identiques pour tous les threads. • Texture Memory utilise le même espace mémoire que le Global Memory, mais peut être mis en cache. Le cache de texture est optimisé pour la localité spatiale en deux dimensions. Il est le mieux utilisé pour les données en lecture seule qui ne sont pas coalescentes et pour les données en lecture seule qui ne correspondent à aucun des autres espaces mémoire. • Shared Memory est local au multiprocesseur et est seulement visible par les threads actifs sur celui-ci. Le temps de réponse est sensiblement le même que celui des registres, c’est-à-dire deux ordres de grandeur plus rapide que le Global Memory. Il est le mieux utilisé pour les données en lecture/écriture qui sont réutilisées temporellement et sont mémorisables par bloc. Il s’agit maintenant d’appliquer un algorithme de sélection de l’espace mémoire selon les différents critères des espaces mémoire et de leurs meilleures utilisations possibles. L’algorithme va prendre en entrée la matrice d’accès mémoire et le décalage de toutes les instances d’un tableau, la taille des données, les accès en lecture et écriture et l’information de la réutilisation temporelle. Les différents critères suivants sont alors analysés pour faire le choix de l’espace mémoire : • Lecture seule ou lecture et écriture • La taille des données • Le patron d’accès de la mémoire • Le patron d’accès de la mémoire interthread • Le patron d’accès de la mémoire intrathread • L’information de réutilisation temporelle Après l’analyse de l’algorithme, si plusieurs choix sont disponibles, l’ordre de sélection suivant est appliqué lors de l’accès en lecture seule : 1. Texture Memory 2. Global Memory 3. Shared Memory 4. Constant Memory et lors de l’accès en lecture et écriture : 1. Global Memory 2. Shared Memory

Tests et résultats L’application du modèle mathématique et des optimisations subséquentes ont été évaluées à l’aide de suite de tests de performance de calcul de haute performance. Par exemple, la suite Linpack a été utilisée pour tester les optimisations des architectures vectorielles (GPU d’AMD) et la suite Parboil pour tester celles des architectures scalaires (GPU de NVIDIA). Un fait intéressant, l’algorithme servant à quantifier la vectorisation des boucles de calculs a permis de déceler qu’un nombre significatif de logiciels de calcul de haute performance contenait des boucles vectorisables après transformations sur les données. La plupart des boucles qui ne pouvaient être vectorisées avaient des dépendances liées à la boucle ou avaient simplement un patron d’accès de la mémoire Random. Pour les cinq suites de tests effectuées sur un GPU d’AMD, on a vu une augmentation de la vitesse d’exécution de 1.39 fois à 11.4 fois plus rapide. Néanmoins, le temps système requis pour effectuer certaines transformations devient substantiellement significatif. Lors de l’exécution des tests, ce temps système pouvait être négligeable ou prendre jusqu’à 23.16 % du temps total d’exécution. Pour les tests exécutés sur un GPU de NVIDIA, les résultats ont été comparés avec l’espace mémoire par défaut pour les données, c’est-à-dire le Global Memory. L’augmentation de vitesse d’exécution observée va de 0 fois, lorsque la mémoire par défaut est le meilleur choix possible, et jusqu’à 13.5 fois plus rapide.

Discussion Les auteurs se sont penchés sur un des problèmes qui freinent de façon notable l’adoption du GPGPU. En effet, les développeurs souhaitant exploiter les performances du GPGPU se heurtent à beaucoup de difficultés lors du développement du logiciel. Or, le modèle mathématique et les différents algorithmes de sélection que proposent les auteurs visent à simplifier le travail des développeurs en automatisant une partie des décisions et de l’analyse du logiciel. Ainsi, plus de développeurs pourraient se « risquer » à entrer dans le domaine du développement GPGPU. Du moins, la tâche des développeurs actuels s’en trouverait sans aucun doute faciliter. Toutefois, ce n’est pas la première fois que les techniques d’optimisation de la mémoire avancées par les auteurs sont proposées [7], [8]. Aussi, le modèle mathématique qui permet d’identifier les différents patrons d’accès de la mémoire a été développé dans le but d’améliorer le principe de localité pour un processeur à un seul cœur [5]. Malgré tout, ce sont les auteurs qui ont eu l’idée de combiner les deux pour présenter une méthodologie qui systématise et garantie un certain niveau de performance qui se rapproche de la capacité des GPU. La méthodologie présentée ne permet pas encore de traiter tous les patrons d’accès de la mémoire. En effet, plus de recherche serait nécessaire pour arriver à traiter des cas complexes comme les accès mémoire « aléatoires » (le patron Random) où les accès mémoires ne suivent pas de patrons particuliers ou qui ne peuvent être prévus. D’ailleurs, bien que la méthodologie ait été testée avec des programmes qui sont couramment utilisés dans le calcul de haute performance, les auteurs ne tiennent pas compte des performances du programme en entier. En effet, ils regardent seulement les performances de la boucle de calculs qu’ils ont optimisée et quelques fois ils regardent le temps système requis comme avec les transformations sur les données. Or, pour les architectures vectorielles comme les GPU d’AMD, les transformations doivent être faites sur le CPU. Le temps système utilisé pour ces transformations ne tient pas compte du fait que le CPU est préemptif et que la transformation pourrait facilement prendre plus de temps que le temps qui est sauvé en vectorisant. D’ailleurs, en tenant compte de la loi d’Amdahl, l’ajout de traitement sur le CPU vient en fait augmenter grandement le temps total d’exécution puisque ce traitement ne peut être fait que séquentiellement. Il serait alors pertinent de vérifier à quel point le temps système utilisé pour les transformations vient impacter le gain de performance de la vectorisation. Du côté des architectures scalaires comme les GPU de NVIDIA, le temps de déplacement d’un espace mémoire vers un autre ainsi que le temps qui doit être utilisé pour la cohérence de l’espace mémoire n’est pas inclut dans les résultats des auteurs. Aussi, l’article ne fait pas nécessairement mention de tous les désavantages de la méthodologie. Par exemple, lors des transformations de données d’entrées, il peut être nécessaire de faire plusieurs duplications de matrice ou, du moins, y avoir plusieurs matrices qui contiennent les mêmes données en mémoire. La taille de la mémoire nécessaire pour contenir toutes ces matrices pourrait dépasser la taille disponible. Donc, plus de recherches et de tests seraient nécessaires afin d’obtenir de meilleurs résultats qui expliciteraient bien les différents cas, ou plutôt les points limites où l’optimisation faite en appliquant une des deux techniques de la méthodologie ne serait plus utile, mais plutôt nuisible. Finalement, bien que l’article ait été publié en 2011, les auteurs ne tiennent pas compte d’un changement assez important chez AMD. En effet, AMD supporte la spécification OpenCL depuis 2009 [3]. Or, la spécification OpenCL oblige de permettre la gestion des espaces mémoire, tout comme NVIDIA le faisait déjà avec CUDA [9], [10]. Ainsi, il serait fort possible de combiner les deux techniques avancées par les auteurs afin d’obtenir de meilleures performances.

Conclusion Après tout ce qui a été dit, les résultats de l’exploitation de la méthodologie sont probants, il est possible de mieux exploiter l’architecture sous-jacente d’un programme parallèle en étudiant les patrons d’accès de la mémoire. Ainsi, dans plusieurs cas, un niveau significativement plus élevé de la performance de la mémoire peut être atteint qu’en laissant simplement toutes les décisions aux compilateurs. Néanmoins, l’article démontre d’une façon éloquente de la plus grande complexité que présente le développement de programmes parallèles comparativement aux programmes séquentiels. Il est donc essentiel de bien réfléchir au problème que veut régler le programme et d’analyser minutieusement les données d’entrées et les différents accès mémoires requis. Or, tout comme les auteurs en font mention, la méthodologie présentée pourrait aisément faire partie d’outils de décisions utilisés lors de la conception et du développement du programme. D’ailleurs, l’intégration de ces techniques dans un compilateur simplifierait encore plus la tâche des développeurs et permettrait de présenter de meilleures performances dans plusieurs cas, sans même avoir à retoucher le code source.

Bibliographie

1] Harris, Mark, Greg Coombe, Thorsten Scheuermann et Anselmo Lastra. 2002. « Physically-Based Visual Simulation on Graphics Hardware ». En ligne. 11 p. <http://www.markmark.net/cml/dl/HWW02_Harris_electronic.pdf>. Consulté le 22 janvier 2011.
2] NVIDIA. s. d. «What is GPU Computing?». En ligne. <http://www.nvidia.com/object/GPU_Computing.html>. Consulté le 28 février 2011.
3] AMD. 2009. «A Brief History of General Purpose (GPGPU) Computing». En ligne. <http://www.amd.com/us/products/technologies/stream-technology/opencl/pages/gpgpu-history.aspx>. Consulté le 28 février 2011.
4] Byunghyun Jang, Dana Schaa, Perhaad Mistry et David Kaeli. “Exploiting Memory Access Patterns to Improve Memory Performance in Data-Parallel Architectures” IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS, Vol. 22, No. 1. 14 p.
5] S.T. Leung and J. Zahorjan. «Optimizing Data Locality by Array Restructuring». Technical Report TR 95-09-01, Univ. of Washington, 1995.
6] ANONYME. s.d. «BLAS (Basic Linear Algebra Subprograms)». En Ligne. <http://www.netlib.org/blas/>. Consulté le 2 mars 2010.
7] AMD. “ATI Stream Computing User Guide, V 1.4 Beta, Brook+ SDK,” http://developer.amd.com/gpu/ATIStreamSDK/, 2010.
8] NVIDIA, “CUDA Programming Guide 2.3,” http://www.nvidia.com/cuda/, July 2009.
9] Khronos Group. 2009. «The OpenCL Specification Version: 1.1». En Ligne. 379 p. <http://www.khronos.org/registry/cl/specs/opencl-1.1.pdf>. Consulté le 2 mars 2010.
10] AMD. 2011. «AMD Accelerated Parallel Processing OpenCL». En ligne. 180p. <http://developer.amd.com/gpu/amdappsdk/assets/AMD_Accelerated_Parallel_Processing_OpenCL_Programming_Guide.pdf>. Consulté le 2 mars 2010.