Un modèle de transition pour le calcul parallèle – Valiant 1990 Valiant a développé une extension au modèle BSP dans les années 2000, conduisant à la publication du modèle multi-BSP [2] en 2011. Le modèle de calcul parallèle synchrone en vrac (BSP) a été introduit par Valiant [77] comme un «modèle de transition» pour l`informatique parallèle à usage général. Le modèle BSP peut être considéré comme une abstraction du matériel et des logiciels parallèles, et prend en charge une approche de calcul parallèle qui est à la fois indépendante de l`architecture et évolutive. Les principaux principes de BSP sont le traitement d`un support de communication en tant que réseau abstrait entièrement connecté, et le découplage de toute interaction entre les processeurs dans la communication de données asynchrones point à point et la synchronisation des barrières. Un tel découplage permet un… W {displaystyle W}, H {displaystyle H} et S {displaystyle S} sont généralement modélisés en tant que fonctions, qui varient en fonction de la taille du problème. Ces trois caractéristiques d`un algorithme BSP sont généralement décrites en termes de notation asymptotique, p. ex. H (n/p) {displaystyle Hin O (n/p)}. Dans BSP, un programme parallèle s`exécute sur un ensemble de processeurs virtuels (appelés processus pour les distinguer des processeurs physiques) et s`exécute sous la forme d`une séquence de supersteps parallèles séparés par des synchronisations de barrière. Chaque superstep est composé de trois phases ordonnées, comme illustré à la Fig. 1:1) une phase de calcul local, où chaque processus peut effectuer le calcul à l`aide des valeurs de données locales et émettre des demandes de communication telles que des lectures et des écritures de mémoire distante; 2) une phase de communication globale, où les données sont échangées entre les processus selon les demandes faites pendant la phase de calcul locale; et 3) une synchronisation de barrière, qui attend que tous les transferts de données se terminent et rende les données transférées à la disposition des processus pour une utilisation dans le prochain superstep. En 2017, McColl a développé une nouvelle extension majeure du modèle BSP qui fournit une tolérance aux pannes et une tolérance de queue pour les calculs parallèles à grande échelle dans l`IA, l`analytique et le HPC.

[3] dans la pratique, g {displaystyle g} est déterminé empiriquement pour chaque ordinateur parallèle. Notez que g {displaystyle g} n`est pas le délai de livraison de mot unique normalisé, mais le délai de livraison d`un seul mot dans des conditions de trafic continues. Le nombre maximal de messages entrants ou sortants pour un superstep est noté par h {displaystyle h}. La capacité d`un réseau de communication à fournir des données est capturée par un paramètre g {displaystyle g}, défini de telle sorte qu`il prend le temps h g {displaystyle Hg} pour qu`un processeur délivre des messages h {displaystyle h} de taille 1. Le mécanisme de synchronisation capte l`idée d`une sychronisation globale à un niveau de grossièreté contrôlable. Aucune hypothèse n`est faite sur les délais de livraison relatifs des messages dans un superstep. Les opérations locales sont effectuées uniquement sur les données disponibles localement avant le début du superstep. Tout cela sera familier des documents graphiques que nous étudions. Nouvelle est l`analyse de Valiant des propriétés du modèle BSP, qui éclaire sur son applicabilité générale…

Figure 2 montre pseudo-code pour un programme simple où chaque processus transmet les données à son voisin droit et effectue un peu de calcul local.