|
TriDenT CoLUMBO
Les Arbres en HPF2
L’équipe de recherche était située à l’Université de Bordeaux I au laboratoire LABRI (LABoratoire de Recherche en Informatique). Nos travaux ont débuté avec l’étude d’une nouvelle façon de décrire les structures de données irrégulières en HPF. Cette méthode s’appuie sur une écriture arborescente des structures de données via les types dérivés de Fortran 90/95 et les extensions approuvées de HPF 2.0. Ces notations permettent de supprimer les accès indirects nécessaires présents dans l’écriture des structures de données irrégulières classiques comme le format CCS (Compressed Column Storage). Les accès indirects empêchent le compilateur de générer des codes efficaces parallèles en raison de la non connaissance des valeurs de ces indices indirects.
L’exemple suivant montre une matrice creuse avec des accès orientés par colonne, sa représentation sous forme d’un arbre et son écriture en HPF 2.0 ainsi que sa distribution.
Nous proposons également d’étendre les possibilités de distribution des arbres ainsi que l’ajout d’une nouvelle directive TREE au langage HPF : cette directive spécifie l’usage restreint qui est fait des notations pointeurs et des types dérivés, restrictions produisant effectivement une structure de données arborescente et à profondeur connue lors de la compilation.
Ces restrictions ainsi que les ajouts pour la distribution permettent une implémentation efficace des types dérivés par le compilateur ainsi que des optimisations à la compilation issues du cadre régulier basées sur les analyses de dépendances et de localité. Ces analyses ne sont pas réalisables avec les formats standards irréguliers.
Inspection-Exécution
Malgré cette amélioration des analyses à la compilation, il demeure des informations inconnues lors de celle-ci. Les propriétés parallèles de ces applications ne sont pas en conséquences exploitables lors de la compilation. Il est nécessaire d’utiliser le paradigme d’inspection-exécution.
Le compilateur génère un code comportant deux phases : la première phase, l’inspection, scanne ces informations connues uniquement à l’exécution afin de produire lors de la deuxième phase, l’exécution, la réalisation des calculs avec des schémas optimisés tant au niveau des communications que de la répartition des calculs. Nous avons utilisé ce paradigme pour différentes propriétés qui n’ont pas été étudiées jusqu’à ce jour dans les précédents travaux. Nous nous sommes notamment intéressés aux cas des boucles avec dépendances inter-itérations partielles (BDIIP).
Il est à noter que nos inspecteurs-exécuteurs sont très différents des approches classiques au sens où, dans notre étude, l’inspection doit être rentabilisée avec un seule phase d’exécution, contrairement aux autres approches qui sont utilisées dans un contexte itératif, c’est à dire avec plusieurs phases d’exécution identiques en termes d’accès et de communications.
Les ensembles irréguliers de processeurs
Les indices irréguliers de boucles
Les communications inter- et extra-itérations (BDDIP)
L’ordonnancement du DAG associé à une BDIIP
-
L’opération préfixe irrégulière progressive
Nous présentons maintenant succinctement chacune de ces inspections-exécutions :
Nature |
HPF 2.0 |
Exemple |
Ensemble Irréguliers de Processeurs |
Non supportés |
DO I= 1, N
!HPF$ ON HOME (A(J), ANY (INDEX(I,1:NB(I)))=J .or. J=I), BEGIN
!HPF$ INDEPENDENT, REDUCTION(A(I))
DO J1= 1, NB(I)
J=INDEX(I,J1)
A(I) = A(I) + B(J)
END DO
A(I)= f(A(I))
!HPF$ END ON
END DO
La directive ON HOME étendue (comportant une expression algorithmique du type FORALL) permet de déclarer un ensemble irrégulier de processeurs :
|
Indices Irréguliers de Boucles |
Non spécifiés |
DO I= 1, N
!HPF$ INDEPENDENT, REDUCTION(A(I))
FORALL(J=1:I, ANY(INDEX(I,1:NB(I)) = J)
A(I) = A(I) + B(J)
END FORALL
A(I) = f(A(I))
END DO
L’inspecteur des indices de boucles précalcule les indices valides pour chaque processeur (ici, basés sur l’expression FORALL). Cela permet dans certains cas de réduire le coût algorithmique induit par les gardes évaluées à chaque itération. |
Communications Inter- et Extra-Itérations (BDIIP) |
Non supportées |
Cet inspecteur permet d’optimiser les communications extractibles de la boucle globale, ou d’émettre au plus tôt les communications inter-itérations. Les communications sont scindées en deux : émission et réception (contrairement à la génération de code standard en HPF). |
Ordonnancement de DAG (BDIIP) |
Non supportés |
!HPF$ SCHEDULE (J = 1:I-1, ANY(INDEX(I,1:NB(I)) = J)
DO I = 1, N
...
END DO
Donne :
Call Schedule(task, 1, N)
Subroutine task(I)
!HPF$ ON HOME (A(J), ANY (INDEX(I,NB(I)))= J .or. J= I), BEGIN
!HPF$ INDEPENDENT, REDUCTION(A(I))
FORALL(J = 1:I, ANY(INDEX(I,1:NB(I)) = J)
A(I) = A(I) + B(J)
END FORALL
A(I) = f(A(I))
!HPF$ END ON
END Subroutine
Cette nouvelle directive SCHEDULE permet la prise en compte de BDIIP et du graphe de tâches associé (chaque itération est assimilée à une tâche, le DAG associé est extrait de l’expression algorithmique de la directive précisant les précédences de l’itération I courante). Le code de la boucle est alors réécrit en une sous-routine qui sera exécutée en fonction du résultat de l’ordonnanceur. |
Opération Préfixe Irrégulière Progressive (BDIIP) |
Non supportés |
!HPF$ PREFIX(A)
DO I= 1, N
!HPF$ ON HOME (A(J), ANY (INDEX(I,NB(I)))= J .or. J= I), BEGIN
!HPF$ INDEPENDENT, PREFIX(A)
FORALL(J = 1:I, ANY(INDEX(I,1:NB(I)) = J)
A(I) = A(I) + A(J)
END FORALL
A(I)= f(A(I))
!HPF$ END ON
END DO
La directive PREFIX définie l’opération data-parallèle présente dans la boucle comme étant une opération préfixe irrégulière progressive. Cette opération est progressive car chaque indice est calculé à partir des valeurs finales du tableau. Il ne s’agit pas d’une simple réduction, car le tableau en entrée est également le tableau en sortie. La gestion de cette opération utilise des opérations de communications asynchrones. |
Résultats Expérimentaux
Il s’agit de résultats d’une factorisation de Cholesky de matrices creuses en version bloc-colonnes 1D (distribution des blocs-colonnes). Chaques versions incluent de plus en plus d’optimisations.
La dernière version correspond à une factorisation de Cholesky de l’équipe aux performances importantes [A Mapping and Scheduling Algorithm for Parallel Sparse Fan-In Numerical Factorization, EuroPar'99, 1999, P. Henon, P. Ramet and J. Roman].
La factorisation est elle même placée dans un cadre itératif avec la structure creuse de la matrice constante (seules les valeurs évoluent), comme dans l’algorithme de Karmarkar qui résoud le système AX = B et qui minimise une fonction objective CTX.
La première itération est obtenue après l’ordonnancement statique (s’il y a lieu) avec le temps de l’inspection inclus, la seconde avec l’ordonnancement dynamique (ou le temps de l’itération en l’absence de la directive PREFIX sans le temps de l’inspection) sans le temps de l’inspection.
Version |
Temps Première itération |
Temps ré-itération |
Version 0 : notation TREE uniquement (TriDenT) |
190s |
190s |
Ensembles irréguliers de processeurs (TriDenT + CoLUMBO) |
- |
- |
+ Indices de boucles et Communications |
8.56s |
6.83s |
+ DAG (SCHEDULE) |
6.42s |
3.36s |
+ DAG et système d’exécution threadé (SCHEDULE) |
6.18s |
3.31s |
+ opération PREFIX |
4.65s |
2.04s |
PasTiX : version très optimisée MPI (en C, source LABRI) |
1.80s |
1.80s |
Articles
Propositions de Gestion de l’Irregularité avec HPF2, Frédéric Brégier, Conférence RenPar’10, Prix IEEE Jeune Chercheur (meilleure présentation en parallélisme) , Strasbourg, 9-12 Juin 1998.
Contribution to Better Handling of Irregular Problems in HPF2 , Thomas Brandes (1), Frederic Bregier (2), Marie Christine Counilh (2), Jean Roman (2) , (1) GMD/SCAI, (2) LaBRI, ENSERB, Euro-Par’98, Southampton, LNCS Vol. 1470, pp 639-649, Springer-Verlag Ed., 1-4 September 1998.
Asynchronous Progressive Irregular Prefix Operation in HPF2 , Frederic Bregier, Marie Christine Counilh, Jean Roman, PDP’2000 (IEEE), pp 275-282, 2000.
Scheduling Loops with Partial Loop-Carried Dependencies in HPF2 , Frederic Bregier, Marie Christine Counilh, Jean Roman, Parallel Computing for Irregular Applications, 2000.
Extensions d’OpenMP pour les Architectures a Hierarchies Memoire Multiple , Frederic Bregier, Barbara Chapman, A. Patil et A. Prabhakar RenPar’2001
-
Achieving Performance under OpenMP on ccNUMA and Software Distributed Shared Memory Systems , Frederic Bregier, Barbara Chapman, A. Patil et A. Prabhakar accepté à Concurrency: Practice and Experiment 2001
Interventions
RenPar’10, Strasbourg, 9-12 Juin 1998 (Rencontres Francophones du Parallélisme des Architectures et des Systèmes) .
HUG’98, Porto, 25-26 June 1998 (HPF User Group meeting).
Euro-Par’98, Southampton, 1-4 September 1998.
COCA’98, Baie de Somme, 15-17 Septembre 1998 (Journées sur le Calcul Out of core & Compilation Adaptative).
Séminaire du PRiSM, Versailles Saint Quentin, Novembre 1998.
Séminaire du LaMI , Evry, Juin 1999.
-
PDP’2000 conference, Rhodos, Greese, January 2000
Thèse
|