21. ---

    メモリ階層

• RAM(Random Access Memory)：理想的には整数（address）で添え字が付けられたＮ語の記憶領域。取り出しと格納は添え字で指定された語に対してのみ行われ、どちらも同様に早い。
• しかし、格納できる語数（大きさ）　←トレードオフ→　アクセスの早さ
• ⇒　小さな高速メモリ（高頻度アクセス）と大きな低速（安価）メモリ（その他のデータ）の組み合わせ
• しかし、この使い分け、管理をプログラマが行うのは大変。⇒　キャッシュ機構
• キャッシュ機構の下でプロセッサがアドレスxの値にアクセスする際には：

1. キャッシュをアクセス。
2. キャッシュになければ（cash miss）主記憶をアクセス。
3. 主記憶の内容をキャッシュにコピー。これで次回からはキャッシュで見つかる（キャッシュ・ヒット、cash hit）。
4. 場所を空ける必要があれば古いものを主記憶に掃き出す。

1. キャッシュ機構

• 直接マップ方式：　

1. メモリを2^wバイトづつワードに区切る。
2. 2^lワードづつブロックに分ける（キャッシュ・ブロック）。
3. ブロックを2^m個のグループ（キャッシュ・ライン）に分ける。グループ内のブロックはタグで区別できる。
4. キャッシュは2^m個のエントリを持ち、各グループ内から1ブロックをキャッシュに格納し、格納したブロックを区別するタグを記録する。

1ワード2^wバイト、1ブロック2^lワード、キャッシュ・エントリの数2^m個、アドレス空間2ⁿバイト。

• キャッシュの構成は他にもset associative方式などがあるが、最適化に関しては直接マップ方式について考えればよい。
• 読み出しポリシは前節のとおり。
• 書き出しポリシは下表のように分類される。

• 多層キャッシュ

• プロセッサのバイト・アクセス

• コンパイラは実行命令数あたりのキャッシュミスを減らすよう最適化する。

1. キャッシュ・ブロックの整列

• 典型的なキャッシュ・ブロックのサイズ（8ワード前後）は典型的なオブジェクトのサイズに似ている（似せてある？）。⇒　あるオブジェクトのフィールドを読むと、そのオブジェクトの別のフィールドもキャッシュされている可能性が高い。
• キャッシュブロックの境界にまたがるオブジェクトは複数のキャッシュ・ブロックを同時に占有する。→　跨がないで一個のキャッシュ・ブロックに載せられれば一回の読み取りでそのオブジェクトのフィールドがすべてキャッシュ上。
• ⇒　オブジェクトを不必要に別のブロックへ分割しないことで実行効率がよくなる。具体的には：

1. 順にオブジェクトを並べるが、ブロックの残りの大きさがオブジェクトに足りなければ次のブロックの先頭までスキップする。
2. オブジェクトを2のべき乗ごとのサイズ別に分類し、それぞれをキャッシュブロックに敷き詰める。

• 基本ブロックを命令「オブジェクト」と考えると整列は基本ブロックの配置にも有効。
• ⇒　基本ブロックもデータ同様キャッシュブロックを跨がないようにする。（特に、高頻度で実行されるブロックがキャッシュをまたがないようにすると効果的。）
• ⇒　高頻度で実行されるブロックと低頻度で実行されるブロックを同じキャッシュ・ブロックに載せない。

（497pのコードでxがめったに真にならないならば、基本ブロックQの実行頻度は低い。この場合、21.4(a)より21.4(b)のような配置のほうがキャッシュを無駄に占有しない。）

• また、幾つかのマシンでは分岐命令の飛び先が、ある決まった2のベキ乗語数のブロックの境界に整列されている必要がある。
• さらに、現代のマシンは命令をk語（kは2のベキ乗、通常は2〜4）づつ読み込むので整列されていないと無駄な命令を読み込むことになる。
• 最適化コンパイラは基本ブロックの配列を行うフェーズを持つ。（命令選択とレジスタ割付の後）

• トレース・スケ―ジュ―リング（8.3節）によって高頻度で実行されるブロックを一続きのキャッシュブロックに並べられる。条件分岐でのトレースは分岐予測（20.3節）によって決定できる。

1. 先読み

• 読み込みがキャッシュ・ミスに遭うと1次キャッシュで7〜10サイクル、2次キャッシュで70〜100サイクル遅れる。必要なデータが前もってわかっていれば、コンパイラが先読み（prefetch）を促す命令を差し挟める。

• 例のループ（例：内積（dot product）次ページの図）を素直に実行すると順に配列（大きさNがキャッシュブロックよりも十分大きい場合。）をアクセスする過程でB/W（B：ブロック・サイズ、W：ワード・サイズ）の割合でキャッシュ・ミスが起こる。

• 典型的な場合で1/8か1/4。キャッシュ・ミス一回あたりの遅延は典型的には7cycleか14cycle（2命令同時実行マシン）。これは高率過ぎる。（90年代後半の計算機では動的な実行順序の変更で減少するとはいえ…。）

• 先読みはソフトウェア・パイプライン（20章）の技術による命令の遅延実行によって代替できる。特に、命令の実行順を動的に変更できるプロセッサならば、コンパイラが何もしなくても同様の効果が達成できる。（例の左(a)）。
• しかし、（例に挙がっている11命令分程度の1次キャッシュならともかく）2次キャッシュでのミスによる遅延（例で言えば約200命令、ループ約29周分。）を隠そうとすると一時的な記憶領域が増大する。
• 先読みではそのようなことはない。（例の右（b）。）

上図はテキストの図21.5に印を付けたもの。

• 先読み命令はプロッセッサに対して、キャッシュ上に必要なデータを持ってくるように示唆するヒント。
• プロセッサは停止せず、ページ・フォルト等の例外的な事態では無視される。
• 成功すれば読み込み時にはキャッシュから読み取れ、失敗時には通常のキャッシュ・ミスになる。どちらにせよプログラムは正しく動く。
• 最近の多くのマシンが先読みを指示する命令を備えている。
• 先読み命令を備えていないものでも停止しない読み込み(load)命令を備えていれば代用できる。（ただしこの場合、load/storeを行うユニットがフルに使われる一方で、演算ユニットが暇しているようなメモリ・バウンドなプログラムでは効果がない。これはキャッシュに直接ヒントを与える先読み命令とは違う。）
• 順に各ワードにアクセスするような場合はそれらの内の数語は同一ブロック上。⇒　各ワード毎に先読みしなくても良い。（501ページの例：16byteブロック、4byteワードとし、if文でmod演算を行って必要な時だけ先読み。）
• 先読みする場所を指定するパラメータKの大きさはキャッシュ・ミス時の遅れ（ここでは2次キャッシュについて200命令）とループ一周分の命令数（ここでは7命令）とループ一周分で進む添え字の量（ここでは1ワード4byte分）から200 * 4 / 7 = 114.3をブロックサイズの倍数に切り上げてK = 128
• 図21.5(b)の例ではキャッシュ・ミス時の遅れ（ここでは1次キャッシュについて11命令）とループ一周分の命令数（ここでは7命令）とループ一周分で進む添え字の量（ここでは1ワード4byte分）から11 * 4 / 7 = 6.3をブロックサイズの倍数に切り上げてK = 16
• ループの展開（図21.6左側）や二重ループ（図21.6右側）を使うならmod演算を含むif文はいらない。

• 503ページの例：Nがキャッシュ・サイズより大きければ順次アクセスすると添え字がキャッシュ・ブロックを横切るたびにwrite missが発生。

• forループについて実際に先読み命令を差し挟むアルゴリズムについては参考文献Mowry 他[1992]を参照。

1. ループ交換

• 配列で幾つか続きのデータをアクセスすることがしばしばある。すると最内ループで外側のループの添え字が変わっても同じ値を参照する場合が発生する。
• 例 504ページの上側：B[i,j+1,k]はjに関する次のループではB[i,j,k]として参照されるが、その間に内側のループで配列Bについて3P個、配列AについてP個のデータへのアクセスがあるので恐らくキャッシュから追い出される。
• 上の問題はjとkのループを交換すれば解決できる。
• 例 504ページ下側：B[i,jk]B[i,j-1,k]のおかげで必ずhitする。
• このような交換が可能であるかどうかはデータ依存グラフを作ってみる必要がある。
• 反復(j,k)が反復(j’,k’)に依存するとは：

• このような場合にループを交換すると結果が違ってしまうので不適当。

1. ブロック化

• ブロック化とは、データの一部について計算を完了させてから次の一部の計算に取りかかること。
• 例：行列の掛け算（505ページ上側）：

• 行列AとBがキャッシュに載りきる大きさならば、jループ中で一回づつC[i,j]への書きこみでキャッシュ・ミスが発生する以外、計算途中でキャッシュ・ミスは発生しない。
• しかし以下では、キャッシュが2cN個（ここで1 < c < N）の要素（浮動小数点数）しか載せられない場合を考える。
• 例えば、N=50、つまり50x50の行列について浮動小数点数が8byteの大きさでキャッシュが8Kbyteある場合、c=10。
• この場合、最内ループでのB[k,j]は必ずキャッシュ・ミス。
• 何故なら、（キャッシュは20N=1,000個の要素しか保持できないのに）Bのあるセルにアクセスしてからもう一度アクセスするまでの間には（N²=2,500個の要素を持つ）B全体がキャッシュに送り込まれているから前の値は必ず追い出されている。
• jを最外側に持ってくるとAについて同様のことが起きるので、ループ交換は助けにならない。
• 解決策は図のようにCのc×cの大きさの部分小行列を計算するためにAの行c個（大きさcN）とBの列c個（大きさcN）について計算すること（図21.7左側）。
• こうすると読みこまれたAとBの部分はc回再利用されるのでAとBの部分を送り込むのにかかっていた2c²N回のキャッシュ・ミスが2cNになります。
• こうするとキャッシュ・ミスは、c²N回実行される最内ループ一回あたり2 cN/( c²N)= 2/cまで減ります。
• 最外側に小行列を必要なだけの(N/c)²個計算する二重ループを書き足して出来上がり。

• この1度に1ブロックづつ計算を完了させる最適化技法をブロック化といいます。
• 最適化コンパイラは多重ループを持つプログラムに対し、この変換を自動的に行います。
• 但し、ループが互いに依存していないことが重要です。上の例では小行列の計算は独立に行えます。

• 例では、C[i,j]の計算が毎回キャッシュ・ミスしていましたが、ここでC[i,j]を（メモリ階層を一段引き上げて）レジスタに載せてしまいます。
• このレジスタにキャッシュする技法がスカラ置換最適化です。（507ページ上段の例）
• これによって最内ループにおける書き出しと読みこみが半分になります。

• 複数次キャッシュ等についても最適化できる。
• さらにレジスタもメモリ階層の一部と考えてブロック化できる。
• 例：507ページ中段：32個の浮動小数点レジスタがある時、c×cループの部分を書き換えてAの行の一部d個をレジスタにキャッシュする。（Tという配列で表現。）

• 添え字ではアクセスできないレジスタをキャッシュに使うにはループの展開が必須。
• 例：507ページ下段：レジスタにキャッシュすることをあらわしていた配列Tを一時変数に展開。（例はd=3。しかしd=25くらいがもっともらしい。）
• 相変わらずBから読みこむ必要はあるが、Aの値はキャッシュされc回再利用されるので最内ループのメモリへのアクセスはほぼ半減する。
• ハイテクコンパイラは同一のループに以下を行うハメになります。

1. ガベージ・コレクションとメモリ階層

• ガベージ・コレクションはランダムにメモリに触るので参照に局所性がなく「キャッシュ・スラッシャー（打ち据えるものの意味？）」という評判があった。
• しかし、ガベージ・コレクタは実際にメモリ管理プログラムの1つであり、参照の局所性を維持するよう改善できる。

• 世代別コピー・コレクタを用いる際には最若世代を二次キャッシュに収めるようにすべき。（一次キャッシュは狭すぎる。）
• ⇒　毎回のメモリ割り当てはキャッシュにhitする。
• ＆　ガベージ・コレクションもキャッシュ内で行える。
• 世代を上げる際にはwrite missが発生。

• （コピー・コレクタ等）順次割り付けて順次初期化を行う方式はブロックサイズ／ワードサイズの割合でwrite missを起こす。
• しかし現代の幾つかのwrite validateなwrite missポリシを持つマシンではそれほど深刻なコストではない。
• ただ、それ以外のポリシのマシンではそうは行かない。⇒ 先読みが有効。
• この場合、アドレスaに割り当て時にa + Kの先読みを行えば良いから、ループの解析は不要。
• Kは関連するキャッシュの遅れと計算に対する割り当て頻度を比較考慮すれば良い。大概のマシンにおいてK=100で十分。

• オブジェクトxがオブジェクトyを指すならそれらは同一ブロックに載せたほうがよい。
• 深さ優先でポインタを調べるコピー・コレクタならば、これはある程度まで自動的に達成される。
• これは広さ優先探索では成り立たない。
• ⇒　（オブジェクトの大きさに対してキャッシュ・ブロックが大きければ）深さ優先探索の方が効率が改善される。

• Boehm[1991]で：