FPGA開発日記

カテゴリ別記事インデックス https://msyksphinz.github.io/github_pages , English Version https://fpgadevdiary.hatenadiary.com/

高性能プロセッサの分岐予測のサーベイ論文を読んで分岐予測について学ぶ (1. 分岐予測のサーベイと分類)

最近はプロセッサアーキテクチャについて再度復習しようかと思っている。

読んでいるのはA Survey of Techniques for Dynamic Branch Predictionという論文で、新規技術の解説ではないのだが、現在の有名どころの分岐予測技術についてまんべんなく解説してくれている論文だ。 これを読み進めていこうと思っている。といっても最初の方はからにGoogle翻訳に頼っているけれども。次からはもう少し自分の言葉でまとめる。

  • A Survey of Techniques for Dynamic Branch Prediction
    • Sparsh Mittal

https://arxiv.org/pdf/1804.00261.pdf

本稿では動的分岐予測手法について概説する。 図1は、このホワイトペーパーの構成を示しています。

  • 第2章 : BPに関する簡単な背景を説明し、BPを管理する上での課題について説明し、研究成果の概要を示します。
  • セクション3と4では、一般的な分岐と特定の分岐用のいくつかのBPデザインについて説明し、
  • セクション5ではハイブリッドBPデザインについて説明します。
  • 第6節では血圧の正確性を改善するための技術について論じる。
  • セクション7では、ニューラルBPとそれらの実装オーバーヘッドを削減するための手法について説明します。
  • セクション8では、BPの待ち時間とエネルギーのオーバーヘッドを削減するための手法について説明します。
  • 私たちは将来の課題に言及して第9章でこの論文を締めくくります。

ページ制限内で何十年ものBP調査を効果的に要約するために、我々は以下の方法でこの論文の範囲を制限しなければなりませんでした。我々は、条件付き分岐がとられるかどうかを推測する分岐方向(結果)予測に焦点を合わせる。分岐目標予測や、間接分岐または無条件分岐の手法は含みません。静的分岐予測は分岐を予測するためにソースコードの知識またはコンパイル分析のみを使用します[5]一方、動的予測は分岐の時変および入力依存実行パターンを説明します。静的予測の手法と動的BPを支援するためのコンパイラのヒントを含む手法は別の調査に値するので、ここではそれらを含めず、動的予測のみに焦点を当てます。我々は一般的に各論文の重要な考えに焦点を当てており、選択された定量的結果のみを含む。この論文は、コンピュータアーキテクト、チップ設計者、そしてパフォーマンスの最適化に興味を持っている研究者に役立つと期待されています。

2. Background and Motivation

ここでは、分類法[6]、値局所性[7]、静的BP [5]、複数BPの比較評価[2, 3, 8–10]および商用のBPについての議論[3,11-15]について議論を行います。3.1章では、BPの命令体系[6, 16]について議論します。

2.1 有用な用語と概念

分岐の種類(Types of branches)：分岐の種類

  • 条件付きまたは無条件
  • 直接または間接
    • 直接分岐 : 命令自体の中で目標アドレスを指定する
    • 間接分岐 : 目標アドレスが見つかるべき場所(例えばメモリまたはレジスタ位置)を指定する。

偏った分岐(Biased branches)：ほとんどの場合、分岐は実行されるか、行われないかのどちらかです。偏った分岐というのは、分岐の結果が、分岐・非分岐のどちらかに偏ったような状況を意味します。例えばfor文で、ループ中は大部分が分岐しますが、最後の1回だけは分岐せずに抜けます。このような一度だけ分岐が成立しないような分岐ケースを、偏った分岐(Biased Branches)と呼んでいます。

偏った分岐は方向に変化がないことを示すもの[17]またはパーセプトロンの重みが最大/最小値に達したもの[18]として検出されます。

エイリアシングまたは干渉(Aliasing or interference)：複数の無関係な分岐が同じ予測器エントリを使用すると、それらはエイリアシングと呼ばれる破壊的な干渉を発生させます。図2は分岐間の干渉の例を示しています。 予測が変化しない場合、干渉は中立(無害)、予測を修正する場合は正(有益)、誤予測を引き起こす場合は負(有害)です。 一般的にワーキングセットが大きくなると、有害なエイリアシングの方が無害なエイリアシングよりも影響が大きくなる。

f:id:msyksphinz:20190623232602p:plain

サイドプレディクター：一般的に使用されるBP(例：TAGE [20])は、ほとんどの分岐を正確に予測できますが、他の比較的頻度の低い分岐クラスを予測することはできません。そのような分岐を予測するために、全体的な正確性を改善するために、主BPを副(補完的または補完的または修正子とも呼ばれる)BPで増強することができます。

ローカルおよびグローバルの履歴(Local and global history)：いくつかの分岐はそれら自身の実行パターンによってのみ予測することができ、したがって「ローカル」(または自己もしくは分岐ごとの)履歴に基づいて動くと言われています。たとえば、for(i = 1; i <= 4; i ++)というループ制御分岐を考えます。ループ本体の最後でループテストを実行すると、パターン$(1110)n$が表示されます。したがって、最後の3つのインスタンスの分岐の結果を知ることで、次の結果を予測できます。

比較すると、以前の分岐の実行が候補分岐の結果についてのヒントを提供できる場合、そのような分岐は相関していると言われ、この情報を利用するBPは「グローバル履歴」に取り組むと言われます。分岐相関は、複数の理由で発生する可能性があります[8, 21]。

  1. 2つの分岐が関連情報によって決定されてもよく、例えば図3(a)において分岐B1が取られると、分岐B3も取られる。
  2. 1つの分岐の結果が他の分岐の結果に影響を及ぼす条件を変更する、例えば図3(B)において、分岐B4が取られるとB5は取られない。この場合と前の場合が「方向相関(Directional correlation)」の例です。

f:id:msyksphinz:20190623232630p:plain

  1. 現在の分岐にたどり着いたパスについての情報は、相関分岐の前の分岐についてのヒントを与えてくれます。例えば、図3(c)では、分岐B8の方向は分岐B9の方向と相関していないが、分岐B8が経路上で観察された(すなわち、前のK個の分岐の1つであった)場合、分岐B9の結果は予測された。このような相関は「経路内相関(Path-based correlation)」と呼ばれる。経路履歴は現在の分岐への経路上に見られる分岐からなり、パターン履歴は現在の分岐に至った分岐の結果(方向)パターンを示す。パターン履歴と比較して、パスの履歴の使用は相関のより良い活用を可能にします[8]。

一般に、より多数の分岐を考慮すると、例えば図3(a)において、B1の結果を知るだけではB3を予測するのに十分ではなく、B1とB2の両方の結果を知ることはB3を予測するのに十分です。ニューラルBPに関するいくつかの研究では、分岐間の相関の強さの尺度としてパーセプトロン重みを使用していることに注意してください[2, 22–24]。

基本ブロック(Basic Block) : 基本ブロックは、分岐のないコードの最大長シーケンスです[25]。例外が発生しない限り、BB内の命令は常に一緒に実行されます。

評価基準(Metrics) : BPを評価するための評価基準に関しては、研究では、

  • パフォーマンス(IPC)
  • 予測ミスされた分岐の数(1キロ命令あたり)
  • フェッチされたマイクロオペマイクロ操作ごとのフラッシュ
  • 予測ミスのペナルティ[26]

などが挙げられる。

2.2 Challenges in managing BPs

以下に示すように、BPの効果的な設計と運用にはいくつかの課題があります。

  • 高速な分岐予測の必要性 : 分岐予測は、分岐命令と分かってから高々1サイクル以内に予測を行う必要があり、非常にクリティカルな論理を必要とする。しかし、複雑な予測を行えば行うほど論理は増大し、クリティカルパスは長くなってしまう。クロック周波数の向上とともに、分岐予測のアクセスサイクルは1サイクルを超える場合が発生してしまう。また、分岐予測のアップデートも高速に実行する必要があり、これも性能に大きな影響を与える。
  • 面積オーバヘッドと分岐予測の精度 : 分岐予測テーブルのサイズを大きくするだけでは、予測精度は向上しない。例えば、2BP + gskew BPのサイズを64kBから1MBに増やしても分岐予測の精度はほとんど向上しない。分岐予測の精度と面積オーバヘッドを考慮する必要がある。
  • エネルギーオーバヘッド : 分岐予測はほぼ毎サイクルアクセスが発生するため、エネルギー消費が大きくオーバヘッドになりやすい。分岐予測器のエネルギー効率の向上は不可欠となっている。
  • 分岐予測のウォームアップ : コンテキストスイッチングの発生などにより、分岐予測のウォームアップの向上は重要な要素となりうる。ウォームアップが長ければ、現代のコンテキストスイッチングの多いプロセッサでは真の効率を発揮することができないかもしれない。
  • 分岐予測のタグにおける課題 : 分岐予測は失敗しても性能に影響を与えるだけで機能的な影響を与える事は無い。したがってタグを実装する必要は必ずしも無いが、エイリアシングが発生することを防ぐためにタグは必要となる。分岐予測においてタグサイズとエントリサイズと比較して必ずしも無視できるサイズではないので(キャッシュの場合はキャッシュのエントリの方がタグよりもはるかに大きいため無視できる)、タグの実装方法について考える必要がある。
  • ハイブリッド分岐予測 : 分岐予測は各種予測アルゴリズムを複数動かして、そのコンポーネントから正確なものを選択する(セレクタ、もしくはチューザ)。複数の予測器から正確な予測器を選択するためのメタ予測器が必要となり、単独に予測器を使う場合に比べて有効性が低下する可能性がある。
  • プロセッサ設計要因 : パイプライン化した場合、GHRを更新する前に同じアドレスに対して分岐予測が必要なる可能性があり、アウトオブオーダコアの分岐予測はインオーダのコアよりも予測精度が低くなる可能性が高い。また、パイプラインが深くなると分岐解決時間が長くなり、分岐予測ミスの可能性とコストが増大する。