Prédiction de branchement

Un processeur n'attend pas de savoir dans quel sens va un if : il devine et commence à travailler. Une bonne devinette est gratuite, une mauvaise jette le travail, soit environ 15 cycles perdus. La fréquence des bonnes devinettes dépend des données : la même boucle sur les mêmes rendements SPY coûte 8,3 fois moins de cycles une fois les rendements triés.

Un processeur fonctionne comme une chaîne de montage : pendant qu'une instruction s'exécute, les suivantes sont déjà lues et décodées. Un if casse la chaîne, car l'instruction suivante dépend de sa réponse, qui n'est pas encore prête. Le processeur fait donc une prédiction de branchement et avance dessus. Si elle est juste, rien n'est perdu. Si elle est fausse, le travail fait sur le mauvais chemin est jeté et la chaîne redémarre, ce qui coûte environ 15 cycles sur un cœur moderne, autant qu'une visite au cache L2. Nous notons le résultat d'un branchement True quand il est pris. Dans une boucle de trading, un branchement est par exemple if daily_return > 0, et le flux de ses résultats est simplement un True ou un False par jour.

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

Sur six jours, quatre ont eu un rendement positif : le branchement est donc pris quatre fois et non pris deux fois. Le prédicteur le plus simple, toujours pris, se trompe exactement sur les deux résultats False. Il a raison aussi souvent que le branchement est pris, et il ignore l'historique.

Les vrais processeurs utilisent l'historique. Le prédicteur à 1 bit se souvient de ce que le branchement a fait la dernière fois et devine la même chose. Il est bon quand les résultats viennent par séries, mais il paie deux fois chaque résultat isolé : une fois à son arrivée et une fois à la reprise de la série. Le prédicteur à 2 bits corrige cela avec un compteur de 0 à 3 qui s'arrête aux deux bouts. Il devine « pris » à 2 et 3, avance d'un cran vers chaque résultat, et il lui faut donc deux résultats d'affilée contre sa devinette pour changer d'avis. Nous partons de « non pris » pour le 1 bit et de 1 pour le compteur.

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. 1Le compteur avance d'un cran vers le résultat et s'arrête à 0 et 3 : c'est ce qui le rend saturant.

Sur les séries de quatre, les deux prédicteurs se trompent trois fois (la première devinette et les deux changements). Avec un seul False isolé parmi des résultats pris, le 1 bit se trompe trois fois et le 2 bits une seule, car le compteur passe de 3 à 2 et devine encore « pris ». C'est pourquoi les vrais processeurs préfèrent les compteurs. Gardez en tête l'autre face : quand les résultats n'ont aucun motif, aucun prédicteur ne peut faire mieux que deviner la réponse la plus fréquente.

Pour transformer les erreurs en temps, on les additionne : chaque branchement coûte un cycle de base et chaque erreur ajoute une pénalité de 15. Voici l'expérience qui donne son nom à ce cours : prenons les 4 000 premiers rendements quotidiens de SPY et exécutons le branchement return > 0 deux fois, sur les rendements dans l'ordre des dates et sur les mêmes rendements triés. Trier ne change rien aux nombres, seulement à leur ordre, mais cela transforme les résultats d'un pile ou face en deux longues séries : tous les False d'abord et tous les True ensuite.

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

Dans l'ordre des dates, 2 200 des 4 000 rendements sont positifs : le branchement est pris 55 % du temps et il passe d'une réponse à l'autre presque sans motif. Toujours pris se trompe 1 800 fois, le 1 bit 2 035 fois et le 2 bits 1 950 fois. Les prédicteurs à mémoire font même pire que le simple pari, car ils suivent chaque bascule. Triés, les résultats sont 1 800 False suivis de 2 200 True, et le 2 bits ne se trompe que 2 fois. Le coût passe de 33 250 à 4 030 cycles, 8,3 fois moins, avec exactement les mêmes données et la même boucle.

Le labo suit le cours : les résultats d'un branchement, les trois prédicteurs, le coût en cycles, le flux trié et une étude des rendements SPY dans l'ordre des dates et triés.

• Fonction · questionS'appuie sur
• taken_sequence(values, threshold)Que fait le branchement pour chaque valeur ?De l'arithmétique simple
• always_taken_mispredicts(outcomes)Combien de fois « toujours pris » se trompe-t-il ?De l'arithmétique simple
• one_bit_mispredicts(outcomes)Et un prédicteur qui retient le dernier résultat ?De l'arithmétique simple
• two_bit_mispredicts(outcomes)Et un compteur saturant ?De l'arithmétique simple
• cycles(n_branches, mispredicts)Combien cela coûte-t-il en tout ?De l'arithmétique simple
• sorted_stream(values, threshold)Et si les valeurs étaient triées d'abord ?taken_sequence
• study(bars)Combien le tri fait-il gagner sur SPY ?sorted_streamtwo_bit_mispredictscycles

Sujet suivant : le projet final réunit toute la compétence. On vous donne une table de ticks et une charge qui la lit ; vous la réorganisez en lignes, en colonnes ou en blocs, comptez les défauts de cache de chaque disposition avec le cache que vous avez construit, les chiffrez avec le modèle de latence du premier sujet et prouvez quelle disposition gagne.