コンピュータアーキテクチャの論文を読んでいたのだが、どうもよく知らない項目がある。よく考えてみたらコンピュータアーキテクチャの最新トレンドも含め最近勉強量が不足していたので、ここらへんでもう一度復習しておきたい。せっかくなので海外の大学の講義資料を読んでみよう。

Advanced Computer Architecture

https://www.ece.ucsb.edu/~strukov/ece154BSpring2018/home.htm

Advanced Computer Architecture

3. 高度なキャッシュ最適化

1. ウェイ予測

ダイレクトマップの高速なタグ検索と、2ウェイSAキャッシュのミス率の低さを同時に達成するために、ウェイ予測とうい方式が考えられた。キャッシュにビットを追加して次にアクセスされるキャッシュブロックを予測できるようにする。

所望のブロックを選択できるようにマルチプレクサをや早めに設定しておき、1つのタグ比較を並列に実行することでキャッシュのデータを読み出す。

これにより精度を85％程度まで向上させることができる。欠点としては1～2サイクル必要となるとCPUパイプラインはつらい。命令キャッシュを使用するかL1データキャッシュを使用するか。MIPS R10KではオフチップのL2ユニファイドキャッシュを使用しており、ウェイ予測を使用していた。

この方式の欠点は、キャッシュアクセスのパイプライン化を難しくしてしまうことである。

2. Victimキャッシュ

ダイレクトマップのキャッシュにおいてスラッシングの問題に対して有効。L1キャッシュ中の20％～90％のキャッシュミスを削除できる。L1とVictimキャッシュは相補的な関係なある。L1キャッシュとVictimキャッシュは以下のどちらかの関係となる。

L1キャッシュでミスしてもVictimキャッシュでヒットする。
L1キャッシュでミスし、Victimキャッシュでもミスをする。

3. Critical word first and early start

Early restart : ブロック中の必要なワードが到着したら、すべてのブロックが到着するのを待つことなくCPUにデータを転送する。CPUは早期に実行を再開することができる。
Critical Word First : メモリに対してミスを発生させたワードを先に要求し、CPUに先に転送する。CPUはそれ以外のワードブロックを後で埋めようとする。ブロックサイズは非常に長くなっているため、Critical Word Firstは一般的に使用されている。

4. Merging write buffer

メモリにデータを書き込む際、ライトバッファを保持することでCPUは処理を継続する。バッファに変更されたブロックが含まれる場合、アドレスをチェックして、新しいデータのアドレスが有効な書き込みバッファエントリのアドレスと一致するかどうかを確認する。もしそうであれば、新しいデータはそのエントリにマージされる。

Sun T1(Niagara)プロセッサがライトマージを使用していた。

以下の例では、各アドレスへの書き込みはそれぞれライトバッファのエントリを使用しているが、アドレスとしては同じブロックに入っているため、1つのエントリにマージすることができる。

5. Nonblocking cache

キャッシュミスが発生しても次のメモリアクセスリクエストを受け続け、依存関係がない場合はキャッシュのリクエストをもらい続ける。

Nonblocking Cacheの性能だが、SPECINTとSPECFPでベンチマークを計測した。1回のミスを許すと、SPECINTにおいては平均で9％のミスペナルティが削減され、SPECFPでは12.5%のミスペナルティが削減された。2回のミスを許すと10%と16％となり、さらに64ミスまで増加させると更なる効果が得られた。

Nonblocking Cacheの実装にはアウトオブオーダ実行が必要であり、複数のアウトスタンディングメモリアクセスを受け付けるためにキャッシュコントローラが複雑になってしまう。パイプラインもしくはバンク化されたキャッシュが必要である。

6. Pipelined cache

キャッシュへの書き込みはキャッシュからの読み込みよりも時間がかかるため、パイプライン化する。

7. Multibanked cache

複数バンクに分割することにより、異なるアドレスへのアクセスを別のバンクに配置することで並列に処理を行う。単純な例として「シーケンシャルインタリーブ」の場合に性能を向上させることができる。

8. Compiler Optimizations

キャッシュの構成に合わせてプログラムの構成を最適化する。

コードをデータブロックのアクセスがシーケンシャルになるように変更する。
データがキャッシュに入ってしまうことを示す。キャッシュする必要のないものについては、キャッシュさせないことでキャッシュの無駄な動作を防ぐ。
今後使わないデータに関してはデータをKillし、不要なデータがキャッシュに存在しないようにする。

9. Prefetching

将来使用される命令とデータアクセスを予想し、あらかじめキャッシュに取り込んでおく。これに関しては様々な手法が存在している。

ハードウェアプリフェッチ
ソフトウェアプリフェッチ
ミックスドプリフェッチ

プリフェッチの問題

ベストタイミングでデータをプリフェッチして、キャッシュリクエストをヒットさせなければならない。このタイミングは速すぎても遅すぎてもならない。これを間違えるとキャッシュとバンド幅を汚してしまうことになる。

ハードウェア命令プリフェッチ

Alpha AXP 21064の命令プリフェッチではミス時にリクエストのブロックと後続のブロックを取得する。リクエストされたブロックはキャッシュに配置され、次のブロックは命令ストリームバッファに配置される。

ハードウェアデータプリフェッチ

ミスしたブロックとその後続のブロックを取得する。

One Block Lookahead(OBL)とう機構を用いて、ブロックbにアクセスが発生した場合にブロックb+1をプリフェッチさせる。

ストライドプリフェッチでは、ブロックb, b+N, b+2Nがアクセスされた場合、次にb+3Nをプリフェッチする。

ソフトウェアプリフェッチ

for (i = 0; i < N; i++) {
    prefetch(&a[i+1]); // プリフェッチ命令を挿入する。
    prefetch(&b[i+1]);
    SUM = SUM + a[i] * b[i];
}

例：ARM Cortex-A8 Cache

f:id:msyksphinz:20200314234108p:plain:w400

例 : Opteronの仮想アドレス

f:id:msyksphinz:20200314234119p:plain:w400

例 : OpteronのL1キャッシュ

f:id:msyksphinz:20200314234136p:plain:w400

FPGA開発日記

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

UCBのAdvanced Computer Architectureの講義資料を読む(6. 高度なキャッシュ最適化)

目次