Travaux existant sur la prédictions de performances

Simulation

Un simulateur est capable de reproduire le comportement détaillé, pas à pas, d’une architecture de calcul. La précision d’un simulateur dépend de nombreux facteurs, notamment la qualité de la modélisation de l’architecture et de l’application. Certains simulateurs sont conçus pour cibler des GPUs, c’est le cas notamment de GPGPU-sim [BAKHODA et collab., 2009] et de Barra [COLLANGE et collab., 2010]. Ces deux simulateurs sont capables de simuler l’exécution de code CUDA et génèrent des informations détaillées à propos des compteurs de performances, le nombres d’accès mémoire, l’utilisation des différentes ressources. GPGPU-sim affiche une précision de 97,3% sur le nombre d’instructions par cycle prédit sur un GPU Fermi. Quant à Barra, les auteurs rapportent une erreur allant de 0 à 23 pourcents entre les prédictions et les mesures, suivant les workloads utilisés. D’autres simulateurs ciblent des architectures hétérogènes, le plus souvent composées d’un CPU et d’un GPU avec une mémoire propre à chaque processeur ou avec une mémoire partagée. On peut citer par exemple le très célèbre Multi2Sim, de UBAL et collab. [2012], mais également MacSim [KIM et collab., 2012] ou encore FusionSim [ZAKHARENKO et collab., 2013]. La dernière version de Multi2Sim permet de cibler des CPUs x86, MIPS, ARM, et des GPUs ARM et Nvidia à partir de code OpenCL ou CUDA. Les auteurs rapportent une erreur allant de 7 à 30 pourcents sur plusieurs kernels OpenCL.
Les différentes performances évaluées par des simulateurs sont en général proches de la réalité. Cependant cette approche a plusieurs défauts majeurs. Tout d’abord, les temps de simulation sont plus importants que les temps d’exécution réels sur l’architecture cible, ce qui limite donc assez fortement le nombre de simulations que l’on peut faire en un temps limité. De plus, chacun de ces simulateurs nécessite un code source complet et déjà optimisé, on peut donc se poser la question de l’utilité d’un tel simulateur par rapport à une mesure directe sur l’architecture cible si celle-ci est disponible. Enfin, le nombre et les types d’architectures cibles restent limités, par exemple Multi2Sim ne peut cibler que les GPUs Fermi pour Nvidia, et ne supportent pas le 64 bits.

Temps d’exécution

Pour prédire un temps d’exécution, plusieurs approches peuvent être étudiées : la prédiction basée sur des techniques d’apprentissage ou la prédiction basée sur un modèle analytique de l’architecture et de l’algorithme.
BenchFriend, de CHE et SKADRON [2014], propose de prédire les temps d’exécution d’applications sur GPU en se basant sur une corrélation avec des workloads d’apprentissage. Cependant, le modèle ne se montre pas si précis que le précédent, les auteurs donnent une erreur de prédiction comprises entre 15,8% et 27,3%.
L’approche discutée par SATO et collab. [2011] propose une prédiction du temps de calcul au moment de l’exécution pour une répartition automatique de kernels OpenCL sur les différents processeurs d’une même architecture hétérogène. La méthode se base sur l’analyse des historiques des temps d’exécution d’un kernel sur différents processeurs pour prédire son temps d’exécution. Elle permet également d’identifier l’impact des paramètres d’entrée sur le temps d’exécution. Les auteurs rapportent une très bonne précision des prédictions comparée aux autres approches de l’état de l’art. Ces différentes approches proposent des résultats intéressants, mais elles ont cependant plusieurs défauts qui nous ont poussés à ne pas les utiliser. Tout d’abord, chacune propose d’utiliser un framework en particulier, ce qui implique un travail supplémentaire pour traduire un kernel décrit en pseudo code dans le langage du framework en question. De plus les résultats de ces approches sont très fortement dépendants de la base d’apprentissage. Ainsi, la prédiction du temps d’exécution d’un kernel pour lequel il n’existe pas de workload similaire dans la base d’apprentissage risquera d’être plutôt mauvaise.
L’approche par analyse de l’historique permet une prédiction très précise, mais elle est beaucoup trop contraignante. En effet, elle nécessite d’exécuter le kernel sur les différentes unités d’exécution pour modéliser son temps d’exécution. Pour ces différentes raisons, nous avons choisi de nous focaliser sur un modèle analytique pour la prédiction de performances.

Modèle analytique pour GPU

Un modèle analytique consiste à un ensemble d’équations représentant les caractéristiques de l’application et de l’architecture de calcul et permet de cette manière de prédire le temps d’exécution. Remarquons que la plupart des modèles analytique n’adressent qu’un seul type d’architecture. Par exemple le très célèbre modèle de HONG et KIM [2009] cible uniquement la prédiction de performances pour GPU. Le modèle se base sur deux métriques :
— MWP pour Memory Warp Parallelism, qui mesure le nombre maximum de warps par SMX pouvant accéder à la mémoire de manière simultanée. Cette métrique caractérise le degré de parallélisme mémoire de l’architecture, elle dépend de la bande passante mémoire, du nombre de warps par SMX, etc.
— CWP pour Computation Warp Parallelism, qui mesure le nombre de warps pouvant être exécutés pendant qu’un autre warp est en attente de données depuis la mémoire, plus 1. Cette métrique est surtout liée aux caractéristiques de l’application, un peu comme l’IA mais de manière inverse : un grand CWP signifie peu de calculs par accès mémoire.
Les auteurs proposent plusieurs formules permettant d’exprimer ces deux métriques et d’en déduire un temps d’exécution. En fait l’idée générale du modèle est que lorsque MW P 6 CW P la performance est limitée par le temps d’accès à la mémoire, et lorsque MW P > CW P les délais d’accès à la mémoire sont cachés par le temps de calcul. Les auteurs rapportent une erreur moyenne de 13,3% entre les prédictions et les temps d’exécutions mesurés. Il s’agit un peu de la même approche que le modèle Roofline de WILLIAMS et collab. [2009] avec l’IA.

Prédiction pour des architectures hétérogènes

Lorsque l’on parle d’accélération utilisant du parallélisme, les connaisseurs abordent immédiatement la très célèbre loi d’AMDAHL [1967]. Cette loi propose de lier l’accélération d’une tâche en termes de temps de calcul en fonction du nombre de cœurs alloués à cette tâche. Ainsi, la loi définit la relation suivante.

Discussion

En étudiant les travaux existant dans la littérature à propos de la prédiction de performances, on s’aperçoit qu’il existe très peu d’approches pouvant répondre à notre besoin. Ainsi, la majorité des approches ne cible qu’un seul type d’architecture ou exige d’effectuer une mesure pour chaque prédiction de performances. En fait, à notre connaissance, seul le modèle Boat-Hull permet de répondre à nos besoins, mais avec la contrainte de la classification qui ne lui permet pas de gérer n’importe quel type de kernels. De plus, nous avons pu voir au cours du chapitre précédent que les performances d’un kernel dépendent fortement des types d’opérations et des types de données à traiter. Or cette dimension n’est pas du tout explorée dans les méthodes de prédiction de performances existantes dans la littérature. Nous souhaitons donc contribuer à la recherche sur la prédiction de performances en proposant un modèle prenant en compte les différents types d’opérations et de données à traiter, et qui puisse gérer du code arbitraire.

Méthodologie de prédiction de performances

Notre méthodologie de prédiction de performances doit pouvoir adresser différents types d’unités d’exécution. Comme discuté dans la section 1.3.1, une unité d’exécution de l’état de l’art est composée de plusieurs unités élémentaires, chacune étant conçue pour exécuter un certain type d’instruction. Ainsi, soient sept classes d’unités élémentaires composant une unité d’exécution :
— ALU : unité arithmétique et logique,
— BMU : unité de multiplication,
— FPU : unité de calcul à virgule flottante,
— SFU : unité de calcul spécifique,
— BU : unité de branche,
— AU : unité d’adresse,
— LSU : unité d’instruction mémoire.
Au moment de l’exécution, chaque unité élémentaire exécute les instructions pour lesquels elle a été conçue. Remarquons que le nombre d’unités élémentaires n’est pas le même pour l’ensemble des processeurs, par exemple certains processeurs ne disposent pas de FPU, certains GPUs disposent de SFU (notamment pour le calcul trigonométrique), ou encore l’ARM A15 qui dispose de deux ALUs par cœur. Comme discuté dans la section 2.4.3 et illustré par WILLIAMS et collab. [2009] et NUGTEREN et CORPORAAL [2012], le temps d’exécution d’un kernel peut être soit limité par les capacités de calcul soit par la bande passante et latence mémoire de l’architecture sur laquelle il est exécuté. Ainsi, nous choisissons donc de différencier la prédiction du temps de calcul et la prédiction des délais d’accès à la mémoire.

Prédiction du temps de calcul

Dans [SAUSSARD et collab., 2015b,c], nous présentons une méthodologie pour prédire le temps de calcul d’un kernel sur différentes unités d’exécution. Nous nous intéressons ici uniquement à l’aspect calcul, donc soit Uc l’ensemble des unités élémentaires impliquant des instructions de calcul (pas de LSU) :

Prédiction des délais d’accès à la mémoire

D’après WILLIAMS et collab. [2009] et NUGTEREN et CORPORAAL [2012] la performance d’un kernel ayant une faible IA est limitée par la bande passante et la latence mémoire de l’architecture sur laquelle il s’exécute. Le modèle de prédiction de performances doit être capable de prendre en compte ce genre de comportement. De plus, nous avons également besoin d’être capables de prédire les temps de transfert entre les différents processeurs d’un même SoC.
Comme discuté dans la section 1.3, la mémoire est organisée suivant plusieurs niveaux (registres, caches, RAM, etc.), chacun ayant des latences et bandes passantes différentes. Or lorsque l’on accède à une donnée (en lecture ou en écriture), il est très complexe de prédire depuis quel niveau de mémoire celle-ci sera chargée et encore plus complexe si l’on cherche à prédire le délai d’accès. Pour garder une approche simple et générique, nous avons choisi de baser la prédiction des délais d’accès à la mémoire directement à partir des résultats issus des vecteurs de test low-level en rapport avec la mémoire. Ainsi, à partir des données brutes issues de ces tests, nous procédons à une régression linéaire par morceaux, nous obtenons de la sorte un délai en fonction d’une taille de donnée. Un exemple de régression linéaire par morceaux est donné en figure 5.1. Remarquons que cette interpolation linéaire n’est pas toujours possible, par exemple sur les résultats des tests ReadAfterWrite. Dans ce cas, nous considérerons des interpolations par des polynômes dont le degré varie en fonction des cas.