速化記憶階層の活用 5. メモリの高機能化 メモリインタリーブ メモリインタリーブとは 0 2 3 5 バンク番号 0 2 3 5 8 9 0 2 3 5 8 9 20 並列アクセス 主記憶装置をいくつかのバンクに分割し 各バンク毎にアクセスパスを設定する あるバンクの情報に対するアクセスがある時は それに続く全てのバンクの情報を同時にそれぞれのアクセスパスを経由して読み出す バンク数をウェイといい 2~32ウェイが多い キャッシュメモリへのブロック転送 パイプライン処理のような先行制御に有効なハードウェアアーキテクチャである キャッシュメモリ キャッシュメモリとは キャッシュなしの場合 実質アクセス時間 参照局所性と高ヒット率を利用して 見か見かけ上のアクセス時間け上のアクセス時間を短縮する 高ヒット率 キャッシュメモリは高速バッファメモリともいい プロセッサに近接して装備され 主記憶装置内の命令やデータを一時的に格納する装置である 高速読み出し小容量の記憶装置で バイポーラ型のSRAMが使われ 容量はレジスタより大きいが主記憶装置よりは小さい アクセス速度は主記憶よりは速いがレジスタよりは遅い 主記憶装置からの実行上の読み出し速度を向上させる目的に用いられ キャッシュを利用すると命令の解読と実行速度は数ナノ秒 ~ - -
0 ナノ秒に向上する キャッシュの性能キャッシュの性能として ヒット率とアクセス時間がある ヒット率は命令またはデータがキャッシュメモリ内に存在する割合であり 存在しない割合をミスヒット率という ヒット率はプログラムの参照局所性に左右され マッピング方式やブロック置換アルゴリズムの影響を受ける キャッシュアクセス時間はキャッシュを構成するメモリ素子によって決まる キャッシュメモリへのアクセス手順 キャッシュに存在すればそれにアクセスする 2 キャッシュに存在しなければ キャッシュの一部と主記憶装置の一部を置換アルゴリズムに従って置き換える 3 アクセス対象の主記憶装置の命令やデータをキャッシュ内に読み出し それにアクセスする キャッシュメモリの実効アクセス時間 T T=TC H+TM (-H) TC: キャッシュメモリのアクセス時間 TM: 主記憶装置のアクセス時間 H : ヒット率 データキャッシュと命令キャッシュキャッシュには 命令格納専用の命令キャッシュとデータ格納専用のデータキャッシュがある 命令キャッシュは主記憶装置への書き戻しが不要であり データに比べて命令の参照局所性は安定して高くなる ライトスルー方式とライトバック方式ライトスルー方式はキャッシュメモリのブロックに書き込むときに 同時に主記憶装置のブロックにも書き込む方式である ライトバック方式はキャッシュメモリからブロックを追い出すときに 主記憶装置への書き込みを行う方式である キャッシュメモリのマッピング主記憶装置とキャッシュメモリの間で ブロック単位に命令やデータを移動する際の配置の関係をマッピングという マッピング単位をブロックサイズといい 主記憶装置とキャッシュメモリ間の転送単位になる 主記憶装置とキャッシュメモリ間の転送時間はブロックサイズに比例し 転送性能 ( スループット ) に逆比例する キャッシュメモリの置換アルゴリズム 置換アルゴリズムは キャッシュメモリから主記憶装置に書き戻す対象のブロックを決定す - 2 -
る方式である FIFO 方式先入れ先出し方式ともいい キャッシュメモリに最も長くいたブロックを書き戻すブロックとして決定する方式である 2 LRU 方式キャッシュメモリ上にあるブロックの内 最後に参照されてからその時点までの経過時間が最も長いブロックを書き戻すブロックとして決定する方式である 3 LFU 方式参照頻度が最も小さいブロックを書き戻すブロックとして決定する方式である キャッシュメモリのマッピング マッピングテーブル主記憶装置とキャッシュメモリの間で ブロック単位に命令やデータを移動する際の配置の関係をマッピングという マッピング単位をブロックサイズといい 主記憶装置とキャッシュメモリ間の転送単位になる 主記憶装置とキャッシュメモリ間の転送時間はブロックサイズに比例し 転送性能 ( スループット ) に逆比例する 主記憶とキャッシュメモリの対応には マッピングテーブルを使用する マッピングテーブル上にはキャッシュメモリの各ブロックに対応するエントリがあり そのエントリに主記憶のブロック番号を格納する 主記憶のブロックとキャッシュメモリのブロックは多対 の関係になる 複数のキャッシュメモリのブロックを一つのセットにしてまっピングに使用する 主記憶 マッピングテーブル キャッシュ J I J I M M キャッシュブロック番号 N 主記憶ブロック番号 マッピングの方式マッピングの方式には ダイレクトマッピング フルアソシアティブ セットアソシアティブ セクタマッピングの方式がある ダイレクトマッピングダイレクトマッピングは 主記憶装置をブロック単位に分割し キャッシュメモリの位置ごとに主記憶装置の特定のブロックが固定して関係付けられる方式である 利点はハードウェア化や実現が簡単 アクセス時間にオーバヘッドがない 欠点はミスペナルティ時間が大きい ブロック置換の自由度が少ない - 3 -
主記憶 0 2 3 5 マッピングテーブル キャッシュ マッピングが固定 2 フルアソシアティブフルアソシアティブは 主記憶装置のブロックがキャッシュメモリのどのブロックにも自由にアクセスできる方式である 利点はマッピングの自由度が大きいのでブロック置換アルゴリズムなどの決定における自由度が大きい 欠点は大容量のマッピングテーブルがが必要となり 実現のコストが高くなる 3 セットアソシアティブセットアソシアティブは 主記憶装置とキャッシュメモリを複数のセットに分割し 特定のセットに属するブロックはセット間ではダイレクトマッピングを利用し セット内でフルアソシアティブ方式を用いる ノイマン型コンピュータの大半はこの方式を利用している 主記憶 0 2 3 5 マッピングテーブル 5 キャッシュ 5 セットセット間は固定 セット内は自由 主記憶のブロック数 N セット数 n キャッシュのブロック数 M セット数 m セットのブロック数をkとすると 次の関係が成り立つ n=n/k m=m/k マッピングテーブルの大きさはmkとなる セクタマッピングセクタマッピングは 主記憶装置内のセクタは最初はキャッシュメモリ内のどのセクタへもマッピングできるが 一度キャッシュメモリ内のセクタが決まると その主記憶装置のセクタに属するブロックはキャッシュメモリ内のそのセクタに配置される - -
例題 例題 処理装置で用いられるキャッシュメモリの使用目的として, 適切な記述はどれか ア仮想記憶のアドレス変換を高速に行う イ仮想記憶のページング処理を高速に行う ウ主記憶へのアクセス速度とプロセッサの処理速度の差を埋める エ使用頻度の高いプログラムを常駐させる 解説キャッシュメモリの使用目的に関する問題である ア イの仮想記憶はメインメモリの容量よりも大きな容量のプログラムを実行する場合に セグメント単位またはページ単位に補助記憶との間でプログラムやデータの読み込み 書き込みを行う方式で 高速処理のためにテーブルをメインメモリ上に常駐したり リロケータブルなプログラム構造を利用して処理の高速化を図る方式である キャッシュメモリは直接には関係がない ウの主記憶へのアクセス速度とプロセッサの処理速度の差を埋める記述がキャッシュメモリの使用目的として正しい答えになる 求める答えはウとなる エの使用頻度の高いプログラムの常駐化はページングやスワッピングを減少させ 高速化を実現するが 小容量の高速メモリと大容量の低速メモリを組み合わせて 経済的な高速メモリを実現するキャッシュメモリの考え方ではない 解答ウ 例題 2 キャッシュメモリに関する記述のうち, 適切なものはどれか ア書込み命令を実行したときに, キャッシュメモリと主記憶の両方を書き換える方式と, キャッシュメモリだけを書き換えておき, 主記憶の書換えはキャッシュメモリから当該データが追い出されるときに行う方式とがある イキャッシュメモリにヒットしない場合に割込みが生じ, プログラムによって主記憶からキャッシュメモリにデータが転送される ウキヤツシュメモリは, 実記憶と仮想記憶とのメモリ容量の差を埋めるために採用される エ半導体メモリのアクセス速度の向上が著しいので, キャッシュメモリの必要性は減っている 解説キャッシュメモリに関する問題である キャッシュメモリは プロセッサに近接して装備され 主記憶装置内の命令やデータを一時的に格納する装置である 高速読み出し小容量の記憶装置で 主記憶装置からの実行上の読み出し速度を向上させる目的に用いられる 主記憶装置に書き込みを行うタイミングにライトスルー方式とライトバック方式がある - 5 -
ライトスルー方式は キャッシュメモリのブロックに書き込むときに 同時に主記憶装置のブロックにも書き込む方式である ライトバック方式は キャッシュメモリからブロックを追い出すときに 主記憶装置への書き込みを行う方式である アの主記憶装置への書き込みタイミングは ライトスルー方式とライトバック方式がある 求める答えはアとなる イの割込は 命令の実行順序を強制的に 動的に変える手段であり 不測の事態や異常 例外などの動作が発生した場合の処理法である キャッシュメモリは主記憶へのアクセス手段の一つで 定常の処理であり 割込処理を伴うものではない ウの実記憶と仮想記憶のメモリ容量の差を埋めるは誤りであり 主記憶へのアクセス時間の短縮を図るための仕組みである エの主記憶へのアクセス速度の向上のために 現在でも より大容量のキャッシュメモリが求められている 解答ア 例題 3 あるプロセッサが主記憶装置及びキャッシュメモリにアクセスするとき アクセス時間は それぞれ850ナノ秒及び0ナノ秒である キャッシュメモリのヒット率を0.8としたとき このプロセッサの平均アクセス時間 ( ナノ秒 ) は幾らか ア 202 イ 20 ウ 88 エ 858 解説キャッシュメモリを有するシステムの平均アクセス時間を求める問題である 次の計算式から求めることができる T=850 0.2+0 0.8=202( ナノ秒 ) 求める答えはアである 解答ア 例題 アクセス時間 0ナノ秒のキャッシュメモリとアクセス時間 50ナノ秒の主記憶を使用した処理装置の実効メモリアクセス時間を25ナノ秒以下にしたい 最低限必要なキャッシュメモリのヒット率は何 % か ア 50 イ 0 ウ 0 エ 80 解説キャッシュメモリを使用した場合の実効メモリアクセス時間を計算する問題である ヒット率をFとすると 次の式になる 25=50 (-F)+0 F 0 F=50-25 F=25/0=0.25 2.5% を満足させる最小のヒット率は0% であり 求める答えはウとなる - -
解答 ウ 例 題 5 システムA,Bのキャッシュメモリと主記憶のアクセス時間は表のとおりである あるプログラムをシステムAで実行したときのキャッシュメモリのヒット率と実効アクセス 時間は, システムBで実行したときと同じになった このときのキャッシュメモリのヒット率 は幾らか 単位 ナノ秒 システムA システムB キャッシュメモリ 5 0 主記憶 50 0 ア 0.2 イ 0.3 ウ 0.5 エ 0.8 解説キャッシュメモリの実効アクセス時間に関する問題である キャッシュメモリの実効アクセス時間 Tは次の式で求める T=TC H+TM (-H) TC: キャッシュメモリのアクセス時間 TM: 主記憶装置のアクセス時間 H : ヒット率キャッシュメモリへのヒット率をHとすると 5 H+50 (-H)=0 H+0 (-H) -35H+50=-0H+0 25H=20 H=0.8 求める答えはエとなる 解答エ 例題 表のようにページ分のメモリキャッシュC0~C3があり それぞれにページの内容 M0~ M3が格納されている ここで 新たに別のページの内容をキャッシュにロードする必要が生じたとき キャッシュC2の内容 M2を置換の対象とするアルゴリズムはどれか ア FIFO キャッシュ C0 C C2 C3 イ LFU 内容 M0 M M2 M3 ウ LIFO ロード時刻 ( 時 : 分 ) 0:02 0:03 0:0 0:05 エ LRU 最終参照時刻 ( 時 : 分 ) 0:08 0:0 0:05 0:0 参照回数 0 3 5 解説 キャッシュメモリの置換アルゴリズムに関する問題である アの FIFO は先入れ先出しで ロード時刻が最も古い内容が置換されることになる 表 - -
の場合には 内容 M0が対象になる イのLFUは最近の一定時間内の参照回数が最も少ないものが置換の対象になるアルゴリズムである 表の場合には 内容 Mが対象になる ウのLⅠFOは最後に入ったものを先に出すアルゴリズムで 表の場合には 内容 M3が対象になる エのLRUは最後に参照されてから最も長い時間参照されていない内容が置換の対象になる 表の場合には 内容 M2が対象になる キャッシュのC2の内容 M2は ロード時刻では3 番目であり 最終参照時刻では最も古い 従って この場合の置換アルゴリズムはLRUで 求める答えはエとなる 解答エ 例題 キャッシュメモリと主記憶との間でブロックを置き換える方式に LRU 方式がある この方 式で置換えの対象になるブロックはどれか アー定時間参照されていないブロックイ最後に参照されてから最も長い時間が経過したブロックウ参照頻度の最も低いブロックエ読み込んでから最も長い時間が経過したブロック 解説置換アルゴリズムLRUに関する問題である LRU 方式はキャッシュメモリ上にあるブロックの内 最後に参照されてからその時点までの経過時間が最も長いブロックを書き戻すブロックとして決定する方式である アはNRU 方式 イはLRU 方式 ウはLFU 方式 FIFO 方式である 求める答えはイとなる 解答イ 例題 8 メモリインタリーブに関する正しい記述はどれか ア処理速度の異なるCPUと主記憶装置間に高速の記憶装置を設け 待ち時間を縮めること イ一つの主記憶装置をいくつかのバンクに分割し バンクごとに一括してアドレス選択を行うこと ウ複数のバンクと呼ぶ装置にアドレスを振り分け 独立してアクセスできるようにすること エ命令の実行過程を複数のステージに分けて それぞれをずらしながら並行して処理すること 解説メモリインタリーブに関する問題である メモリインタリーブは 主記憶装置を複数のアクセス単位に分けておき 各バンクを並行 - 8 -
してアクセスできるようにすることによって 主記憶へのアクセスを高速化する方法である アはCPUと主記憶装置のアクセス時間の差を縮めるためのキャッシュメモリ方式である イは主記憶をいくつかのバンクに分割し それぞれのバンクごとに一括してプログラムまたはデータのアドレスを割り付ける方式である ウはメモリを複数のバンクに分割し 空間の局所性を確保できるようにして プログラムやデータを振り分け それぞれのバンクに独立してアクセスできるようにしたもので 一つのバンクを呼び出すときに局所性の高いバンクを同時に呼び出す方式であり メモリインタリーブといわれる方式である メモリにアクセスする場合には複数のバンクが対象になる 求める答えはウとなる エは 命令処理の過程を高速化するためのパイプライン処理の方式である 解答ウ 例題 9 コンピュータの高速化技術の一つであるメモリインタリーブに関する記述として, 適切なも のはどれか ア主記憶と入出力装置, 又は主記憶同士のデータの受渡しをCPU 経由でなく直接やり取りする方式イ主記憶にデータを送り出す際に, データをキャッシュに書き込み, キャッシュがあふれたときに主記憶へ書き込む方式ウ主記憶のデータの一部をキャッシュにコピーすることによって, レジスタと主記憶とのアクセス速度の差を締める方式エ主記憶を複数の独立して動作するグループに分けて, 各グループに並列にアクセスする方式 解説メモリインタリーブに関する問題である アはDMA 方式 イはキャッシュメモリのライトバック方式の考え方 キャッシュメモリの考え エがメモリインタリーブである 求める答えはエとなる 解答エ 例題 0 主記憶装置の高速化の技法として, 主記憶を幾つかのアクセス単位に分割し, 各アクセス単位をできるだけ並行動作させることによって, 実効的なアクセス時間を短縮する方法を何というか ア 仮想記憶 イ パイプライン ウ マイクロプログラム エ メモリインタリーブ 解説 高速化技法に関連するメモリインタリーブに関する問題である - 9 -
アの仮想記憶は 主記憶の実容量を超える記憶領域を確保する手法で 補助記憶を利用して 情報が存在するアドレスと処理装置が呼び出すアドレスとを分離して使えるようにする仕組みである イのパイプライン処理は つの処理を複数のステップに分割し それぞれのステップを独立させて 同時に並行して処理を進める方式で CPUの処理速度の高速化を実現する ウのマイクロプログラムはコンピュータの命令を細分化した基本動作命令の集まりとして実現することで 機能の拡張や修正を容易するものである エのメモリインタリーブは主記憶装置を独立した動作可能な複数のバンクに分け 連続したアドレスがアクセスされる場合に並列して動作させ 実効的なアクセス時間を短縮する方法である 求める答えはエとなる 解答エ 例題 CPU と主記憶装置の間に置かれるキャッシュメモリにおいて 主記憶装置上のあるブロッ クを キャッシュメモリ上の数個の特定ブロックと対応づけるマッピング方式はどれか アセットアソシアティブ方式イダイレクトマッピング方式ウフルアソシアティブ方式エライトスルー方式 解説キャッシュメモリのマッピング方式に関する問題である アのセットアソシアテイブ方式は メインメモリをブロックに分割した場合 セットアドレスに対してキャッシュメモリの対応する位置が複数存在する方式である メインメモリとキャッシュメモリのセット間ではダイレクトマッピング方式を用いる セット内の複数のブロックに対してはキャッシュメモリのどのアドレスでも対応するフルアソシアティブ方式を用いるようにした方式である イのダイレクトマッビング方式は メインメモリをブロックに分割した場合 キャッシュメモリの対応する位置が固定される方式である メモリのセットアドレスが決まると格納できるキャッシュのアドレスが決まる方式である ウのフルアソシアティブ方式は メインメモリとキャッシュメモリのブロック間で任意に対応付けが可能で 任意にアクセスできるようにしたものである 主記憶上のブロックがキャッシュメモリ上の複数個の特定ブロックと対応づく方式であるためセットアソシアテイブ方式である 求める答えはアとなる エのライトスルー方式は CPUがデータ書き込み命令を実行する場合 キャッシュメモリとメインメモリの両方に書き込む方式である 主記憶上のブロックがキャッシュメモリ上の複数個の特定ブロックと対応づく方式であるためセットアソシアテイブ方式である 求める答えはアとなる 解答ア - 0 -