Un modèle de coût symbolique pour les programmes parallèles asynchrones à dépendances structurées
L'objectif d'une parallélisation est souvent de minimiser en premier lieu le temps d'exécution. Il paraît donc indispensable de disposer d'un modèle permettant d'évaluer a priori les performances d'un algorithme. Or, l'évaluation repose sur l'identification de...
Salvato in:
| Autore principale: | |
|---|---|
| Altri autori: | |
| Natura: | Thèse et Mémoire papier |
| Lingua: | Français |
| Pubblicazione: |
[S.l.] :
[s.n.]
2000.
|
| Soggetti: | |
| Nota: |
Publication autorisée par le jury |
| Autres localisations: | Voir dans le Sudoc |
| Variante du titre: | A symbolic cost model for asynchronous parallel programs with structured dependences |
| LEADER | 03288nam a22002657a 4500 | ||
|---|---|---|---|
| 001 | 183633 | ||
| 008 | 020604s2000 xxe ||| |||| 00| 0 fre d | ||
| 009 | PPN061089702 | ||
| 041 | 0 | |a fre |b fre |b eng | |
| 084 | |a 004 | ||
| 100 | 1 | |a Rebeuf, Xavier, |d 1972- | |
| 240 | 1 | 0 | |a A symbolic cost model for asynchronous parallel programs with structured dependences |
| 245 | 1 | 0 | |a Un modèle de coût symbolique pour les programmes parallèles asynchrones à dépendances structurées |c par Xavier Rebeuf ; [sous la dir. de] François Le Berre,... |
| 260 | |a [S.l.] : |b [s.n.], |c 2000. | ||
| 300 | |a 166 p. ; |c 30 cm. | ||
| 500 | |a Publication autorisée par le jury | ||
| 502 | |a Thèse de doctorat. Informatique. Orléans. 2000 | ||
| 504 | |a Bibliogr. p. 161-166 | ||
| 520 | |a L'objectif d'une parallélisation est souvent de minimiser en premier lieu le temps d'exécution. Il paraît donc indispensable de disposer d'un modèle permettant d'évaluer a priori les performances d'un algorithme. Or, l'évaluation repose sur l'identification des synchronisations pour chaque exécution (dépendances-écriture-lecture). Sans restriction de l'expression du parallélisme, un calcul exact conduit généralement à une explosion combinatoire. Pour pallier ce problème, les modèles de coût classiques, ne prennent généralement en compte qu'une partie du parallélisme possible, permettant ainsi de définir statiquement un surensemble cohérent des dépendances de toutes les exécutions d'un algorithme. Nous proposons un modèle intermédiaire fondé sur la structuration de la résolution dynamique des accès aux données. Nous montrons qu'il est possible de représenter symboliquement l'ensemble des dépendances effectives de chaque exécution, et d'obtenir ainsi une évaluation exacte du coût sans explosion combinatoire. Nous conditionnons l'existence de chaque dépendance en l'annotant par un prédicat. Le coût d'un programme est alors exprimé symboliquement en fonction de ces prédicats. Pour être capable de l'évaluer dans l'environnement initial, nous transformons les prédicats grâce à une méthode fondée sur le calcul des plus faibles préconditions. Le coût symbolique obtenu est paramétré par l'environnement initial et il intègre les indépendances dynamiques. Afin d'assurer la compositionalité des coûts symboliques, nous étendons le calcul des plus faibles préconditions aux expressions. Nous développons pour cela une sémantique permettant d'exprimer symboliquement ce que calcule le programme et de calculer son coût par induction sur la syntaxe. Nous montrons qu'il est possible d'intégrer au modèle des paramètres de l'architecture ainsi qu'une charge instantanée du réseau. Nous comparons les résultats obtenus sur plusieurs algorithmes avec des expérimentations sur Cray T3E. | ||
| 650 | |a Programmation parallèle (informatique) | ||
| 650 | |a Parallélisme (informatique) | ||
| 650 | |a Thèses et écrits académiques | ||
| 700 | 1 | |a Le Berre, François, |d 1932- |4 ths | |
| 710 | 2 | |a Université d'Orléans. |4 dgg | |
| 997 | |0 183633 |1 Thèse et Mémoire papier |a Ressource papier |c 0/Orléans/ |c 1/Orléans/BU Sciences, Technologies, STAPS/ |z Orléans, BU Sciences, Technologies, STAPS, TS 19-2000-56 |z Orléans, BU Sciences, Technologies, STAPS, TS 19-2000-56 b | ||