パタヘネ5.1～5.4節です。ようやく下巻に到達しました。今回はあまり低レイヤーの話はなく、キャッシュを実現するためのデータ構造とアルゴリズムの話になります。
こうやって教科書を読んで自分の言葉で説明するのは絶対必要なことだしやめる気は無いですが、一方でこれしかないとトレンド技術や特定のミドルウェア・フレームワークへの対応力が無い人だと思われても仕方ないので、別の形でアウトプットしていく必要を最近感じました（唐突）。よりアピールに効く活動を並行していきたいと思います。去年ひとまず資格系をある程度取ったので今年はその時間を実学にまわしていきたいです。
5.1
プログラムが情報にアクセスするパターンは局所性の法則に従う事が多い。局所性は2種類に分けられる。1つは時間的局所性で、ある項目が参照された場合、同じ項目が再び参照されることが多いことを意味する。2つ目は空間的局所性で、ある項目が参照された場合、付近の項目が続けて参照されることが多い。コンピュータのメモリには容量・速度・価格の間にトレードオフがある。小容量・高速・高価格のメモリをキャッシュとして用い、局所性を利用すれば再度アクセスされると予想されるデータを置けば動作速度を向上させることができると予想される。キャッシュは複数階層で実装される事が多い。上位レベルと下位レベルでやり取りするデータの最小単位をブロックもしくはラインという。要求されたデータが上位レベル上に存在することをヒット、存在しないことをミスという。キャッシュにヒットしたときデータにアクセスするのにかかる時間をヒット時間、ミスしたとき下位レベルからデータを取ってきて上位のキャッシュを置き換え、プロセッサに取り込むのにかかる時間をミス・ペナルティという。
5.2
メモリのアクセス時間はSRAM・DRAM・フラッシュ半導体メモリ・磁気ディスクの順番となる。SRAMはアクセス時間0.5~2.5ns、DRAMは50~70ns、フラッシュ半導体メモリは5000~50000ns、磁気ディスクは5000000~20000000nsとなる。
SRAMへのアクセス時間はいかなるデータでも一定である。読み出し・書き込みでは異なることがある。SRAMはリフレッシュする必要がなく、アクセス時間はサイクル時間と非常に近い。SRAMは1ビットに6~8個のトランジスタを使用する。待機状態にいるときは最小電力しか使用しない。過去キャッシュ用にチップとして提供されていた事があるが、現在はプロセッサ上に統合されており、単独のチップとしては廃れた。
DRAMではキャパシタに電荷を貯める形で値を保持する。アクセスには1個のトランジスタを使用する。そのためSRAMより記憶密度が高く価格が低い。一方キャパシタに電荷を貯める性質上定期的にリフレッシュが必要である。リフレッシュでは値を読み出して同じ値を書き戻す。DRAMでは2レベルのデコード方式が取られており、読み出しサイクルの直後に書き込みサイクルを続けて行全体をリフレッシュできる。DRAMでは繰り返しデータにアクセスされることに備えてバッファを持っている。また、プロセッサとのインターフェースを改善するためDRAMにクロックが追加されたSDRAMという物がある。これによりメモリとプロセッサの同期を取る時間が省略できる。クロックの立ち上がりエッジと質下がりエッジの両方でデータを転送するSDRAMをダブルデータレート（DDR）SDRAMという。この方式の最新バージョンはDDR4と呼ばれる。DDR4では1回のアクセスで4つのバンクを順にアクセスし、バンド幅を4倍にしている。この順次アクセス方式をアドレス・インターリービングという。また、別軸の分類として、サーバー用のメモリをデュアル・インライン・メモリモジュール（DIMM）という。
フラッシュメモリは電気的に消去書き込み可能な読み出し専用メモリEEPROMの一種である。書き込み時にビットが劣化する性質がある。フラッシュメモリの制御ユニットはよく書き込まれているブロックへの書き込みを別のあまり書き込まれていないブロックに振り替えることで、劣化を遅らせようとする。これをウェア・レベリングという。
磁気ディスクは、磁性体が塗布された数枚のプラッタで構成されている。ディスク上のデータを読み書きするため可動アームに取り付けられた読み/書きヘッドという電磁コイルがプラッタ表面からわずかに浮いた位置に配置されている。ディスクは多数の同心円（トラック）に分割されており、トラックは更にセクターに分割される。セクターは512～4096バイト記録している。複数枚のプラッタ上の同一円周上に存在するトラックをまとめてシリンダという。ヘッドは全て同時に動くのでシリンダー上のデータを並列的に読むことになる。ヘッドが移動することをシークといい、それにかかる時間をシーク時間という。磁気ディスクへのアクセス速度はシーク時間と、ほしいセクタが回ってくるのを待つ回転待ち時間からなる。ただし、ほとんどのディスクはキャッシュを持っておりそこからのアクセスを考慮するとより高速になる。また、従来同一シリンダ上に隣接するブロックが存在していたが近年はそうではない。シーケンシャルアクセスで最高の性能を達成するためにブロックはディスク上で蛇行して配置される。
5.3
最も単純なキャッシュの方式はダイレクトマップ方式である。この方式では、元データが配置されているメモリ上のアドレスから、キャッシュ上の位置が一意に決まる。具体的には、(ブロックのアドレス) % (キャッシュ中のブロック数)でキャッシュ上のブロックがきまる。キャッシュ中のブロック数が2のべき乗なら、アドレスから下位数ビットを取ってくるだけでブロックを出せる。要するにアドレスの下位部分を使ったハッシュマップを作ってデータを保持する。キャッシュ上の同じブロックに複数のアドレスが対応するので、今何のアドレスの値が入っているか、別に情報として保持しておく必要がある。そのために元データアドレスの上位ビットをタグとして保持する。また、キャッシュに一回もデータが書き込まれていないことを表す有効ビットを付加する必要もある。
キャッシュ上のブロックサイズは全体サイズに対して大きすぎるとヒット率が低くなる。メモリアドレス間の競合が増え、すぐ別のアドレスのデータでキャッシュが置き換わってしまうためである。ヒット率に加え、ミス・ペナルティも増大する。
キャッシュミスが起きたとき、プロセッサはパイプラインをストールさせる。例えば、命令フェッチでキャッシュミスした場合を考える。キャッシュミスしたとわかったときにはPCは4繰り上げられているので、メモリからの読み出しのため、PC-4をメモリに送る。次にメモリからの読み出しを指示し、その完了を待つ。読みだしたらキャッシュの該当ブロックに書き込む。また、タグを更新する。有効ビットがオフだったならオンにする。最後に命令実行を最初から再開する。キャッシュに命令が入っているので、必ずヒットする。一方で、書き込みの際の挙動は異なる。書き込み内容をキャッシュにだけ反映させると主記憶と乖離が出る。キャッシュと主記憶の一貫性を保つ最も単純な方法はライトスルーである。この方法では書き込みの際に毎回キャッシュと主記憶の両方を更新する。キャッシュミスが発生した場合、一旦主記憶から当該メモリの内容をキャッシュに読み込んでから上書きする。この方式の設計は単純だが、主記憶の更新がオーバーヘッドとなる。主記憶を毎回更新しないようにする方式として、ライトバッファを保持し、バッファが満杯になった時書き込むようにすることが考えられる。しかしこの方法は主記憶への書き込みのスループットが書き込み発生頻度より小さいと役に立たない。バッファが常に満杯になるためである。ライトスルーに代わる方式としては、ライトバックが存在する。書き込み発生時は一旦キャッシュにだけ書き込む。同じブロックへの別の書き込みが発生して初めて、当該ブロックの内容を主記憶に書き込む。この方式では主記憶の処理速度を越えた書き込み要求が出た場合の改善効果が大きい。しかし、ライトスルーより設計が複雑となる。
5.4
CPU時間は
CPU時間=(CPU実行クロック数+メモリ・ストール・クロック数)×クロック・サイクル時間
で求められる。メモリ・ストール・クロック数がキャッシュミスだけに依存すると仮定する。メモリ・ストール・クロック数は
メモリ・ストール・クロック数=読み出しストール・クロック数+書き込みストール・クロック数
で表される。読み出しストール・クロック数は
読み出しストール・クロック数=プログラムあたりの読み出し件数×読み出しミス率×読み出しミス・ペナルティ
で表される。一方、書き込みでは、ライトスルー方式の場合
書き込みストール・クロック数=(プログラムあたりの書き込み件数×書き込みミス率×書き込みミス・ペナルティ)+書き込みバッファストール
となる。
ここまででの説明では、メモリ上のデータアドレスからキャッシュ上のブロックが一意に特定できるダイレクトマップ方式を使ってきた。この方式の対極がフル・アソシアティブ方式である。データアドレスからは一切キャッシュ上の位置は特定できない。中間的な設計がセット・アソシアティブ方式である。この方式ではデータアドレスからキャッシュ上の位置の候補が数個特定される。セット・アソシアティブ方式ではブロックが含まれるセット位置は ブロック番号%キャッシュ中のセット数 で与えられる。セット中のどこに所望の値があるかわからないのでセット内の要素を全て見る必要がある。
一個のアドレスがキャッシュ上の何個の位置に対応するかという値を連想度という。フルアソシアティブ方式では全ブロック数が連想度となる。セット・アソシアティブ方式を用いるとキャッシュ上の値の更新でどのブロックを更新するかという選択肢が生まれる。一般的に用いられるのはLRU(least recently used)方式である。連想度を増加させるとキャッシュヒット率が上がる。
キャッシュ内のブロックの探し方について考える。ダイレクトマップ方式では求める値はあるとすれば一箇所だった。セット・アソシアティブ方式では複数箇所にわたって候補ブロックが存在するので、それらに並列的にアクセスする必要がある。また、アクセスしたブロックのタグが探しているアドレスのものと一致するかの照合と、一致したブロックの選択が必要となる。そのため比較器とマルチプレクサが余計に必要となり、比較・選択の時間がかかる。これが連想度を上げることに対するオーバーヘッドとなる。
置き換え対象ブロックにLRUを使う場合、最後にそのブロックにアクセスされたのはいつかという情報が必要となる。2ウェイ・セット・アソシアティブ方式ならどちらの要素が最後にアクセスされたかというビットを持っておけばいい。一方連想度が上がると実現が難しくなる。
キャッシュは複数階層で構成される事が多い。これをマルチレベルキャッシュという。1次キャッシュはヒット時間を最小化してクロックサイクルを短縮することに専念し、2次キャッシュはミス率を減らして主記憶にアクセスする際の長いミスペナルティを削減することに専念する。
キャッシュの性質を活用したソフトウェアの例として、行列積を考える。単純に要素にアクセスするとキャッシュサイズを超え、キャッシュミスによるペナルティを支払うことになる。一方、キャッシュサイズに応じたブロックに行列を区切り、ブロックごとに行列積を計算することでヒット率が上がり、高速化できる。
コメント