Comment un seul thread s'exécute-t-il sur plusieurs cœurs?

61

J'essaie de comprendre, à un haut niveau, comment les threads simples fonctionnent sur plusieurs cœurs. Ci-dessous ma meilleure compréhension. Je ne crois pas que ce soit correct cependant.

D'après mes lectures sur Hyper-threading , il semble que le système d'exploitation organise les instructions de tous les threads de manière à ce qu'ils ne s'attendent pas les uns les autres. Ensuite, la partie frontale de la CPU organise ces instructions en distribuant un thread à chaque cœur et distribue des instructions indépendantes de chaque thread parmi tous les cycles ouverts.

Donc, s'il n'y a qu'un seul thread, le système d'exploitation ne fera aucune optimisation. Cependant, le processeur frontal distribuera des jeux d'instructions indépendants entre chaque cœur.

Selon https://stackoverflow.com/a/15936270 , un langage de programmation spécifique peut créer plus ou moins de threads, mais ce n'est pas pertinent pour déterminer quoi faire avec ces threads. Le système d’exploitation et le processeur le gèrent, ce qui se produit quel que soit le langage de programmation utilisé.

entrez la description de l'image ici

Juste pour clarifier, je pose une question sur un seul thread exécuté sur plusieurs cœurs, et non sur l'exécution de plusieurs threads sur un seul cœur.

Quel est le problème avec mon résumé? Où et comment les instructions d'un fil sont-elles réparties entre plusieurs cœurs? Le langage de programmation est-il important? Je sais que c'est un sujet vaste. J'espère une compréhension de haut niveau.

Evorlor
la source
6
Un ensemble d'instructions pour un seul thread logiciel peut s'exécuter sur plusieurs cœurs, mais pas en même temps.
Kroltan
1
Vous mélangez des threads logiciels (qui impliquent le planificateur de système d'exploitation) et des threads matériels ou HyperThreading (une fonctionnalité de processeur permettant à un cœur de se comporter comme deux).
Ugoren
2
J'ai 20 chauffeurs et 4 camions. Comment est-il possible qu'un conducteur puisse livrer des colis avec deux camions? Comment est-il possible qu'un camion puisse avoir plusieurs conducteurs? La réponse aux deux questions est la même. À tour de rôle.
Eric Lippert

Réponses:

84

Le système d'exploitation offre des tranches de temps de la CPU aux threads pouvant s'exécuter.

S'il n'y a qu'un seul noyau, le système d'exploitation planifie l'exécution du thread le plus éligible sur ce noyau pour une tranche de temps. À la fin d'une tranche de temps ou lorsque le thread en cours se bloque sur IO ou lorsque le processeur est interrompu par des événements externes, le système d'exploitation réévalue le prochain thread à exécuter (et peut choisir à nouveau le même thread ou un autre).

L’éligibilité à courir consiste en des variations d’équité, de priorité et de disponibilité, et selon cette méthode, différents threads obtiennent des tranches de temps, certaines plus que d’autres.

S'il y a plusieurs cœurs, N, le système d'exploitation programme les N threads les plus éligibles pour s'exécuter sur les cœurs.

L'affinité du processeur est un facteur d'efficacité. Chaque fois qu'un processeur exécute un thread différent du précédent, il a tendance à ralentir un peu car son cache est chaud pour le précédent, mais froid pour le nouveau. Ainsi, exécuter le même thread sur le même processeur sur de nombreuses tranches de temps constitue un avantage en termes d'efficacité.

Toutefois, le système d'exploitation est libre d'offrir des tranches de temps d'un thread sur différents processeurs et il peut effectuer une rotation entre tous les processeurs sur des tranches de temps différentes. Comme @ gnasher729 le dit , il ne peut pas exécuter simultanément un thread sur plusieurs processeurs.

L'hyperthreading est une méthode matérielle par laquelle un seul cœur de processeur amélioré peut prendre en charge l'exécution simultanée de deux ou plusieurs threads différents . (Un tel processeur peut offrir des threads supplémentaires à moindre coût en immobilier réel que des cœurs complets supplémentaires.) active le partage des unités fonctionnelles au sein de cette CPU sans confondre les threads.

L'hyperthreading, bien que techniquement difficile du point de vue matériel, du point de vue du programmeur, le modèle d'exécution est simplement celui de cœurs de processeur supplémentaires, plutôt que de quelque chose de plus complexe. Ainsi, le système d'exploitation voit des cœurs de processeur supplémentaires, bien qu'il y ait de nouveaux problèmes d'affinité de processeur, car plusieurs threads hyperthreaded partagent l'architecture de cache d'un cœur de processeur.


Nous pourrions penser naïvement que deux threads fonctionnant sur un noyau hyperthreadded courent chacun deux fois moins vite que chacun avec son propre noyau complet. Mais ce n'est pas nécessairement le cas, car l'exécution d'un seul thread est pleine de cycles creuses, et une partie d'entre eux peut être utilisée par l'autre thread hyperthreaded. En outre, même pendant les cycles sans temps morts, un thread peut utiliser différentes unités fonctionnelles que l'autre, de sorte qu'une exécution simultanée peut se produire. Le processeur amélioré pour l'hyperthreading peut avoir un peu plus de certaines unités fonctionnelles très utilisées spécialement pour supporter cela.

Erik Eidt
la source
3
"Ainsi, exécuter le même thread sur le même processeur sur de nombreuses tranches de temps constitue un avantage en termes d'efficacité." Ne faudrait-il pas qu'il s'agisse de tranches de temps contiguës ? Sinon, les caches seraient effacés par d'autres threads, non? +1 pour une bonne explication.
jpmc26
2
@Luaan: HT est souvent bon, mais la situation n'est pas aussi simple que vous le décrivez. La bande passante d'émission frontale (4 Ups par horloge sur Intel, 6 sur Ryzen) est répartie de manière égale entre les threads (sauf si l'un d'entre eux est bloqué). Si c'est le goulot d'étranglement, alors comme je l'ai dit, HT ne va pas aider du tout. Il n'est pas rare que Skylake s'en rapproche dans une boucle bien réglée, s'il y a un mélange de charges, d'ALU et de magasins ... Les transistors sont bon marché (et ne peuvent pas tous commuter en même temps car le processeur ferait fondre), les processeurs x86 modernes ont plus de ports d'exécution que le front-end ne peut en alimenter (de nombreuses unités d'exécution étant ...
Peter Cordes
2
... sur plusieurs ports) ... Cela peut sembler un gaspillage, mais souvent une boucle n'utilise qu'un type d'unité d'exécution ALU à la fois. Par conséquent, le fait de dupliquer tout signifie que quel que soit le type de code exécuté, il en existe plusieurs. ports pour ses instructions. Ainsi, la raison que vous avez citée pour bénéficier de HT n’est pas si commune, car la plupart des codes utilisent des charges et / ou des magasins prenant de la bande passante frontale, et ce qui reste n’est souvent pas suffisant pour saturer les unités d’exécution.
Peter Cordes
2
@Luaan: dans les processeurs Intel, les unités d'exécution entière et FP / vector partagent les mêmes ports d' exécution . Par exemple, les unités FP FMA / mul / add sont sur les ports 0/1. Mais le multiplicateur entier est aussi sur le port1, et de simples opérations entières peuvent être exécutées sur l’un des 4 ports d’exécution (diagramme dans ma réponse). Un deuxième thread utilisant la bande passante des problèmes les ralentira tous les deux même s'ils ne se font pas concurrence pour les unités d'exécution, mais il y a souvent un gain de débit net s'ils ne se font pas trop concurrence pour le cache. Même un code à haut débit bien réglé tel que x264 / x265 (encodeurs vidéo) bénéficie d'environ 15% sur Skylake de HT.
Peter Cordes
3
@luaan En plus de ce que Peter a dit, votre affirmation selon laquelle "C'était le raisonnement initial derrière HT" est incorrecte. Le raisonnement à l'origine de HT était que la microarchitecture NetBurst avait tellement prolongé le pipeline (dans le but d'augmenter la vitesse d'horloge) que les prédictions erronées de la branche et les autres bulles de pipeline ont totalement réduit les performances. HT était l'une des solutions d'Intel pour réduire au minimum le temps d'inactivité des unités d'exécution de cette puce coûteuse en raison de bulles dans le pipeline: le code provenant d'autres threads pouvait être inséré et exécuté dans ces trous.
Cody Gray
24

Il n’existe pas de thread unique fonctionnant simultanément sur plusieurs cœurs.

Cela ne signifie toutefois pas que les instructions d'un thread ne peuvent pas être exécutées en parallèle. Il existe des mécanismes appelés traitement des instructions et exécution dans le désordre qui le permettent. Chaque cœur contient de nombreuses ressources redondantes qui ne sont pas utilisées par de simples instructions, de sorte que plusieurs instructions peuvent être exécutées ensemble (tant que le suivant ne dépend pas du résultat précédent). Cependant, cela se produit toujours dans un seul noyau.

L'hyper-threading est une sorte de variante extrême de cette idée, dans laquelle un noyau exécute non seulement les instructions d'un thread en parallèle, mais mélange les instructions de deux threads différents pour optimiser encore davantage l'utilisation des ressources.

Entrées apparentées dans Wikipedia: Pipeline d'instruction , exécution dans le désordre .

Frax
la source
3
Ils ne peuvent pas fonctionner simultanément, mais ils peuvent fonctionner en parallèle? N'est-ce pas la même chose?
Evorlor
10
@Evorlor L'essentiel ici est la différence entre une unité centrale et une unité d'exécution. Un seul thread ne peut être exécuté que sur un seul cœur, mais un processeur peut utiliser l'analyse dynamique pour déterminer quelles instructions exécutées par un cœur ne dépendent pas les unes des autres et les exécuter simultanément sur différentes unités d'exécution. Un noyau peut avoir plusieurs unités d'exécution.
user1937198
3
@Evorlor: un processeur en panne peut trouver et exploiter le parallélisme au niveau des instructions dans le flux d'instructions d'un seul thread. Par exemple, les instructions qui mettent à jour un compteur de boucle sont souvent indépendantes des autres tâches effectuées par une boucle. Ou, dans une a[i] = b[i] + c[i]boucle, chaque itération est indépendante. Ainsi, les charges, les ajouts et les magasins d'itérations différentes peuvent être en vol en même temps. Il doit préserver l’illusion que les instructions exécutées dans l’ordre du programme, mais par exemple, un magasin qui manque dans le cache ne retarde pas le thread (jusqu’à ce qu’il manque d’espace dans le tampon du magasin).
Peter Cordes
3
@ user1937198: La phrase "analyse dynamique" conviendrait mieux à un compilateur JIT. Les processeurs en panne n'analysent pas vraiment ; cela ressemble plus à un algorithme glouton qui exécute toutes les instructions décodées et émises et qui ont leurs entrées prêtes. (La fenêtre de réorganisation hors service est limitée par quelques ressources micro-architecturales, par exemple, Intel Sandybridge a une taille de tampon de réorganisation de 168 uops. Reportez-vous également à la mesure de la taille de ROB à titre expérimental ). Tous mis en œuvre avec des machines d'état matérielles pour gérer 4 UPS par horloge.
Peter Cordes
3
@ Luan ouais, c'était une idée intéressante, mais les compilateurs AOT ne sont toujours pas assez intelligents pour l'exploiter pleinement. En outre, Linus Torvalds (et d’autres) ont fait valoir que le fait de révéler qu’une grande partie des composants internes du pipeline constituait une contrainte majeure pour les conceptions futures. Par exemple, vous ne pouvez pas vraiment augmenter la largeur du pipeline sans changer l'ISA. Ou vous construisez un processeur qui suit les dépendances de la manière habituelle, et peut-être émet deux groupes VLIW en parallèle, mais vous perdez l'avantage de la complexité du processeur d'EPIC tout en conservant les inconvénients (bande passante perdue lorsque le compilateur ne peut pas remplir un mot).
Peter Cordes
22

Récapitulatif: La recherche et l'exploitation du parallélisme ( au niveau instruction) dans un programme mono-thread se fait uniquement de manière matérielle, par le cœur du processeur sur lequel il s'exécute. Et seulement par-dessus une fenêtre de quelques centaines d'instructions, pas de réorganisation à grande échelle.

Les programmes à un seul thread ne tirent aucun avantage des processeurs multicœurs, à la différence que d' autres tâches peuvent s'exécuter sur les autres cœurs au lieu de prendre du temps pour la tâche à un seul thread.


le système d'exploitation organise les instructions de tous les threads de manière à ce qu'ils ne s'attendent pas les uns les autres.

Le système d'exploitation ne regarde pas à l'intérieur des flux d'instructions des threads. Il ne planifie que les threads vers les cœurs.

En réalité, chaque cœur exécute la fonction de planificateur du système d'exploitation lorsqu'il doit déterminer ce qu'il faut faire ensuite. La planification est un algorithme distribué. Pour mieux comprendre les machines multicœurs, imaginez que chaque noyau exécute le noyau séparément. Tout comme un programme multi-thread, le noyau est écrit pour que son code sur un noyau puisse interagir en toute sécurité avec le code sur d'autres cores pour mettre à jour des structures de données partagées (comme la liste des threads prêts à être exécutés).

Quoi qu'il en soit, le système d'exploitation aide les processus multi-threadés à exploiter le parallélisme au niveau des threads, ce qui doit être explicitement exposé en écrivant manuellement un programme multi-thread . (Ou par un compilateur à parallélisation automatique avec OpenMP ou quelque chose).

Ensuite, la partie frontale de la CPU organise ces instructions en distribuant un thread à chaque cœur et distribue des instructions indépendantes de chaque thread parmi tous les cycles ouverts.

Un cœur de processeur n'exécute qu'un flux d'instructions s'il n'est pas arrêté (endormi jusqu'à la prochaine interruption, par exemple une interruption du minuteur). C'est souvent un thread, mais il peut également s'agir d'un gestionnaire d'interruption du noyau ou de divers codes de noyau si le noyau décide de faire autre chose que de simplement revenir au thread précédent après le traitement et l'interruption ou l'appel système.

Avec HyperThreading ou d'autres conceptions SMT, un cœur de processeur physique agit comme plusieurs cœurs "logiques". La seule différence d'un point de vue de système d'exploitation entre un processeur quadricœur avec hyperthreading (4c8t) et une machine ordinaire à 8 cœurs (8c8t) est qu'un système d'exploitation compatible HT essaye de programmer les threads pour séparer les cœurs physiques afin de ne pas t rivaliser les uns avec les autres. Un système d'exploitation qui ne connaissait pas l'hyperthreading ne verrait que 8 cœurs (sauf si vous désactivez HT dans le BIOS, il n'en détectera que 4).


Le terme " front-end" fait référence à la partie d'un cœur de processeur qui récupère le code machine, décode les instructions et les émet dans la partie en panne du cœur . Chaque noyau a son propre front-end et fait partie du noyau dans son ensemble. Les instructions qu'il récupère correspondent à ce que le processeur exécute actuellement.

À l'intérieur de la partie hors service du noyau, des instructions (ou uops) sont envoyées aux ports d'exécution lorsque leurs opérandes d'entrée sont prêtes et qu'il existe un port d'exécution libre. Cela ne doit pas nécessairement se produire dans l'ordre des programmes. C'est ainsi qu'un processeur OOO peut exploiter le parallélisme au niveau des instructions au sein d'un seul thread .

Si vous remplacez "noyau" par "unité d'exécution" dans votre idée, vous êtes sur le point de corriger. Oui, la CPU distribue des instructions / unités indépendantes aux unités d'exécution en parallèle. (Mais il y a une confusion dans la terminologie, puisque vous avez dit "front-end" alors que c'est en réalité le programmateur d'instructions du processeur, appelé Reservation Station, qui sélectionne les instructions prêtes à être exécutées).

Une exécution dans le désordre ne peut trouver ILP qu’à un niveau très local, jusqu’à quelques centaines d’instructions, et non entre deux boucles indépendantes (à moins qu’elles ne soient courtes).


Par exemple, l’équivalent asm de cette

int i=0,j=0;
do {
    i++;
    j++;
} while(42);

fonctionnera à peu près aussi vite que la même boucle, incrémentant d’un seul compteur sur Intel Haswell. i++dépend uniquement de la valeur précédente de i, alors que j++ne dépend que de la valeur précédente de j, de sorte que les deux chaînes de dépendance puissent s'exécuter en parallèle sans rompre l'illusion que tout soit exécuté dans l'ordre du programme.

Sur x86, la boucle ressemblerait à ceci:

top_of_loop:
    inc eax
    inc edx
    jmp .loop

Haswell dispose de 4 ports d’exécution entiers, et chacun d’eux est additionné, de sorte qu’il peut supporter un débit allant jusqu’à 4 incinstructions par horloge s’ils sont tous indépendants. (Avec une latence = 1, il vous suffit donc de 4 registres pour maximiser le débit en conservant 4 incinstructions en vol. Contrastez ceci avec le vecteur-FP MUL ou FMA: latence = 5 débits = 0.5 nécessite 10 accumulateurs vectoriels pour garder 10 FMA en vol. maximum, et chaque vecteur peut être 256b, contenant 8 flotteurs simple précision).

La branche prise est également un goulet d'étranglement: une boucle prend toujours au moins une horloge complète par itération, car le débit de la branche prise est limité à 1 par horloge. Je pourrais insérer une instruction supplémentaire dans la boucle sans réduire les performances, sauf si elle lit / écrit également eaxou, edxdans ce cas, cela allongerait la chaîne de dépendance. Le fait de placer 2 instructions supplémentaires dans la boucle (ou une instruction complexe comportant plusieurs étapes) créerait un goulot d'étranglement au niveau du front-end, car il ne peut émettre que 4 uops par horloge dans le cœur en panne. (Voir ce SO Q & A pour des détails sur ce qui se passe pour les boucles qui ne sont pas un multiple de 4 uops: le tampon de boucle et le cache uop rendent les choses intéressantes.)


Dans des cas plus complexes, trouver le parallélisme nécessite de regarder une fenêtre d'instructions plus grande . (par exemple, il existe peut-être une séquence de 10 instructions qui dépendent toutes les unes des autres, puis de quelques instructions indépendantes).

La capacité de la mémoire tampon de réapprovisionnement est l’un des facteurs limitant la taille de la fenêtre hors d’ordre. Sur Intel Haswell, c'est 192 oups. (Et vous pouvez même le mesurer expérimentalement , ainsi que la capacité de changement de nom de registre (taille du fichier de registre).) Les cœurs de processeur à faible consommation, tels que ARM, ont des tailles de ROB beaucoup plus petites, si elles exécutent du tout dans le désordre.

Notez également que les processeurs doivent être en pipeline, mais également en panne. Il doit donc extraire et décoder les instructions bien avant celles qui sont exécutées, de préférence avec un débit suffisant pour remplir les tampons après avoir manqué les cycles d'extraction. Les succursales sont délicates, car nous ne savons même pas où aller chercher si nous ne savons pas comment une succursale est allée. C'est pourquoi la prédiction de branche est si importante. (Et pourquoi les processeurs modernes ont recours à une exécution spéculative: ils déterminent le sens dans lequel une branche ira et commenceront à extraire / décoder / exécuter ce flux d'instructions. Lorsqu'une erreur de prévision est détectée, ils reviennent au dernier état connu et s'exécutent à partir de là.)

Si vous souhaitez en savoir plus sur les composants internes du processeur, vous trouverez des liens dans le wiki des balises Stackoverflow x86 , y compris vers le guide microarch d'Agner Fog et vers les écritures détaillées de David Kanter avec des diagrammes de processeurs Intel et AMD. D'après sa description de la microarchitecture d'Intel Haswell , il s'agit du diagramme final de l'ensemble du pipeline d'un noyau Haswell (et non de la puce entière).

Ceci est un schéma fonctionnel d'un seul cœur de processeur . Une CPU quad-core en a 4 sur une puce, chacune avec ses propres caches L1 / L2 (partage d'un cache L3, de contrôleurs de mémoire et de connexions PCIe avec les périphériques système).

Haswell plein pipeline

Je sais que c'est extrêmement compliqué. L'article de Kanter montre également certaines parties de cette discussion pour parler de l'interface séparément des unités d'exécution ou des caches, par exemple.

Peter Cordes
la source
2
"La recherche et l’exploitation du parallélisme (au niveau instruction) dans un programme mono-thread se fait uniquement dans du matériel" Notez que cela ne s’applique qu’aux ISA classiques, pas aux VLIW dans lesquels ILP est entièrement déterminé par le compilateur ou le programmeur, ou de manière coopérative entre matériels et logiciel.
Hadi Brais
1
@ user7813604: oui. L'hyperthreading ne peut pas paralléliser un seul thread. C'est l'inverse: il exécute plusieurs threads sur un même cœur, ce qui réduit les performances par thread mais augmente le débit global.
Peter Cordes
1
@ user7813604: Le but de ILP est de trouver quelles instructions peuvent être exécutées en parallèle tout en maintenant l' illusion que chaque instruction a été exécutée dans l'ordre, chacune se terminant avant le début de la suivante. Un processeur en pipeline scalaire peut avoir besoin de caler parfois des dépendances si la latence est supérieure à 1. Mais c'est un problème encore plus important pour les processeurs superscalaires.
Peter Cordes
1
@ user7813604: oui, ma réponse utilise littéralement cela à titre d'exemple. Haswell, par exemple, peut exécuter jusqu'à 4 incinstructions dans le même cycle d'horloge, sur ses 4 unités d'exécution ALU entières.
Peter Cordes
1
@ user7813604: Oui, ILP correspond au montant pouvant être exécuté en parallèle. Un processeur réel aura une capacité limitée à trouver et à exploiter ILP en l’exécutant en parallèle au sein d’un même cœur, par exemple jusqu’à superscalar jusqu’à 4 en largeur dans Intel. Cette réponse tente d'expliquer cela avec des exemples.
Peter Cordes