Was macht der Prozessor, während er auf einen Hauptspeicherabruf wartet?

26

Unter der Annahme, dass die Cache-Anforderungen l1 und l2 zu einem Fehler führen, bleibt der Prozessor stehen, bis auf den Hauptspeicher zugegriffen wurde?

Ich habe von der Idee gehört, zu einem anderen Thread zu wechseln. Wenn ja, womit wird der blockierte Thread aufgeweckt?

102948239408
quelle
4
Welche Nachforschungen haben Sie angestellt? Dies ist sicherlich Informationen, die verfügbar sind. Ich überlasse die Beantwortung den Experten, halte aber einen Threadwechsel nicht für sinnvoll. Im Allgemeinen führt das Wechseln des Kontexts auf einer CPU zu vielen Speicherzugriffen (und daher wahrscheinlich zu Cache-Fehlern). Es gibt einige Maßnahmen wie die Neuordnung des Betriebs (Nutzung der Pipeline), aber das Abwürgen scheint keine Alternative zu haben.
Raphael
@Raphael Ich habe gerade hauptsächlich Bücher über Computerarchitektur gelesen. ARM System-on-Chip-Architektur von Steve Furber war wahrscheinlich die umfassendste, die ich vollständig gelesen habe. Ich habe jedoch angefangen, Computerarchitektur zu lesen: Ein quantitativer Ansatz. Es werden Techniken besprochen, die ein Abwürgen verhindern sollen, wie z. B. Threadwechsel, OOE und Speicheroperationen ohne ordnungsgemäßen Betrieb. Es wird jedoch nie viel über die Feinheiten moderner Designs gesagt, da sie, wie die meisten Lehrbücher, entweder ältere Architekturen abdecken oder vage Vorschläge dazu machen, wie diese Dinge aussehen umgesetzt und zusammenarbeiten.
102948239408
Wenn ich meine Frage erweitere, scheinen die Caches eine geringere Latenz zu haben und eine deterministische Antwort zu haben. Im Fall einer Seitentabelle für den schlimmsten Fall, in der die physische Adresse abgerufen wird, könnten Tausende von Anweisungen ausgeführt werden, einige aus demselben Thread, der von ILP extrahiert wurde. Welche Hardware-Interaktionen treten auf dem Prozessor auf, um zu entscheiden, ob er einen anderen Thread plant, und welche Kommunikation wird verwendet, um diesen Thread in diesem Fall zu aktivieren. Gibt es noch eine Technik, um mit einer vollen Ergebniswarteschlange umzugehen, wenn Threads gewechselt werden?
102948239408
1
Aus Ihrer Frage geht nicht hervor, dass Sie sich für Einzelheiten moderner CPUs interessieren. Das ist nicht nur wahrscheinlich offtopisch, es könnte auch proprietäre Informationen sein. Mit den Konzepten können wir Ihnen helfen; Diese haben sich im Laufe der Jahrzehnte wahrscheinlich weniger verändert als die Implementierungen. Geben Sie für Ihre Frage an, was Sie wissen, und formulieren Sie eine bestimmte konzeptionelle Frage (oder Referenzanfrage).
Raphael
1
Ich habe über die allgemeinen Konzepte geantwortet, aber nach Ihren Kommentaren zu urteilen, können Sie nach weitergehenden Überlegungen sein. Wenn Sie jedoch erweiterte Antworten wünschen, müssen Sie Ihre Frage spezifischer auf bestimmte Architekturen und Arten von Techniken ausrichten.
Gilles 'SO - hör auf böse zu sein'

Antworten:

28

Die Speicherlatenz ist eines der grundlegenden Probleme, die in der Computerarchitekturforschung untersucht werden.

Spekulative Ausführung

Bei der spekulativen Ausführung mit Instruction Issue Out-of-Order wird häufig nützliche Arbeit gefunden, um die Latenz während eines L1-Cache-Treffers auszufüllen. In der Regel geht jedoch nach 10 oder 20 Zyklen die nützliche Arbeit aus. Es wurden mehrere Versuche unternommen, um den Arbeitsaufwand zu erhöhen, der während eines Fehlschlags mit langer Latenzzeit ausgeführt werden kann. Eine Idee war , zu versuchen zu tun Wert Vorhersage (Lipasti, Wilkerson und Shen, (ASPLOS-VII): 138-147, 1996). Diese Idee war in akademischen Architekturforschungskreisen für eine Weile sehr in Mode, scheint aber in der Praxis nicht zu funktionieren. Ein letzter Versuch, die Wertvorhersage aus dem Mülleimer der Geschichte zu retten, war die Runahead-Ausführung(Mutlu, Stark, Wilkerson und Patt (HPCA-9): 129, 2003). In runahead Ausführung erkennen Sie , dass Ihr Wert Prognosen falsch sein werden, aber spekulativ ausführen sowieso und dann die ganze Arbeit werfen basierend auf der Vorhersage, auf der Theorie , dass Sie zumindest werden einige der Prefetch für starten , was sonst L2 - Cache vermisst. Es stellt sich heraus, dass Runahead so viel Energie verschwendet, dass es sich einfach nicht lohnt.

Ein letzter Ansatz in diesem Sinne, der in der Industrie möglicherweise Anklang findet, besteht darin, enorm lange Puffer für die Neuordnung zu erstellen. Anweisungen werden spekulativ auf der Grundlage einer Verzweigungsvorhersage ausgeführt, es wird jedoch keine Wertvorhersage durchgeführt. Stattdessen sitzen und warten alle Anweisungen, die von einer Last mit langer Latenz abhängig sind, im Neuordnungspuffer. Da der Neuordnungspuffer jedoch so groß ist, dass Sie weiterhin Anweisungen abrufen können, wenn die Verzweigungsvorhersage einen anständigen Job ausführt, werden Sie manchmal viel später nützliche Arbeit im Anweisungsdatenstrom finden. Ein einflussreiches Forschungspapier in diesem Bereich war Continuous Flow Pipelines(Srinivasan, Rajwar, Akkary, Gandhi und Upton (ASPLOS-XI): 107-119, 2004). (Trotz der Tatsache, dass die Autoren alle von Intel sind, glaube ich, dass die Idee bei AMD mehr Anklang gefunden hat.)

Multithreading

Die Verwendung mehrerer Threads für die Latenztoleranz hat eine viel längere Tradition und ist in der Industrie viel erfolgreicher. Alle erfolgreichen Versionen verwenden Hardware-Unterstützung für Multithreading. Die einfachste (und erfolgreichste) Version davon wird oft als FGMT ( Fine Grained Multi-Threading ) oder Interleaved Multi-Threading bezeichnet . Jeder Hardwarekern unterstützt mehrere Thread-Kontexte (ein Kontext ist im Wesentlichen der Registerzustand, einschließlich der Register wie der Befehlszeiger und aller impliziten Merkerregister). In einem feinkörnigen Prozessor Multithreading jeder Thread verarbeitet wird in-bestellen. Der Prozessor verfolgt, welche Threads bei einem Load-Miss mit langer Latenzzeit angehalten werden und welche für ihre nächste Anweisung bereit sind, und verwendet eine einfache FIFO-Planungsstrategie für jeden Zyklus, um auszuwählen, welcher Ready-Thread diesen Zyklus ausführen soll. Ein frühes Beispiel dafür in großem Maßstab waren die HEP-Prozessoren von Burton Smith (Burton Smith entwarf den Tera-Supercomputer, der auch ein feinkörniger Multi-Threading-Prozessor war). Aber die Idee geht viel weiter zurück, bis in die 1960er Jahre, denke ich.

FGMT ist besonders effektiv beim Streamen von Workloads. Alle modernen GPUs (Grafikprozessoren) sind Multicore-Grafikprozessoren, bei denen jeder Kern FGMT ist, und das Konzept ist auch in anderen Computerbereichen weit verbreitet. Suns T1 war ebenfalls Multicore-FMGT, ebenso wie Intels Xeon Phi (der Prozessor, der oft noch als "MIC" und früher als "Larabee" bezeichnet wurde).

Die Idee des simultanen Multithreading (Tullsen, Eggers und Levy, (ISCA-22): 392-403, 1995) kombiniert Hardware-Multithreading mit spekulativer Ausführung. Der Prozessor hat mehrere Thread-Kontexte, aber jeder Thread wird spekulativ und nicht in der richtigen Reihenfolge ausgeführt. Ein ausgefeilterer Scheduler kann dann verschiedene Heuristiken verwenden, um aus dem Thread abzurufen, für den die wahrscheinlichste nützliche Arbeit vorliegt ( Malik, Agarwal, Dhar und Frank, (HPCA-14: 50-61), 2008 ). Ein gewisses großes Halbleiterunternehmen hat angefangen, den Begriff Hyperthreading für simultanes Multithreading zu verwenden, und dieser Name scheint heutzutage der am häufigsten verwendete zu sein.

Bedenken hinsichtlich der Mikroarchitektur auf niedriger Ebene

Nachdem ich Ihre Kommentare noch einmal gelesen hatte, wurde mir klar, dass Sie auch an der Signalisierung zwischen Prozessor und Speicher interessiert sind. Moderne Caches ermöglichen es normalerweise, dass mehrere Fehler gleichzeitig ausstehen. Dies wird als sperrfreier Cache bezeichnet (Kroft, (ISCA-8): 81-87, 1981). (Aber das Papier ist online schwer zu finden und etwas schwer zu lesen. Kurze Antwort: Es gibt viel Buchhaltung, aber Sie beschäftigen sich nur damit. Die Hardware-Buchhaltungsstruktur wird als MSHR (Miss Information / Status Holding Register) bezeichnet ), wie Kroft es 1981 in seiner Arbeit nannte.)

Wandering Logic
quelle
Dank wirklich umfassender Antwort werde ich versuchen, in den sperrfreien Cache zu schauen. Meine schlecht formulierte Frage wollte wirklich bestätigen, dass Prozessoren während eines Hauptspeicherzugriffs weiterhin geladen und gespeichert wurden und welche Mikroarchitekturtechniken verwendet wurden, um dies zu tun.
102948239408
+1, 1. Ist es wirklich Fassverarbeitung, wenn Round-Robin-Scheduling nicht verwendet wird? Wikipedia macht es zu einem Synonym für FGMT. (Ich kann akzeptieren, dass "Fass-Prozessor" auf Round-Robin mit Überspringen angewendet wird, obwohl dies die Analogie bricht, da eine fehlende Daube (vgl. Nicht bereites Gewinde) den Umfang eines Fasses nicht zusammenzieht. (Ich denke, dass "echte" Fass-Prozessoren es waren.) ? Selten vielleicht der Peripherprozessor für die CDC 6600 -weil sie einen Zyklus verschwendet aber es simplify Hardware) 2. eine Erwähnung von SoEMT wie Itanium Hyper-Threading und IBMs Northstar et al scheint vor allem der Frage gegeben angemessen...
Paul A. Clayton
@ 102948239408, eine andere Sache, nach der Sie googeln könnten, sind Begriffe wie "hit under miss" und "miss under miss" (die andere Option ist "stall under miss", aber ich habe es gerade ausprobiert und es scheint nichts Nützliches zurückzugeben.) Das sind Begriffe, die derzeit von (einigen) Architekten für verschiedene Optionen verwendet werden, die der Cache möglicherweise zulässt.
Wandering Logic
@ PaulA.Clayton, Terminologie ist definitiv nicht meine Stärke. Ich bin mit Ihnen einverstanden, dass Fassverarbeitung Round-Robin bedeuten sollte. Aber ich kann mir keinen anderen Begriff vorstellen, der das zyklische Verschachteln einer Reihe von Threads in der richtigen Reihenfolge bedeutet (genau das tun GPUs, Xeon Phi und Sun T1). Ist es FGMT? Ich habe immer gedacht, dass FGMT SMT einschließt (dh, es gibt nicht an, dass die Threads in der richtigen Reihenfolge ausgeführt werden müssen), aber vielleicht ist FGMT in diesem Fall besser als "Fassprozessor"?
Wandering Logic
Im Wikipedia-Artikel zum Fass-Prozessor heißt es: "Auch bekannt als" Interleaved "oder" Fine-Grained "Temporal Multithreading, also sind IMT und FGMT zumindest anerkannte Begriffe. Ich glaube, ich habe mehr "feinkörnig" als "verschachtelt" gelesen, aber verschachtelt ist keine Seltenheit. Ich habe allgemein FG verwendet (für mich bedeutet "gekörnt" mehr Trennung als SMT bietet); FG hat den Vorteil, dass Interleaved auf SoEMT zutreffen könnte. Ich vermute, dies ist nur eine Änderung in der Verwendung von "Fassprozessor", die ich grinsen (d meine Zähne) und tragen muss.
Paul A. Clayton
16

Die kurze Antwort lautet: Nichts, der Prozessor bleibt stehen.

Es gibt nicht so viele Möglichkeiten. Ein Wechsel zu einer anderen Aufgabe ist aus zwei Gründen nicht wirklich möglich. Dies ist eine kostspielige Operation, und da die aktuelle Task und die andere Task um Speicherplatz im Cache konkurrieren, kann das Umschalten auf die andere Task selbst einen Hauptspeicherzugriff erfordern und somit zur ursprünglichen Task zurückkehren. Außerdem müsste dies das Betriebssystem einbeziehen, sodass der Prozessor eine Art Interrupt oder Trap auslösen müsste - in der Tat würde der Prozessor zu einem Kernel-Code wechseln.

Während der Prozessor blockiert ist, läuft der Timer weiter, sodass möglicherweise ein Timer-Interrupt oder ein Interrupt von anderen Peripheriegeräten auftritt. Daher ist es wahrscheinlicher, dass ein Kontextwechsel während eines Hauptspeicherzugriffs stattfindet als während eines Cache-Zugriffs, aber nur, weil er länger dauert.

Nichtsdestotrotz enthalten moderne Computer eine Vielzahl von Techniken, um die Zeit zu reduzieren, die der Prozessor für das Warten auf den Hauptspeicher benötigt. Abwürgen passiert, aber nur, wenn es nicht zu vermeiden ist.

Eine Technik sind spekulative Abfragen : Der Prozessor versucht zu erraten, auf welche Speicherstelle zugegriffen wird, und ruft diese ab, um sie vorzeitig zwischenzuspeichern. Beispielsweise sind Schleifen über einen Speicherblock üblich. Wenn für die Speicheradressen 0x12340000, 0x12340010 und 0x12340020 Cache-Zeilen geladen wurden, empfiehlt es sich möglicherweise, die Zeile für 0x12340030 zu laden. Der Compiler kann helfen, indem er Prefetch-Anweisungen generiert , die wie Ladevorgänge aussehen, außer dass sie nur Daten vom Hauptspeicher in den Cache übertragen, nicht in ein Prozessorregister.

Eine andere Technik ist die spekulative Ausführung . Der Prozessor beginnt mit der Ausführung des nächsten Befehls, bevor das Laden durchgeführt wird. Dies geschieht natürlich sowieso wegen des Pipelining von Anweisungen. Nur Anweisungen, die nicht vom geladenen Wert abhängen, können auf diese Weise ausgeführt werden: Der Prozessor muss eine Abhängigkeitsanalyse durchführen. Für bedingte Anweisungen (z. B. Laden von r1; Verzweigung, wenn r1 ≤ 0) verwenden Prozessoren Verzweigungsvorhersageheuristiken, um zu erraten, wie hoch der Wert sein wird. Die spekulative Ausführung nach einem Ladevorgang muss möglicherweise zurückgespult werden, falls der Ladevorgang einen Abbruch auslöst.

Einige Architekturen wie Itanium erleichtern die Ausführung von Befehlen in einer bequemen Reihenfolge, indem sie standardmäßig die Neuordnung von Befehlen ermöglichen: Anstatt aus einer Folge von elementaren Befehlen zu bestehen, die semantisch nacheinander ausgeführt werden, bestehen Programme aus sehr langen Befehlswörtern : Ein einzelner Befehl enthält viele Operationen, die von verschiedenen Komponenten des Prozessors parallel ausgeführt werden sollen.

Das Wechseln zu einem anderen Thread geschieht beim Hyperthreading , das bei High-End-x86-Prozessoren auftritt. Dies ist eine Hardware-Entwurfstechnik: Jeder Prozessorkern enthält zwei separate Registerbänke (von denen jede einem Task-Kontext entspricht), jedoch eine einzelne Instanz anderer Elemente, sodass er zwei unabhängige Ausführungsthreads unterstützen kann, aber nur Befehle von einem zum anderen effektiv ausführt eine Zeit. Während ein Thread blockiert ist, fährt der andere Thread fort. Aus Sicht der Software gibt es zwei unabhängige Prozessoren; Es kommt einfach vor, dass sich diese Prozessoren viele Komponenten unter der Haube teilen.

Swap ist eine weitere Ebene in der Speicher-Cache-Hierarchie: Der Hauptspeicher kann als Cache für den Swap-Bereich angesehen werden. Beim Tauschen unterscheiden sich die Mechanismen und die Leistungsverhältnisse. Wenn für eine Task das Laden von Daten aus dem Swap erforderlich ist, löst der Ladebefehl einen Trap aus, der den Kernelcode ausführt, um eine Seite im RAM zuzuweisen und ihren Inhalt von der Festplatte zu laden. In diesem Fall kann der Kernel durchaus beschließen, zu einer anderen Aufgabe zu wechseln.

Gilles 'SO - hör auf böse zu sein'
quelle
Im Gegensatz zum ersten und vorletzten Absatz ist der "Trick", dass beim Hyperthreading kein wirklicher Kontextwechsel stattfinden muss, oder? Die CPU verwaltet zwei Kontexte gleichzeitig.
Raphael
1
@Raphael Richtig: In Bezug auf die Software gibt es für alles außer Leistung zwei CPUs.
Gilles 'SO- hör auf böse zu sein'
Eine Hyperthread-CPU hat viele halbunabhängige Ausführungseinheiten (Ganzzahl- und Gleitkomma-Addierer, Multiplikatoren usw.), und ich denke, dass beide Kontexte gleichzeitig separate Ausführungseinheiten verwenden können - dies ist jedoch nicht 100% sicher.
Russell Borogove
@RussellBorogove Ja, ich habe es nicht erwähnt , weil auch nicht mit Hyper - Threading - CPUs kann mehrere ALU / FPU / ... und umgekehrt separate Kerne manchmal FPU teilen usw.
Gilles ‚SO- Anschlag, die
5

Die Antwort auf diese Frage hängt von der jeweiligen Architektur ab. Während viele CPUs blockieren (ARM, x86 ohne Hyperthreading usw.), weil das Wechseln von Threads zu lange dauert, ist dies nicht der Ansatz, den jede Architektur verfolgt. In einigen Architekturen hat jeder auf einer CPU geplante Thread eine eigene unabhängige Registerdatei, sodass der Prozessor möglicherweise einfach die Arbeit von einem Thread ausführen kann, der nicht auf einen Speicherzugriff wartet. Soweit ich weiß, funktioniert x86-Hyperthreading (mit nur zwei Threads) nur in begrenztem Umfang, unter GPGPU ist dies jedoch weitaus häufigerArchitekturen. Im speziellen Fall von CUDA werden in der Regel mindestens Dutzende, wenn nicht Hunderte von Threads gleichzeitig in einen bestimmten Multiprozessor geladen, wobei jeder Thread (Hunderte oder Tausende von Threads) seine eigenen Register hat. Dies ermöglicht der Architektur, eine Anweisung von einem anderen Thread im nächsten Zyklus auszuführen, wenn ein bestimmter Thread einen Speicherzugriff ausgibt. Solange also genügend viele Threads geladen sind, sind die Prozessorkerne nie für Speicherzugriffe im Leerlauf. Weitere Informationen finden Sie in den Leistungsrichtlinien und der Speicherhierarchie .

reirab
quelle