メモリ投機を支援する CMPキャッシュコヒーレンスプロトコルの検討 東京大学大学院 情報理工学系研究科 坂井修一研究室 豊島 隆志　田代 大輔　バルリ ニコ デムス　坂井修一

発表の流れ 背景 スレッド投機実行モデル キャッシュコヒーレンスプロトコル メモリ投機 コンシステンシ プロトコル 評価・結果 まとめ

背景 Instruction Level Parallelism -ILP- の限界 Thread Level Parallelism -TLP- の探求 資源は潤沢になりつつある SMP, CMP, SMT, etc… 過去の資産から少ない労力でTLPを抽出したい ソースには手を加えない コンパイラ、ハードウェアによる実現 バイナリには手を加えない ランタイム環境、ハードウェアによる実現 スレッド投機実行

発表の流れ 背景 スレッド投機実行モデル キャッシュコヒーレンスプロトコル メモリ投機 コンシステンシ プロトコル 評価・結果 まとめ

L1 DCache with Spec. Support Thread Validation Unit スレッド投機実行～構成～ Sequential program L1 ICache Rename Map Decode/ Rename Instruction Queue Register File Func. Unit L1 DCache with Spec. Support Thread Predictor Thread Validation Unit L2 Cache Reg. Comm. IF Compiler binary execution binary

L1 DCache with Spec. Support Thread Validation Unit スレッド投機実行～構成～ Sequential program binary Compiler binary execution L1 ICache Rename Map Decode/ Rename Instruction Queue Register File Func. Unit L1 DCache with Spec. Support Thread Predictor Thread Validation Unit L2 Cache Reg. Comm. IF

スレッド投機実行～スレッド分割～ コンパイラにより静的に分割 データ依存・制御依存 レジスタデータ依存 メモリデータ依存 先行→後続方向のみ許す レジスタデータ依存 静的に解析 レジスタ通信命令により解決 メモリデータ依存 投機 キャッシュ コヒーレンスプロトコル

L1 DCache with Spec. Support Thread Validation Unit スレッド投機実行～構成～ Sequential program binary Compiler binary execution L1 ICache Rename Map Decode/ Rename Instruction Queue Register File Func. Unit L1 DCache with Spec. Support Thread Predictor Thread Validation Unit L2 Cache Reg. Comm. IF

スレッド投機実行～スレッド割り当て～ スレッド予測器による動的割り当て スレッドの破棄 スレッドの再実行 制御依存は投機により処理 ラウンドロビン方式 スレッドの破棄 制御依存予測の失敗 スレッドの再実行 メモリ投機の失敗

L1 DCache with Spec. Support Thread Validation Unit スレッド投機実行～構成～ Sequential program binary Compiler binary execution L1 ICache Rename Map Decode/ Rename Instruction Queue Register File Func. Unit L1 DCache with Spec. Support Thread Predictor Thread Validation Unit L2 Cache Reg. Comm. IF

スレッド投機実行～レジスタ同期～ プロセッサコア レジスタ同期命令 同期用ネットワーク

L1 DCache with Spec. Support Thread Validation Unit スレッド投機実行～構成～ Sequential program binary Compiler binary execution L1 ICache Rename Map Decode/ Rename Instruction Queue Register File Func. Unit L1 DCache with Spec. Support Thread Predictor Thread Validation Unit L2 Cache Reg. Comm. IF

スレッド投機実行～メモリ投機～ 一次データキャッシュ コンシステンシの確保 各プロセッサ毎に個別 メモリ投機の支援 ロード・ストア 投機ロード・投機ストア 巻き戻し コンシステンシの確保 バージョン管理

発表の流れ 背景 スレッド投機実行モデル キャッシュコヒーレンスプロトコル メモリ投機 コンシステンシ プロトコル 評価・結果 まとめ

メモリ投機支援 ロード・ストア 投機ロード 投機ストア 巻き戻し コンシステンシがとれるよう注意する 非投機状態に移行するまで投機ロードを記録 投機ロード後にストアされたら投機ミスを検出 投機ストア 投機ストアは２次キャッシュ以降に伝えない 非投機状態になるまでフラッシュできない 巻き戻し キャッシュを無効化するだけで良い

コンシステンシの確保 スレッドの境界をまたいで・・・ 競合するロードがストアを追い越さない 競合するストアがロードを追い越さない 投機ロードミスの検出でフォロー 競合するストアがロードを追い越さない ストアの伝送（無効化・更新）に工夫が必要 本来の時系列を遡って伝送しない 競合するストア同士で追い越しが起きない ストアの発行元を記録し、正しくバージョン管理する

ストアの伝送先 競合するストアがロードを追い越さない 本来のスレッド実行順序 load from X store to X 投機実行 load from X store to X store to X load from X

ストアの遅延伝送 本来のスレッド実行順序 store to X 直前のスレッド完了時に store to X 遅延伝送（無効化・更新） する必要がある store to X load from X load from X 投機実行 load from X store to X store to X load from X

無効なストア伝送 競合するストア同士で追い越しが起きない 本来のスレッド実行順序 ストア元のスレッドを記憶・比較 load from X することで対処 store to X store to X load from X 投機実行 load from X store to X store to X load from X

プロトコル 無効化方式（Invalidate-based） 更新方式（Update-based） 投機ロードはワード単位で記録 遅延無効化（ワード単位／ライン単位） ブロードキャスト（有／無） 更新方式（Update-based）

ブロードキャスト あるプロセッサがアクセスしたメモリは、近い将来に別のプロセッサもアクセスする可能性が高い、という性質を利用した一種のプリフェッチ リード・ブロードキャスト ある一次キャッシュがリードミスした際、同じラインを無効状態として保持しているキャッシュは同時に更新する ライト・ブロードキャスト ある一次キャッシュがライトミスした際、同じラインを無効状態として保持しているキャッシュは同時に更新する（更新方式でも無効状態が存在し得るため）

更新 ｖｓ ブロードキャスト どちらも、無効化された値をアクセス前に有効に戻す事でキャッシュミスを減らす手法 スレッド投機実行では、ライト以外の要因でもキャッシュが無効になり得、更新のみではカバーできない スレッドの破棄 遅延無効化 更新とブロードキャストでは、有効に戻すタイミングが異なる 早過ぎると・・・有効に戻す事のできる対象範囲が減少 遅すぎると・・・投機ミス、キャッシュミスを招く

キャッシュディレクトリ 無効化方式 更新方式 投機ミス判定のための追加情報 コンシステンシ確保のための追加情報 Line Tag State Condition Word 7 … Word 0 Data Conditions Obsolete Speculative Loaded Stored 2bit 1bit 64bit 更新方式 Line Tag State Conditions Word 7 … Word 0 Data Invalid Shared Modified Obsolete Store Loaded 1bit 64bit 4bit 投機ミス判定のための追加情報 コンシステンシ確保のための追加情報

状態遷移図 無効化方式 更新方式

発表の流れ 背景 スレッド投機実行モデル キャッシュコヒーレンスプロトコル メモリ投機 コンシステンシ プロトコル 評価・結果 まとめ

評価 評価環境 サイクルベース・シミュレータ SPEC CINT95 スーパースカラプロセッサ スレッド投機実行 アウトオブオーダ実行 分岐予測 スレッド投機実行 スレッド予測器 レジスタ同期 メモリ投機 SPEC CINT95 専用の最適化コンパイラにより生成

評価 パラメータ パラメータ 値 プロセッサユニット数 ４ユニット パイプライン段数 ７段 フェッチ・発行・リタイヤ幅 ４命令 物理レジスタ数 １２８レジスタ 機能ユニット ALU×２ ロード・ストア×２ リオーダバッファ ６４エントリ 発行キュー ２０エントリ ロード・ストアキュー BTB １０２４エントリ Bimodalスレッド予測器 ４０９６エントリ １次命令キャッシュ 16KB 64Bライン 2-way セットアソシアティブ アクセスレイテンシ 1サイクル １次データキャッシュ 64KB 64Bライン アクセスレイテンシ 2サイクル ２次キャッシュ 理想化（常にヒット） アクセスレイテンシ 16サイクル 無効化レイテンシ 3サイクル 更新レイテンシ 5サイクル

結果 ブロードキャストの効果

結果 投機ミス

結果 相対実行サイクル 0.05差

発表の流れ 背景 スレッド投機実行モデル キャッシュコヒーレンスプロトコル メモリ投機 コンシステンシ プロトコル 評価・結果 まとめ

まとめ メモリ投機の可能な各種キャッシュコヒーレンスプロトコルを設計、シミュレータ上に実装し、性能を比較評価した スレッド投機実行時のキャッシュミスが、更新方式、ブロードキャスト方式によって、どの程度軽減されているか調べた 更新方式とブロードキャストの組み合わせが性能はもっとも高い どちらか１つを採用するなら性能は僅差で更新方式が勝る 設計コストやバスのトラフィックを考えるとブロードキャストを選択するメリットも大きい