Parallélisation automatique - Automatic parallelization

Parallélisation automatique , également parallélisation automatique , ou autoparallelization se réfère à la conversion séquentielle de code en multi-thread et / ou vectorisé code afin d'utiliser plusieurs processeurs simultanément dans une mémoire partagée multiprocesseur ( SMP machine). La parallélisation entièrement automatique de programmes séquentiels est un défi car elle nécessite une analyse de programme complexe et la meilleure approche peut dépendre de valeurs de paramètres qui ne sont pas connues au moment de la compilation.

Les structures de contrôle de programmation sur lesquelles l'autoparallélisation met le plus l'accent sont les boucles , car, en général, la plupart du temps d'exécution d'un programme se déroule à l'intérieur d'une forme de boucle. Il existe deux approches principales pour la parallélisation des boucles : le multi-threading en pipeline et le multi-threading cyclique. Par exemple, considérons une boucle qui, à chaque itération, applique une centaine d'opérations et s'exécute sur mille itérations. Cela peut être considéré comme une grille de 100 colonnes par 1000 lignes, un total de 100 000 opérations. Le multi-threading cyclique affecte chaque ligne à un thread différent. Le multi-threading en pipeline affecte chaque colonne à un thread différent.

Technique de parallélisation automatique

Analyser

C'est la première étape où le scanner lira les fichiers source d'entrée pour identifier toutes les utilisations statiques et externes. Chaque ligne du fichier sera vérifiée par rapport à des modèles prédéfinis pour être séparée en jetons . Ces jetons seront stockés dans un fichier qui sera utilisé ultérieurement par le moteur de grammaire. Le moteur de grammaire vérifiera les modèles de jetons qui correspondent aux règles prédéfinies pour identifier les variables, les boucles, les instructions de contrôle, les fonctions, etc. dans le code.

Analyser

L' analyseur est utilisé pour identifier les sections de code qui peuvent être exécutées simultanément. L'analyseur utilise les informations de données statiques fournies par le scanner-parser. L'analyseur trouvera d'abord toutes les fonctions totalement indépendantes et les marquera comme des tâches individuelles. L'analyseur trouve ensuite quelles tâches ont des dépendances.

Calendrier

Le planificateur listera toutes les tâches et leurs dépendances les unes par rapport aux autres en termes d'heures d'exécution et de début. L'ordonnanceur produira le calendrier optimal en termes de nombre de processeurs à utiliser ou de temps d'exécution total pour l'application.

Génération de code

Le planificateur générera une liste de toutes les tâches et les détails des cœurs sur lesquels elles s'exécuteront ainsi que le temps pendant lequel elles s'exécuteront. Le générateur de code insère dans le code des constructions spéciales qui seront lues lors de l'exécution par le planificateur. Ces constructions indiqueront au planificateur sur quel cœur une tâche particulière s'exécutera, ainsi que les heures de début et de fin.

Multi-threading cyclique

Un compilateur de parallélisation multithread cyclique essaie de diviser une boucle afin que chaque itération puisse être exécutée simultanément sur un processeur distinct .

Analyse de parallélisation du compilateur

Le compilateur effectue généralement deux passes d'analyse avant la parallélisation réelle afin de déterminer les éléments suivants :

  • Est-il sûr de paralléliser la boucle ? Répondre à cette question nécessite une analyse de dépendance et d' alias précise
  • Cela vaut-il la peine de le paralléliser ? Cette réponse nécessite une estimation fiable (modélisation) de la charge de travail du programme et de la capacité du système parallèle.

La première passe du compilateur effectue une analyse de dépendance des données de la boucle pour déterminer si chaque itération de la boucle peut être exécutée indépendamment des autres. La dépendance des données peut parfois être traitée, mais elle peut entraîner une surcharge supplémentaire sous la forme de transmission de messages , de synchronisation de la mémoire partagée ou d'une autre méthode de communication du processeur.

La seconde passe tente de justifier l'effort de parallélisation en comparant le temps d'exécution théorique du code après parallélisation au temps d'exécution séquentiel du code. De manière quelque peu contre-intuitive, le code ne bénéficie pas toujours d'une exécution parallèle. La surcharge supplémentaire qui peut être associée à l'utilisation de plusieurs processeurs peut réduire l'accélération potentielle du code parallélisé.

Exemple

Une boucle est appelée DOALL si toutes ses itérations, dans une invocation donnée, peuvent être exécutées simultanément. Le code Fortran ci-dessous est DOALL et peut être auto-parallélisé par un compilateur car chaque itération est indépendante des autres et le résultat final du tableau zsera correct quel que soit l'ordre d'exécution des autres itérations. 

   do i = 1, n
     z(i) = x(i) + y(i)
   enddo

Il existe de nombreux problèmes agréablement parallèles qui ont de telles boucles DOALL. Par exemple, lors du rendu d' un film avec lancer de rayons, chaque image du film peut être rendue indépendamment et chaque pixel d'une seule image peut être rendu indépendamment.

En revanche, le code suivant ne peut pas être auto-parallélisé, car la valeur de z(i)dépend du résultat de l'itération précédente, z(i - 1). 

   do i = 2, n
     z(i) = z(i - 1)*2
   enddo

Cela ne signifie pas que le code ne peut pas être parallélisé. En effet, cela équivaut à 

   do i = 2, n
     z(i) = z(1)*2**(i - 1)
   enddo

Cependant, les compilateurs de parallélisation actuels ne sont généralement pas capables de faire apparaître ces parallélismes automatiquement, et on peut se demander si ce code bénéficierait en premier lieu de la parallélisation.

Multi-threading en pipeline

Article principal: pipeline de logiciels

Un compilateur de parallélisation multithread en pipeline essaie de diviser la séquence d'opérations à l'intérieur d'une boucle en une série de blocs de code, de sorte que chaque bloc de code puisse être exécuté simultanément sur des processeurs distincts .

Il existe de nombreux problèmes agréablement parallèles qui ont de tels blocs de code relativement indépendants, en particulier des systèmes utilisant des tuyaux et des filtres . Par exemple, lors de la production d'émissions télévisées en direct, les tâches suivantes doivent être effectuées plusieurs fois par seconde :

  1. Lire une trame de données de pixels brutes à partir du capteur d'image,
  2. Faire une compensation de mouvement MPEG sur les données brutes,
  3. L'entropie compresse les vecteurs de mouvement et d'autres données,
  4. Divisez les données compressées en paquets,
  5. Ajoutez la correction d'erreur appropriée et effectuez une FFT pour convertir les paquets de données en signaux COFDM , et
  6. Envoyez les signaux COFDM par l'antenne TV.

Un compilateur de parallélisation multithread en pipeline pourrait affecter chacune de ces 6 opérations à un processeur différent, peut-être disposé dans un tableau systolique , en insérant le code approprié pour transmettre la sortie d'un processeur au processeur suivant.

Des recherches récentes se concentrent sur l'utilisation de la puissance des GPU et des systèmes multicœurs pour calculer de tels blocs de code indépendants (ou simplement des itérations indépendantes d'une boucle) au moment de l'exécution. La mémoire accédée (qu'elle soit directe ou indirecte) peut être simplement marquée pour différentes itérations d'une boucle et peut être comparée pour la détection de dépendances. A partir de ces informations, les itérations sont regroupées en niveaux de telle sorte que les itérations appartenant au même niveau soient indépendantes les unes des autres, et puissent être exécutées en parallèle.

Des difficultés

La parallélisation automatique par des compilateurs ou des outils est très difficile pour les raisons suivantes :

  • l'analyse de dépendance est difficile pour le code qui utilise l'adressage indirect, les pointeurs, la récursivité ou les appels de fonction indirects car il est difficile de détecter de telles dépendances au moment de la compilation ;
  • les boucles ont un nombre d'itérations inconnu ;
  • les accès aux ressources globales sont difficiles à coordonner en termes d'allocation mémoire, d'E/S et de variables partagées ;
  • les algorithmes irréguliers qui utilisent l'indirection dépendante de l'entrée interfèrent avec l'analyse et l'optimisation au moment de la compilation.

solution de contournement

En raison des difficultés inhérentes à la parallélisation entièrement automatique, plusieurs approches plus simples existent pour obtenir un programme parallèle de meilleure qualité. L'un d'eux est de permettre aux programmeurs d'ajouter des "indices" à leurs programmes pour guider la parallélisation du compilateur, tels que HPF pour les systèmes à mémoire distribuée et OpenMP ou OpenHMPP pour les systèmes à mémoire partagée . Une autre approche consiste à construire un système interactif entre les programmeurs et les outils/compilateurs de parallélisation. Des exemples notables sont Vector Fabrics ' Pareon, SUIF Explorer (le compilateur de format intermédiaire de l'Université de Stanford), le compilateur Polaris et ParaWise (anciennement CAPTools). Enfin, une autre approche est le multithreading spéculatif pris en charge par le matériel .

Paralléliser les compilateurs et les outils

Voir aussi : Outil de parallélisation automatique

La plupart des compilateurs de recherche pour la parallélisation automatique considèrent les programmes Fortran , car Fortran offre des garanties plus solides sur l' aliasing que les langages tels que C . Des exemples typiques sont :

  • Compilateur de paradigme
  • Compilateur Polaris
  • Compilateur Rice Fortran D
  • compilateur SUIF
  • Compilateur Fortran de Vienne

Voir également

Les références