Les applications informatiques sont de plus en plus nombreuses.
Des réalisations qui étaient jusque là impensables à cause
de la puissance de calcul et de la place disque nécessaires
commencent à être envisagées. Ces applications concernent
la prévision météo sur quelques jours, les études climatiques
sur quelques millénaires, la reconnaissance de l'écriture et de
la parole, la synthèse d'image en temps réel (en particulier
les simulateurs de vol pour la formation des pilotes)
et plus généralement toutes les simulations numériques.
L'informatique est la victime de son succès ; les ordinateurs
sont condamnés à être toujours plus puissants. Pour augmenter
la vitesse de ces machines, une solution est d'améliorer les
unités centrales. Les technologies de fonte des circuits
se sont succédées en tentant de réduire le pas de masque des
circuits et en dopant le silicium pour accélérer les temps
de commutation des portes. Les fréquences des processeurs ont
donc été augmentées pour atteindre, par exemple, les
200 Mhz du processeur Alpha (le DEC 21064AA) de chez Digital.
Il est remarquable que cette diminution de la période d'horloge
n'est pas uniquement limitée aux processeurs de haut de gamme
puisque les Pentium d'Intel tournent à près de 100 Mhz.
Mais cette course à la fréquence a des limites d'autant plus
que les temps d'accès aux mémoires ne suivent pas. Même
en rajoutant une hiérarchie de mémoires, il n'est pas possible
d'atteindre la puissance de crête des processeurs les plus
récents. Comme la compression du temps bute sur ces
limites, une autre idée est apparue : s'étendre sur l'espace.
Le principe est simple : si une machine comporte plusieurs
processeurs (mettons p processeurs) alors elle doit pouvoir
répartir son travail sur ces processeurs pour réduire
le temps d'exécution jusqu'à p fois.
La réalité est plus sombre. Si des applications très
particulières (comme le calcul de l'ensemble de Mandelbrot)
se parallélisent très bien, ce n'est pas le cas général.
Plusieurs raisons peuvent expliquer ces performances décevantes.
L'algorithme utilisé peut ne pas contenir de parallélisme ou
le programmeur et le compilateur n'ont pas su mettre en relief
ce parallélisme.
Il est aussi possible que les temps des communications entre les
processeurs occultent le gain dû au parallélisme. En effet
les échanges de données s'effectuent par passage de messages
sur un réseau de communication ou par l'intermédiaire d'une
mémoire globale (d'ailleurs souvent implantée par passage de
messages). En conséquence les communications sont lentes ; c'est
le talon d'Achille des machines parallèles.
Le lecteur aura compris que l'adaptation d'un programme à une
machine parallèle (i.e. possédant plusieurs processeurs
à usage général) n'est pas une sinécure ; il faut tenir
compte de nombreux paramètres. C'est alors qu'est apparue l'idée
de la parallélisation automatique : puisqu'il s'agit d'une tâche
complexe, laissons une machine s'en charger. De nombreuses équipes
de recherche travaillent actuellement dans le domaine de la
parallélisation automatique. Différentes méthodes pour
la parallélisation de programmes impératifs (comme Fortran)
existent. Ces méthodes détectent une grande partie du
parallélisme implicite d'un programme séquentiel, mais
pas encore la totalité. Avec l'émergence de machines
disposant d'un nombre important de processeurs, chaque parcelle
de parallélisme doit être exploitée pour qu'aucun processeur
ne reste inactif. Les calculs de récurrences font partie des
portions de code encore mal parallélisées par les compilateurs
modernes. Cette thèse donne une méthode pour détecter certaines
récurrences calculables efficacement sur des machines parallèles.
Elle montre aussi comment il est possible d'exploiter ces récurrences,
c'est-à-dire de générer un code parallèle efficace.
