Mémoire partagée et parallélisme de données

Le parallélisme à mémoire partagée implique que plusieurs fils d'exécution opèrent sur un espace d'adressage commun, tandis que le parallélisme de données applique la même opération simultanément à de nombreux éléments de données.

Definition

Dans le modèle à mémoire partagée, les fils d'exécution parallèles communiquent implicitement en lisant et écrivant dans une mémoire commune, se coordonnant via des primitives de synchronisation ; le parallélisme de données est le cas particulier dans lequel la même computation est appliquée indépendamment aux éléments d'une structure de données.

Scope

Ce sujet aborde le modèle d'espace d'adressage partagé et ses interfaces de programmation (fils d'exécution, OpenMP), les primitives de synchronisation qui coordonnent les fils d'exécution (verrous, barrières, opérations atomiques) et les risques qu'elles gèrent (courses aux données, interblocage, faux partage), les constructions de parallélisme de données et de boucles, ainsi que les environnements d'exécution basés sur les tâches avec des ordonnanceurs à vol de travail. Il traite de l'aspect programmation dont les fondements théoriques sont présentés sous les modèles de mémoire partagée.

Core questions

• Comment les fils d'exécution coordonnent-ils l'accès aux données partagées sans courses aux données ni interblocage ?
• Comment les boucles et les opérations sur les tableaux peuvent-elles être exprimées pour une exécution parallèle ?
• Comment les tâches générées dynamiquement sont-elles équilibrées efficacement entre les cœurs ?

Key theories

Synchronisation et cohérence de la mémoire

Les programmes à mémoire partagée corrects reposent sur des primitives de synchronisation et une compréhension du modèle de mémoire qui régit le moment où les écritures d'un fil d'exécution deviennent visibles pour un autre, une mauvaise gestion pouvant entraîner des courses aux données ou un interblocage.

Parallélisme de données basé sur des directives

OpenMP permet aux programmeurs d'annoter du code séquentiel avec des directives qui parallélisent les boucles et les régions sur un espace d'adressage partagé, offrant une voie portable et incrémentale vers le parallélisme à mémoire partagée.

Ordonnancement de tâches par vol de travail

Les environnements d'exécution basés sur les tâches planifient les tâches créées dynamiquement en faisant en sorte que les processeurs inactifs volent du travail aux processeurs occupés, atteignant un bon équilibrage de charge démontré et une surcharge bornée pour les calculs parallèles irréguliers.

Clinical relevance

La programmation à mémoire partagée et le parallélisme de données permet aux logiciels courants d'exploiter les processeurs multicœurs et aux noyaux scientifiques, simulations et charges de travail intensives en tableaux d'atteindre des accélérations sur un nœud unique, ce qui en fait la forme de programmation parallèle la plus répandue.

History

Le multiprocesseur à mémoire partagée a mûri avec le modèle des fils d'exécution et la norme OpenMP de 1998 pour le parallélisme portable basé sur des directives ; les ordonnanceurs à vol de travail du projet Cilk (à partir de 1996) ont fourni un parallélisme basé sur les tâches efficace, et ces idées sous-tendent désormais la programmation multicœur dans tous les langages.

Key figures

• Maurice Herlihy
• Nir Shavit
• Charles Leiserson
• Vipin Kumar

Seminal works

• herlihy2008
• grama2003
• blumofe1996

Frequently asked questions

Qu'est-ce qu'une course aux données et pourquoi est-elle dangereuse ?

Une course aux données se produit lorsque deux fils d'exécution accèdent simultanément à la même adresse mémoire et qu'au moins l'un d'eux écrit, sans synchronisation. Le résultat est indéfini et peut varier d'une exécution à l'autre, produisant des bogues intermittents et difficiles à reproduire, c'est pourquoi la synchronisation est essentielle dans les programmes à mémoire partagée.