Wie läuft ein einzelner Thread auf mehreren Kernen?

Ich versuche auf hoher Ebene zu verstehen, wie einzelne Threads über mehrere Kerne laufen. Unten ist mein bestes Verständnis. Ich glaube jedoch nicht, dass es richtig ist.

Basierend auf meiner Lektüre von Hyper-Threading scheint das Betriebssystem die Anweisungen aller Threads so zu organisieren, dass sie nicht aufeinander warten. Dann organisiert das Front-End der CPU diese Anweisungen weiter, indem es einen Thread auf jeden Kern verteilt und unabhängige Anweisungen von jedem Thread auf alle offenen Zyklen verteilt.

Wenn es also nur einen einzigen Thread gibt, führt das Betriebssystem keine Optimierung durch. Das Front-End der CPU verteilt jedoch unabhängige Befehlssätze auf jeden Kern.

Laut https://stackoverflow.com/a/15936270 kann eine bestimmte Programmiersprache mehr oder weniger Threads erstellen, dies ist jedoch für die Entscheidung, was mit diesen Threads geschehen soll, unerheblich. Das Betriebssystem und die CPU übernehmen dies, und dies geschieht unabhängig von der verwendeten Programmiersprache.

Um dies zu verdeutlichen, frage ich nach einem einzelnen Thread, der auf mehreren Kernen ausgeführt wird, und nicht nach dem Ausführen mehrerer Threads auf einem einzelnen Kern.

Was stimmt mit meiner Zusammenfassung nicht? Wo und wie werden die Anweisungen eines Threads auf mehrere Kerne aufgeteilt? Ist die Programmiersprache wichtig? Ich weiß, dass dies ein breites Thema ist. Ich hoffe auf ein umfassendes Verständnis davon.

Das Betriebssystem bietet Threads, die zur Ausführung berechtigt sind, Zeitscheiben für die CPU an.

Wenn es nur einen Kern gibt, plant das Betriebssystem, dass der am besten geeignete Thread für eine bestimmte Zeitspanne auf diesem Kern ausgeführt wird. Nach Ablauf einer Zeitscheibe oder wenn der laufende Thread auf E / A blockiert oder wenn der Prozessor durch externe Ereignisse unterbrochen wird, überprüft das Betriebssystem erneut, welcher Thread als nächstes ausgeführt werden soll (und es kann auch wieder denselben oder einen anderen Thread auswählen).

Die Berechtigung zum Ausführen besteht aus Variationen in Bezug auf Fairness, Priorität und Bereitschaft, und durch diese Methode erhalten verschiedene Threads Zeitscheiben, einige mehr als andere.

Wenn mehrere Kerne vorhanden sind (N), plant das Betriebssystem, dass die am besten geeigneten N Threads auf den Kernen ausgeführt werden.

Prozessoraffinität ist eine Überlegung zur Effizienz. Jedes Mal, wenn eine CPU einen anderen Thread ausführt als zuvor, verlangsamt sie sich etwas, da der Cache für den vorherigen Thread warm, für den neuen jedoch kalt ist. Das Ausführen desselben Threads auf demselben Prozessor über mehrere Zeitscheiben ist daher ein Effizienzvorteil.

Es steht dem Betriebssystem jedoch frei, Zeitscheiben für einen Thread auf verschiedenen CPUs anzubieten, und es könnte sich auf verschiedenen Zeitscheiben durch alle CPUs drehen. Es kann jedoch nicht, wie @ gnasher729 sagt , einen Thread auf mehreren CPUs gleichzeitig ausführen.

Hyperthreading ist eine Hardwaremethode, mit der ein einzelner erweiterter CPU-Kern die Ausführung von zwei oder mehr verschiedenen Threads gleichzeitig unterstützen kann. (Eine solche CPU kann zusätzliche Threads zu geringeren Kosten in Silizium-Immobilien als zusätzliche Voll-Cores anbieten.) Dieser erweiterte CPU-Core muss einen zusätzlichen Status für die anderen Threads unterstützen, wie z. B. CPU-Registerwerte, und hat auch einen Koordinationsstatus und ein entsprechendes Verhalten Ermöglicht die gemeinsame Nutzung von Funktionseinheiten innerhalb dieser CPU, ohne die Threads zusammenzuführen.

Hyperthreading ist zwar aus Hardware-Sicht eine technische Herausforderung, aus Sicht des Programmierers ist das Ausführungsmodell jedoch eher das von zusätzlichen CPU-Kernen als von etwas Komplexerem. Daher sieht das Betriebssystem zusätzliche CPU-Kerne, obwohl es einige neue Probleme mit der Prozessoraffinität gibt, da mehrere Hyperthread-Threads die Cache-Architektur eines CPU-Kerns gemeinsam nutzen.

Wir könnten naiv annehmen, dass zwei Threads, die auf einem Hyperthread-Core ausgeführt werden, jeweils halb so schnell laufen, wie sie es mit ihrem eigenen vollständigen Core tun würden. Dies ist jedoch nicht unbedingt der Fall, da die Ausführung eines einzelnen Threads mit Pufferzyklen voll ist und ein Teil davon vom anderen Thread mit Hyperthreading verwendet werden kann. Selbst während nicht lockerer Zyklen kann ein Thread andere Funktionseinheiten als der andere verwenden, so dass eine gleichzeitige Ausführung erfolgen kann. Die erweiterte CPU für Hyperthreading verfügt möglicherweise über einige weitere häufig verwendete Funktionseinheiten, um dies zu unterstützen.

Es gibt keinen einzigen Thread, der gleichzeitig auf mehreren Kernen ausgeführt wird.

Dies bedeutet jedoch nicht, dass Anweisungen von einem Thread nicht parallel ausgeführt werden können. Es gibt Mechanismen, die als Anweisungs-Pipelining und Out-of-Order-Ausführung bezeichnet werden und dies ermöglichen. Jeder Kern verfügt über eine Menge redundanter Ressourcen, die nicht von einfachen Befehlen verwendet werden, sodass mehrere solcher Befehle zusammen ausgeführt werden können (solange der nächste nicht vom vorherigen Ergebnis abhängt). Dies geschieht jedoch immer noch in einem einzelnen Kern.

Hyper-Threading ist eine extreme Variante dieser Idee, bei der ein Kern nicht nur Befehle von einem Thread parallel ausführt, sondern Befehle von zwei verschiedenen Threads mischt, um die Ressourcennutzung noch weiter zu optimieren.

Verwandte Wikipedia-Einträge: Instruction Pipelining , Out-of-Order-Ausführung .

Zusammenfassung: Das Auffinden und Ausnutzen der (Befehls-) Parallelität in einem Single-Threaded-Programm erfolgt rein hardwaremäßig durch den CPU-Kern, auf dem es ausgeführt wird. Und nur über ein Fenster von ein paar hundert Anweisungen, keine groß angelegte Nachbestellung.

Single-Threaded-Programme profitieren nicht von Multi-Core-CPUs, außer dass andere Dinge auf den anderen Kernen ausgeführt werden können, anstatt Zeit für die Single-Threaded-Aufgabe zu verlieren.

Das Betriebssystem organisiert die Anweisungen aller Threads so, dass sie nicht aufeinander warten.

Das Betriebssystem schaut NICHT in die Befehlsströme von Threads. Es werden nur Threads für Kerne geplant.

Tatsächlich führt jeder Kern die Scheduler-Funktion des Betriebssystems aus, wenn er herausfinden muss, was als Nächstes zu tun ist. Scheduling ist ein verteilter Algorithmus. Stellen Sie sich zum besseren Verständnis von Mehrkern-Rechnern vor, dass jeder Kern den Kernel separat ausführt. Genau wie ein Multithread-Programm ist der Kernel so geschrieben, dass sein Code auf einem Kern sicher mit seinem Code auf anderen Kernen interagieren kann, um gemeinsam genutzte Datenstrukturen zu aktualisieren (wie die Liste der ausführbaren Threads).

Auf jeden Fall hilft das Betriebssystem Multithread-Prozessen dabei, die Parallelität auf Thread-Ebene auszunutzen, die durch manuelles Schreiben eines Multithread-Programms explizit verfügbar gemacht werden muss . (Oder durch einen automatisch parallelisierenden Compiler mit OpenMP oder so).

Dann organisiert das Front-End der CPU diese Anweisungen weiter, indem es einen Thread auf jeden Kern verteilt und unabhängige Anweisungen von jedem Thread auf alle offenen Zyklen verteilt.

Ein CPU-Kern führt nur einen Befehlsstrom aus, wenn er nicht angehalten wird (schläft bis zum nächsten Interrupt, z. B. Timer-Interrupt). Oft ist das ein Thread, aber es kann auch ein Kernel-Interrupt-Handler oder ein anderer Kernel-Code sein, wenn der Kernel sich dazu entschlossen hat, etwas anderes zu tun, als nach der Behandlung und dem Interrupt oder Systemaufruf nur zum vorherigen Thread zurückzukehren.

Bei HyperThreading oder anderen SMT-Designs verhält sich ein physischer CPU-Kern wie mehrere "logische" Kerne. Aus Sicht des Betriebssystems besteht der einzige Unterschied zwischen einer Quad-Core-mit-Hyperthreading (4c8t) -CPU und einer einfachen 8-Core-Maschine (8c8t) darin, dass ein HT-fähiges Betriebssystem versucht, Threads so zu planen, dass sie physische Kerne trennen, damit sie nicht " nicht miteinander konkurrieren. Ein Betriebssystem, das sich mit Hyperthreading nicht auskannte, konnte nur 8 Kerne erkennen (sofern Sie HT nicht im BIOS deaktivieren, würde es nur 4 erkennen).

Der Begriff " Front-End" bezieht sich auf den Teil eines CPU-Kerns, der Maschinencode abruft, die Anweisungen decodiert und sie in den Teil des Kerns außerhalb der Reihenfolge ausgibt . Jeder Kern hat ein eigenes Front-End und ist Teil des gesamten Kerns. Anweisungen, die er abruft, sind das, was die CPU gerade ausführt.

Innerhalb des nicht in der richtigen Reihenfolge befindlichen Teils des Kerns werden Anweisungen (oder Uops) an Ausführungsports gesendet, wenn ihre Eingabeoperanden bereit sind und es einen freien Ausführungsport gibt. Dies muss nicht in der Programmreihenfolge geschehen. Auf diese Weise kann eine OOO-CPU die Parallelität auf Befehlsebene innerhalb eines einzelnen Threads ausnutzen .

Wenn Sie in Ihrer Idee "core" durch "execution unit" ersetzen, sind Sie fast richtig. Ja, die CPU verteilt parallel unabhängige Befehle / Ups an Ausführungseinheiten. (Aber es gibt eine Terminologie-Verwechslung, da Sie "Front-End" gesagt haben, wenn es wirklich der Befehlsplaner der CPU, auch Reservation Station genannt, ist, der Befehle auswählt, die zur Ausführung bereit sind).

Bei der Ausführung außerhalb der Reihenfolge wird ILP nur auf sehr lokaler Ebene gefunden, nur bis zu ein paar hundert Anweisungen, nicht zwischen zwei unabhängigen Schleifen (sofern diese nicht kurz sind).

Zum Beispiel das asm-Äquivalent dazu

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

läuft ungefähr so ​​schnell wie die gleiche Schleife und erhöht nur einen Zähler auf Intel Haswell. i++hängt nur vom vorherigen Wert von ab i, während j++nur vom vorherigen Wert von abhängt j, sodass die beiden Abhängigkeitsketten parallel ausgeführt werden können, ohne die Illusion zu unterbrechen , dass alles in der Programmreihenfolge ausgeführt wird.

Auf x86 würde die Schleife ungefähr so ​​aussehen:

top_of_loop:
    inc eax
    inc edx
    jmp .loop

Haswell verfügt über 4 ganzzahlige Ausführungsports und alle haben Addierereinheiten, sodass ein Durchsatz von bis zu 4 incBefehlen pro Takt möglich ist, wenn alle unabhängig sind. (Bei Latenz = 1 benötigen Sie nur 4 Register, um den Durchsatz zu maximieren, indem Sie 4 incAnweisungen im Flug halten. Vergleichen Sie dies mit Vektor-FP-MUL oder FMA: Bei Latenz = 5 Durchsatz = 0,5 sind 10 Vektorspeicher erforderlich, um 10 FMAs im Flug zu halten Um den Durchsatz zu maximieren, kann jeder Vektor 256 b groß sein und 8 Gleitkommazahlen mit einfacher Genauigkeit enthalten.

Der genommene Zweig ist auch ein Engpass: Eine Schleife benötigt immer mindestens einen ganzen Takt pro Iteration, da der Durchsatz des genommenen Zweigs auf 1 pro Takt begrenzt ist. Ich könnte eine weitere Anweisung in die Schleife einfügen, ohne die Leistung zu verringern, es sei denn, sie liest / schreibt ebenfalls eaxoder würde edxin diesem Fall die Abhängigkeitskette verlängern. Das Einfügen von zwei weiteren Befehlen in die Schleife (oder eines komplexen Multi-UOP-Befehls) würde zu einem Engpass am Front-End führen, da nur vier UOPs pro Takt in den Kern außerhalb der Reihenfolge ausgegeben werden können. (In diesen SO-Fragen und Antworten finden Sie einige Details dazu, was bei Schleifen passiert, die kein Vielfaches von 4 Uops sind: Der Schleifenpuffer und der Uop-Cache machen die Dinge interessant.)

In komplexeren Fällen muss zum Ermitteln der Parallelität ein größeres Fenster mit Anweisungen angezeigt werden . (zB gibt es eine Folge von 10 Anweisungen, die alle voneinander abhängen, dann einige unabhängige).

Die Kapazität des Nachbestellungspuffers ist einer der Faktoren, die die Fenstergröße außerhalb der Reihenfolge begrenzen. Bei Intel Haswell sind es 192 Uops. (Und Sie können es sogar experimentell messen , zusammen mit der Kapazität zum Umbenennen von Registern (Größe der Registerdatei).) CPU-Kerne mit geringem Stromverbrauch wie ARM haben viel kleinere ROB-Größen, wenn sie überhaupt nicht in der richtigen Reihenfolge ausgeführt werden.

Beachten Sie auch, dass CPUs sowohl in Pipelines als auch außer Betrieb sein müssen. Es muss also Anweisungen weit vor der Ausführung abrufen und dekodieren, vorzugsweise mit genügend Durchsatz, um die Puffer nach dem Fehlen von Abrufzyklen aufzufüllen. Zweige sind schwierig, weil wir nicht einmal wissen, wohin wir sie holen sollen, wenn wir nicht wissen, in welche Richtung ein Zweig gegangen ist. Aus diesem Grund ist die Verzweigungsvorhersage so wichtig. (Und warum moderne CPUs spekulative Ausführung verwenden: Sie raten, in welche Richtung ein Zweig gehen wird, und beginnen mit dem Abrufen / Dekodieren / Ausführen dieses Befehlsstroms. Wenn eine falsche Vorhersage erkannt wird, kehren sie zum letzten bekannten Zustand zurück und werden von dort ausgeführt.)

Wenn Sie mehr über CPU-Interna erfahren möchten, finden Sie im Stackoverflow x86-Tag-Wiki einige Links , einschließlich des Microarch-Handbuchs von Agner Fog und detaillierter Beschreibungen von David Kanter mit Diagrammen von Intel- und AMD-CPUs. Nach seiner Beschreibung der Intel Haswell-Mikroarchitektur ist dies das endgültige Diagramm der gesamten Pipeline eines Haswell-Kerns (nicht des gesamten Chips).

Dies ist ein Blockdiagramm eines einzelnen CPU-Kerns . Bei einer Quad-Core-CPU befinden sich 4 davon auf einem Chip, von denen jeder über einen eigenen L1 / L2-Cache verfügt (gemeinsam genutzter L3-Cache, Speichercontroller und PCIe-Verbindungen zu den Systemgeräten).

Ich weiß, das ist überwältigend kompliziert. In Kanters Artikel werden auch Teile davon gezeigt, um beispielsweise getrennt von den Ausführungseinheiten oder den Caches über das Frontend zu sprechen.