第6章 メモリ階層

6章について
この章では、メモリ階層ごとの特性や回転ディスク、半導体ドライブといったデバイスがどのように配置されているかについて書かれていました。
メモリ階層の仕組みや局所性の原理を学ぶことで効率的なプログラムの書き方を学んでいきます。
以下まとめです。

メモリ階層

メモリ階層とデータ移動の流れを理解すれば、上位階層にデータを保持するようなプログラムを書くことが可能となる。

メモリ階層のイメージ

## 上に行くほど小さく速い(高価)
L0: CPUレジスタ
L1: キャッシュ(SRAM)
L2: キャッシュ(SRAM)
L3: キャッシュ(SRAM)
L4: メイン･メモリ(DRAM)
L5: ローカルの二次記憶(ローカル･ディスク)
L6: リモートの二次記憶(分散ファイル･システム, ウェブ･サービス)
## 下に行くほど大きく遅い(安価) 

データの格納場所によるコストの違い

収納場所	コスト(サイクル数)
CPU レジスタ	0
キャッシュ	4 ~ 75
メインメモリ	数百
ディスク	数千万

最上位のレジスタとディスクで、かなりの差があることが分かりますね。

ストレージの技術

初期のコンピュータの RAM は数キロバイトしかなかったが、1982年に10 メガバイト。2015年でその30 万倍と進化している。
そして現在では、ストレージ容量は数年ごとに 2 倍の早さで増加し続けている。

ランダム･アクセス･メモリ(RAM)

RAM にはスタティック(SRAM)とダイナミック(DRAM)の二種類が存在する。

SRAM : DRAMに比べて高速で高価だが容量が小さい。キャッシュ･メモリに用いられる。

DRAM : 主記憶の他、グラフィック･システムのフレーム･バッファに用いられる。

DRAMの種類

定期的に新しい種類が現れ、それぞれアクセス速度を改善するための最適化がなされている。

FPM DRAM : 同じ行への連続したアクセスは行バッファと直接的にはやり取りできるように改良している。

EDO DRAM : FPM DRAM の強化版。それぞれの CAS 信号をより近い時間内に送ることができる。

SDRAM : 制御信号の多くを、外部クロック信号の立ち上がりエッジで起き換える。

DDR SDRAM : SDRAM の強化版。クロック信号の両方のエッジを用いることにより DRAM の速度を倍にする。

VRAM : グラフィック･システムのフレーム･バッファに用いられる。

不揮発メモリ (ROM)

DRAM やSRAM は、電源を切ると情報を失う(揮発的)が、ROMは、電源が切られてもその情報を保持する。

ROM は書き込める回数と、その再プログラムのための仕組みによって区別される。

PROM、EPROM、EEPROM、フラッシュ･メモリといった種類がある。

ファームウェア : ROM デバイスに保持されたプログラムのこと。

メイン･メモリへのアクセス

データはプロセッサと DRAM メイン･メモリの間を、バス上で行ったり来たりする。

読み出しトランザクション : メイン･メモリから CPU へデータを転送する。

書き込みトランザクション : CPU からメイン･メモリへデータを転送する。

バス

バスとは並列する配線の集まりでコンピュータ内部でデータや信号を伝達するための回路や通路のこと。

CPUや主記憶装置、入出力装置などのそれぞれの装置が共通の伝送路であるバスで接続されている。

CPUとメイン･メモリを接続するバスの構成例

構成要素は CPU チップ、I/O ブリッジとよばれるチップ･セット、メイン･メモリを形作る DRAM メモリ･モジュール群。

これらの構成要素は 2つのバスで接続されている。

システム･バス :CPU を I/O ブリッジに接続する。

メモリ･バス : I/O ブリッジをメインメモリに接続する。

ディスク･ストレージ

ディスクは膨大な量のデータを保持するが読み出すのに時間がかかる。

容量は数年ごとに2倍になり続けている。

構成

プラッタ : 円盤状の媒体。

サーフェス : 各プラッタには 2つあり、それらは磁気記憶材料で覆われている。トラックとよばれる同心円の集まりでできている。

スピンドル : プラッタの中心にあって回転している。

半導体ディスク (SSD)

フラッシュ･メモリをベースとしている。

状況によっては従来の回転ディスクの代替となる。

性能

読み出しは書き込みより早い。またデータはページ単位で読み書きされる。
ページは、それが属するブロック全体が消去されて初めて書き込むことができる。

長所 : 半導体メモリでできており、可動部品がない。これによりアクセスタイムが速くなり、電力消費が少なく頑丈となる。

短所 : フラッシュ･ブロックは書き込みを繰り返すうちに消耗してしまうため、寿命がある。そして高価。

局所性

最近参照した他のデータ項目そのものやその近くを参照すること。

時間的局所性 : 一度参照されたメモリに再びアクセスする。(例)同じ変数を利用する。

空間的局所性 : 一度参照されたメモリの近くのメモリにアクセスする。(例)ループ文で1ずつインデックスを増やして配列にアクセスする。

キャッシュ

階層内の各レベルは一つ下位のレベルからのデータをキャッシュする。

キャッシュ･ヒット : 命令処理に必要なデータがキャッシュに存在し、キャッシュからデータを読み込むことができること。

キャッシュ･ミス : 命令処理に必要なデータがキャッシュに存在せず、キャッシュからデータを読み込むことができないこと。

リプレースメント･ポリシー : キャッシュのブロックを置き換えるルール。ランダムに選択されるか、最も古いブロックを選択するかなど。

キャッシュ･ミスの種類 : コールド･ミス、競合ミス、容量ミスなどがある。

キャッシュ･メモリ

CPU とメイン･メモリのギャップ増大のため、L1キャッシュとよばれる小さなSRAMキャッシュ･メモリを導入した。

そしてCPU とメイン･メモリの性能差が増え続けたため、L2, L3 キャッシュも導入された。

キャッシュがデータを保持しているか調べるのに、ハッシュ･テーブルのような仕組みを使っている。

キャッシュの種類

ダイレクト･マップ、セット･アソシアティブ、フル･アソシアティブなどがある。

ミス時のライン･リプレースメント

LFU ポリシー : 一定期間中に最も参照回数が少なかったラインをリプレースする。

LRU ポリシー : 最後のアクセスが最も古いラインをリプレースする。

ライトに関する問題

ライト･スルー : キャッシュ･ブロックを次の下位レベルへ即座に書き込む。

ライト･バック : 更新されたブロックがキャッシュから追い出されるときのみ、一つ下位レベルに書き込むことで可能な限り更新を遅らせる。

ライト･ミスの処理

ライト･アロケート : 該当するブロックを一つ下位から読み出した後、そのキャッシュ･ブロックを更新する。

ノー･ライト･アロケート : キャッシュを通り抜けて一つ下位レベルへ直接ワードへ書き込む。

キャッシュ･パラメタの性能への影響

キャッシュの性能はミス率、ヒット率、ヒット時間、ミス･ペナルティの4つの指標によって評価される。

キャッシュサイズの影響

大きいキャッシュはヒット率を増加させやすい。一方で、大きいメモリを高速に動作させることは難しい。

そのため L1 は L2 よりも L2 は L3 よりも小さい。

ブロック･サイズの影響

大きいブロックはキャッシュ･ライン数が少ない。

利点 : 空間的局所性を利用してヒット率を上げる。

欠点 : 長い転送時間必要とするのでミス･ペナルティが大きい。

局所性を活かすには

空間的局所性を高める : データ･オブジェクトを、メモリに格納されている順序に従ってリードする。

時間的局所性を高める: データ･オブジェクトが一度リードされたら、できる限りそれを繰り返し使用する。

感想

自分は普段メモリ階層についてあまり意識していませんでした。
なんとなくレジスタが速くて、ディスクは遅いくらいのイメージだったので、メモリ階層について学ぶことができてよかったです。
またコード･レベルでも、なるべくよい局所性を持つように工夫していこうと思います。
この本の表紙となっているメモリ･マウンテンについてもようやく知ることができて、スッキリしました。