Modélisation des algorithmes itératifs parallèles synchrones et asynchrones
Algorithmes parallèles asynchrones I - Modélisation et analyse

Les premiers ordinateurs étaient essentiellement constitués d’une mémoire chargée de stocker les programmes informatiques ainsi que les données nécessaires à ces derniers, une unité arithmétique et logique chargée d’effectuer ces types d’opérations, et les unités d’échanges vers les périphériques (disques, imprimantes, etc.). En raison de la présence d’une seule unité arithmétique et logique, sur ce type d’architecture, un code de calcul est exécuté en mode séquentiel sur cette seule ressource ; cela correspond à l’exécution des instructions l’une après l’autre, donc une seule à la fois, même si les opérations à effectuer sont indépendantes. Ce type d’exécution séquentielle a très rapidement atteint des limites de performances lorsque le calcul ne permet pas d’obtenir des résultats dans des délais raisonnables et nécessite un stockage mémoire important. Ainsi, pour des calculs rendus nécessaires pour traiter de grosses applications, comme par exemple en météorologie, ce type de programmation séquentielle n’est plus adapté et les performances de calcul ne sont pas satisfaisantes pour obtenir des résultats de simulation dans des temps relativement brefs.

Pour remédier à ces limitations le calcul parallèle est apparu comme une solution. Afin d’améliorer les performances des ordinateurs, cette solution consiste à exploiter au mieux les ressources de calcul et de mémorisation. La solution retenue revient à paralléliser les codes, c’est-à-dire à effectuer plusieurs calculs simultanément sur différentes ressources constituées pour chacune d’elle par une unité arithmétique et logique, appelée aussi processeur ; ainsi un plus grand nombre d’opérations sont effectuées en un temps minimal. Pour paralléliser un code de calcul, l’utilisateur est amené à décomposer le problème global à traiter en plusieurs sous-problèmes couplés chacun de taille plus petite. Ainsi plusieurs tâches de calcul pourront être traitées simultanément sur ces processeurs, le couplage entre les sous-problèmes étant effectué par des échanges de résultats entre les processus coopérants en parallèle. Par ce biais, à condition de bien optimiser les codes de calcul parallélisés, les temps d’exécution pourront nettement diminuer ce qui permettra de résoudre des problèmes de plus grande taille et de traiter des volumes de données plus importants.

Ce nouveau mode de calcul nécessite d’une part de remettre en cause l’architecture des premiers ordinateurs, d’autre part d’adapter le programme de calcul à un mode d’exécution parallèle et enfin d’apprendre de nouveaux langages et outils de programmation.

Les architectures de ces superordinateurs ont donc évoluées d’abord par la construction de machines à mémoire commune où tous les processeurs ont accès à cette dernière. Cependant ce type de machine est d’une part onéreux à construire et d’autre part il ne permet pas un parallélisme massif souhaitable pour traiter de grosses applications. Les constructeurs ont donc conçu des machines à mémoire distribuée où chaque processeur possède sa propre mémoire locale, les liaisons entre ces processeurs s’effectuant par un réseau d’interconnexion ; ce dernier permet des échanges de messages entre les processeurs ce qui réalise une mise en œuvre du parallélisme. Il existe également des architectures mixtes combinant les deux cas extrêmes précédents. On verra plus en détail dans un second article d’autres possibilités de concevoir des architectures parallèles.

Par ailleurs sur le plan de la programmation de ce type de machine, il convient de repenser le codage des algorithmes afin de prendre en compte les possibilités offertes d’effectuer simultanément plusieurs instructions en même temps. La solution idéale est de découper le problème à résoudre en tâches indépendantes. Ce mode de calcul est rarement possible et en général le programmeur considère un découpage du problème en tâches couplées entre elles ; dans ces conditions les processeurs échangent les résultats de leurs calculs avec les autres unités avec lesquelles ils doivent communiquer. On distingue essentiellement deux modes de communication : un mode de communication synchrone et un mode de communication asynchrone. Pour fixer les idées nous nous limiterons dans cette série d’articles à un mode de calcul itératif bien adapté à la résolution de problèmes de grande dimension ; dans ces conditions :

• en mode de communication synchrone chaque processeur peut commencer une nouvelle itération lorsqu’il a reçu les données de tous les processeurs avec lesquels il doit communiquer ce qui implique des périodes d’inactivité entre les itérations ; ce mode de communication est donc bloquant ;

• en mode de communication asynchrone, chaque processeur exécute ses propres itérations sans tenir compte de la progression des autres processeurs avec lesquels il doit communiquer ; ainsi les processeurs effectuent leurs calculs à leur propre rythme sans attendre les données émises par les autres processeurs en utilisant les dernières données disponibles délivrées par ces derniers. Dans ce mode de communication, il n’y a donc pas de période d’inactivité ; ce mode de communication est donc non bloquant.

Enfin, il existe de nombreux outils permettant de paralléliser les codes de calcul implémentés à partir des langages de programmation classiques (Fortran, C, C++).