openlsd250-smallOpenLSD
 
Accueil OpenLSD and Co Outils BBMAP TriDenT CoLUMBO Divers CV

TriDenT CoLUMBO

Les Arbres en HPF2

trident

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.

tree

 

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

columbo

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 :

  • la réduction ne met alors en jeu que ce sous-ensemble, réduisant les synchronisations induites.

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

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