Cache Reﬁll/Access Decoupling for Vector Machinesの論文を読む (1. 概要)

面白そうな論文があったので読んでみることにした。

Cache Reﬁll/Access Decoupling for Vector Machines

https://ieeexplore.ieee.org/document/1551005

Cache Reﬁll/Access Decoupling for Vector Machines
諸元
- 37th International Symposium on Microarchitecture (MICRO-37’04)
- Christopher Batten, Ronny Krashinsky, Steve Gerding, and Krste Asanovic
  - MIT Computer Science and Artiﬁcial Intelligence Laboratory
概要
- 背景
  - ベクトル・プロセッサは、メモリの帯域幅の要求を提言するためにキャッシュを使用する
- 課題
  - ベクトル・プロセッサは大量の未処理キャッシュミスを追加するハードウェアが必要
- 提案
  - ベクトル・リフィル・ユニット(VRU)を提案する
    - キャッシュ・ラインのリフィルを通常の実行に先駆けて実行する
  - アドレスのリクエストの要求を提言するためのベクトル・セグメント・アクセスを提案
- 結果
  - キャッシュが小さく、メモリレイテンシが800サイクルと長い場合でも、数kBのインフライトデータを維持することができる
- ベクトル・アーキテクチャは、データ並列性を使用するアーキテクチャ
- ベクトル・アーキテクチャをマイクロプロセッサと同じ部品で構成する場合の課題
  - 初期のスーパーコンピュータは、インターリーブされたSRAMメモリバンクを使用していた
  - 現在のマイクロプロセッサは汎用DRAM部品でメイン・メモリを使用している
  - ベクトル・マシンの設計者は、ベクトル・データ・キャッシュを追加することが増えている
- キャッシュを搭載することにことにより、スループットを大幅に向上させることができる
  - 既存のノンブロッキング・ベクター・キャッシュ設計
    - プライマリ・ミスを追跡し、リプレイ・キューでセカンダリ・ミスをマージしなければならないため複雑 [1, 11]。
    - ベクタ・レジスタまたは非連結ロード・データ・キュー[9]のいずれかに、すべての保留中のデータ・アクセスのためのエレメント・ストレージを確保しなければならない(???)
提案：ベクトル・リフィル・アクセスのデカップリング
- スカラ・ユニット
  - ベクトル・ユニットのためにコンパクトに符号化された命令をキューイングして先に実行
- ベクトル・リフィル・ユニット
  - ベクトル・メモリ命令を素早く事前実行して、それらが触れることになるラインのうち、キャッシュになくプリフェッチされるべき行を検出する。
    - 非指定的ハードウェア・プリフェッチ
  - ベクタメモリ命令が最終的に実行されるときに、キャッシュ内にすでにデータがあることを確実する
  - 利点：大量の保留中のミスを追跡してマージする必要がない
  - 利点：保留中のエレメント・アクセスに対するバッファリングが少なくて済む
背景：メモリの帯域幅 – 遅延積 (Bandwidth-Delay Products)
- サイクルあたりのピークメモリ帯域幅Bに、往復アクセスレイテンシLの積
  - メモリ・システムを飽和させるには、プロセッサは少なくとも(B/b)×L個の独立したbバイトのデータ・エレメントを同時にインフライトさせなけらばならない
  - Pentium-4
    - 約400サイクルのレイテンシ
    - 1サイクルあたり約2Bのメインメモリ帯域幅
    - 4Bの要素を200個インフライトさせる必要がある
  - Cray-X1
    - マルチプロセッサマシンで最大800サイクルのレイテンシ
    - 1サイクルあたり32Bのグローバルメモリ帯域幅
    - 8Bの要素を1600個インフライトさせる必要がある
課題：インフライトなメモリアクセスをサポートするためのハードウェア
- インフライトなメモリ・リクエストを管理するためのハードウェア
  - Access Management State
    - インフライト・アクセスを追跡するためのステート (MSHR?)
    - Unit-Stride / Stridedの場合は複数のアドレス情報をコンパクトにエンコードして管理する
  - Reserved Element Data Buffering
    - メモリシステムが返したデータを書き込むストレージ (キャッシュに書くまでの一時領域?)
    - リクエスト開始時にはReserved Element Data Bufferingを予約する必要がある
      - ストールを防ぐため？
- 各キャッシュ・ミスは多くのデータ・エレメントを取り込む
  - キャッシュ・ミスが発生するだけでメモリシステムを容易に飽和させることができる？
  - 先行するすべてのリクエストを発行するまで、次のミスを発生させるリクエストを発行できない
  - リクエストはそのラインが戻るまでバッファリングされていなければならない
提案： Vector Refill/Access Decoupling
- キャッシュ・データを前もってプリフェッチさせる
  - 必要なデータのみをフェッチすること
  - プロセッサがデータを必要とする前にフェッチすること
  - 有用なデータをキャッシュから対比させないこと
  - Refill/Access Decoupling
ベース・ライン・システム
- Non-Blocking Cache
  - タグ・アレイ
  - データ・アレイ
  - MSHR
    - プライマリ・ミス (最初にMSHRエントリに割り当てられたミス)
    - セカンダリ・ミス (既に割り当てられたMSHRエントリにヒットしたミス)
      - リプレイ・キューに割り当てられる

基本的なDecoupled Vector Processor
- 概要
  - CP(Control Proc)が先に実行される
  - ベクトルユニット用のメモリ・アクセス/計算コマンドをキューイングする
    - (Vector-CmdQ)
  - VEU: 計算ユニット
  - VLU: ロード・ユニット
  - VSU: ストア・ユニット
- ベクトル・ロードの動作
  - CPがまず、ベクトル・ロード・コマンドをVector-CmdQに送る
  - アドレスはVLU-CmdQに送られる
  - レジスタのライトバックはVEU-CmdQに送られる
  - VLUが長いベクトル・ロード・コマンドを複数の小さなサブブロックに分割する
  - 各サブブロックがVLDQを確保 à キャッシュ・リクエストを発行
    - ヒットするとVLDQにデータが格納される
    - VLDQからFIFOの順序でVEUにデータが渡される
基本的なDecoupled Vector Processor
- VLUが先行する距離
  - VEC-CmdQ/VSU-CmdQ, VLDQ, Replay Queue, Primary Tagの大きさによって制約される
- 重要な観点
  - メモリ・レイテンシが増加することによって、すべてのリソースがBandwidth-Delay積に比例する必要がある
  - 上記の図では、CPから発行後にメモリアクセスがキャッシュに到達後に
    - VEUが常に予約状態
    - VLDQとReplay Queue、Primary Miss Tagが常に予約状態

Vector Refill Unit
- VRUの導入
  - VLUと同じコマンドを受信する
  - VLUよりも同じキャッシュ・ラインのリフィル要求を先に発行する
  - リフィル・リクエストはデータをキャッシュに入れるだけ
- VRUの理想
  - VLUが常にキャッシュヒットするように十分に先行して実行すること
- 必要なリソース (Figure. 3)
  - Vector-CmdQを大きくする必要がある
  - VLUのアクセスはヒットすると仮定
    - VLUとVEUの間は小さくなるため、VLDQは小さくなる
  - メモリ・アクセスのレイテンシにより増加するリソース
    - Vector-CmdQとプライマリ・タグ
- VLUとVRUの相対的な定常速度を管理する必要がある
  - VRUが先行しすぎる à VLUがアクセスしていないラインが退避される
  - VLUがVRUを先行する à リフィル・アクセスのデカップリングの効果がなくなる
  - VLUとVRUをスロットリングすることで、レートと距離をうまく制約する