Conservatoire national des arts et métiers
Architectures des systèmes informatiques
CHAPITRE 10
Parallélisme, taxinomies et classifications
Année 2002-2003

Sachant qu'un terrassier creuse un trou cubique d'un mètre de côté en une heure,
combien de temps mettront 50 terrassiers pour creuser le même trou ?
    Auteur inconnu

10.0 PRÉSENTATION

Ce chapitre et les trois suivants traitent du parallélisme explicite entre processeurs ou entre données. Les formes plus modestes du parallélisme ou parallélisme fin, pipelines (flot unique d'instructions), chemins de données (plusieurs octets d'un même flot), superscalaire ont été traités précédemment.

Ce chapitre contient :
10.1 une introduction générale;
10.2 quelques informations sur les modes de programmation;
10.3 des repères historiques qui n'étaient pas dans le chapitre 1;
10.4 la présentation de plusieurs taxinomies;
10.5 l'état actuel des taxinomies et des classifications;
10.6 les caractères généraux du parallélisme.

10.1. QU'EST CE QUE LE PARALLÉLISME EN INFORMATIQUE ?

C'est une organisation et des techniques de réalisation telles que des travaux (pris dans le sens le plus général) y sont exécutés en simultanéité. Le but est de faire plus vite les mêmes travaux ainsi que de faire des travaux plus longs ou plus complexes.
 

Le parallélisme caractérise  l'organisation matérielle et les techniques de mise en œuvre. En découle une simultanéité qui caractérise les processus exécutés sur des machines dotées de parallélisme.

Le parallélisme et la simultanéité qui en découle ont des degrés.

On distingue, allant du détail au global :

• les bits traités simultanément par 8, 12, 16, 32 ou 64 dans les bus, les registres, les unités fonctionnelles;
• les données traitées par collections petites, grandes ou très grandes dans les machines dites vectorielles;
• les instructions décodées en concomitance dans un pipeline;
• la prise en compte de plusieurs instructions à la fois (VLIW);
• les instructions exécutées simultanément dans un processeur superscalaire;
• la gestion des entrées et sorties pendant que le processeur continue à opérer;
• plusieurs processeurs traitant des parties d'une même tâche;
• plusieurs processeurs traitant des tâches différentes.

• des miniprocessus (threads);
• des tâches différentes (multitâche);
• des travaux indépendants (multiutilisateur);

Plus largement encore, un site de la toile a proposé en 1996 [MER96] de contribuer à la recherche de nombres premiers. Le visiteur se voit proposer une tranche de nombres à explorer et un logiciel à charger. Le logiciel s'exécute ensuite en tâche de fond et cherche les nombres premiers dans la tranche. Des milliers d'ordinateurs dans le monde recherchent simultanément des nombres premiers.

10.2. POURQUOI LE PARALLÉLISME ?

Nous venons de voir que les machines série qui respectent plus ou moins strictement le schéma de Neumann incorporent du parallélisme à des degrés divers. Néanmoins les traitements y sont faits sur un seul processeur. La rapidité de traitement dépend alors à la fois de la rapidité de commutation des circuits, de la vitesse de transport des données et de divers temps de latence.

Pour fixer les idées, une cadence d'exécution, et non une fréquence d'horloge, de 100 millions d'instructions par seconde correspond à une instruction exécutée chaque 10 ns. Le GHz d'exécution, soit un milliard d'instructions par seconde est attendu vers 2004.

Pour ce qui est de la vitesse de déplacement des données, les limites sont très différentes.
La célérité de la lumière dans le vide, limite absolue, est d'environ 30 cm/ns.
La célérité de l'électricité dans le fil de cuivre est inférieure à 20 cm/ns, dans un conducteur de qualité moyenne elle est de l'ordre de 15 cm/ns. Elle est bien moindre quand le signal parcourt des circuits, environ 1 cm par nanoseconde.

On pourrait penser que 100 millions à un milliard d'instructions par seconde suffisent pour traiter les problèmes humainement concevables. Il n'en est rien. Au moins deux grandes classes de problèmes demandent un traitement plus rapide. Ce sont :

• des simulations et modélisations parce qu'elles sont basées sur des approximations successives et que plus petite est la largeur de la maille, plus grand est le nombre de calculs et plus précis est le résultat;
• des traitements de grandes quantités de données :

• des traitements de signaux comme l'analyse sismique;
• le traitement de l'image animée;
• l'animation d'images de synthèse;
• les accès multiples aux bases de données.

• la modélisation du climat et la circulation des océans;
• la modélisation des fluides turbulents (mécanique statistique);
• la modélisation des semi-conducteurs et des supraconducteurs;
• la dispersion de la pollution;
• la gestion du code du génome des êtres vivants;
• la chromodynamique quantique en physique fondamentale;
• la simulation des systèmes explosifs et en combustion.

Vue en ultra grand angle de l'IBM «Blue Pacific» (1998)
1464 nœuds de 4 processeurs POWER, 3.9 TeraFlops, 2.6 TB de SDRAM et 75TB de RAID.

10.3 LE PASSAGE AU PARALLÉLISME EST UN CHANGEMENT IMPORTANT

La fabrication des machines parallèles est simple. Leur mise en œuvre est difficile comme on le verra dans le chapitre 12.

Une tâche de grande dimension peut toujours être exécutée pas à pas. Il se peut qu'on puisse la décomposer en tâches plus petites exécutables simultanément.

La simultanéité est d'exécution pour une tâche est réalisable en :

• décomposant le travail à faire en tâches de moindre importance;
• confiant ces tâches à des processeurs différents pour qu'ils les exécutent simultanément;
• coordonnant ces opérateurs;
• prenant soin de ne pas décomposer le travail en tâches si petites qu'il serait plus rapide de les exécuter plutôt que d'expliquer au processeur ce qu'il doit faire.

Le calcul parallèle va nécessiter :

• des opérateurs ou processeurs nombreux;
• un ou des liens entre eux;
• des outils spéciaux pour gérer le calcul en parallèle en termes de
• de système d'exploitation;
• de compilateurs;
• des outils de programmation pour gérer les communications et la coordination des processeurs;
• un algorithme particulier et un programme qui le réalise; décomposition du problème en morceaux, que plusieurs opérateurs peuvent traiter simultanément.
• des processeurs particuliers pour certains usages.

Dans la plupart des cas, l'algorithmique spécifique aux machines parallèles présente une difficulté conceptuelle.

Les processeurs pour le traitement du signal sont présentés dans le chapitre 13.