Sprungvorhersage

Ein Prozessor wartet nicht ab, wohin ein if geht: Er rät und fängt an zu arbeiten. Ein richtiger Tipp ist gratis, ein falscher wirft die Arbeit weg, etwa 15 Takte verloren. Wie oft er richtig rät, hängt von den Daten ab: Dieselbe Schleife über dieselben SPY-Renditen kostet 8,3-mal weniger Takte, sobald die Renditen sortiert sind.

Ein Prozessor arbeitet wie ein Fließband: Während eine Anweisung läuft, werden die nächsten schon geholt und dekodiert. Ein if unterbricht das Band, denn die nächste Anweisung hängt von seiner Antwort ab, die noch nicht fertig ist. Also macht der Prozessor eine Sprungvorhersage und läuft darauf voraus. Stimmt sie, geht nichts verloren. Stimmt sie nicht, wird die Arbeit auf dem falschen Pfad weggeworfen und das Band startet neu, was auf einem modernen Kern etwa 15 Takte kostet, so viel wie ein Besuch im L2-Cache. Wir schreiben das Ergebnis eines Sprungs als True, wenn er genommen wird. In einer Trading-Schleife ist ein Sprung etwa if daily_return > 0, und der Strom seiner Ergebnisse ist einfach ein True oder False pro Tag.

def taken_sequence(values, threshold):    return [bool(value > threshold) for value in values]def always_taken_mispredicts(outcomes):    return sum(1 for outcome in outcomes if not outcome)returns = [0.004, -0.012, 0.007, 0.001, -0.003, 0.009]outcomes = taken_sequence(returns, 0)print(outcomes)print(always_taken_mispredicts(outcomes), "misses out of", len(outcomes))

[True, False, True, True, False, True]
2 misses out of 6

Von sechs Tagen hatten vier eine positive Rendite, der Sprung wird also viermal genommen und zweimal nicht. Der einfachste Prädiktor, immer genommen, liegt genau bei den zwei False-Ergebnissen falsch. Er liegt so oft richtig, wie der Sprung genommen wird, und ignoriert die Vorgeschichte.

Echte Prozessoren nutzen die Vorgeschichte. Der 1-Bit-Prädiktor merkt sich, was der Sprung zuletzt getan hat, und rät dasselbe. Er ist gut, wenn die Ergebnisse in Serien kommen, zahlt aber für jedes Ausreißer-Ergebnis doppelt: einmal beim Auftreten und einmal, wenn die Serie weitergeht. Der 2-Bit-Prädiktor behebt das mit einem Zähler von 0 bis 3, der an beiden Enden stehen bleibt. Er rät „genommen“ bei 2 und 3, macht einen Schritt zu jedem Ergebnis und braucht daher zwei Ergebnisse in Folge gegen seinen Tipp, um umzudenken. Wir starten den 1-Bit-Tipp bei „nicht genommen“ und den Zähler bei 1.

def one_bit_mispredicts(outcomes):    guess = False    wrong = 0    for outcome in outcomes:        if guess != outcome:            wrong += 1        guess = outcome    return wrongdef two_bit_mispredicts(outcomes):    counter = 1    wrong = 0    for outcome in outcomes:        if (counter >= 2) != outcome:            wrong += 1        counter = min(3, counter + 1) if outcome else max(0, counter - 1)1    return wrongruns = [True] * 4 + [False] * 4 + [True] * 4stray = [True] * 6 + [False] + [True] * 6for name, stream in (("runs", runs), ("one stray", stray)):    print(name, "| 1-bit", one_bit_mispredicts(stream), "| 2-bit", two_bit_mispredicts(stream))

runs | 1-bit 3 | 2-bit 5
one stray | 1-bit 3 | 2-bit 2

1. 1Der Zähler macht einen Schritt zum Ergebnis und bleibt bei 0 und 3 stehen: Das macht ihn sättigend.

Bei den Vierer-Serien liegen beide Prädiktoren dreimal falsch (der erste Tipp und die zwei Wechsel). Bei einem einzelnen False zwischen genommenen Ergebnissen liegt der 1-Bit-Prädiktor dreimal falsch und der 2-Bit-Prädiktor nur einmal, weil der Zähler von 3 auf 2 fällt und weiter „genommen“ rät. Deshalb bevorzugen echte Prozessoren Zähler. Behalten Sie die andere Seite im Kopf: Haben die Ergebnisse kein Muster, kann kein Prädiktor besser sein als das Raten der häufigeren Antwort.

Um Fehler in Zeit umzurechnen, addieren wir sie: Jeder Sprung kostet einen Basistakt, und jeder Fehler addiert eine Strafe von 15. Nun das Experiment, nach dem diese Lektion benannt ist: Nehmen Sie die ersten 4.000 täglichen SPY-Renditen und führen Sie den Sprung return > 0 zweimal aus, über die Renditen in Datumsreihenfolge und über dieselben Renditen sortiert. Das Sortieren ändert nichts an den Zahlen, nur an ihrer Reihenfolge, aber es verwandelt die Ergebnisse von einem Münzwurf in zwei lange Serien: erst alle False, dann alle True.

def cycles(n_branches, mispredicts, penalty=PENALTY, base=BASE_CYCLES):    return base * n_branches + penalty * mispredictsdef sorted_stream(values, threshold):    return taken_sequence(sorted(values), threshold)returns = [float(r) for r in load_bars()["close"].pct_change().dropna()][:4000]for name, stream in (("unsorted", taken_sequence(returns, 0)), ("sorted", sorted_stream(returns, 0))):    wrong = two_bit_mispredicts(stream)    print(name, "| always", always_taken_mispredicts(stream), "| 1-bit", one_bit_mispredicts(stream), "| 2-bit", wrong, "|", cycles(len(stream), wrong), "cycles")

unsorted | always 1800 | 1-bit 2035 | 2-bit 1950 | 33250 cycles
sorted | always 1800 | 1-bit 1 | 2-bit 2 | 4030 cycles

In Datumsreihenfolge sind 2.200 der 4.000 Renditen positiv, der Sprung wird also zu 55 % genommen und wechselt fast ohne Muster zwischen den Antworten: Immer-genommen liegt 1.800-mal falsch, der 1-Bit-Prädiktor 2.035-mal und der 2-Bit-Prädiktor 1.950-mal. Die Prädiktoren mit Gedächtnis sind sogar schlechter als der einfache Tipp, weil sie jedem Wechsel folgen. Sortiert sind die Ergebnisse 1.800 False gefolgt von 2.200 True, und der 2-Bit-Prädiktor liegt nur 2-mal falsch. Die Kosten fallen von 33.250 auf 4.030 Takte, 8,3-mal weniger, mit denselben Daten und derselben Schleife.

Das Labor folgt der Lektion: die Ergebnisse eines Sprungs, die drei Prädiktoren, die Kosten in Takten, der sortierte Strom und eine Studie der SPY-Renditen in Datumsreihenfolge und sortiert.

• Funktion · FrageBaut auf
• taken_sequence(values, threshold)Was tut der Sprung bei jedem Wert?Einfache Arithmetik
• always_taken_mispredicts(outcomes)Wie oft liegt „immer genommen“ falsch?Einfache Arithmetik
• one_bit_mispredicts(outcomes)Und ein Prädiktor, der sich das letzte Ergebnis merkt?Einfache Arithmetik
• two_bit_mispredicts(outcomes)Und ein sättigender Zähler?Einfache Arithmetik
• cycles(n_branches, mispredicts)Was kostet das alles?Einfache Arithmetik
• sorted_stream(values, threshold)Und wenn die Werte zuerst sortiert würden?taken_sequence
• study(bars)Was spart das Sortieren bei SPY?sorted_streamtwo_bit_mispredictscycles

Nächstes Thema: Das Abschlussprojekt führt die ganze Fähigkeit zusammen. Sie erhalten eine Tick-Tabelle und eine Last, die sie liest, ordnen sie in Zeilen, Spalten oder Blöcken neu an, zählen die Cache-Fehlzugriffe jeder Anordnung mit dem selbst gebauten Cache, bewerten sie mit dem Latenzmodell des ersten Themas und beweisen, welche Anordnung gewinnt.