メモリ投機を支援する CMPキャッシュコヒーレンスプロトコルの検討 東京大学大学院 情報理工学系研究科 坂井修一研究室 豊島 隆志 田代 大輔 バルリ ニコ デムス 坂井修一 発表の流れ 背景 スレッド投機実行モデル キャッシュコヒーレンスプロトコル メモリ投機 コンシステンシ プロトコル 評価・結果 まとめ 背景 Instruction Level Parallelism -ILP- の限界 Thread Level Parallelism -TLP- の探求 資源は潤沢になりつつある SMP, CMP, SMT, etc… 過去の資産から少ない労力でTLPを抽出したい ソースには手を加えない スレッド投機実行 コンパイラ、ハードウェアによる実現 バイナリには手を加えない ランタイム環境、ハードウェアによる実現 発表の流れ 背景 スレッド投機実行モデル キャッシュコヒーレンスプロトコル メモリ投機 コンシステンシ プロトコル 評価・結果 まとめ スレッド投機実行～構成～ Sequential program L1 ICache Thread Predictor Compiler binary execution Decode/ Rename Rename Map L1 ICache Decode/ Rename Rename Map Instruction Queue Instruction Queue Func. Func. Func. Func. Unit Unit Unit Unit Func. Func. Func. Func. Unit Unit Unit Unit Register File Register File Reg. Comm. IF Thread Validation Unit binary L1 DCache with Spec. Support L1 DCache with Spec. Support L2 Cache スレッド投機実行～構成～ Sequential program L1 ICache Thread Predictor Compiler binary execution Decode/ Rename Rename Map L1 ICache Decode/ Rename Rename Map Instruction Queue Instruction Queue Func. Func. Func. Func. Unit Unit Unit Unit Func. Func. Func. Func. Unit Unit Unit Unit Register File Register File Reg. Comm. IF Thread Validation Unit binary L1 DCache with Spec. Support L1 DCache with Spec. Support L2 Cache スレッド投機実行～スレッド分割～ コンパイラにより静的に分割 データ依存・制御依存 レジスタデータ依存 先行→後続方向のみ許す 静的に解析 レジスタ通信命令により解決 メモリデータ依存 投機 キャッシュ コヒーレンスプロトコル スレッド投機実行～構成～ Sequential program L1 ICache Thread Predictor Compiler binary execution Decode/ Rename Rename Map L1 ICache Decode/ Rename Rename Map Instruction Queue Instruction Queue Func. Func. Func. Func. Unit Unit Unit Unit Func. Func. Func. Func. Unit Unit Unit Unit Register File Register File Reg. Comm. IF Thread Validation Unit binary L1 DCache with Spec. Support L1 DCache with Spec. Support L2 Cache スレッド投機実行～スレッド割り当て～ スレッド予測器による動的割り当て 制御依存は投機により処理 ラウンドロビン方式 スレッドの破棄 制御依存予測の失敗 スレッドの再実行 メモリ投機の失敗 スレッド投機実行～構成～ Sequential program L1 ICache Thread Predictor Compiler binary execution Decode/ Rename Rename Map L1 ICache Decode/ Rename Rename Map Instruction Queue Instruction Queue Func. Func. Func. Func. Unit Unit Unit Unit Func. Func. Func. Func. Unit Unit Unit Unit Register File Register File Reg. Comm. IF Thread Validation Unit binary L1 DCache with Spec. Support L1 DCache with Spec. Support L2 Cache スレッド投機実行～レジスタ同期～ プロセッサコア レジスタ同期命令 同期用ネットワーク スレッド投機実行～構成～ Sequential program L1 ICache Thread Predictor Compiler binary execution Decode/ Rename Rename Map L1 ICache Decode/ Rename Rename Map Instruction Queue Instruction Queue Func. Func. Func. Func. Unit Unit Unit Unit Func. Func. Func. Func. Unit Unit Unit Unit Register File Register File Reg. Comm. IF Thread Validation Unit binary L1 DCache with Spec. Support L1 DCache with Spec. Support L2 Cache スレッド投機実行～メモリ投機～ 一次データキャッシュ 各プロセッサ毎に個別 メモリ投機の支援 ロード・ストア 投機ロード・投機ストア 巻き戻し コンシステンシの確保 バージョン管理 発表の流れ 背景 スレッド投機実行モデル キャッシュコヒーレンスプロトコル メモリ投機 コンシステンシ プロトコル 評価・結果 まとめ メモリ投機支援 ロード・ストア コンシステンシがとれるよう注意する 投機ロード 非投機状態に移行するまで投機ロードを記録 投機ロード後にストアされたら投機ミスを検出 投機ストア 投機ストアは２次キャッシュ以降に伝えない 非投機状態になるまでフラッシュできない 巻き戻し キャッシュを無効化するだけで良い コンシステンシの確保 スレッドの境界をまたいで・・・ 競合するロードがストアを追い越さない 投機ロードミスの検出でフォロー 競合するストアがロードを追い越さない ストアの伝送（無効化・更新）に工夫が必要 本来の時系列を遡って伝送しない 競合するストア同士で追い越しが起きない ストアの伝送（無効化・更新）に工夫が必要 ストアの発行元を記録し、正しくバージョン管理する ストアの伝送先 競合するストアがロードを追い越さない 本 来 の ス レ ッ ド 実 行 順 序 load from X store to X store to X load from X 投 機 実 行 store to X load from X store to X load from 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 投 機 実 行 store to X load from X store to X load from X プロトコル 無効化方式（Invalidate-based） 投機ロードはワード単位で記録 遅延無効化（ワード単位／ライン単位） ブロードキャスト（有／無） 更新方式（Update-based） 投機ロードはワード単位で記録 遅延無効化（ワード単位／ライン単位） ブロードキャスト（有／無） ブロードキャスト あるプロセッサがアクセスしたメモリは、近い将来に別の プロセッサもアクセスする可能性が高い、という性質を利 用した一種のプリフェッチ リード・ブロードキャスト ある一次キャッシュがリードミスした際、同じラインを無効状 態として保持しているキャッシュは同時に更新する ライト・ブロードキャスト ある一次キャッシュがライトミスした際、同じラインを無効状 態として保持しているキャッシュは同時に更新する（更新方 式でも無効状態が存在し得るため） 更新 ｖｓ ブロードキャスト どちらも、無効化された値をアクセス前に有効に戻す事 でキャッシュミスを減らす手法 スレッド投機実行では、ライト以外の要因でもキャッシュ が無効になり得、更新のみではカバーできない スレッドの破棄 遅延無効化 更新とブロードキャストでは、有効に戻すタイミングが異 なる 早過ぎると・・・有効に戻す事のできる対象範囲が減少 遅すぎると・・・投機ミス、キャッシュミスを招く キャッシュディレクトリ 無効化方式 Line Tag Conditions State 2bit … Word 7 Condition Obsolete Speculative 1bit 1bit Data 64bit Loaded Stored 1bit 1bit Word 0 Conditions … Data … 64bit Loaded Stored 1bit 1bit 更新方式 Line State Tag Conditions Invalid Shared Modified Obsolete 1bit 1bit 1bit 1bit 投機ミス判定のための追加情報 … Word 7 Data 64bit Conditions Store Loaded 4bit 1bit Word 0 … Data … 64bit Conditions Store Loaded 4bit 1bit コンシステンシ確保のための追加情報 状態遷移図 無効化方式 更新方式 Input/Output Input/Output PrRd/BusRd PrRd/BusRd PrRd/BusRd PrSquash/- Invalid BusInv/PrSquash/- PrRd/BusRd PrCommit/- PrCommit/ BusCommit PrCommit/BusCommit PrWr/- Modified Clean PrCommit/BusCommit,BusFlush Clean PrSquash/PrCommit/ BusCommit,BusFlush PrCommit/ BusCommit Shared BusRd/- BusRd/Forward BusRd/Forward BusUpd/PrSquash/PrCommit/BusCommit PrWr/- BusInv/PrSquash/PrCommit/BusFlush Invalid BusUpd/PrSquash/PrCommit/BusCommit,BusFlush PrCommit/BusFlush PrRd/BusRd PrWr/BusRd,BusInv Modified PrWr/BusRd PrWr/BusRd,BusInv Shared Clean PrWr/BusUpd BusRd/Forward BusRd/Forward PrCommit/BusCommit PrWr/BusUpd PrCommit/ BusFlush,BusCommit Shared Modified PrRd/BusRd,BusUpd 発表の流れ 背景 スレッド投機実行モデル キャッシュコヒーレンスプロトコル メモリ投機 コンシステンシ プロトコル 評価・結果 まとめ 評価 評価環境 サイクルベース・シミュレータ スーパースカラプロセッサ アウトオブオーダ実行 分岐予測 スレッド投機実行 スレッド予測器 レジスタ同期 メモリ投機 SPEC CINT95 専用の最適化コンパイラにより生成 評価 パラメータ パラメータ 値 プロセッサユニット数 ４ユニット パイプライン段数 ７段 フェッチ・発行・リタイヤ幅 ４命令 物理レジスタ数 １２８レジスタ 機能ユニット ALU×２ ロード・ストア×２ リオーダバッファ ６４エントリ 発行キュー ２０エントリ ロード・ストアキュー ２０エントリ BTB １０２４エントリ Bimodalスレッド予測器 ４０９６エントリ １次命令キャッシュ 16KB 64Bライン 2-way セットアソシアティブ アクセスレイテンシ 1サイクル １次データキャッシュ 64KB 64Bライン 2-way セットアソシアティブ アクセスレイテンシ 2サイクル ２次キャッシュ 理想化（常にヒット） アクセスレイテンシ 16サイクル 無効化レイテンシ 3サイクル 更新レイテンシ 5サイクル 0 099.go 124.m88ksim 126.gcc 129.compress 130.li 132.ijpeg 134.perl 147.vortex AVG inv inv_robr upd upd_rwbr inv inv_robr upd upd_rwbr 70 inv inv_robr upd upd_rwbr inv inv_robr upd upd_rwbr inv inv_robr upd upd_rwbr inv inv_robr upd upd_rwbr inv inv_robr upd upd_rwbr inv inv_robr upd upd_rwbr inv inv_robr upd upd_rwbr キャッシュミス率 [%] 結果 ブロードキャストの効果 80 Hit by broadcast rate Miss rate 60 50 40 30 20 10 0 upd_rwbr upd inv_robr inv upd_rwbr upd inv_robr inv upd_rwbr upd inv_robr inv upd_rwbr upd inv_robr inv upd_rwbr upd inv_robr inv upd_rwbr upd inv_robr inv upd_rwbr upd inv_robr inv upd_rwbr upd inv_robr inv upd_rwbr upd inv_robr inv サイクルあたりの投機ミス数 結果 投機ミス 0.018 0.016 0.014 0.012 0.01 0.008 0.006 0.004 0.002 099.go 124.m88ksim 126.gcc 129.compress 130.li 132.ijpeg 134.perl 147.vortex AVG 0 099.go 124.m88ksim 126.gcc 129.compress 130.li 132.ijpeg 134.perl inv_robr inv upd_rwbr upd inv_robr inv inv_robr inv upd_rwbr upd inv_robr inv upd_rwbr upd inv_robr inv upd_rwbr upd inv_robr inv upd_rwbr upd inv_robr inv upd_rwbr upd inv_robr inv upd_rwbr upd upd_rwbr upd inv_robr inv upd_rwbr upd 相対実行サイクル 結果 相対実行サイクル 2.5 2 0.05差 1.5 1 0.5 147.vortex AVG 発表の流れ 背景 スレッド投機実行モデル キャッシュコヒーレンスプロトコル メモリ投機 コンシステンシ プロトコル 評価・結果 まとめ まとめ メモリ投機の可能な各種キャッシュコヒーレンスプロトコ ルを設計、シミュレータ上に実装し、性能を比較評価した スレッド投機実行時のキャッシュミスが、更新方式、ブ ロードキャスト方式によって、どの程度軽減されているか 調べた 更新方式とブロードキャストの組み合わせが性能はもっ とも高い どちらか１つを採用するなら性能は僅差で更新方式が勝る 設計コストやバスのトラフィックを考えるとブロードキャスト を選択するメリットも大きい
© Copyright 2024 ExpyDoc
