Parallélisation interprocédurale de programmes scientifiques

Le projet PIPS a été initié au Centre de Recherche en Informatique de l'École des mines de Paris en 1988. Il a bénéficié depuis de nombreux projets financés par le CNRS, par la DRET (Direction des recherches et Études techniques), ou encore l'Union Européenne (ESPRIT). La conception initiale a été réalisée par Remi Triolet, François Irigoin, et Pierre Jouvelot. Les choix techniques se sont révélés suffisamment pertinents pour ne pas demander de mise à jour majeure jusqu'à ce jour et assurer une bonne évolution pendant deux décennies. L'article présenté à l'International Conference on Supercomputing(ICS) en 1991[1] est toujours d'actualité, bien que des fonctionnalités majeures aient été ajoutées depuis.

PIPS a été utilisé pour développer des nouvelles analyses ou des transformations de programmes par plusieurs équipes de recherche du CEA-DAM, de l'Université de Southampton, de Télécom Bretagne, Télécom et management SudParis, de SRU ('Slippery Rock University - Université de Pennsylvanie), du RPI (Rensselaer Polytechnic Institute) et de l'ENS Cachan. Ces nouveaux développement ont bénéficié de l'infrastructure générale et des nombreuses analyses et transformations disponibles. PIPS a également été utilisé pour développer un prototype de compilateur et pour étudier les optimisations pour HPF.

Structure générale de pips

PIPS est construit sur deux autres outils. Le premier est Newgen, qui fournit une description abstraite des structures de données. Il fournit les fonctions de manipulations basiques décrites dans un fichier de déclaration. Il supporte les données persistantes et les hiérarchies de types. Tous les types de données de PIPS sont basés sur NewGen.

Le second outil est la bibliothèque d'algèbre linéaire Linear C3 qui gère les vecteurs, les matrices, les contraintes linéaires et les structures qui se basent sur ces contraintes comme les polyèdres. Les algorithmes utilisés sont conçus pour des coefficients entiers et/ou rationnel. Cette bibliothèque est intensivement utilisée pour des analyses comme les tests de dépendances, les préconditions et les calculs de région, ainsi que pour les transformations comme le pavage, et enfin pour la génération de code, comme le code d'envoi et de réception dans la compilation HPF. La bibliothèque Linear C3 est un projet conjoint avec l'IRISA et le (fr) PRISM, partiellement financé par le CNRS. L'IRISA a contribué à une implémentation de l'algorithme de Chernikova et le PRISM à une implémentation de PIP (Parametric Integer Programming).

Toutes les structures de données de PIPS sont basées sur NewGen.

PIPS inclut un grand nombre d'analyses (notamment des analyses d'accès aux tableaux (en)) parmi lesquelles :

• Conditions de continuation
• Dépendances de données (en)
• Effets mémoire
• Graphe d'appel de fonction (en)
• Graphe de flot de contrôle
• Complexité de programme
• Détection de réduction
• Préconditions
• Privatisation de tableaux
• Privatisation de section de tableaux
• Privatisation de variable scalaire
• Région d'éléments de tableaux
• Transformers
• Use-define chain (en)

• Atomisation
• Clonage
• Suppression du code mort
• Élimination de définition inutile
• Nettoyage de déclaration
• Restructuration de contrôle

• Déroulage de boucle
• Distribution de boucles
• Échange de boucle (en)
• Évaluation partielle
• Normalisation de boucle (en)
• Optimisations d'expression
• Parallélisation
• Parallélisation à gros grain
• Reductions de boucle (en)
• Strip Mining
• Substitution avant

Capture d'écran de l'interface Wpips

PIPS offre historiquement cinq interfaces utilisateurs :

• une interface par le shell (Pips)
• une interface en ligne de commande (Tpips)
• et trois interfaces X-window : Wpips, Epips and Jpips.

Une nouvelle interface en Python (Pyps) est en cours de développement. Les interfaces classiques interagissent avec l'utilisateur, qui guide les choix des optimisations. Cette nouvelle interface est destinée à permettre plus facilement le traitement de programme sans intervention d'utilisateur, et permettra de s'interfacer avec des programmes externes.

Actuellement PIPS est utilisé principalement sous Linux, mais peut également être utilisé sous Solaris, AIX et Digital UNIX. Le système d'exploitation utilisé pour exploiter PIPS ne limite pas le champ des programmes qu'il peut traiter. Depuis peu des paquets debian[2] sont disponibles, ce qui facilite la gestion des dépendances pour l'installation.