Que fait le processeur en attendant une extraction de la mémoire principale

26

En supposant que les requêtes de cache l1 et l2 entraînent un échec, le processeur se bloque-t-il jusqu'à ce que la mémoire principale soit accessible?

J'ai entendu parler de l'idée de passer à un autre fil, si oui, qu'est-ce qui est utilisé pour réveiller le fil bloqué?

102948239408
la source
4
Quelles recherches avez-vous faites? Ce sont certainement des informations disponibles. Je vais laisser la réponse aux experts, mais je ne pense pas qu'un changement de thread soit une chose utile à faire. Généralement, le changement de contexte sur un CPU induira de nombreux accès à la mémoire (et donc, probablement des ratés de cache). Il existe certaines mesures telles que la réorganisation des opérations (en utilisant le pipeline), mais le décrochage ne semble pas avoir d'alternative.
Raphael
@Raphael Je viens principalement de lire des livres d'architecture informatique, ARM System-on-Chip Architecture de Steve Furber, était probablement le plus complet que j'ai lu complètement. Cependant, j'ai commencé à lire Architecture informatique: une approche quantitative. Il décrit les techniques pour éviter le blocage, telles que la commutation de threads, les opérations OOE et les opérations de mémoire hors service, bien qu'il ne donne jamais beaucoup d'informations sur les subtilités des conceptions modernes, car comme la plupart des manuels, elles couvrent des architectures plus anciennes ou donnent de vagues suggestions sur la façon dont ces choses sont mis en œuvre et travailler ensemble.
102948239408
S'étendant sur ma question, les caches semblent avoir de petites latences et être déterministes dans leur réponse, mais en cas de marche dans le pire des tableaux de pages de scénario pour récupérer l'adresse physique, des milliers d'instructions pourraient se terminer, certaines à partir du même thread extrait par ILP. Quelles interactions matérielles se produisent sur le processeur pour décider qu'il peut planifier un autre thread et quelle communication est utilisée pour réveiller ce thread si cela se produit. De plus, si OoOE existe-t-il une technique pour gérer une file d'attente de résultats complète lors du changement de threads?
102948239408
1
Il ne ressort pas clairement de votre question que vous vous intéressez aux détails des processeurs modernes. Non seulement cela est probablement hors sujet, mais il peut également s'agir d'informations exclusives. Avec les concepts, nous pouvons vous aider; celles-ci ont probablement moins changé au cours des décennies que les mises en œuvre. Quant à votre question, veuillez incorporer ce que vous savez et formuler une question spécifique, conceptuelle (ou demande de référence).
Raphael
1
J'ai répondu sur les concepts généraux, mais à en juger par vos commentaires, vous pouvez être après des considérations plus avancées. Cependant, si vous voulez des réponses plus avancées, vous devrez rendre votre question plus spécifique à des architectures particulières et à des types de techniques.
Gilles 'SO- arrête d'être méchant'

Réponses:

28

La latence de la mémoire est l'un des problèmes fondamentaux étudiés dans la recherche en architecture informatique.

Exécution spéculative

L'exécution spéculative avec un problème d'instruction dans le désordre est souvent en mesure de trouver un travail utile à faire pour combler la latence lors d'un accès au cache L1, mais elle manque généralement de travail utile après 10 ou 20 cycles environ. Il y a eu plusieurs tentatives pour augmenter la quantité de travail qui peut être effectué lors d'une absence à longue latence. Une idée était d'essayer de faire des prévisions de valeur (Lipasti, Wilkerson et Shen, (ASPLOS-VII): 138-147, 1996). Cette idée était très à la mode dans les cercles de recherche en architecture universitaire pendant un certain temps, mais ne semble pas fonctionner dans la pratique. Une dernière tentative pour sauver la prédiction de valeur de la poubelle de l'histoire a été l' exécution runahead(Mutlu, Stark, Wilkerson et Patt (HPCA-9): 129, 2003). Dans l'exécution runahead, vous reconnaissez que vos prédictions de valeur vont être erronées, mais exécutez quand même de manière spéculative , puis jetez tout le travail basé sur la prédiction, sur la théorie que vous commencerez au moins quelques préfetches pour ce qui serait autrement le cache L2 manque. Il s'avère que runahead gaspille tellement d'énergie que cela n'en vaut pas la peine.

Une approche finale dans ce sens, qui peut être en train de gagner du terrain dans l'industrie, consiste à créer des tampons de réapprovisionnement extrêmement longs. Les instructions sont exécutées de manière spéculative sur la base de la prédiction de branche, mais aucune prédiction de valeur n'est effectuée. Au lieu de cela, toutes les instructions qui dépendent d'une charge à longue latence manquent de s'asseoir et d'attendre dans le tampon de réorganisation. Mais comme le tampon de réorganisation est si grand, vous pouvez continuer à chercher des instructions si le prédicteur de branche fait un travail décent, vous pourrez parfois trouver du travail utile beaucoup plus tard dans le flux d'instructions. Un article de recherche influent dans ce domaine était Pipelines à débit continu(Srinivasan, Rajwar, Akkary, Gandhi et Upton (ASPLOS-XI): 107-119, 2004). (Malgré le fait que les auteurs sont tous d'Intel, je pense que l'idée a gagné en popularité chez AMD.)

Multi-threading

L'utilisation de plusieurs threads pour la tolérance de latence a une histoire beaucoup plus longue, avec un succès beaucoup plus grand dans l'industrie. Toutes les versions réussies utilisent le support matériel pour le multithreading. La version la plus simple (et la plus réussie) de ceci est ce qui est souvent appelé FGMT ( multi-threading à grain fin ) ou multi-threading entrelacé . Chaque noyau matériel prend en charge plusieurs contextes de threads (un contexte est essentiellement l'état du registre, y compris les registres comme le pointeur d'instruction et tous les registres de drapeaux implicites). Dans un processeur multi-thread à grain fin, chaque thread est traité en-ordre. Le processeur garde une trace des threads qui sont bloqués en cas de manque de charge à longue latence et qui sont prêts pour leur prochaine instruction et il utilise une stratégie de planification FIFO simple à chaque cycle pour choisir le thread prêt à exécuter ce cycle. Un premier exemple de cela à grande échelle était les processeurs HEP de Burton Smith (Burton Smith a ensuite architecté le supercalculateur Tera, qui était également un processeur multi-thread à grain fin). Mais l'idée remonte beaucoup plus loin dans les années 1960, je pense.

FGMT est particulièrement efficace sur les charges de travail en streaming. Tous les GPU modernes (unités de traitement graphique) sont multicœurs où chaque cœur est FGMT, et le concept est également largement utilisé dans d'autres domaines informatiques. Le T1 de Sun était également FMGT multicœur, tout comme le Xeon Phi d'Intel (le processeur qui est souvent encore appelé "MIC" et était autrefois appelé "Larabee").

L'idée du multithreading simultané (Tullsen, Eggers et Levy, (ISCA-22): 392-403, 1995) combine le multi-threading matériel avec une exécution spéculative. Le processeur a plusieurs contextes de threads, mais chaque thread est exécuté de manière spéculative et dans le désordre. Un ordonnanceur plus sophistiqué peut ensuite utiliser diverses heuristiques pour extraire du thread qui est le plus susceptible d'avoir un travail utile ( Malik, Agarwal, Dhar et Frank, (HPCA-14: 50-61), 2008 ). Une certaine grande entreprise de semi-conducteurs a commencé à utiliser le terme hyperthreading pour le multithreading simultané, et ce nom semble être le plus utilisé de nos jours.

Préoccupations microarchitecturales de bas niveau

J'ai réalisé après avoir relu vos commentaires que vous êtes également intéressé par la signalisation qui se passe entre le processeur et la mémoire. Les caches modernes permettent généralement à plusieurs échecs d'être simultanément en suspens. C'est ce qu'on appelle un cache sans verrouillage (Kroft, (ISCA-8): 81-87, 1981). (Mais le document est difficile à trouver en ligne, et quelque peu difficile à lire. Réponse courte: il y a beaucoup de comptabilité mais il suffit de s'en occuper. La structure de comptabilité matérielle est appelée MSHR (Miss Information / Status Holding Register ), qui est le nom que Kroft lui a donné dans son article de 1981.)

Logique errante
la source
Merci réponse vraiment complète, je vais essayer de regarder dans le cache sans verrouillage. Ma question mal formulée cherchait vraiment à confirmer que les processeurs continuaient à charger et à stocker pendant un accès à la mémoire principale et quelles techniques microarchitecturales étaient utilisées pour ce faire.
102948239408
+1, 1. S'agit-il vraiment d'un traitement en baril si la programmation par tourniquet n'est pas utilisée? Wikipedia en fait un synonyme de FGMT. (Je peux accepter d'appliquer le "barrel processor" au round robin avec skipping, bien que cela brise l'analogie car une portée manquante (cf. fil non prêt) ne contracte pas la circonférence d'un baril. (Je pense que les "vrais" processeurs de barils étaient rare - peut-être le processeur périphérique du CDC 6600? - parce qu'il gaspille un cycle, mais cela simplifie le matériel.) 2. Une mention de SoEMT comme Hyperanium Threading d'Itanium et Northstar et al d'IBM semble particulièrement appropriée compte tenu de la question.
Paul A. Clayton
@ 102948239408, une autre chose que vous pourriez rechercher sur Google est des termes comme "hit under miss" et "miss under miss" (l'autre option est "stall under miss", mais je viens de l'essayer et il semble ne rien retourner d'utile.) Ce sont termes qui sont actuellement utilisés par (certains) architectes pour différentes options de ce que le cache pourrait permettre.
Wandering Logic du
@ PaulA.Clayton, la terminologie n'est certainement pas mon fort. Je suis d'accord avec vous que le traitement du baril devrait signifier un tournoi à la ronde. Mais je ne peux penser à aucun autre terme qui signifie: entrelacement cycle par cycle d'un tas de threads dans l'ordre (ce que font tous les GPU, Xeon Phi et Sun T1). Est-ce FGMT? J'ai toujours pensé que FGMT incluait SMT (c'est-à-dire, ne spécifie pas que les threads doivent être exécutés dans l'ordre) mais peut-être que FGMT est meilleur que "barrel processor" dans ce cas?
Wandering Logic
L'article de Wikipedia sur le processeur Barrel déclare: "également connu sous le nom de" multithreading temporel "entrelacé" ou "à grain fin", donc IMT et FGMT sont au moins des termes reconnus. Je pense que j'ai lu "à grain fin" plus que "entrelacé", mais entrelacé n'est pas rare. J'ai généralement utilisé le FG (pour moi, "grainé" implique plus de séparation que SMT ne le prévoit); FG a l'avantage que l'entrelacé pourrait s'appliquer à SoEMT. Je soupçonne que c'est juste un changement d'utilisation du "processeur de baril" que je devrai sourire (et mes dents) et supporter.
Paul A. Clayton
16

La réponse courte est: rien, le processeur cale.

Il n'y a pas tellement de possibilités. Passer à une autre tâche n'est pas vraiment une option pour deux raisons. C'est une opération coûteuse, et puisque la tâche en cours et une autre tâche sont en concurrence pour l'espace dans le cache, le passage à l'autre tâche peut lui-même nécessiter un accès à la mémoire principale, et peut donc revenir à la tâche d'origine. De plus, cela aurait à la participation du système d'exploitation, de sorte que le processeur devrait déclencher une forme d' interruption ou piège - en fait le processeur transfèrerait à un code du noyau.

Pendant que le processeur est bloqué, le minuteur continue de fonctionner, il peut donc y avoir une interruption du minuteur ou une interruption provenant d'autres périphériques. Ainsi, un changement de contexte est plus susceptible de se produire lors d'un accès à la mémoire principale que lors d'un accès au cache, mais uniquement parce que cela prend plus de temps.

Néanmoins, les ordinateurs modernes incluent une variété de techniques pour essayer de réduire le temps perdu par le processeur à attendre la mémoire principale. Le calage se produit, mais seulement lorsqu'il ne peut être évité.

Une technique est la récupération spéculative : le processeur essaie de deviner à quel emplacement de la mémoire sera accessible et le récupère pour le mettre en cache à l'avance. Par exemple, les boucles sur un bloc de mémoire sont courantes, donc si des lignes de cache ont été chargées pour les adresses mémoire 0x12340000, 0x12340010 et 0x12340020, il peut être judicieux de charger la ligne pour 0x12340030. Le compilateur peut vous aider en générant des instructions de prélecture qui sont comme des charges, sauf qu'elles transfèrent uniquement les données de la mémoire principale vers le cache, pas dans un registre de processeur.

Une autre technique est l' exécution spéculative . Le processeur commence à exécuter l'instruction suivante avant que le chargement ne soit effectué. Cela se produit naturellement de toute façon en raison du pipelining des instructions. Seules les instructions qui ne dépendent pas de la valeur chargée peuvent être exécutées de cette façon: le processeur doit effectuer une analyse de dépendance. Pour les instructions conditionnelles (par exemple charger r1; branche si r1 ≠ 0), les processeurs utilisent des heuristiques de prédiction de branche pour deviner quelle sera la valeur. L'exécution spéculative après une charge peut devoir être rembobinée au cas où la charge déclencherait un abandon.

Certaines architectures comme Itanium facilitent l'exécution des instructions dans un ordre commode en permettant le réordonnancement des instructions par défaut: au lieu de se composer d'une séquence d'instructions élémentaires qui sont exécutées sémantiquement les unes après les autres, les programmes se composent de mots d'instructions très longs : une seule instruction comprend de nombreuses opérations qui doivent être exécutées en parallèle par différents composants du processeur.

Le passage à un autre thread se produit dans l' hyperthreading , trouvé sur les processeurs x86 haut de gamme. Il s'agit d'une technique de conception matérielle: chaque cœur de processeur contient deux banques de registres distinctes (chacune correspondant à un contexte de tâche), mais une seule instance d'autres éléments, afin qu'il puisse prendre en charge deux threads d'exécution indépendants, mais n'exécute efficacement les instructions que depuis un à un temps. Pendant qu'un thread est bloqué, l'autre thread continue. Du point de vue du logiciel, il existe deux processeurs indépendants; il se trouve que ces processeurs partagent de nombreux composants sous le capot.

L'échange est un niveau de plus dans la hiérarchie du cache mémoire: la mémoire principale peut être vue comme un cache pour l'espace d'échange. Avec l'échange, les mécanismes et les ratios de performance sont différents. Si une tâche nécessite le chargement de données à partir du swap, l'instruction de chargement déclenche un trap qui exécute le code du noyau pour allouer une page en RAM et charger son contenu à partir du disque. Pendant ce temps, le noyau pourrait bien décider de passer à une autre tâche.

Gilles 'SO- arrête d'être méchant'
la source
Contrairement au premier et à l'avant-dernier paragraphe, l'astuce est qu'aucun changement de contexte réel ne doit se produire avec l'hyperthreading, non? Le CPU gère entièrement deux contextes en même temps.
Raphael
1
@Raphael Right: en ce qui concerne le logiciel, pour tout sauf les performances, il y a deux CPU.
Gilles 'SO- arrête d'être méchant'
Un processeur hyperthreadé possède de nombreuses unités d'exécution semi-indépendantes (additionneurs entiers et à virgule flottante, multiplicateurs, etc.), et je pense que les deux contextes peuvent utiliser simultanément des unités d'exécution distinctes - pas sûr à 100% cependant.
Russell Borogove
@RussellBorogove Oui, je ne l'ai pas mentionné parce que même les CPU non hyperthreadés peuvent avoir plusieurs ALU / FPU /… et inversement des cœurs séparés partagent parfois FPU etc.
Gilles 'SO- arrête d'être mauvais'
5

La réponse à cette question variera selon l'architecture en question. Alors que de nombreux processeurs vont caler (ARM, x86 sans hyperthreading, etc.) car cela prend trop de temps pour changer de threads, ce n'est pas l'approche adoptée par chaque architecture. Dans certaines architectures, chaque thread planifié sur un processeur possède son propre fichier de registre indépendant, de sorte que le processeur peut simplement exécuter le travail à partir d'un thread qui n'attend pas d'accès à la mémoire. Je crois comprendre que c'est, dans une mesure limitée, ce que fait l'hyperthreading x86 (en utilisant seulement 2 threads), mais c'est beaucoup plus courant sur GPGPUarchitectures. Dans le cas particulier de CUDA, au moins des dizaines, voire des centaines, de chaînes de threads sont généralement chargées sur un multiprocesseur donné à un moment donné, chaque thread (des centaines ou des milliers) ayant ses propres registres. Cela permet à l'architecture d'exécuter une instruction à partir d'un autre thread lors du cycle suivant lorsqu'un thread donné émet un accès à la mémoire. Ainsi, tant que suffisamment de threads sont chargés, les cœurs de processeur ne sont jamais inactifs pour les accès à la mémoire. Voir les directives de performances et la hiérarchie de mémoire pour plus d'informations.

reirab
la source