L'étude présentée dans cette thèse n'est pas que théorique.
Plusieurs prototypes ont permis de vérifier nos concepts, en particulier
en ce qui concerne la phase de détection des scans. Un premier prototype
de détection de récurrences a été écrit en Lisp. Ce prototype
comporte 20 fichiers Lisp totalisant 7000 lignes. Le logiciel est
commenté à l'aide du système d'auto-documentation du projet PAF.
Ce système permet d'extraire automatiquement la documentation LATEX
des commentaires des fichiers sources.
Les caractéristiques de ce prototype sont décrites ci-dessous.
-
Un grand effort a été fait pour obtenir une normalisation
efficace. Si les substitutions sont effectuées au vu du graphe
des équations, l'introduction des opérateurs de récurrence
est faite au vu du graphe des clauses. La stratégie employée
est celle de la normalisation partielle, profondeur par profondeur.
De plus l'algorithme de normalisation le plus efficace est utilisé
à chaque profondeur. Il s'agit de l'algorithme présenté en
8.5.3.
- Le prototype est basé sur l'opérateur de récurrence décrit
dans [55]. Il s'agit d'un opérateur un peu plus fruste
que l'actuel opérateur Scan. Aussi seuls les scans avec des
directions colinéaires aux vecteurs canoniques sont détectés.
Par contre, les récurrences quelconques sont elles aussi
détectées et remplacées par un opérateur. Cet opérateur
est semblable à l'opérateur Scan ;
|
Recur(o, D |
,(ei) |
|
,f,
(gi) |
|
)
.
|
- Toutes les opérations sur les convexes et tous les appels
au logiciel PIP se font via une interface nommée CIPOL-Light.
Cette interface est programmée en C, elle assure une liaison
entre la structure de données du logiciel Lisp et la structure
de données des fonctions C. En effet, PIP ainsi que la
bibliothèque polyédrique de l'Irisa [64] sont
écrits en C. La liaison est réalisée par une interface
de type ASCII.
La session CIPOL-light ci-dessous permet de calculer l'intersection
de deux polyèdres définis par un ensemble de contraintes :
(print_dom
(inter
(constraints
(i j) (i >= 1) (i <= 10)
(j >= 0) (j <= i)
)
(constraints
(i j) (j >= 0) (j <= 2)
)))
Le résultat est retourné sous une forme un peu moins lisible
pour un humain mais parfaitement analysable par un interpréteur
Lisp (les commentaires ont été ajoutés à la main pour le
confort du lecteur) :
((
#[#[1 1 0 -1 ] ; i >= 1
#[1 -1 0 10 ] ; i <= 10
#[1 1 -1 0 ] ; i >= j
#[1 0 1 0 ] ; j >= 0
#[1 0 -1 2 ] ; j <= 2
] .
#[#[1 10 0 1 ] ; le point de coordonnées (10,0)
#[1 1 0 1 ] ; le point de coordonnées (1,0)
#[1 1 1 1 ] ; le point de coordonnées (1,1)
#[1 2 2 1 ] ; le point de coordonnées (2,2)
#[1 10 2 1 ] ; le point de coordonnées (10,2)
]
))
La première matrice donne les coefficients des contraintes
du polyèdre résultat et la seconde les rayons de ce polyèdre.
Les premières colonnes des matrices donnent le type des contraintes
(ici des inéquations) et des rayons (ici des points extrêmes).
Ce prototype se montre largement capable de traiter les réductions et
les scans présents dans la batterie de tests de l'Argonne (cf
[15]). Les temps d'exécution et les résultats obtenus
par le prototype sont donnés dans l'annexe A.
Ce prototype s'est avéré capable de trouver des scans dans des
situations assez difficiles comme pour le calcul d'un indice de
maximum (cf A.2.5). Le cas du test A.2.15 est encore plus
complexe puisque la recherche des indices est combinée avec
un scan bi-directionnel. Dans un premier temps le détecteur
s'est montré incapable de trouver le scan du test A.2.16
car il lui était impossible d'extraire une fonction binaire
et associative de la fonction de propagation suivante :
if (a[i'] > 0) then x + a[i'] else x
Il a suffit de rajouter la règle de simplification
(if p then x+e1 else x+e2)
º
(x + if p then e1 else e2)
,
pour que la détection aboutisse.
Seul le test A.2.14 n'a pas pu être traité car
le goto de sortie de la boucle principale, n'a
pas pu être enlevé par le restructureur du compilateur
PAF.
L'efficacité de la détection est donc satisfaisante, par
contre les temps d'exécution (en particulier pour le test
A.2.15) sont élevés. Après analyse, il apparaît
que plus de 75% du temps d'exécution est passé dans les
opérations sur les convexes. Une autre raison de la
lenteur du détecteur est le fait qu'il soit programmé
en Lisp. La lenteur n'est pas tant due au fait que ce langage
n'est pas vraiment compilable qu'au fait que la programmation
en Lisp à tendance à accentuer la paresse du programmeur.
Ainsi certains appels à des fonctions coûteuses de manipulation
symbolique apparaissent, à la réflexion, inutiles. La programmation
dans un langage de bas niveau comme C oblige à coder de façon
efficace tout simplement parce qu'il n'existe pas de telles fonctions.
Aussi nous avons démarré la construction d'un prototype de détection
de scans en C. Ce prototype est en fait une (large) extension de CIPOL-light.
L'interface a été étendue pour accepter en entrée un système
d'équations complet et des fonctions de manipulation de systèmes ont
été rajoutées.
Par exemple la session CIPOL-light ci-dessous demande le calcul
du graphe des clauses d'un système d'équations particulier.
(print_dfg
(dfg
(system (n)
(equation v1 (i)
(clause (constraints (i n) (i = 1))
(add (aref b 0) (aref a 1))
)
(clause (constraints (i n) (i >= 2) (i <= n))
(subst v2
(add (eref v2 (function (i n) ( - i 1) n)) (aref a i))
0)))
(equation v2 (i)
(clause (constraints (i n) (i = 1) )
(add (aref a 0) (aref b 1))
)
(clause (constraints (i n) (i >= 2) (i <= n))
(add (eref v1 (function (i1 n) ( - i1 1) n)) (aref b i))
)))))
Il est assez facile de reconnaître le système d'équations
manipulé :
v1 : { i | 1 <= i <= n } cf real ;
v2 : { i | 1 <= i <= n } of real ;
v1[i] = case
{ i | i = 1 } : b[0] + a[1] ;
{ i | i >= 2 } : v2[i-1] + a[i] ;
esac ;
v2[i] = case
{ i | i = 1 } : a[0] + b[1] ;
{ i | i >= 2 } : v1[i-1] + b[i] ;
esac ;
Plus exactement, comme un mot clef subst se trouve dans la clause
v1.1, le système dont le graphe des clauses est calculé est
le système ci-dessus avec la référence à v2 dans v1.1
remplacée par sa valeur, c'est-à-dire :
v1 : { i | 1 <= i <= n } of real ;
v2 : { i | 1 <= i <= n } of real ;
v1[i] = case
{ i | i = 1 } : b[0] + a[1] ;
{ i | i = 2 } : a[0] + b[1] + a[2] ;
{ i | i >= 3 } : v1[i-2] + b[i-1] + a[i] ;
esac ;
v2[i] = case
{ i | i = 1 } : a[0] + b[1] ;
{ i | i >= 2 } : v1[i-1] + b[i] ;
esac ;
Nous donnons ci-dessous un extrait de la réponse de CIPOL-light en
omettant les transformations et les domaines des arcs du graphe des clauses :
( graph (
( vertex v2 0) ( vertex v2 1) ( vertex v1 0)
( vertex v1 1) ( vertex v1 2)
) (
( edge (v2 1) (v1 0) ) ( edge (v2 1) (v1 1) )
( edge (v2 1) (v1 2) ) ( edge (v1 2) (v1 0) )
( edge (v1 2) (v1 1) ) ( edge (v1 2) (v1 2) )
) )
Ce graphe contient bien les arcs attendus
(la source est le second sommet d'un arc).
L'extension de CIPOL-light est construite autour d'une grammaire
géré par lex et yacc, elle est constituée de
5000 lignes de code. Pour l'instant seuls les outils de base
de la normalisation de systèmes sont disponibles (i.e.
la substitution dans les systèmes d'équations et le choix
des substitutions à appliquer). Nous avons implanté la
stratégie de normalisation globale avec l'heuristique de
choix des substitutions présentée en 8.4.
Les résultats obtenus indiquent une accélération de
l'ordre de 10 par rapport au prototype Lisp. Il faut cependant
finaliser le prototype et mener une campagne de mesure sur
un plus grand nombre de programmes tests pour être sûr de
ce résultat. Il n'est pas prévu de réécrire
tout le détecteur en C, les parties complexes comme l'extraction de
la fonction binaire seront codées dans un langage de plus haut niveau.
Nous avons aussi écrit un prototype Lisp de calcul de bases
de temps pour les systèmes d'équations comportant des
scans explicites. Ce prototype calcule des bases de
temps approximatives, basées sur des conditions de causalité
approchées du type de (11.4) (voir la section 11.3).
Cela est cependant suffisant pour les exemples simples (comme
les tests de l'Argonne). C'est ce prototype qui a été utilisé
pour les tests de la section 11.5.
Notre prototype se greffe sur le prototype du professeur Feautrier
de calcul des bases de temps pour des programmes sans scan
explicite. La greffe ne comporte que 500 lignes de Lisp.
Aucun prototype n'a été développé pour la génération de
code. En ce qui concerne les prototypes la liste des travaux futurs
est :
-
terminer le nouveau prototype de détection de scans, il reste
principalement la partie en langage de haut niveau à écrire :
introduction des opérateurs Scan et extraction des fonctions
binaires ;
- améliorer le prototype Lisp de calcul des bases de temps ; il faut
générer des conditions de causalité du type de
(11.2) ;
- vérifier, par l'écriture d'un prototype de génération de
code, que le choix du code à générer et la génération
de ce code puissent être automatisés (c'est possible en
théorie mais la pratique réserve toujours des surprises).
| 16.2 |
Contribution de la thèse |
|
Nous avons présenté une méthode de détection de scan plus
précise que les méthodes existantes. Cette précision est due
à l'utilisation du graphe du flot des données qui permet de
traduire un programme à contrôle statique en un système
d'équations équivalent. Il est alors possible de normaliser
fortement le système en utilisant des substitutions de variables
à la Gauss. Nous avons présenté un algorithme original pour
normaliser le système. Cet algorithme se trouve être un algorithme
de recherche de transversal minimal dans l'hypergraphe des circuits
d'un graphe donné. Il a la bonne propriété de trouver tous les
transversaux minimaux de cardinal 1 et d'être bien adapté
à notre problème. Nous présentons aussi un opérateur pour
exprimer les scans calculés dans les programmes
impératifs à contrôle statique. Cet opérateur présente
des points communs avec les opérateurs de récurrence déjà
existants mais a la particularité de bien décrire les scans
portant sur des tableaux multi-dimensionnels. De plus, l'opérateur
Scan facilite la détection de scan multi-directionnels, c'est-à-dire
de scans calculés sur plusieurs directions d'un tableau.
L'exploitation des scans détectés est aussi abordée dans cette
thèse. Nous avons montré qu'il était possible de modifier les
techniques classiques de l'ordonnancement pour tenir compte des scans.
L'ordonnancement est calculé pour une machine virtuelle,
avec un nombre illimité de processeurs et avec des UAL à nombre
illimité d'entrées. Nous avons donc montré comment adapter cette
base de temps pour des machines réelles. Nous avons aussi montré
que deux types de codes pouvaient être générés pour un scan
donné et que le choix du code le plus efficace ainsi que la
génération du code pouvaient être automatisés. L'algorithme
de choix du code n'est cependant qu'une heuristique en fonction du
type du langage parallèle cible et du type du scan.
Enfin nous avons montré que la détection de scans pouvait
accélérer l'exécution des programmes traités. En effet,
une accélération de 2 par rapport au code généré par
le compilateur de Cray Research a été constaté sur deux
exemples. Il est important de dire que ces deux exemples n'ont pas
été construit pour l'occasion, il s'agit d'exemples réalistes.
Nos travaux ne sont pas limités à l'amélioration de la
parallélisation de programmes numériques. En effet
notre méthode de détection des scans a tendance à
réécrire le programme source comme une suite de
formules mathématiques. D'autres applications de ces travaux
sont donc la vérification de programmes (le programme
calcule-t-il la bonne formule ?) et l'ingénierie à
rebours (quelle formule calcule le programme ?).
Imaginons qu'un programmeur a écrit le programme ci-dessous
pour implanter l'algorithme de la remontée (voir section
12.3.3).
DO i=0,n-1
x(n-i)=b(n-i) (v1)
DO j=1,i
x(n-i)=x(n-i)-a(n-i,n-i+j)*x(n-i+j) (v2)
END DO
x(n-i)=x(n-i)/a(n-i,n-i) (v3)
END DO
La détection de scans dans ce programme conduit à l'équation
suivante :
v3 : { i | 0 <= i <= n-1 } of real ;
v3[i] = Scan( { i',j' | 0<=i'<=n-1, -1<=j<=i }, ( [0 1] ),
+, - a[n-i',n-i'+j'] * v3[i'-j'], b[n-i]
)[i,i] / a[n-i.n-i] ;
Cette équation peut être traduite automatiquement en l'expression
mathématique :
|
v3(i)= |
|
b(n-i)-a(n-i,n-i)*b(n-i)- |
|
v(i-j')*a(n-i,n-i+j') |
|
|
| a(n-i,n-i) |
|
D'un certain point du vue, les travaux présentés dans cette thèse
visent à améliorer la parallélisation d'un programme par
reconnaissance de schémas de programmation. Plus précisément
certains types de calculs mal parallélisés par les compilateurs
modernes sont reconnus et remplacés par des appels à des procédures
de calcul optimisées.
Dans cette thèse nous nous sommes limités à la détection de
scans et réductions. Ces calculs sont remplacés par un appel
à une procédure virtuelle ; l'opérateur Scan.
Mais pourquoi se restreindre à un seul type de calcul ?
Un premier pas vers la généralisation est la détection des
récurrences quelconques. Nous avons vu que notre prototype Lisp
était capable de ce genre de détection, pour preuve les tests
A.2.10 et A.2.11. Ces récurrences sont parallélisables
car il est possible d'extraire de leurs fonctions de propagation
des fonctions binaires et associatives (voir la section
10.4). Cependant, il existe une manière plus simple
d'en tirer parti, il suffit de les remplacer par un appel à une procédure
optimisée. Or la bibliothèque du Cray comporte de telles procédures ;
FOLRP et SOLR3. Les tests A.2.10 et A.2.11
s'exécutent 50% plus rapidement sur un Cray Y-MP lorsque les
récurrences sont remplacées par des appels aux procédures
optimisées.
Une généralisation possible de notre méthode serait donc de
détecter une partie des calculs classiques, c'est-à-dire les
calculs effectués par les procédures des bibliothèques
standard comme BLAS, et de les remplacer par des appels à ces
procédures.
Nous n'en sommes, déjà, pas très loin. Le programme
ci-dessous est une implantation courante de la
multiplication de matrices.
integer i,j,k,n
real a(n,n),b(n,n),c(n,n),s
do 1 i=1,n
do 1 j=1,n
s=0. (v1)
do 2 k=1,n
2 s = s + a(i,k) * b(k,j) (v2)
1 c(i,j) = s (v3)
Notre détecteur de scans transforme ce programme
en un système d'équations très concis :
v4 : { i,j | 1<=i<=n, 1<=j<=n } of real ;
v4[i,j] = Scan( { i',j',k' | 1<=i'<=n, 1<=j'<=n, 0<=k'<=n },
( [0 0 1] ), +, a[i',k'] * b[k',j'], 0 )[i,j,n] ;
Il est facile de reconnaître cet opérateur Scan particulier
et de générer un appel à une procédure optimisée
de multiplication de matrice.
Comme notre phase de normalisation est très efficace, quasiment
toutes les implantations de la multiplication de matrices se
ramènent à cet opérateur Scan.
Pour arriver ce résultat, il faut cependant approfondir l'étude
de l'opérateur Scan. Toute une algèbre peut être développée
autour de cet opérateur, certaines règles sont déjà connues
comme le changement de base décrit en 12.1.1, mais il existe
d'autres règles, particulièrement des règles de simplification.
Le programme de la multiplication de matrices peut être bruité,
il suffit pour cela d'initialiser s avec le premier terme de
la somme :
integer i,j,k,n
real a(n,n),b(n,n),c(n,n),s
do 1 i=1,n
do 1 j=1,n
s=a(i,1)+b(1,j) (v1)
do 2 k=2,n
2 s = s + a(i,k) * b(k,j) (v2)
1 c(i,j) = s (v3)
Ce programme est valide dès que les matrices ne sont pas de
taille 0. Sans règle de simplification sur les opérateurs
Scan, le système d'équations obtenu par le détecteur de
récurrence est :
v4 : { i,j | 1<=i<=n, 1<=j<=n } of real ;
v4[i,j] = Scan( { i',j',k' | 1<=i'<=n, 1<=j'<=n, 1<=k'<=n },
( [0 0 1] ), +, a[i',k'] * b[k',j'],
a[i',1] * b[1,j'] )[i,j,n] ;
Cependant, il est facile de voir que le domaine d'accumulation
de cet opérateur Scan peut être étendu. Le nouvel opérateur
est celui qui apparaît dans l'exemple précédent.
Le prototype Lisp applique ce genre de simplification. Cela a
nécessité l'écriture d'une reconnaissance de forme
intégrant la plupart des règles d'algèbre linéaire.
Par exemple cette reconnaissance de forme est capable d'apparier
le terme i+1+x avec i en posant x=-1.
En résumé, la généralisation de notre méthode de
détection de scans peut déboucher sur une nouvelle forme
de parallélisation automatique par reconnaissance de schémas
de programmation. Cette méthode serait bien plus efficace que les
méthodes de parallélisation par simple reconnaissance de formes
qu'implantent la plupart des compilateurs commerciaux car elle
hériterait des points forts de notre méthode de détection
de scans :
-
la précision de l'analyse du programme due au graphe
du flot des données ;
- l'efficacité d'une normalisation du programme basée
sur les substitutions d'équations ;
- un opérateur Scan dont la sémantique est particulièrement
bien adaptée aux programmes impératifs manipulant des tableaux
multi-dimensionnels.
Cette méthode, bien que moins élégante, pourrait même
rivaliser avec la méthode de parallélisation automatique dite
géométrique. En effet l'analyse ne porterait pas simplement
sur les dépendances entre les opérations mais directement sur
la sémantique du programme.