分岐予測

プロセッサは if がどちらに進むかを待たずに、予想して作業を始めます。当たれば無料で、外れれば作業は捨てられ、約15サイクルを失います。どれだけ当たるかはデータ次第で、同じSPYのリターンに対する同じループでも、リターンをソートすると必要なサイクルは8.3分の1になります。

プロセッサは組み立てラインのように動きます。ある命令の実行中に、次の命令はすでに読み込まれデコードされています。if はこのラインを断ち切ります。次の命令がその答えに依存し、答えはまだ出ていないからです。そこでプロセッサは分岐予測を行って先に進みます。当たれば何も失いません。外れれば、誤った道で行った作業は捨てられてラインがやり直しとなり、最近のコアで約15サイクル、L2キャッシュに行くのと同じだけかかります。分岐が成立したときの結果を True と書きます。トレードのループでは、たとえば if daily_return > 0 が分岐で、その結果の流れは1日につき True か False が1つというだけのものです。

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

6日のうち4日はプラスのリターンだったので、分岐は4回成立し2回成立しません。最も単純な予測器である常に成立は、2つの False の結果でだけ外れます。分岐が成立する割合だけ当たり、履歴は無視します。

実際のプロセッサは履歴を使います。1ビット予測器は、分岐が前回したことを覚えて同じ予想をします。結果が連続して並ぶときは優秀ですが、突発的な結果1つにつき2回外れます。その結果が来たときと、連続が再開したときです。2ビット予測器は、両端で止まる0から3のカウンタでこれを解決します。2と3で「成立」と予想し、結果ごとに1段ずつ動くので、考えを変えるには予想に反する結果が2回続く必要があります。1ビットの予想は「不成立」から、カウンタは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. 1カウンタは結果に向かって1段動き、0と3で止まります。これが「飽和」の意味です。

4つの連続では、どちらの予測器も3回外れます（最初の予想と2回の切り替わり）。成立が続く中に False が1つだけあると、1ビット予測器は3回、2ビット予測器は1回しか外れません。カウンタが3から2に下がるだけで、まだ「成立」と予想するからです。実際のプロセッサがカウンタを好むのはこのためです。ただし逆の面も覚えておいてください。結果にパターンがなければ、どの予測器も、より多い答えを予想する以上のことはできません。

ミスを時間に換算するため足し合わせます。分岐1回あたり基本1サイクル、ミス1回あたり15のペナルティです。この講義の題名にもなった実験をしましょう。SPYの最初の4,000日分のリターンで、分岐 return > 0 を2回走らせます。日付順のリターンと、同じリターンをソートしたものです。ソートは数値を変えず順序だけを変えますが、結果をコイン投げから2つの長い連続に変えます。先にすべての False、その後にすべての 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

日付順では4,000件のうち2,200件のリターンがプラスで、分岐は55%の確率で成立し、ほぼパターンなしに答えが入れ替わります。「常に成立」は1,800回、1ビットは2,035回、2ビットは1,950回外れます。記憶を持つ予測器は、すべての切り替えに付いていくため、単純な予想より悪くなります。ソートすると結果は1,800個の False のあとに2,200個の True が続き、2ビット予測器は2回しか外れません。コストは33,250から4,030サイクルへ、8.3分の1になります。データもループもまったく同じです。

ラボは講義の順に進みます。分岐の結果、3つの予測器、サイクルでのコスト、ソート済みの流れ、そして日付順とソート後のSPYリターンの研究です。

• 関数 · 問い前提
• taken_sequence(values, threshold)各値で分岐はどうなるか？単純な算術
• always_taken_mispredicts(outcomes)「常に成立」は何回外れるか？単純な算術
• one_bit_mispredicts(outcomes)直前の結果を覚える予測器は？単純な算術
• two_bit_mispredicts(outcomes)飽和カウンタは？単純な算術
• cycles(n_branches, mispredicts)全体でいくらかかるか？単純な算術
• sorted_stream(values, threshold)先に値をソートしたら？taken_sequence
• study(bars)SPYでソートはどれだけ節約するか？sorted_streamtwo_bit_mispredictscycles

次のトピック：最終課題でスキル全体をまとめます。ティックのテーブルと、それを読むワークロードが与えられ、行・列・ブロックのどれかに並べ替えて、作ったキャッシュで各配置のミスを数え、最初のトピックのレイテンシモデルでコストを出し、どの配置が勝つかを示します。