020105．メモリの高機能化

(1)

５．メモリの高機能化

◆メモリインタリーブ

◇メモリインタリーブとは

主記憶装置をいくつかのバンクに分割し、各バンク毎にアクセスパスを設定する。あるバンクの情報に対するアクセスがある時は、それに続く全てのバンクの情報を同時にそれぞれのアクセスパスを経由して読み出す。バンク数をウェイといい、２～３２ウェイが多い。キャッシュメモリへのブロック転送、パイプライン処理のような先行制御に有効なハードウェアアーキテクチャである。

◆キャッシュメモリ

◇キャッシュメモリとは

キャッシュメモリは高速バッファメモリともいい、プロセッサに近接して装備され、主記憶装置内の命令やデータを一時的に格納する装置である。高速読み出し小容量の記憶装置で、バイポーラ型のＳＲＡＭが使われ、容量はレジスタより大きいが主記憶装置よりは小さい。アクセス速度は主記憶よりは速いがレジスタよりは遅い。主記憶装置からの実行上の読み出し速度を向上させる目的に用いられ、キャッシュを利用すると命令の解読と実行速度は数ナノ秒～１０１２３４５６６７１４８９１０１１１２１３２０１９１８１７１６１５バンク番号０１２３４５６並列アクセス実質アクセス時間キャッシュなしの場合見かけ上のアクセス時間 ●参照局所性と高ヒット率を利用して、見かけ上のアクセス時間を短縮する。高速化記憶階層の活用ヒット率

(2)

０ナノ秒に向上する。

◇キャッシュの性能

キャッシュの性能として、ヒット率とアクセス時間がある。ヒット率は命令またはデータがキャッシュメモリ内に存在する割合であり、存在しない割合をミスヒット率という。ヒット率はプログラムの参照局所性に左右され、マッピング方式やブロック置換アルゴリズムの影響を受ける。キャッシュアクセス時間はキャッシュを構成するメモリ素子によって決まる。

◇キャッシュメモリへのアクセス手順

① キャッシュに存在すればそれにアクセスする。 ② キャッシュに存在しなければ、キャッシュの一部と主記憶装置の一部を置換アルゴリズムに従って置き換える。 ③ アクセス対象の主記憶装置の命令やデータをキャッシュ内に読み出し、それにアクセスする。

◇キャッシュメモリの実効アクセス時間Ｔ

Ｔ＝ＴＣ×Ｈ＋ＴＭ×(１－Ｈ) ＴＣ：キャッシュメモリのアクセス時間ＴＭ：主記憶装置のアクセス時間Ｈ：ヒット率

◇データキャッシュと命令キャッシュ

キャッシュには、命令格納専用の命令キャッシュとデータ格納専用のデータキャッシュがある。命令キャッシュは主記憶装置への書き戻しが不要であり、データに比べて命令の参照局所性は安定して高くなる。

◇ライトスルー方式とライトバック方式

ライトスルー方式はキャッシュメモリのブロックに書き込むときに、同時に主記憶装置のブロックにも書き込む方式である。ライトバック方式はキャッシュメモリからブロックを追い出すときに、主記憶装置への書き込みを行う方式である。

◇キャッシュメモリのマッピング

主記憶装置とキャッシュメモリの間で、ブロック単位に命令やデータを移動する際の配置の関係をマッピングという。マッピング単位をブロックサイズといい、主記憶装置とキャッシュメモリ間の転送単位になる。主記憶装置とキャッシュメモリ間の転送時間はブロックサイズに比例し、転送性能(スループット)に逆比例する。

◇キャッシュメモリの置換アルゴリズム

置換アルゴリズムは、キャッシュメモリから主記憶装置に書き戻す対象のブロックを決定す

(3)

る方式である。 ① ＦＩＦＯ方式先入れ先出し方式ともいい、キャッシュメモリに最も長くいたブロックを書き戻すブロックとして決定する方式である。 ② ＬＲＵ方式キャッシュメモリ上にあるブロックの内、最後に参照されてからその時点までの経過時間が最も長いブロックを書き戻すブロックとして決定する方式である。 ③ ＬＦＵ方式参照頻度が最も小さいブロックを書き戻すブロックとして決定する方式である。

◆キャッシュメモリのマッピング

◇マッピングテーブル

主記憶装置とキャッシュメモリの間で、ブロック単位に命令やデータを移動する際の配置の関係をマッピングという。マッピング単位をブロックサイズといい、主記憶装置とキャッシュメモリ間の転送単位になる。主記憶装置とキャッシュメモリ間の転送時間はブロックサイズに比例し、転送性能(スループット)に逆比例する。主記憶とキャッシュメモリの対応には、マッピングテーブルを使用する。マッピングテーブル上にはキャッシュメモリの各ブロックに対応するエントリがあり、そのエントリに主記憶のブロック番号を格納する。主記憶のブロックとキャッシュメモリのブロックは多対１の関係になる。複数のキャッシュメモリのブロックを一つのセットにしてまっピングに使用する。

◇マッピングの方式

マッピングの方式には、ダイレクトマッピング、フルアソシアティブ、セットアソシアティブ、セクタマッピングの方式がある。 ① ダイレクトマッピングダイレクトマッピングは、主記憶装置をブロック単位に分割し、キャッシュメモリの位置ごとに主記憶装置の特定のブロックが固定して関係付けられる方式である。利点はハードウェア化や実現が簡単、アクセス時間にオーバヘッドがない。欠点はミスペナルティ時間が大きい、ブロック置換の自由度が少ない。主記憶キャッシュマッピングテーブル 1 M 1 M I I 1 N J J キャッシュブロック番号主記憶ブロック番号

(4)

② フルアソシアティブフルアソシアティブは、主記憶装置のブロックがキャッシュメモリのどのブロックにも自由にアクセスできる方式である。利点はマッピングの自由度が大きいのでブロック置換アルゴリズムなどの決定における自由度が大きい。欠点は大容量のマッピングテーブルがが必要となり、実現のコストが高くなる。 ③ セットアソシアティブセットアソシアティブは、主記憶装置とキャッシュメモリを複数のセットに分割し、特定のセットに属するブロックはセット間ではダイレクトマッピングを利用し、セット内でフルアソシアティブ方式を用いる。ノイマン型コンピュータの大半はこの方式を利用している。主記憶のブロック数Ｎ、セット数ｎ、キャッシュのブロック数Ｍ、セット数ｍ、１セットのブロック数をｋとすると、次の関係が成り立つ。ｎ＝Ｎ／ｋ、ｍ＝Ｍ／ｋマッピングテーブルの大きさはｍｋとなる。 ④ セクタマッピングセクタマッピングは、主記憶装置内のセクタは最初はキャッシュメモリ内のどのセクタへもマッピングできるが、一度キャッシュメモリ内のセクタが決まると、その主記憶装置のセクタに属するブロックはキャッシュメモリ内のそのセクタに配置される。主記憶キャッシュマッピングテーブル０１２３４５６７４１６７４１６７マッピングが固定主記憶キャッシュマッピングテーブル０１２３４５６７６４５７６４５７セット間は固定・セット内は自由セット

(5)

◆例題

例題１処理装置で用いられるキャッシュメモリの使用目的として，適切な記述はどれか。ア仮想記憶のアドレス変換を高速に行う。イ仮想記憶のページング処理を高速に行う。ウ主記憶へのアクセス速度とプロセッサの処理速度の差を埋める。エ使用頻度の高いプログラムを常駐させる。 □解説キャッシュメモリの使用目的に関する問題である。ア、イの仮想記憶はメインメモリの容量よりも大きな容量のプログラムを実行する場合に、セグメント単位またはページ単位に補助記憶との間でプログラムやデータの読み込み、書き込みを行う方式で、高速処理のためにテーブルをメインメモリ上に常駐したり、リロケータブルなプログラム構造を利用して処理の高速化を図る方式である。キャッシュメモリは直接には関係がない。ウの主記憶へのアクセス速度とプロセッサの処理速度の差を埋める記述がキャッシュメモリの使用目的として正しい答えになる。求める答えはウとなる。エの使用頻度の高いプログラムの常駐化はページングやスワッピングを減少させ、高速化を実現するが、小容量の高速メモリと大容量の低速メモリを組み合わせて、経済的な高速メモリを実現するキャッシュメモリの考え方ではない。 □解答ウ例題２キャッシュメモリに関する記述のうち，適切なものはどれか。ア書込み命令を実行したときに，キャッシュメモリと主記憶の両方を書き換える方式と，キャッシュメモリだけを書き換えておき，主記憶の書換えはキャッシュメモリから当該データが追い出されるときに行う方式とがある。イキャッシュメモリにヒットしない場合に割込みが生じ，プログラムによって主記憶からキャッシュメモリにデータが転送される。ウキヤツシュメモリは，実記憶と仮想記憶とのメモリ容量の差を埋めるために採用される。エ半導体メモリのアクセス速度の向上が著しいので，キャッシュメモリの必要性は減っている。 □解説キャッシュメモリに関する問題である。キャッシュメモリは、プロセッサに近接して装備され、主記憶装置内の命令やデータを一時的に格納する装置である。高速読み出し小容量の記憶装置で、主記憶装置からの実行上の読み出し速度を向上させる目的に用いられる。主記憶装置に書き込みを行うタイミングにライトスルー方式とライトバック方式がある。

(6)

ライトスルー方式は、キャッシュメモリのブロックに書き込むときに、同時に主記憶装置のブロックにも書き込む方式である。ライトバック方式は、キャッシュメモリからブロックを追い出すときに、主記憶装置への書き込みを行う方式である。アの主記憶装置への書き込みタイミングは、ライトスルー方式とライトバック方式がある。求める答えはアとなる。イの割込は、命令の実行順序を強制的に、動的に変える手段であり、不測の事態や異常・例外などの動作が発生した場合の処理法である。キャッシュメモリは主記憶へのアクセス手段の一つで、定常の処理であり、割込処理を伴うものではない。ウの実記憶と仮想記憶のメモリ容量の差を埋めるは誤りであり、主記憶へのアクセス時間の短縮を図るための仕組みである。エの主記憶へのアクセス速度の向上のために、現在でも、より大容量のキャッシュメモリが求められている。 □解答ア例題３あるプロセッサが主記憶装置及びキャッシュメモリにアクセスするとき、アクセス時間は、それぞれ８５０ナノ秒及び４０ナノ秒である。キャッシュメモリのヒット率を０.８としたとき、このプロセッサの平均アクセス時間(ナノ秒)は幾らか。ア２０２イ２１０ウ６８８エ８５８ □解説キャッシュメモリを有するシステムの平均アクセス時間を求める問題である。次の計算式から求めることができる。Ｔ＝８５０×０.２＋４０×０.８＝２０２(ナノ秒) 求める答えはアである。 □解答ア例題４アクセス時間１０ナノ秒のキャッシュメモリとアクセス時間５０ナノ秒の主記憶を使用した処理装置の実効メモリアクセス時間を２５ナノ秒以下にしたい。最低限必要なキャッシュメモリのヒット率は何％か。ア５０イ６０ウ７０エ８０ □解説キャッシュメモリを使用した場合の実効メモリアクセス時間を計算する問題である。ヒット率をＦとすると、次の式になる。２５＝５０×(１－Ｆ)＋１０×Ｆ４０×Ｆ＝５０－２５Ｆ＝２５／４０＝０.６２５６２.５％を満足させる最小のヒット率は７０％であり、求める答えはウとなる。

(7)

□解答ウ例題５システムＡ，Ｂのキャッシュメモリと主記憶のアクセス時間は表のとおりである。あるプログラムをシステムＡで実行したときのキャッシュメモリのヒット率と実効アクセス時間は，システムＢで実行したときと同じになった。このときのキャッシュメモリのヒット率は幾らか。単位ナノ秒システムＡシステムＢキャッシュメモリ１５１０主記憶５０７０ア０.２イ０.３ウ０.５エ０.８ □解説キャッシュメモリの実効アクセス時間に関する問題である。キャッシュメモリの実効アクセス時間Ｔは次の式で求める。Ｔ＝ＴＣ×Ｈ＋ＴＭ×(１－Ｈ) ＴＣ：キャッシュメモリのアクセス時間、ＴＭ：主記憶装置のアクセス時間、Ｈ：ヒット率キャッシュメモリへのヒット率をＨとすると１５×Ｈ＋５０×(１－Ｈ)＝１０×Ｈ＋７０×(１－Ｈ) －３５Ｈ＋５０＝－６０Ｈ＋７０２５Ｈ＝２０Ｈ＝０.８求める答えはエとなる。 □解答エ例題６表のように４ページ分のメモリキャッシュＣ0～Ｃ3があり、それぞれにページの内容Ｍ0～Ｍ3が格納されている。ここで、新たに別のページの内容をキャッシュにロードする必要が生じたとき、キャッシュＣ2の内容Ｍ2を置換の対象とするアルゴリズムはどれか。アＦＩＦＯキャッシュＣ0 Ｃ1 Ｃ2 Ｃ3 イＬＦＵ内容Ｍ0 Ｍ1 Ｍ2 Ｍ3 ウＬＩＦＯロード時刻（時：分） 0:02 0:03 0:04 0:05 エＬＲＵ最終参照時刻（時：分） 0:08 0:06 0:05 0:10 参照回数 10 １３５ □解説キャッシュメモリの置換アルゴリズムに関する問題である。アのＦＩＦＯは先入れ先出しで、ロード時刻が最も古い内容が置換されることになる。表

(8)

の場合には、内容Ｍ０が対象になる。イのＬＦＵは最近の一定時間内の参照回数が最も少ないものが置換の対象になるアルゴリズムである。表の場合には、内容Ｍ１が対象になる。ウのＬⅠＦＯは最後に入ったものを先に出すアルゴリズムで、表の場合には、内容Ｍ３が対象になる。エのＬＲＵは最後に参照されてから最も長い時間参照されていない内容が置換の対象になる。表の場合には、内容Ｍ２が対象になる。キャッシュのＣ２の内容Ｍ２は、ロード時刻では３番目であり、最終参照時刻では最も古い。従って、この場合の置換アルゴリズムはＬＲＵで、求める答えはエとなる。 □解答エ例題７キャッシュメモリと主記憶との間でブロックを置き換える方式にＬＲＵ方式がある。この方式で置換えの対象になるブロックはどれか。アー定時間参照されていないブロックイ最後に参照されてから最も長い時間が経過したブロックウ参照頻度の最も低いブロックエ読み込んでから最も長い時間が経過したブロック □解説置換アルゴリズムＬＲＵに関する問題である。ＬＲＵ方式はキャッシュメモリ上にあるブロックの内、最後に参照されてからその時点までの経過時間が最も長いブロックを書き戻すブロックとして決定する方式である。アはＮＲＵ方式、イはＬＲＵ方式、ウはＬＦＵ方式、ＦＩＦＯ方式である。求める答えはイとなる。 □解答イ例題８メモリインタリーブに関する正しい記述はどれか。ア処理速度の異なるＣＰＵと主記憶装置間に高速の記憶装置を設け、待ち時間を縮めること。イ一つの主記憶装置をいくつかのバンクに分割し、バンクごとに一括してアドレス選択を行うこと。ウ複数のバンクと呼ぶ装置にアドレスを振り分け、独立してアクセスできるようにすること。エ命令の実行過程を複数のステージに分けて、それぞれをずらしながら並行して処理すること。 □解説メモリインタリーブに関する問題である。メモリインタリーブは、主記憶装置を複数のアクセス単位に分けておき、各バンクを並行

(9)

してアクセスできるようにすることによって、主記憶へのアクセスを高速化する方法である。アはＣＰＵと主記憶装置のアクセス時間の差を縮めるためのキャッシュメモリ方式である。イは主記憶をいくつかのバンクに分割し、それぞれのバンクごとに一括してプログラムまたはデータのアドレスを割り付ける方式である。ウはメモリを複数のバンクに分割し、空間の局所性を確保できるようにして、プログラムやデータを振り分け、それぞれのバンクに独立してアクセスできるようにしたもので、一つのバンクを呼び出すときに局所性の高いバンクを同時に呼び出す方式であり、メモリインタリーブといわれる方式である。メモリにアクセスする場合には複数のバンクが対象になる。求める答えはウとなる。エは、命令処理の過程を高速化するためのパイプライン処理の方式である。 □解答ウ例題９コンピュータの高速化技術の一つであるメモリインタリーブに関する記述として，適切なものはどれか。ア主記憶と入出力装置，又は主記憶同士のデータの受渡しをＣＰＵ経由でなく直接やり取りする方式イ主記憶にデータを送り出す際に，データをキャッシュに書き込み，キャッシュがあふれたときに主記憶へ書き込む方式ウ主記憶のデータの一部をキャッシュにコピーすることによって，レジスタと主記憶とのアクセス速度の差を締める方式エ主記憶を複数の独立して動作するグループに分けて，各グループに並列にアクセスする方式 □解説メモリインタリーブに関する問題である。アはＤＭＡ方式、イはキャッシュメモリのライトバック方式の考え方、キャッシュメモリの考え、エがメモリインタリーブである。求める答えはエとなる。 □解答エ例題 10 主記憶装置の高速化の技法として，主記憶を幾つかのアクセス単位に分割し，各アクセス単位をできるだけ並行動作させることによって，実効的なアクセス時間を短縮する方法を何というか。ア仮想記憶イパイプラインウマイクロプログラムエメモリインタリーブ □解説高速化技法に関連するメモリインタリーブに関する問題である。

(10)

アの仮想記憶は、主記憶の実容量を超える記憶領域を確保する手法で、補助記憶を利用して、情報が存在するアドレスと処理装置が呼び出すアドレスとを分離して使えるようにする仕組みである。イのパイプライン処理は、１つの処理を複数のステップに分割し、それぞれのステップを独立させて、同時に並行して処理を進める方式で、ＣＰＵの処理速度の高速化を実現する。ウのマイクロプログラムはコンピュータの命令を細分化した基本動作命令の集まりとして実現することで、機能の拡張や修正を容易するものである。エのメモリインタリーブは主記憶装置を独立した動作可能な複数のバンクに分け、連続したアドレスがアクセスされる場合に並列して動作させ、実効的なアクセス時間を短縮する方法である。求める答えはエとなる。 □解答エ例題 11 ＣＰＵと主記憶装置の間に置かれるキャッシュメモリにおいて、主記憶装置上のあるブロックを、キャッシュメモリ上の数個の特定ブロックと対応づけるマッピング方式はどれか。アセットアソシアティブ方式イダイレクトマッピング方式ウフルアソシアティブ方式エライトスルー方式 □解説キャッシュメモリのマッピング方式に関する問題である。アのセットアソシアテイブ方式は、メインメモリをブロックに分割した場合、セットアドレスに対してキャッシュメモリの対応する位置が複数存在する方式である。メインメモリとキャッシュメモリのセット間ではダイレクトマッピング方式を用いる。セット内の複数のブロックに対してはキャッシュメモリのどのアドレスでも対応するフルアソシアティブ方式を用いるようにした方式である。イのダイレクトマッビング方式は、メインメモリをブロックに分割した場合、キャッシュメモリの対応する位置が固定される方式である。メモリのセットアドレスが決まると格納できるキャッシュのアドレスが決まる方式である。ウのフルアソシアティブ方式は、メインメモリとキャッシュメモリのブロック間で任意に対応付けが可能で、任意にアクセスできるようにしたものである。主記憶上のブロックがキャッシュメモリ上の複数個の特定ブロックと対応づく方式であるためセットアソシアテイブ方式である。求める答えはアとなる。エのライトスルー方式は、ＣＰＵがデータ書き込み命令を実行する場合、キャッシュメモリとメインメモリの両方に書き込む方式である。主記憶上のブロックがキャッシュメモリ上の複数個の特定ブロックと対応づく方式であるためセットアソシアテイブ方式である。求める答えはアとなる。 □解答ア