Méthodologie de placement sur processeur graphique

 Analyses de code statique

La première étape consiste à effectuer un ensemble d’analyses sur le code source choisi, afin de recueillir les informations permettant d’orienter la stratégie de placement. Ces analyses sont regroupées en deux catégories : les analyses statiques et dynamiques. Dans le premier cas, l’analyse porte uniquement sur le code source de l’application et permet d’extraire des informations qui sont toujours vraies quelque soit les données en entrée du programme. Dans le second cas, détaillé dans la section 3.2, l’analyse porte sur une, voire plusieurs, instances d’exécution du programme. Cette dernière complète les informations collectées par l’analyse statique avec des informations connues uniquement lors de l’exécution du programme. L’analyse de code statique prend place après les phases d’analyse lexicale puis syntaxique. De ce fait, nous n’avons pas de présupposé quant au langage de programmation utilisé, du moment que celui-ci reste compatible avec les API de mise en œuvre pour GPU énumérées au chapitre 1. Ces deux phases pourront être réalisées automatiquement par l’utilisation d’un parser de code tel que ceux de PIPS ou de LLVM [86, 85] par exemple. Nous utiliserons cependant, dans la suite du manuscrit, les langages C ou C++ à des fins d’illustration. La structure du code étant supposée connue, nous pouvons alors procéder aux diverses analyses statiques. La figure 3.2 donne un aperçu de l’ensemble des analyses statiques appliquées sur le code source de l’application. Dans un premier temps sont réalisées les analyses portant sur l’identification des boucles, des appels de fonction, des branchements ou encore des accès mémoire. Ensuite vient l’identification des blocs de base correspondant aux portions de code restantes. Enfin, les analyses des itérations de boucles et des accès aux espaces mémoire permettent de calculer les dépendances de données. Celles-ci donnent lieu à une classification des boucles de l’application. Nous utilisons comme illustration le listing 3.1, qui est un extrait original de code provenant de l’algorithme simpleflow 1 . Ce dernier est issu du dépôt des contributions [2] à la librairie OpenCV et a servi de base d’étude pour l’élaboration de cette méthodologie car il présente de nombreuses caractéristiques intéressantes détaillées en section 4.2. Les résultats de l’étude complète du portage de cet algorithme sont disponibles dans le chapitre 4.

Identification des appels de fonction

Un programme se limite rarement à une seule et unique fonction. Il est souvent composé de fonctions multiples dès que sa taille devient conséquente. Ce découpage permet d’améliorer d’une part la compréhension du programme, mais aussi de réduire la complexité spatiale du code en factorisant au sein de fonctions certains patterns redondants. Du fait que notre méthodologie considère des programmes dans leur globalité et de manière interprocédurale, nous nous intéressons aux fonctions et à leurs appels qui doivent être identifiés. Notre objectif est de prendre en compte les aspects interprocéduraux au sein de nos analyses, notamment pour le calcul des dépendances ou encore pour une identification en profondeur des nids de boucles du programme. Bien que le principe de l’inlining eut été une solution envisageable, elle n’a pas été retenue. Cette opération étant la contraposée du découpage par fonction, le choix de ne pas l’employer se justifie à plusieurs titres. D’une part, la taille du code source aurait dans certains cas tendance à augmenter de façon exponentielle 2 . D’autre part, la compréhension globale du programme s’en retrouverait réduite et pourrait aller à l’encontre d’un placement sur GPU par fonction choisi par le programmeur. Enfin, à partir de cette analyse des appels de fonctions, il est possible d’obtenir le graphe des appels, ou Call Graph, de notre programme avec le nombre d’appels effectués pour chaque fonction. L’analyse dynamique de la section 3.2 permet entre autres de traiter les cas de contrôle dynamique. Dans le cadre du listing 3.1, nous observons à la ligne 79 l’appel à la fonction dist faisant référence à la fonction de même nom et de même signature détaillée en lignes 61 à 63. Les appels répétés à la fonction at aux lignes 79, 81 et 83 en revanche font référence à une méthode d’objet provenant de la librairie OpenCV. Enfin, la fonction zeros à la ligne 75 présente des caractéristiques similaires à celles que nous venons de décrire pour la fonction at. Nous reviendrons sur ces cas particuliers dans la section 3.1.3. 

Identification des boucles

L’identification des boucles revêt une forte importance dans cette méthodologie car l’architecture des GPUs est particulièrement adaptée au parallélisme de données. Ce type de parallélisme est très courant dans les applications de traitement d’images. En fonction du langage de programmation utilisé, mais aussi au sein d’un même langage, les paradigmes de boucles peuvent avoir des structures syntaxiques variées telles que for, while ou encore do/while. Cependant un état d’amorce, une condition de fin et un paramètre d’incrément sont les trois éléments caractéristiques de toute boucle, déterminant l’ensemble d’itérations. Ce sujet sera traité plus en détails dans la section 3.1.7. Les fonctions récursives peuvent être considérées comme des boucles potentielles à condition que les trois éléments caractéristiques précédents puissent être déterminés. Le choix d’écarter l’inlining évoqué dans la section 3.1.1 prend ici tout son sens. En effet, dans le cas où ces paramètres ne pourraient être définis, la profondeur d’inlining serait aussi indéterminée. Dans le cadre de notre méthodologie, chaque entête de boucle est affectée d’un identifiant unique de la forme ln. Ici l signifie qu’il s’agit d’une boucle 3 et n en est son numéro unique incrémenté selon l’ordre lexicographique et l’analyse interprocédurale du code source analysé. Dans le listing 3.1, l’exemple est composé de deux boucles for parfaitement imbriquées (lignes 77 et 78) et recevant respectivement les identifiants l0 et l1. Si la fonction dist intégrait une boucle, celle-ci recevrait l’identifiant l3. Du fait qu’une fonction puisse être appelée en plusieurs endroits du code, une boucle peut ainsi recevoir plusieurs identifiants. En revanche un identifiant ne peut être affecté qu’à une unique boucle. Ce processus d’attribution des identifiants à un ensemble de boucles est donc surjectif.