Calcul de temps d'exécution parallèle et de taux de production:
quelques remarques et problèmes en suspens.
Resumé
Il s'agit d'un court exposé,
dont l'objet est de faire une synthèse
de deux travaux indépendants dont le lien est resté probablement
inaperçu et de pointer quelques problèmes
actuels.
On considère les deux problèmes suivants qui
n'ont semble-t-il rien à voir.
- Calcul d'accélérations
parallèles. On considère un ensemble
d'exécutions parallèles.
On peut définir l'accélération parallèle
(ou ``speedup'') d'une exécution comme
le ratio du temps d'exécution séquentiel
de cet ensemble de tâches sur le temps d'exécution
parallèle sur un système donné.
Formellement, on se donne un langage de trace
reconnaissable L, décrivant cette exécution.
Il s'agit de trouver les valeurs maximales,
minimales, et asymptotiques (sur les
longues traces) de cette accelération.
- Probleme classique du calcul du taux de production
d'un graphe d'événements.
Variante (moins classique) du calcul formel de ce taux
lorsque certaines ressources sont vues
comme des indeterminées.
On doit à Cerin et Petit un algorithme
modulaire basé sur les formes normales
de Cartier-Foata pour calculer l'accéleration de langages
de trace reconnaissables. Plus récemment, d'autre
techniques basees sur les automates a multiplicités
(max,+) ont été proposées (S.G et J. Mairesse).
Il existe bien des méthodes pour calculer
le taux de production dans le cas ``constant''
(absence de ressources indéterminées).
Dans le cas ``formel'', un algorithme également modulaire a été proposé (cf. Chap 9 (thèse), ou la
lecture tres informelle, SPA).
Une fois épurées, toutes ces questions se réduisent
en fait à l'unique problème générique suivant.
- Soit M un monoïde, L une partie rationnelle
de M, f, g des morphismes de M vers R^+ (muni
de l'addition). Calculer
phi(L)=\inf_{m\in L} f(m)/g(m). [on convient que 0/0=infty]
- Variante formelle.
Même question lorsque f,g sont des morphismes
de M vers le monoîde additif des formes linéaires
à coefficients positifs de (R^+)^p vers R^+.
On peut calculer phi(L) par induction sur l'expression
rationnelle décrivant L. On s'intéressera particulièrement
aux quotients de M qui permettent de réduire la complexité
du problème. On finira par un problème
ouvert relié.