cpu2007lectureno2.ppt

(1)

メモリに関する話題

• メモリ階層性

• メモリ構造

• Cache（キャッシュ）メモリ

• Cache構造

• Cache効率

• リプレースメント（リフィル）方式

• 書き込み制御

• 多重レベルcache

• cacheが有効でない場合

(2)

17.10.2007 数理情報科学特別演習 2

フォンノイマンボトルネック（隘路）

• プログラム内蔵方式のコンピュータ

（フォンノイマン型）

• プロセッサのプログラム実行時のメモリ参照

• 通常メモリのアクセススピードはプロセッサの計

算スピードに較べて遅い

• 最近この傾向はさらに高まっている

• メモリアクセススピードによってプログラムの実行

性能が規定される

• フォンノイマン型ボトルネック

(3)

メモリの階層性と

Cache

• Register:FF circuits • Cache:Bipolar,CMOS SRAM • Main Storage:SRAM,DRAM • Disk Cache:DRAM • 早いメモリは消費電力発熱量が高い．

(4)

SRAM構造

(5)

プログラムのもつ局所性

• プログラムの特徴としての

局所性

• ある短い時間に限ってみるとメモリのある特定

の領域の情報（命令＋データ）のみで動作

• 情報の再利用あるいは近辺の情報の参照に

よる情報更新

• メモリ参照の局所性

• temporal locality（時間的）

• spatial locality（空間）

(6)

Cacheの登場

• よく参照されるデータの特殊領域への待避

• 効率的に局所性を再現

• 時間とともに内容変化

• Cacheの組み込み

(7)

Cacheの内部構成

• 抽象化されたCacheの構造

• コントロール部（アドレスデコーダとtag，コンパレータ）とCacheメモリ部 • メインストレージのアドレスとtag情報の素早い参照が重要（マッピング） • データの格納法にもさまさまな工夫

(8)

セクタ方式

• メモリ分割：例セクタ（10bit addr），ブロック（16/セクタ，64Byte長） • 16個のセクタのcacheへの登録 • 各セクタ最大16ブロック含有可 • 有効ブロックかどうかのvalidity bitを持たせる • invalid bitであれば同じブロックのメインストレージからの再読み込み • ヒットしない場合，いずれかのセクタデータを追い出しcache更新

(9)

ブロック（バースト）データ転送

• 一般のデータ読込みではアドレスラインをバスに出してしばらくしてデータがバスにメモリからロードされる． • ブロック転送では開始アドレスと転送バイトサイズを指定すれば最初のアドレスロード以降データは間髪をおかずバスにロードされる．

(10)

ダイレクトマップ方式

• ブロック単位に分けたメモリを輪切りにする（row）.各rowはさらに縦に切る（Column）． • Tagは順番に決まったrowを配する．対応するcacheに記録されたブロックのcolumn番号をtagに記録する． • Tagとメインアドレスの比較は10bit以下のcolumn番号のみでよいので制御は容易 • 1 rowにつき1個のブロックしかcacheできない．特定のrowに所属するブロックへのアクセスが集中すると効率は悪くなる．

(11)

フルアソシアティブ方式

• メインストレージとcache間の対応はブロック（例えば64Byte）で行うがその他の対応はなにもしない． • 任意のブロックがcacheの任意の位置に記録される． • メインストレージの実アドレスとtagはフルにブロック番号で比較させ，一致をとるので制御機構が複雑 • 使用頻度の高い複数ブロックの無制限有効利用

(12)

(n-way) セットアソシアティブ方式

• ダイレクトマップ方式の拡大

• cache内で記録ブロック数が1 rowで1個だったものを複

数個に拡大．この複数のブロック数を

_{wayと呼ぶ．}

• 以下の例は2-way,row addr. 6 bit, column addr. 8 bit,ブ

ロックサイズ

64Byte

(13)

(14)

Cache構成のキーポイント

• Cacheメモリの容量（Capacity）

• ブロックサイズ

• マッピング方式

• セットアソシアティブwayの数とrow数（set数）

• replacement方式

• restore動作-メインストレージアクセス方式

• Compulsory（初動遅延）

• Conflict：ブロック集中アクセスによるミス（ダイレ

クトマップ，セットアソシアティブ）

• 実行プログラムの特性（データアクセスの効率）

(15)

実測値例

• 中澤喜三郎「計算機アーキテクチャ…」よりデータ孫引き

• cache容量が大きくなるとcapacity miss，conflict missともに減少． • way数増えるとconflict miss rate下がる

(16)

リプレースメント方式

• ミスヒットによるcache更新時のデータ追出しアルゴリズム

• invalid bitタグのブロックの追放

• LRU（Least Recently Used）ブロックの追放

• 履歴用（タイムスタンプ）のtag bitを必要とする • FIFO（First-In First-Out） • 最古参ブロックから追い出し • LRUより制御機構が簡単 • ブロックのランダム抽出 • 時間にかかわらずどのブロックのアクセス頻度は同じであろうという考え方 • cacheアクセスごと，あるいはクロックごとにカウンターを増やす．カウンター値と同じラインのブロックを追放，そしてカウンターリセット

(17)

書き込み制御

• データ更新にともなうメインストレージへの

再書き込み

• ストアスルーあるいはライトスルー

（

_{Store-Through or Write-Through）}

• ストアイン，ライトバックあるいはコピーバック

（

_{Store-In,Write-Back or Copy-Back）}

(18)

ストア（ライト）スルー

Store（Write）-Through

• 書き込みデータのブロックがcacheでヒットした場

合，

_{cacheデータとメインストレージともに更新}

（

_Write）

• ミスした場合，メインストレージの指定アドレスの

データ更新

• cacheに当該ブロックを読込みメインストレージと

cacheを更新（ライトアロケート），あるいは

• cacheは何もせずメインストレージのみ変更

• ライトバッファ（Write Buffer）

• メインストレージへのアクセス中CPU処理がストール

されてしまう．この期間を最小限にするために中間

バッファ（ライトバッファ）を持つ必要がある．

(19)

ストアインあるいはライト（コピー）バック

（

_{Store In or Write（Copy）-Back）}

• ヒットした場合，cacheのみ変更

• ミスした場合，必ずメインストレージからcacheへ

当該ブロックを読込み，

_{cacheのみを変更}

• cacheとメインストレージとで当該ブロックのある

値が異なるという旨をマークしておく．

（

_{clean bitをOFF→dirty）}

• このブロックがcacheから追出されるときにメイン

ストレージを更新する（ライトバック）．

（

_{clean bitをON→clean）}

(20)

ストアイン（ライトバック）キャッシュの

状態遷移

(21)

cacheの多重（マルチ）レベル化

• L1，L2

• Victim

(22)

cacheが有効でない場合（1）

• 中澤喜三郎「計算機アー

キテクチャ

…」より直引き

• 長い（要素の多い）ベクト

ル計算

• データ量がcacheサイズを

越えるとパフォーマンスの

低下が見える

• サイズのみでなくcacheの

構成をも考慮したプログラ

ミングの配慮が必要

(23)