performance - Verständnis der Auswirkung von lfence auf eine Schleife mit zwei langen Abhängigkeitsketten, um die Länge zu erhöhen




assembly x86 (2)

Ich habe mit dem Code in dieser Antwort gespielt und ihn leicht modifiziert:

BITS 64

GLOBAL _start

SECTION .text

_start:
 mov ecx, 1000000

.loop:

 ;T is a symbol defined with the CLI (-DT=...)

 TIMES T imul eax, eax
 lfence
 TIMES T imul edx, edx


 dec ecx
jnz .loop

 mov eax, 60           ;sys_exit
 xor edi, edi
 syscall

Ohne die lfence die Ergebnisse, die ich erhalte, mit der statischen Analyse in dieser Antwort überein.

Wenn ich eine einzelne lfence würde ich erwarten, dass die CPU die imul edx, edx Sequenz der k-ten Iteration parallel zur imul eax, eax Sequenz der nächsten ( k + 1-ten ) Iteration imul eax, eax .
So etwas wie dieses ( imul eax, eax A das imul eax, eax sequence und D das imul edx, edx one):

|
| A
| D A
| D A
| D A
| ...
| D A
| D
|
V time

Nehmen Sie mehr oder weniger die gleiche Anzahl von Zyklen, aber für eine ungepaarte parallele Ausführung.

Wenn ich die Anzahl der Zyklen für die ursprüngliche und modifizierte Version mit dem taskset -c 2 ocperf.py stat -r 5 -e cycles:u '-x ' ./main-$T für T im Bereich darunter, den ich erhalte

T   Cycles:u    Cycles:u    Delta
    lfence      no lfence

10  42047564    30039060    12008504
15  58561018    45058832    13502186
20  75096403    60078056    15018347
25  91397069    75116661    16280408
30  108032041   90103844    17928197
35  124663013   105155678   19507335
40  140145764   120146110   19999654
45  156721111   135158434   21562677
50  172001996   150181473   21820523
55  191229173   165196260   26032913
60  221881438   180170249   41711189
65  250983063   195306576   55676487
70  281102683   210255704   70846979
75  312319626   225314892   87004734
80  339836648   240320162   99516486
85  372344426   255358484   116985942
90  401630332   270320076   131310256
95  431465386   285955731   145509655
100 460786274   305050719   155735555

Wie lassen sich die Werte von Cycles:u lfence erklären?
Ich hätte erwartet, dass sie denen von Cycles:u no lfence ähneln Cycles:u no lfence da eine einzelne lfence verhindern sollte, dass nur die erste Iteration für die beiden Blöcke parallel ausgeführt wird.
Ich denke nicht, dass es an dem lfence da ich glaube, dass dieser für alle T konstant sein sollte.

Ich möchte beheben, was mit meiner Forma Mentis bei der statischen Analyse von Code nicht stimmt.

Repository mit Quelldateien unterstützen .


Ich denke, Sie messen genau und die Erklärung ist mikroarchitektonisch, keine Art von Messfehler.

Ich denke, dass Ihre Ergebnisse für mittlere bis niedrige T die Schlussfolgerung stützen, dass lfence das Front-End davon lfence sogar nach dem lfence bis alle früheren Anweisungen in den Ruhestand gehen , anstatt dass alle Uops beider Ketten bereits ausgegeben wurden und nur darauf warten, dass lfence Flip-In lfence Schalten Sie und lassen Sie Multiplikationen von jeder Kette abwechselnd starten.

(port1 würde edx, eax, empty, edx, eax, empty, ... für Skylakes 3c-Latenz / 1c-Durchsatz-Multiplikator sofort erhalten, wenn lfence das Front-End nicht blockiert und overhead nicht mit T skaliert.) )

Sie verlieren den imul Durchsatz, wenn sich nur die Uops der ersten Kette im Scheduler befinden, da das Front-End den imul edx,edx Zweig noch nicht durchlaufen hat. Und für die gleiche Anzahl von Zyklen am Ende des Fensters, wenn die Pipeline größtenteils entleert ist und nur noch Uops aus der 2. Kette übrig sind.

Das Overhead-Delta sieht linear bis zu T = 60 aus. Ich habe die Zahlen nicht gezählt, aber die Steigung bis dahin scheint für T * 0.25 Takte angemessen zu sein, um den Engpass bei der Ausführung der ersten Kette gegenüber der 3c-Latenz auszulösen. dh Delta wächst vielleicht 1/12 so schnell wie totale No-Lfence-Zyklen .

Also (angesichts des lfence Overheads, den ich unten gemessen habe) mit T <60:

no_lfence cycles/iter ~= 3T                  # OoO exec finds all the parallelism
lfence    cycles/iter ~= 3T + T/4 + 9.3      # lfence constant + front-end delay
                delta ~=      T/4 + 9.3

@Margaret berichtet, dass T/4 besser passt als 2*T / 4 , aber ich hätte T / 4 sowohl am Anfang als auch am Ende für eine Steigung von insgesamt 2T / 4 des Deltas erwartet.

Nach ungefähr T = 60 wächst Delta viel schneller (aber immer noch linear) mit einer Steigung, die ungefähr gleich den gesamten No-Lfence-Zyklen ist, also ungefähr 3 c pro T. Ich denke, an diesem Punkt ist die Größe des Schedulers (Reservation Station) Begrenzen des Fensters außerhalb der Reihenfolge. Sie haben wahrscheinlich auf einer Haswell- oder Sandybridge / IvyBridge-Karte getestet ( mit 60 bzw. 54 Einträgen). Skylake hat 97 Einträge.

Der RS ​​verfolgt nicht ausgeführte Ups. Jeder RS-Eintrag enthält 1 nicht verschmolzenes Domänen-UOP, das darauf wartet, dass seine Eingaben bereit sind, sowie seinen Ausführungsport, bevor es den RS 1 senden und verlassen kann.

Nach einer lfence wird das Front-End mit 4 pro Takt ausgeführt, während das Back-End mit 1 pro 3 Takten ausgeführt wird. Dabei werden 60 Uops in ~ 15 Zyklen ausgegeben. In dieser Zeit wurden nur 5 imul Befehle aus der edx Kette ausgeführt. (Es gibt hier keine Lade- oder Speicher-Mikroverschmelzung, daher ist jedes UOP einer verschmolzenen Domäne vom Front-End immer noch nur ein UOP einer nicht verschmolzenen Domäne in der RS 2. )

Bei einem großen T füllt sich der RS ​​schnell, und an diesem Punkt kann das Front-End nur mit der Geschwindigkeit des Back-End Fortschritte machen. (Für kleine T treffen wir die Zeit der nächsten Iteration, bevor das passiert, und das lfence das Front-End). Wenn T> RS_size , kann das Back-End keine der Uops von der EAX-IMUL-Kette sehen, bis genügend Back-End-Fortschritt durch die edx Kette Platz in der RS ​​gemacht hat. Zu diesem Zeitpunkt kann ein imul aus jeder Kette alle 3 Zyklen anstatt nur der 1. oder 2. Kette imul .

Denken Sie ab dem ersten Abschnitt daran, dass die Zeit unmittelbar nach der Ausführung der ersten Kette lfence = Zeit unmittelbar vor der Ausführung der zweiten Kette. Das gilt auch hier.

Wir erhalten einen Teil dieses Effekts auch ohne lfence für T> RS_size , aber es besteht die Möglichkeit einer Überlappung auf beiden Seiten einer langen Kette. Der ROB ist mindestens doppelt so groß wie der RS, daher sollte das Fenster für nicht lfence Ausführung, wenn es nicht vom Stillstand lfence ist, in der Lage sein, beide Ketten konstant im Flug zu halten, selbst wenn T etwas größer als die Kapazität des Schedulers ist. (Denken Sie daran, dass Uops die RS verlassen, sobald sie ausgeführt wurden. Ich bin mir nicht sicher, ob das bedeutet, dass sie die Ausführung beenden und ihr Ergebnis weiterleiten müssen oder nur mit der Ausführung beginnen müssen, aber das ist ein kleiner Unterschied für kurze ALU-Anweisungen. Einmal Sie sind fertig, nur der ROB hält sie fest, bis sie in der Programmreihenfolge in den Ruhestand gehen.)

Der ROB und die Registerdatei sollten in dieser hypothetischen Situation oder in Ihrer Realität nicht die Fenstergröße außerhalb der Reihenfolge ( http://blog.stuffedcow.net/2013/05/measuring-rob-capacity/ ) einschränken Situation. Sie sollten beide groß genug sein.

Das Blockieren des Frontends ist ein Implementierungsdetail von lfence auf Intels Uarches . Das Handbuch besagt nur, dass spätere Anweisungen nicht ausgeführt werden können . Dieser Wortlaut würde es dem Front-End ermöglichen, sie alle im Scheduler (Reservation Station) und in ROB lfence / umzubenennen, während lfence noch wartet, solange keine an eine Ausführungseinheit lfence werden.

Eine schwächere lfence hätte also möglicherweise einen flachen Overhead bis zu T = RS_size und dann dieselbe Steigung, wie Sie sie jetzt für T> 60 sehen. (Und der konstante Teil des Overheads könnte niedriger sein.)

Beachten Sie, dass Garantien für die spekulative Ausführung von bedingten / indirekten Verzweigungen nach lfence für die Ausführung gelten, nicht (soweit ich weiß) für das Abrufen von Code. Nur das Auslösen von Code-Fetch ist für einen Spectre- oder Meltdown-Angriff nicht (AFAIK) nützlich. Möglicherweise könnte ein Timing-Seitenkanal, der erkennt, wie er dekodiert, etwas über den abgerufenen Code aussagen ...

Ich denke, AMDs LFENCE ist auf tatsächlichen AMD-CPUs mindestens genauso stark, wenn das entsprechende MSR aktiviert ist. ( Wird LFENCE auf AMD-Prozessoren serialisiert? )

Zusätzlicher lfence :

Ihre Ergebnisse sind interessant, aber es überrascht mich überhaupt nicht, dass es einen signifikanten konstanten Overhead von lfence selbst (für kleines T) gibt, sowie die Komponente, die mit T skaliert.

Denken lfence daran, dass lfence den Start späterer Anweisungen erst zulässt, wenn frühere Anweisungen in den Ruhestand gegangen sind . Dies ist wahrscheinlich mindestens ein paar Zyklen / Pipeline-Phasen später, als wenn ihre Ergebnisse für die Weiterleitung an andere Ausführungseinheiten (dh die normale Latenz) bereit sind.

Für kleine T ist es also auf jeden Fall wichtig, dass Sie der Kette zusätzliche Latenz hinzufügen, indem Sie das Ergebnis nicht nur bereithalten, sondern auch in die Registerdatei zurückschreiben müssen.

Es dauert wahrscheinlich einen zusätzlichen Zyklus oder so, bis die lfence / Umbenennungsstufe wieder in Betrieb genommen werden kann, nachdem lfence , dass die letzte Anweisung vor dem lfence . Der Ausgabe- / Umbenennungsprozess dauert mehrere Phasen (Zyklen) und möglicherweise zu Beginn Lfence-Blöcke, anstatt im allerletzten Schritt, bevor Uops zum OoO-Teil des Kerns hinzugefügt werden.

Selbst Back-to-Back- lfence haben laut Agner Fog-Tests einen Durchsatz von 4 Zyklen für die SnB-Familie. Agner Fog meldet 2 Fused-Domain-Ups (keine Fused-Domain), aber bei Skylake messe ich sie bei 6 Fused-Domain (immer noch keine Fused-Domain), wenn ich nur 1 lfence . Aber mit mehr Zeit lfence , es ist weniger Höhen! Bis zu ~ 2 Höhen pro lfence mit vielen lfence , so misst Agner.

lfence / dec / jnz (eine enge Schleife ohne Arbeit) wird unter SKL mit 1 Iteration pro ~ 10 Zyklen ausgeführt, sodass wir möglicherweise eine Vorstellung von der tatsächlichen zusätzlichen Latenz erhalten, die lfence den Dep-Ketten auch ohne das Front-End und hinzufügt RS-volle Engpässe.

Messen des lfence mit nur einer Dep-Kette , OoO exec ist irrelevant:

.loop:
    ;mfence                  ; mfence here:  ~62.3c (with no lfence)
    lfence                   ; lfence here:  ~39.3c
    times 10 imul eax,eax    ; with no lfence: 30.0c
    ; lfence                 ; lfence here:  ~39.6c
    dec   ecx
    jnz   .loop

lfence ohne lfence mit den erwarteten 30.0c pro Iter. lfence mit ~ 39,3 c pro lfence , fügt lfence der Dep-Kette für kritische lfence effektiv ~ 9,3 c zusätzliche Latenz hinzu. (Und 6 zusätzliche Fused-Domain-Ups).

Mit lfence nach der Imul-Kette, kurz vor dem Loop-Ast, ist es etwas langsamer. Es ist jedoch kein ganzer Zyklus langsamer, was darauf hindeutet, dass das Front-End den Loop-Branch + ausgibt und in einer einzelnen Issue-Gruppe lfence nachdem lfence die Wiederaufnahme der Ausführung ermöglicht. Deshalb ist IDK langsamer. Es ist nicht von Filialfehlern.

Erhalten Sie das Verhalten, das Sie erwartet hatten:

Verschachtele die Ketten in der Programmreihenfolge, wie @BeeOnRope in Kommentaren vorschlägt, erfordert keine Ausführung außerhalb der Reihenfolge, um das ILP auszunutzen, also ist es ziemlich trivial:

.loop:
    lfence      ; at the top of the loop is the lowest-overhead place.

%rep T
    imul   eax,eax
    imul   edx,edx
%endrep

    dec     ecx
    jnz    .loop

Sie könnten paarweise times 8 imul Ketten innerhalb einer %rep , damit OoO exec eine leichte Zeit hat.

Fußnote 1: Wie das Front-End / RS / ROB interagieren

Mein mentales Modell ist, dass das Ausgeben / Umbenennen / Zuweisen von Stufen im Front-End gleichzeitig dem RS und dem ROB neue Uops hinzufügt.

Uops verlassen die RS nach der Ausführung, bleiben aber bis zur ordentlichen Pensionierung in der ROB. Der ROB kann sehr groß sein, da er niemals unregelmäßig gescannt wird, um den ersten bereitgestellten UOP zu finden. Er wird nur gescannt, um zu überprüfen, ob die ältesten UOPs die Ausführung beendet haben und somit bereit sind, in den Ruhestand zu gehen.

(Ich nehme an, der ROB ist physisch ein zirkulärer Puffer mit Start / Ende-Indizes, keine Warteschlange, die tatsächlich bei jedem Zyklus nach rechts kopiert. Stellen Sie sich den ROB jedoch als Warteschlange / Liste mit fester Maximalgröße vor, in der sich das Front-End befindet Fügt an der Front Uops hinzu, und die Retirement-Logik setzt Uops vom Ende an zurück / fest, solange sie vollständig ausgeführt werden, bis zu einem bestimmten pro Zyklus pro Hyperthread festgelegten Retirement-Limit, das normalerweise kein Engpass ist. Skylake hat es zum Besseren erhöht Hyperthreading, möglicherweise auf 8 pro Takt pro logischem Thread. Möglicherweise bedeutet das Zurückziehen auch das Freigeben physischer Register, was HT hilft, da der ROB selbst statisch partitioniert ist, wenn beide Threads aktiv sind.

Uops wie nop , xor eax,eax oder lfence , die im Front-End verarbeitet werden (keine Ausführungseinheiten an einem lfence erforderlich), werden nur in einem bereits ausgeführten Zustand zum ROB hinzugefügt. (Ein ROB-Eintrag weist vermutlich ein Bit auf, das ihn als bereit für den Ruhestand markiert, und wartet noch auf den Abschluss der Ausführung. Dies ist der Zustand, von dem ich spreche. Für Benutzer, die einen Ausführungsport benötigten, gehe ich davon aus, dass das ROB-Bit gesetzt ist über einen Beendigungsport von der Ausführungseinheit. Und das gleiche Beendigungsport-Signal gibt seinen RS-Eintrag frei.)

Uops bleibt von der Ausgabe bis zur Pensionierung im ROB.

Uops bleiben von der Ausgabe bis zur Ausführung in der RS. Der RS ​​kann in einigen Fällen Uops wiedergeben , z. B. für die andere Hälfte eines Cache-Line-Split-Ladevorgangs , oder wenn er in Erwartung des Eintreffens von Ladedaten gesendet wurde , aber tatsächlich nicht. (Cache-Fehler oder andere Konflikte wie seltsame Leistungseffekte von in der Nähe befindlichen abhängigen Speichern in einer Zeigerjagdschleife auf IvyBridge. Durch Hinzufügen einer zusätzlichen Last wird diese beschleunigt? ) Verkürzung der Wartezeit beim Verfolgen von Zeigern mit kleinen Offsets - Gibt es eine Strafe, wenn sich Basis + Offset auf einer anderen Seite als die Basis befindet?

Wir wissen also, dass der RS ​​ein UOP-Recht beim Versand nicht entfernen kann, da es möglicherweise erneut abgespielt werden muss. (Kann sogar Nicht-Lade-Uops passieren, die Ladedaten verbrauchen.) Spekulationen, die erneut abgespielt werden müssen, sind jedoch auf kurze Distanz und nicht über eine Kette von Uops möglich. Sobald das Ergebnis am anderen Ende einer Ausführungseinheit angezeigt wird, kann der Uop dies aus dem RS entfernt werden. Wahrscheinlich ist dies ein Teil dessen, was ein Completion-Port tut, zusammen mit dem Setzen des Ergebnisses in das Bypass-Weiterleitungsnetz.

Fußnote 2: Wie viele RS-Einträge nimmt ein mikrosicheres UOP auf?

TL: DR: P6-Familie: RS ist fusioniert, SnB-Familie: RS ist nicht fusioniert.

Ein mikrosicherer UOP wird an zwei separate RS-Einträge in der Sandybridge-Familie ausgegeben , jedoch nur an einen ROB-Eintrag. (Vorausgesetzt, es ist vor der Ausgabe nicht unlaminiert, siehe Abschnitt 2.3.5 für HSW oder Abschnitt 2.4.2.4 für SnB von Intels Optimierungshandbuch und Mikroschmelz- und Adressierungsmodi . Das kompaktere UOP-Format der Sandybridge-Familie kann kein indiziertes Format darstellen.) Adressierungsmodi im ROB in allen Fällen.)

Der Ladevorgang kann unabhängig erfolgen, bevor der andere Operand für die ALU bereit ist. (Bei Geschäften mit Fusionen können entweder die Geschäftsadresse oder die Geschäftsdaten versendet werden, wenn die Eingabe fertig ist, ohne auf beide zu warten.)

Ich habe die Zwei-Dep-Ketten-Methode aus der Frage verwendet, um dies experimentell an Skylake (RS-Größe = 97) mit mikroverschmolzenem or edi, [rdi] vs. mov + or ) und einer anderen Dep-Kette in rsi . ( Vollständiger Testcode, NASM-Syntax für Godbolt )

; loop body
%rep T
%if FUSE
    or edi, [rdi]    ; static buffers are in the low 32 bits of address space, in non-PIE
%else
    mov  eax, [rdi]
    or   edi, eax
%endif
%endrep

%rep T
%if FUSE
    or esi, [rsi]
%else
    mov  eax, [rsi]
    or   esi, eax
%endif
%endrep

Wenn wir uns uops_executed.thread (nicht uops_executed.thread Domäne) pro Zyklus (oder pro Sekunde, die für uns berechnet wird) ansehen, sehen wir eine Durchsatzzahl, die nicht von getrennten oder gefalteten Lasten abhängt.

Mit kleinem T (T = 30) kann das gesamte ILP ausgenutzt werden, und wir erhalten ~ 0,67 Uops pro Uhr mit oder ohne Mikroverschmelzung. (Ich ignoriere die geringe Abweichung von 1 zusätzlichen UOP pro Loop-Iteration von dec / jnz. Sie ist vernachlässigbar im Vergleich zu dem Effekt, den wir sehen würden, wenn mikrogefixte UOPs nur 1 RS-Eintrag verwenden würden.)

Denken Sie daran, dass load + or 2 Uops ist und wir 2 Dep-Ketten im Flug haben. Dies ist also 4/6, weil or edi, [rdi] eine Latenz von 6 Zyklen hat. (Nicht 5, was überrascht, siehe unten.)

Bei T = 60 haben wir immer noch ungefähr 0,66 nicht abgesicherte Uops pro Takt für FUSE = 0 und 0,64 für FUSE = 1. Grundsätzlich können wir immer noch alle ILP finden, aber es beginnt gerade erst zu sinken, da die beiden Dep-Ketten 120 Uops lang sind (im Vergleich zu einer RS-Größe von 97).

Bei T = 120 haben wir 0,45 nicht verschmolzene Ups pro Takt für FUSE = 0 und 0,44 für FUSE = 1. Wir sind definitiv hinter dem Knie, finden aber immer noch einen Teil der ILP.

Wenn ein mikrogesicherter UOP nur 1 RS-Eingang benötigt, sollte FUSE = 1 T = 120 ungefähr so ​​schnell sein wie FUSE = 0 T = 60, aber das ist nicht der Fall . Stattdessen macht FUSE = 0 oder 1 fast keinen Unterschied bei T. (Einschließlich größerer Werte wie T = 200: FUSE = 0: 0,395 Uops / Clock, FUSE = 1: 0,391 Uops / Clock). Wir müssten auf sehr großes T gehen, bevor wir die Zeit mit 1 Dep-Kette im Flug beginnen, um die Zeit mit 2 im Flug vollständig zu dominieren und auf 0,33 Ups / Uhr (2/6) zu kommen.

Seltsamkeit: Wir haben einen so kleinen, aber immer noch messbaren Unterschied im Durchsatz für geschmolzene und nicht geschmolzene Geräte, wobei die einzelnen mov Lasten schneller sind.

Andere Merkwürdigkeiten: Die Summe uops_executed.thread ist für FUSE = 0 bei jedem gegebenen T etwas niedriger. Wie 2,418,826,591 gegenüber 2,419,020,155 für T = 60. Dieser Unterschied war bis auf + - 60k von 2,4G wiederholbar, genau genug. FUSE = 1 ist in den gesamten Taktzyklen langsamer, aber der größte Unterschied ergibt sich aus niedrigeren Uops pro Takt und nicht aus mehr Uops.

Einfache Adressierungsmodi wie [rdi] sollen nur eine Latenz von 4 Zyklen haben, daher sollte load + ALU nur 5 Zyklen betragen. Aber ich messe die Latenzzeit von 6 Zyklen für die Ladezeit von or rdi, [rdi] oder mit einem separaten MOV-Ladevorgang oder mit einem anderen ALU-Befehl. Ich kann den Ladeteil niemals auf 4c bringen.

Ein komplexer Adressierungsmodus wie [rdi + rbx + 2064] hat die gleiche Latenzzeit, wenn ein ALU-Befehl in der Dep-Kette vorhanden ist. Daher scheint die 4c-Latenzzeit von Intel für einfache Adressierungsmodi nur zu gelten, wenn eine Last an das Basisregister einer anderen Last weitergeleitet wird (mit bis zu einem +) 0..2047 Verschiebung und kein Index).

Pointer-Chasing ist so verbreitet, dass dies eine nützliche Optimierung darstellt. Wir müssen es jedoch als speziellen Load-Load-Forwarding-Fast-Path betrachten und nicht als allgemeine Daten, die früher für die Verwendung durch ALU-Anweisungen bereitstehen.

Die P6-Familie ist anders: Ein RS-Eintrag enthält einen Fused-Domain-UOP.

@Hadi hat ein Intel-Patent aus dem Jahr 2002 gefunden , in dem Abbildung 12 die RS in der fusionierten Domäne zeigt.

Experimentelle Tests an einem Conroe (Core2Duo der ersten Generation, E6600) zeigen, dass es für T = 50 einen großen Unterschied zwischen FUSE = 0 und FUSE = 1 gibt. ( Die RS-Größe beträgt 32 Einträge ).

  • T = 50 FUSE = 1: Gesamtzeit von 2,346 G-Zyklen (0,44 IPC)
  • T = 50 FUSE = 0: Gesamtzeit von 3,272 G-Zyklen (0,62 IPC = 0,31 Last + ODER pro Takt). ( perf / ocperf.py Hat keine Veranstaltungen für uops_executed auf uarches vor Nehalem oder so, und ich habe nicht oprofile auf dieser Maschine installiert.)

  • T = 24 gibt es einen vernachlässigbaren Unterschied zwischen FUSE = 0 und FUSE = 1, etwa 0,47 IPC gegenüber 0,9 IPC (~ 0,45 Last + ODER pro Takt).

T = 24 ist immer noch über 96 Byte Code in der Schleife, zu groß für den 64-Byte-Schleifenpuffer (vor der Dekodierung) von Core 2, sodass er nicht schneller ist, weil er in einen Schleifenpuffer passt. Ohne einen UOP-Cache müssen wir uns um das Front-End sorgen, aber ich denke, wir sind in Ordnung, weil ich ausschließlich 2-Byte-Single-UOP-Anweisungen verwende, die bei 4 UOPs mit fusionierter Domäne pro Takt leicht zu dekodieren sind.


Ich werde eine Analyse für den Fall präsentieren, in dem T = 1 für beide Codes ist (mit und ohne lfence ). Sie können dies dann für andere Werte von T erweitern. Eine visuelle Darstellung finden Sie in Abbildung 2.4 des Intel Optimization Manual.

Da es nur einen einzigen, leicht vorherzusagenden Zweig gibt, wird das Frontend nur angehalten, wenn das Backend angehalten wird. Das Frontend ist in Haswell 4-wide, was bedeutet, dass bis zu 4 verschmolzene Uops von der IDQ (Instruction Decode Queue, die nur eine Warteschlange ist, die in der Reihenfolge verschmolzene Domain-Uops enthält, auch Uop-Queue genannt) an die ausgegeben werden können Reservierungsstation (RS) des Schedulers. Jedes imul wird in ein einzelnes Uop dekodiert, das nicht fusioniert werden kann. Die Anweisungen dec ecx und jnz .loop werden im Frontend zu einem einzigen Uop makrofixiert. Einer der Unterschiede zwischen Mikrofusion und Makrofusion besteht darin, dass der Scheduler, wenn er einen makrofixierten Uop (der nicht mikrofixiert ist) an die Ausführungseinheit sendet, der er zugewiesen ist, diesen als einen einzelnen Uop sendet. Im Gegensatz dazu muss ein mikrogeschmolzenes Uop in seine konstituierenden Uops aufgeteilt werden, von denen jedes separat an eine Ausführungseinheit gesendet werden muss. (Das Aufteilen von mikrogeschmolzenen Ups erfolgt jedoch beim Eintritt in die RS, nicht beim Versand, siehe Fußnote 2 in der Antwort von @ Peter). lfence wird in 6 Uops dekodiert. Das Erkennen von Mikrofusionen spielt nur im Backend eine Rolle. In diesem Fall befindet sich keine Mikrofusion in der Schleife.

Da der Schleifenzweig leicht vorhersehbar ist und die Anzahl der Iterationen relativ groß ist, können wir ohne Abstriche bei der Genauigkeit davon ausgehen, dass der Allokator immer 4 Uops pro Zyklus zuweisen kann. Mit anderen Worten, der Scheduler erhält 4 Uops pro Zyklus. Da es keine Mikrofusion gibt, wird jedes UOP als einzelnes UOP versendet.

imul kann nur von der Ausführungseinheit Slow Int ausgeführt werden (siehe Abbildung 2.4). Das bedeutet, dass Sie die imul Uops nur an Port 1 imul können. In Haswell ist die Slow Int-Pipeline so aufgebaut, dass ein einzelnes imul pro Zyklus imul kann. Es dauert jedoch drei Zyklen, bis das Ergebnis der Multiplikation für jeden erforderlichen Befehl verfügbar ist (die Rückschreibestufe ist der dritte Zyklus ab der Versandstufe der Pipeline). Für jede Abhängigkeitskette kann also höchstens ein imul pro 3 Zyklen imul werden.

Da vorausgesagt wird, dass dec/jnz wird, ist die einzige Ausführungseinheit, die es ausführen kann, der primäre Zweig an Port 6.

Solange also der RS ​​in einem bestimmten Zyklus Platz hat, erhält er 4 Ups. Aber welche Art von Ups? Lassen Sie uns die Schleife ohne Verzögerung untersuchen:

imul eax, eax
imul edx, edx
dec ecx/jnz .loop (macrofused)

Es gibt zwei Möglichkeiten:

  • Zwei imul aus derselben Iteration, ein imul aus einer benachbarten Iteration und ein dec/jnz aus einer dieser beiden Iterationen.
  • Ein dec/jnz von einer Iteration, zwei imul von der nächsten Iteration und ein dec/jnz von derselben Iteration.

Zu Beginn eines Zyklus erhält der RS ​​also mindestens ein dec/jnz und mindestens ein imul von jeder Kette. Gleichzeitig führt der Scheduler im selben Zyklus und von den Uops, die sich bereits in der RS ​​befinden, eine von zwei Aktionen aus:

  • Versenden Sie das älteste dec/jnz an Port 6 und das älteste imul , das für Port 1 bereit ist. Das sind insgesamt 2 Uops.
  • Da das Slow Int eine Latenzzeit von 3 Zyklen hat, es jedoch nur zwei Ketten gibt, ist für jeden Zyklus von 3 Zyklen kein imul in der RS ​​zur Ausführung bereit. Es gibt jedoch immer mindestens ein dec/jnz im RS. So kann der Scheduler das versenden. Das ist insgesamt 1 uop.

Jetzt können wir die erwartete Anzahl von Uops in der RS, X N , am Ende eines gegebenen Zyklus N berechnen:

X N = X N-1 + (die Anzahl der zuzuteilenden Uops in der RS ​​zu Beginn des Zyklus N) - (die erwartete Anzahl der Uops, die zu Beginn des Zyklus N versandt werden)
= X N-1 + 4 - ((0 + 1) * 1/3 + (1 + 1) * 2/3)
= X N-1 + 12/3 - 5/3
= X N-1 + 7/3 für alle N> 0

Die Ausgangsbedingung für die Wiederholung ist X 0 = 4. Dies ist eine einfache Wiederholung, die durch Entfalten von X N-1 gelöst werden kann.

X N = 4 + 2,3 * N für alle N> = 0

Die RS in Haswell hat 60 Einträge. Wir können den ersten Zyklus bestimmen, in dem der RS ​​voraussichtlich voll wird:

60 = 4 + 7/3 * N
N = 56 / 2,3 = 24,3

Am Ende von Zyklus 24.3 wird der RS ​​voraussichtlich voll sein. Dies bedeutet, dass der RS ​​zu Beginn des Zyklus 25.3 keine neuen Uops empfangen kann. Nun bestimmt die Anzahl der Iterationen, die ich in Betracht ziehe, wie Sie mit der Analyse fortfahren sollen. Da für die Ausführung einer Abhängigkeitskette mindestens 3 * I-Zyklen erforderlich sind, dauert es etwa 8,1 Iterationen, bis Zyklus 24.3 erreicht ist. Wenn also die Anzahl der Iterationen größer als 8.1 ist, was hier der Fall ist, müssen Sie analysieren, was nach Zyklus 24.3 passiert.

Der Scheduler sendet in jedem Zyklus Anweisungen mit den folgenden Raten (wie oben erläutert):

1
2
2
1
2
2
1
2
.
.

Der Zuweiser weist jedoch keine Uops in der RS ​​zu, es sei denn, es sind mindestens 4 Einträge verfügbar. Andernfalls wird beim Ausgeben von Uops mit einem nicht optimalen Durchsatz keine Energie verschwendet. Es sind jedoch erst zu Beginn jedes 4. Zyklus mindestens 4 freie Einträge im RS vorhanden. Ab Zyklus 24.3 wird erwartet, dass der Allokator 3 von 4 Zyklen blockiert.

Eine weitere wichtige Beobachtung für den zu analysierenden Code ist, dass niemals mehr als 4 Uops abgesetzt werden können, was bedeutet, dass die durchschnittliche Anzahl der Uops, die ihre Ausführungseinheiten pro Zyklus verlassen, nicht größer als 4 ist. Höchstens 4 Uops kann aus dem ReOrder Buffer (ROB) entfernt werden. Dies bedeutet, dass der ROB niemals auf dem kritischen Pfad sein kann. Mit anderen Worten, die Leistung wird durch den Versanddurchsatz bestimmt.

Wir können den IPC (Anweisungen pro Zyklus) jetzt ziemlich einfach berechnen. Die ROB-Einträge sehen ungefähr so ​​aus:

imul eax, eax     -  N
imul edx, edx     -  N + 1
dec ecx/jnz .loop -  M
imul eax, eax     -  N + 3
imul edx, edx     -  N + 4
dec ecx/jnz .loop -  M + 1

Die Spalte rechts zeigt die Zyklen, in denen die Anweisung zurückgezogen werden kann. Die Pensionierung erfolgt in der richtigen Reihenfolge und wird durch die Latenz des kritischen Pfades begrenzt. Hier hat jede Abhängigkeitskette die gleiche Pfadlänge und daher bilden beide zwei gleiche kritische Pfade mit einer Länge von 3 Zyklen. So können alle 3 Zyklen 4 Befehle abgesetzt werden. Der IPC ist also 4/3 = 1,3 und der CPI ist 3/4 = 0,75. Dies ist viel kleiner als der theoretisch optimale IPC von 4 (auch ohne Berücksichtigung von Mikro- und Makrofusion). Da die Pensionierung in der richtigen Reihenfolge erfolgt, ist das Verhalten bei der Pensionierung dasselbe.

Wir können unsere Analyse sowohl mit perf als auch mit IACA überprüfen. Ich werde perf diskutieren. Ich habe eine Haswell-CPU.

perf stat -r 10 -e cycles:u,instructions:u,cpu/event=0xA2,umask=0x10,name=RESOURCE_STALLS.ROB/u,cpu/event=0x0E,umask=0x1,cmask=1,inv=1,name=UOPS_ISSUED.ANY/u,cpu/event=0xA2,umask=0x4,name=RESOURCE_STALLS.RS/u ./main-1-nolfence

 Performance counter stats for './main-1-nolfence' (10 runs):

         30,01,556      cycles:u                                                      ( +-  0.00% )
         40,00,005      instructions:u            #    1.33  insns per cycle          ( +-  0.00% )
                 0      RESOURCE_STALLS.ROB                                         
         23,42,246      UOPS_ISSUED.ANY                                               ( +-  0.26% )
         22,49,892      RESOURCE_STALLS.RS                                            ( +-  0.00% )

       0.001061681 seconds time elapsed                                          ( +-  0.48% )

Es gibt 1 Million Iterationen, die jeweils etwa 3 Zyklen dauern. Jede Iteration enthält 4 Anweisungen und der IPC ist 1,33. RESOURCE_STALLS.ROB zeigt die Anzahl der Zyklen an, in denen der Allokator aufgrund eines vollen ROB angehalten wurde. Das passiert natürlich nie. UOPS_ISSUED.ANY kann verwendet werden, um die Anzahl der an den RS ausgegebenen Uops und die Anzahl der Zyklen zu zählen, in denen der Allokator angehalten wurde (kein bestimmter Grund). Der erste ist unkompliziert (nicht in der perf Ausgabe gezeigt); 1 Million * 3 = 3 Millionen + geringes Rauschen. Letzteres ist viel interessanter. Es zeigt, dass ungefähr 73% aller Zeit der Allokator aufgrund einer vollen RS ins Stocken geraten ist, was unserer Analyse entspricht. RESOURCE_STALLS.RS zählt die Anzahl der Zyklen, in denen der Allokator aufgrund einer vollen RS angehalten wurde. Dies liegt in der Nähe von UOPS_ISSUED.ANY da der UOPS_ISSUED.ANY aus irgendeinem anderen Grund nicht UOPS_ISSUED.ANY (obwohl die Differenz aus irgendeinem Grund proportional zur Anzahl der Iterationen sein könnte, muss ich die Ergebnisse für T> 1 sehen).

Die Analyse des Codes ohne lfence kann erweitert werden, um festzustellen, was passiert, wenn eine lfence zwischen den beiden imul hinzugefügt wurde. lfence wir uns zuerst die perf Ergebnisse an (IACA unterstützt leider kein lfence ):

perf stat -r 10 -e cycles:u,instructions:u,cpu/event=0xA2,umask=0x10,name=RESOURCE_STALLS.ROB/u,cpu/event=0x0E,umask=0x1,cmask=1,inv=1,name=UOPS_ISSUED.ANY/u,cpu/event=0xA2,umask=0x4,name=RESOURCE_STALLS.RS/u ./main-1-lfence

 Performance counter stats for './main-1-lfence' (10 runs):

       1,32,55,451      cycles:u                                                      ( +-  0.01% )
         50,00,007      instructions:u            #    0.38  insns per cycle          ( +-  0.00% )
                 0      RESOURCE_STALLS.ROB                                         
       1,03,84,640      UOPS_ISSUED.ANY                                               ( +-  0.04% )
                 0      RESOURCE_STALLS.RS                                          

       0.004163500 seconds time elapsed                                          ( +-  0.41% )

Beachten Sie, dass die Anzahl der Zyklen um etwa 10 Millionen oder 10 Zyklen pro Iteration zugenommen hat. Die Anzahl der Zyklen sagt nicht viel aus. Die Zahl der Auszubildenden im Ruhestand ist erwartungsgemäß um eine Million gestiegen. Wir wissen bereits, dass die lfence den Befehl nicht schneller lfence wird, daher sollte lfence nicht geändert werden. Besonders interessant sind UOPS_ISSUED.ANY und UOPS_ISSUED.ANY . In dieser Ausgabe zählt UOPS_ISSUED.ANY Zyklen, nicht Uops. Die Anzahl der Uops kann auch gezählt werden (mit cpu/event=0x0E,umask=0x1,name=UOPS_ISSUED.ANY/u anstelle von cpu/event=0x0E,umask=0x1,cmask=1,inv=1,name=UOPS_ISSUED.ANY/u ) und hat sich um 6 Uops pro Iteration erhöht (keine Fusion). Dies bedeutet, dass eine lfence , die zwischen zwei imul platziert wurde, in 6 Uops dekodiert wurde. Die eine Million Dollar teure Frage ist nun, was diese Uops tun und wie sie sich in der Pipe bewegen.

RESOURCE_STALLS.RS ist null. Was bedeutet das? Dies zeigt an, dass der lfence die Allokation stoppt, bis alle aktuellen Uops im ROB in den Ruhestand gehen, wenn er eine lfence im IDQ sieht. Mit anderen Worten, der Zuweiser weist keine Einträge in der RS ​​nach einer lfence bis die lfence Ruhestand geht. Da der Loop-Body nur 3 andere Uops enthält, ist der RS ​​mit 60 Einträgen niemals voll. In der Tat wird es immer fast leer sein.

Die IDQ ist in Wirklichkeit keine einfache Warteschlange. Es besteht aus mehreren Hardwarestrukturen, die parallel arbeiten können. Die Anzahl der Uops, die ein lfence benötigt, hängt vom genauen Design des IDQ ab. Der Allokator, der ebenfalls aus vielen verschiedenen Hardwarestrukturen besteht, unterbricht die Allokation von dieser Struktur, bis der ROB leer ist, wenn er lfence dass sich an der Vorderseite einer der Strukturen des IDQ ein lfence Uops befindet. So werden unterschiedliche Uops mit unterschiedlichen Hardwarestrukturen verwendet.

UOPS_ISSUED.ANY zeigt, dass der Allokator für ungefähr 9-10 Zyklen pro Iteration keine Uops ausgibt. Was passiert hier? Nun, einer der lfence von lfence besteht darin, dass es uns sagen kann, wie viel Zeit es dauert, eine Anweisung zurückzuziehen und die nächste Anweisung zuzuweisen. Der folgende Assembler-Code kann dazu verwendet werden:

TIMES T lfence

Die Leistungsereigniszähler funktionieren bei kleinen Werten von T nicht gut. Für ein ausreichend großes T und durch Messen von UOPS_ISSUED.ANY können wir bestimmen, dass es ungefähr 4 Zyklen dauert, um jede lfence . UOPS_ISSUED.ANY liegt daran, dass UOPS_ISSUED.ANY ungefähr alle 5 Zyklen viermal inkrementiert wird. Nach jeweils 4 Zyklen gibt der lfence weitere lfence (er lfence nicht), wartet dann auf weitere 4 Zyklen und so weiter. Das heißt, Befehle, die Ergebnisse liefern, können je nach Befehl einen oder mehrere Zyklen mehr benötigen, um in den Ruhestand zu treten. IACA geht immer davon aus, dass es 5 Zyklen dauert, um einen Befehl zu löschen.

Unsere Schleife sieht so aus:

imul eax, eax
lfence
imul edx, edx
dec ecx
jnz .loop

Bei jedem Zyklus an der lfence Grenze enthält der ROB die folgenden Anweisungen, beginnend am lfence Rand des ROB (die älteste Anweisung):

imul edx, edx     -  N
dec ecx/jnz .loop -  N
imul eax, eax     -  N+1

Wobei N die Zyklusnummer bezeichnet, bei der der entsprechende Befehl gesendet wurde. Die letzte Anweisung, die abgeschlossen sein wird (die Rückschreibestufe erreicht), ist imul eax, eax . und dies geschieht im Zyklus N + 4. Die Anzahl der Allokatorblockierzyklen wird während der Zyklen N + 1, N + 2, N + 3 und N + 4 erhöht. Es wird jedoch noch ungefähr 5 Zyklen imul eax, eax bis imul eax, eax Ruhestand geht. Darüber hinaus muss der lfence nach dem Stillstand die lfence Uops von der IDQ bereinigen und die nächste Anweisungsgruppe zuweisen, bevor sie im nächsten Zyklus abgesetzt werden können. Die perf Ausgabe sagt uns, dass es ungefähr 13 Zyklen pro Iteration dauert und dass der lfence (wegen der lfence ) für 10 von diesen 13 Zyklen stehen lfence .

Die Grafik aus der Frage zeigt nur die Anzahl der Zyklen für bis zu T = 100. An dieser Stelle befindet sich jedoch ein weiteres (letztes) Knie. Es ist also besser, die Zyklen bis zu T = 120 zu zeichnen, um das vollständige Muster zu sehen.





perf