Modèle d'accès à la mémoire - Memory access pattern
En informatique , un modèle d'accès à la mémoire ou un modèle d'accès IO est le modèle avec lequel un système ou un programme lit et écrit la mémoire sur le stockage secondaire . Ces modèles diffèrent dans le niveau de localité de référence et affectent considérablement les performances du cache , et ont également des implications pour l'approche du parallélisme et de la distribution de la charge de travail dans les systèmes de mémoire partagée . En outre, les problèmes de cohérence du cache peuvent affecter les performances du multiprocesseur , ce qui signifie que certains modèles d'accès à la mémoire placent un plafond sur le parallélisme (que de nombreuses approches fondamentales cherchent à briser).
La mémoire de l'ordinateur est généralement décrite comme un " accès aléatoire ", mais les traversées par logiciel présenteront toujours des modèles qui peuvent être exploités pour plus d'efficacité. Divers outils existent pour aider les concepteurs de systèmes et les programmeurs à comprendre, analyser et améliorer le modèle d'accès à la mémoire, y compris VTune et Vectorization Advisor , y compris des outils pour traiter les modèles d'accès à la mémoire GPU
Les modèles d'accès à la mémoire ont également des implications pour la sécurité , ce qui motive certains à essayer de déguiser l'activité d'un programme pour des raisons de confidentialité .
Exemples
Séquentiel
L'extrême le plus simple est le modèle d' accès séquentiel , où les données sont lues, traitées et écrites avec un adressage incrémenté / décrémenté simple. Ces modèles d'accès se prêtent très bien à la prélecture .
Foulé
Les modèles d'accès 2D, 3D simples ou progressifs (par exemple, le passage à travers des tableaux multidimensionnels ) sont également faciles à prédire et se retrouvent dans les implémentations d' algorithmes d' algèbre linéaire et de traitement d'image . Le carrelage en boucle est une approche efficace. Certains systèmes avec DMA fournissaient un mode strided pour transférer des données entre des sous-ensembles de tableaux 2D plus grands et une mémoire de bloc - notes .
Linéaire
Un modèle d'accès linéaire est étroitement lié à "strided", où une adresse mémoire peut être calculée à partir d'une combinaison linéaire d'un certain index. Le fait de parcourir les index de manière séquentielle avec un modèle linéaire donne un accès direct . Un modèle d'accès linéaire pour les écritures (avec n'importe quel modèle d'accès pour les lectures sans chevauchement) peut garantir qu'un algorithme peut être parallélisé, ce qui est exploité dans les systèmes prenant en charge les noyaux de calcul .
Voisin le plus proche
Les modèles d'accès à la mémoire du voisin le plus proche apparaissent dans la simulation et sont liés à des modèles séquentiels ou strided. Un algorithme peut traverser une structure de données en utilisant des informations provenant des voisins les plus proches d'un élément de données (dans une ou plusieurs dimensions) pour effectuer un calcul. Celles-ci sont courantes dans les simulations physiques opérant sur des grilles. Le voisin le plus proche peut également faire référence à la communication entre nœuds dans un cluster; Les simulations physiques qui reposent sur de tels modèles d'accès locaux peuvent être parallélisées avec les données partitionnées en nœuds de cluster, avec une communication purement du plus proche voisin entre eux, ce qui peut présenter des avantages pour la latence et la bande passante de communication. Ce cas d'utilisation correspond bien à la topologie du réseau torus .
2D spatialement cohérent
Dans le rendu 3D , les modèles d'accès pour le mappage de texture et la pixellisation de petites primitives (avec des distorsions arbitraires de surfaces complexes) sont loin d'être linéaires, mais peuvent toujours présenter une localité spatiale (par exemple, dans l'espace d'écran ou l' espace de texture ). Cela peut être transformé en une bonne localisation mémoire via une combinaison d' ordre morton et de tuilage pour les cartes de texture et les données de tampon de trame (mappage de régions spatiales sur des lignes de cache), ou en triant les primitives via un rendu différé basé sur des tuiles . Il peut également être avantageux de stocker les matrices dans l'ordre morton dans des bibliothèques d'algèbre linéaire .
Dispersion
Un modèle d'accès à la mémoire dispersée combine des lectures séquentielles avec un adressage indexé / aléatoire pour les écritures. Comparé à la collecte, il peut placer moins de charge sur une hiérarchie de cache car un élément de traitement peut distribuer des écritures de manière "déclencher et oublier" (en contournant complètement un cache), tout en utilisant une prélecture prévisible (ou même DMA) pour ses données sources.
Cependant, il peut être plus difficile de paralléliser car il n'y a aucune garantie que les écritures n'interagissent pas, et de nombreux systèmes sont toujours conçus en supposant qu'un cache matériel fusionnera de nombreuses petites écritures en plus grandes.
Dans le passé, le mappage de texture avant tentait de gérer le caractère aléatoire avec des "écritures", tout en lisant séquentiellement les informations de texture source.
La console PlayStation 2 utilisait le mappage de texture inverse conventionnel, mais géraient tout traitement de dispersion / collecte "sur puce" en utilisant EDRAM, tandis que le modèle 3D (et beaucoup de données de texture) de la mémoire principale était alimenté séquentiellement par DMA. C'est pourquoi il manquait de support pour les primitives indexées, et parfois nécessaire pour gérer les textures «en amont» dans la liste d'affichage .
Recueillir
Dans un modèle d'accès à la mémoire de regroupement , les lectures sont adressées ou indexées de manière aléatoire, tandis que les écritures sont séquentielles (ou linéaires). Un exemple se trouve dans le mappage de texture inverse , où les données peuvent être écrites linéairement sur les lignes de balayage , tandis que les adresses de texture à accès aléatoire sont calculées par pixel .
Par rapport à la dispersion, l'inconvénient est que la mise en cache (et le contournement des latences) est désormais essentielle pour des lectures efficaces de petits éléments, mais il est plus facile de paralléliser puisque les écritures sont garanties de ne pas se chevaucher. En tant que telle, l'approche de collecte est plus courante pour la programmation gpgpu , où le threading massif (activé par le parallélisme) est utilisé pour masquer les latences de lecture.
Collecte et dispersion combinées
Un algorithme peut collecter des données à partir d'une source, effectuer des calculs dans la mémoire locale ou sur la puce et disperser les résultats ailleurs. Il s'agit essentiellement du fonctionnement complet d'un pipeline GPU lors de l'exécution d' un rendu 3D - rassemblant des sommets et des textures indexés et diffusant des pixels ombrés dans l'espace de l'écran . La pixellisation des primitives opaques à l'aide d'un tampon de profondeur est "commutative", permettant la réorganisation, ce qui facilite l'exécution parallèle. Dans le cas général, des primitives de synchronisation seraient nécessaires.
Aléatoire
À l'extrême opposé se trouve un modèle d'accès à la mémoire vraiment aléatoire. Quelques systèmes multiprocesseurs sont spécialisés pour y faire face. L' approche PGAS peut aider en triant les opérations par données à la volée (utile lorsque le problème * est * de déterminer la localité de données non triées). Les structures de données qui reposent fortement sur la recherche de pointeurs peuvent souvent produire une mauvaise localisation de référence , bien que le tri puisse parfois aider. Étant donné un modèle d'accès à la mémoire vraiment aléatoire, il peut être possible de le décomposer (y compris les étapes de dispersion ou de regroupement, ou tout autre tri intermédiaire) ce qui peut améliorer la localité dans son ensemble; c'est souvent une condition préalable à la parallélisation .
Approches
Conception orientée données
La conception orientée données est une approche destinée à maximiser la localité de référence, en organisant les données en fonction de la façon dont elles sont traversées à différentes étapes d'un programme, en contraste avec l' approche orientée objet plus courante (c'est-à-dire en organisant de telle sorte que la disposition des données reflète explicitement la modèle d'accès).
Contraste avec la localité de référence
La localité de référence fait référence à une propriété présentée par les modèles d'accès à la mémoire. Un programmeur modifiera le modèle d'accès à la mémoire (en retravaillant les algorithmes) pour améliorer la localité de référence et / ou augmenter le potentiel de parallélisme. Un programmeur ou un concepteur de système peut créer des cadres ou des abstractions (par exemple, des modèles C ++ ou des fonctions d'ordre supérieur ) qui encapsulent un modèle d'accès mémoire spécifique.
Différentes considérations pour les modèles d'accès mémoire apparaissent dans le parallélisme au-delà de la localité de référence, à savoir la séparation des lectures et des écritures. Ex: même si les lectures et écritures sont "parfaitement" locales, il peut être impossible de paralléliser en raison des dépendances ; séparer les lectures et les écritures dans des zones séparées donne un modèle d'accès à la mémoire différent, peut-être initialement sembler pire en termes de localité pure, mais souhaitable pour tirer parti du matériel parallèle moderne.
La localité de référence peut également faire référence à des variables individuelles (par exemple, la capacité d'un compilateur à les mettre en cache dans des registres ), tandis que le terme modèle d'accès à la mémoire ne fait référence qu'aux données conservées dans une mémoire indexable (en particulier la mémoire principale ).
Voir également
- Gather-scatter (adressage vectoriel)
- Localité de référence
- Traitement en parallèle
- Ensemble de travail