基本情報技術者 2010年 春期 午後 問01
キャッシュメモリに関する次の記述を読んで、設問1，2に答えよ。
キャッシュメモリとは、主記憶とCPUの間に置く高速アクセスが可能なメモリである。キャッシュメモリとCPU及び主記憶との関係を図1に示す。データをキャッシュメモリに保持しておくことによって、CPUは速度の遅い主記憶に直接アクセスしなくて済むので、処理の高速化が図れる。
ここでは、ハードウェアのアーキテクチャを次のように仮定する。
(1) 主記憶はブロック（1ブロックは100語から成る）に分割されている。各ブロックには、その先頭番地が小さいものから順に1、2、3、…とブロック番号が振られている。主記憶とキャッシュメモリ間はブロック単位でデータが転送される。
(2) キャッシュメモリには、命令を保持しておく命令キャッシュと、データを保持しておくデータキャッシュの2種類がある。ここでは、データキャッシュ（以下、キャッシュという）だけを考える。
(3) キャッシュの構成は、図2のとおりとする。
① キャッシュは、ディレクトリ部とデータ部から成る。
② データ部はバッファ1〜3の三つのバッファから成り、各バッファは1ブロック分の主記憶の内容を保持できる。
③ ディレクトリ部は、データ部のバッファ1〜3に対応したディレクトリ1〜3から成る。それぞれのディレクトリは次の内容を保持する三つのフィールドから成る。
なお、データ部のバッファが未使用の場合は、対応するディレクトリの三つのフィールドすべてに0が入っている。
(イ) ブロック番号：対応するデータ部のバッファが保持する主記憶のブロック番号
(ロ) 順位：キャッシュ内に最も古くから存在するブロックから順に1、2、3と番号が振られる。
(ハ) フラグ：対応するデータ部のバッファにブロックを読み込んだとき、0に初期化される。対応するデータ部のバッファに保持されている内容がCPUの処理によって変更されると、1に変わる。
擬似言語で表現された次の繰返し処理を実行する場合について考える。
(1) 配列A、B、C及びDは100個の要素から成り、1要素は1語である。添字は0から始まるものとする。
(2) データ領域の主記憶への割付けは、次のとおりとする。
① Aの配列領域：4000〜4099番地（ブロック番号41）
A[0]は4000番地、A[1]は4001番地という順に割り付けられる。
② Bの配列領域：4100〜4199番地（ブロック番号42）
③ Cの配列領域：4200〜4299番地（ブロック番号43）
④ Dの配列領域：4300〜4399番地（ブロック番号44）
⑤ 定数−1と99の格納領域：4400、4401番地（ブロック番号45）
(3) 変数iはレジスタを使用し、主記憶への割付けは行わない。
(4) プログラム領域の内容は表1のとおりとする。参照ブロックの数値は、その命令を実行するときにCPUが参照するデータのブロック番号を示す。
命令の形式は次のとおりとする。
LOAD / ADD / STORE Rn, adr [, Rx]：
定数adrはアドレスを示す。Rxは指標レジスタである（省略可能）。Rxを指定した場合の実効アドレスは、定数adrとRxの内容を加算した値が示す番地とする。
LOADは、実効アドレスが示す番地に格納されている内容を、レジスタRnに設定する。
ADDは、レジスタRnの内容に実効アドレスが示す番地に格納されている内容を加えて、レジスタRnに設定する。
STOREは、レジスタRnの内容を実効アドレスが示す番地に格納する。
ADDR Rn, Rm：レジスタRnの内容にレジスタRmの内容を加えて、レジスタRnに設定する。
JNM adr：直前の演算結果が0以上ならばadr番地へジャンプする。
設問1：
問題文を見る 次の(1)〜(6)に従って、1000番地のLOAD命令を実行した直後、及び1006番地のSTORE命令を最初に実行した直後のディレクトリ部の内容を、図3と図4に示す。に入れる正しい答えを、解答群の中から選べ。
(1) 参照ブロックがキャッシュ内にある場合は、キャッシュ内のデータが使用される。
(2) 参照ブロックがキャッシュ内にない場合（以下、ミスという）は、参照ブロックが主記憶からキャッシュに読み込まれ、対応するディレクトリのフラグの内容は0に初期化される。
(3) CPUが参照ブロックに対してSTORE命令を実行した場合は、対応するディレクトリのフラグの内容は1に変わる。
(4) ミスが起こったときにキャッシュ内に未使用のバッファがある場合は、未使用のバッファの中で最も番号が小さいバッファに参照ブロックを読み込み、順位を更新する。
(5) ミスが起こったときにキャッシュ内に未使用のバッファがない場合は、次のキャッシュ更新ロジックを用いる。
キャッシュ内に最も古くから存在するブロックが格納されているバッファに、参照ブロックを読み込み、順位を更新する。ただし、対応するディレクトリのフラグの内容が1だったときは、そのブロックを主記憶に書き戻してから、参照ブロックを読み込み、順位を更新する。
(6) プログラム実行開始時は、キャッシュ内にデータが入っていないものとする。
解答群
ア：0
イ：41
ウ：42
エ：43
オ：44
カ：45
模範解答
a：カ、b：エ、c：ウ
解説
解答の導き方
まず、キャッシュメモリは、主記憶より高速で、CPU（Central Processing Unit：命令を実行する装置）が使うデータを一時的に置くメモリです。主記憶とキャッシュメモリの間では、データをブロック単位で転送します。
ディレクトリは、各バッファにどのブロックが入っているかを記録する欄です。フラグは、キャッシュ内のデータがCPUによって変更されたかを示します。ブロックを読み込んだときはフラグが0で、STORE命令で変更すると1になります。
1. 1000番地のLOAD命令を実行した直後
プログラム実行開始時は、キャッシュ内にデータがありません。1000番地の命令は、4400番地の内容を読み込む命令です。表1では、4400番地の参照ブロックは45です。
そのため、ブロック45はキャッシュにない状態、つまりミスです。問題文には、未使用のバッファがある場合は番号が最も小さいバッファに読み込むとあります。最初に使うバッファはバッファ1です。
読み込まれたばかりのブロックなので、順位は1、フラグは0です。したがって、図3の「a」に入るのはブロック番号45です。
2. 最初の1006番地のSTORE命令までの動きを追う
1001番地で読み込む4401番地もブロック45にあります。ブロック45はすでにキャッシュにあるため、ミスにはなりません。
その後の最初の繰返しでは、iの値は99です。たとえばA[99]の実効アドレスは4000+99=4099で、これはブロック41の範囲です。同じように、B[99]、C[99]、D[99]は、それぞれブロック42、ブロック43、ブロック44にあります。
ここまでのバッファの変化を追うと、次のようになります。順位は、キャッシュに入った時期が古いブロックから1、2、3と付きます。
1002番地でブロック41を読み込むと、空いているバッファ2に入ります。1003番地で読み込むブロック42は、空いているバッファ3に入ります。
1004番地で参照するブロック43は、キャッシュにありません。バッファはすべて使用中なので、最も古いブロックを入れ替えます。この時点で最も古いのは、バッファ1にあるブロック45です。ブロック43をバッファ1に読み込み、順位を更新します。
1005番地のSTORE命令は、ブロック41にあるA[99]を書き換えます。したがって、バッファ2にあるブロック41のフラグが1になります。このSTORE命令はキャッシュ内のブロック41を使うため、ミスにはなりません。
続く1006番地のSTORE命令は、ブロック44にあるD[99]を書き込みます。ブロック44はキャッシュにないのでミスです。最も古いブロックは、順位1のブロック41です。ブロック41のフラグは1なので、問題文の置換ルールに従い、ブロック41を主記憶に書き戻してから、ブロック44をバッファ2に読み込みます。
順位を付け直すと、残ったブロック42が順位1、ブロック43が順位2、新しく読み込んだブロック44が順位3です。さらに、1006番地はSTORE命令なので、読み込まれたブロック44のフラグは0から1に変わります。
よって、図4ではディレクトリ1にブロック43、ディレクトリ2にブロック44、ディレクトリ3にブロック42が入ります。したがって、「b」は43、「c」は42です。
誤りやすいポイント
- 配列の添字とブロック番号を混同しないようにします。たとえば、A[99]の番地は4099ですが、参照するブロック番号は41です。
- 1004番地でブロック43を読み込むとき、空きバッファはありません。ブロック番号の大小ではなく、順位1のブロック45が入っているバッファ1を使います。
- 1005番地のSTORE命令で変更されるのは、ブロック41のフラグです。ブロック41はその後に入れ替えられるため、フラグが1であることが書き戻しの根拠になります。
- 1006番地でブロック44を読み込んだ直後のフラグは0ですが、STORE命令で内容を変更するので、実行後は1です。
FAQ
Q: 1005番地でブロック41を使ったのに、順位が変わらないのはなぜですか？
A: この問題では、順位を更新するのはミスが起きてブロックを読み込むときです。1005番地はキャッシュ内のブロック41を使う処理なので、順位は変わりません。
A: この問題では、順位を更新するのはミスが起きてブロックを読み込むときです。1005番地はキャッシュ内のブロック41を使う処理なので、順位は変わりません。
Q: 1006番地でブロック41を入れ替えるとき、なぜ主記憶への書戻しが必要ですか？
A: ブロック41のフラグが1で、キャッシュ内の内容が変更されているためです。変更内容を主記憶に反映してから、別のブロックを読み込みます。
A: ブロック41のフラグが1で、キャッシュ内の内容が変更されているためです。変更内容を主記憶に反映してから、別のブロックを読み込みます。
Q: ブロック44のフラグは、読み込んだときから1ですか？
A: いいえ。ミスで読み込んだ時点では0です。その後、1006番地のSTORE命令で内容を変更するため、実行直後は1になります。
A: いいえ。ミスで読み込んだ時点では0です。その後、1006番地のSTORE命令で内容を変更するため、実行直後は1になります。
関連キーワード: キャッシュメモリ、キャッシュヒット、キャッシュミス、キャッシュ置換、ライトバック
設問2：
問題文を見る 設問1の(5)のキャッシュ更新ロジックを、次に示す新しいキャッシュ更新ロジックに変えた場合の、ディレクトリ部のブロック番号とフラグの内容の変化を、表2に示す。に入れる正しい答えを、解答群の中から選べ。
〔新しいキャッシュ更新ロジック〕
参照されていない時間が最も長いブロックが格納されているバッファに、参照ブロックを読み込む。
なお、この更新ロジックでは、順位の付け方も変更されていて、キャッシュ内で参照されていない時間が最も長いブロックから順に1、2、3と番号が振られる。
解答群
模範解答
d：イ、e：ク、f：ウ
解説
解答の導き方
この設問では、参照するブロックがキャッシュにないとき、どのブロックを置き換えるかを追います。新しい更新ロジックでは、「参照されていない時間が最も長いブロック」を置き換えます。順位は、参照されていない時間が長いものから順に1、2、3です。つまり、順位1が次に置き換えられるブロックです。この考え方は、LRU（Least Recently Used：最近最も使われていないものを優先する方式）と呼ばれます。
まず、表1の「参照ブロック」と配列の割付けから、命令が参照するブロックを整理します。配列の各領域はそれぞれ一つのブロックに収まっているので、添字が変わっても参照ブロックは変わりません。
- 1000番地と1001番地は、定数を格納したブロック45を参照します。
- 1002番地と1005番地は、配列Aのブロック41を参照します。
- 1003番地は、配列Bのブロック42を参照します。
- 1004番地は、配列Cのブロック43を参照します。
- 1006番地は、配列Dのブロック44を参照します。
ブロックがキャッシュにない状態で読み込むことをキャッシュミス、すでにキャッシュにあるブロックを使うことをキャッシュヒットといいます。キャッシュに読み込んだ直後のフラグは0で、STORE命令によって内容が変更されると1になります。
ここまでで、1006番地の実行後は、ディレクトリ2にブロック41、フラグ1が残っています。したがって、表2のdには解答群の「41、1」に当たるイが入ります。
次に、2回目のループを追います。1007番地でを1減らすので、2回目のループではです。配列A[98]もブロック41にあるため、1002番地はブロック41を参照します。これはキャッシュヒットです。読み出すだけなので、フラグは変わりません。ブロック41は引き続きディレクトリ2にあり、ブロック44はディレクトリ3にあります。ブロック44は1006番地のSTOREで変更済みなので、フラグは1のままです。よって、表2のeは「44、1」に当たるクです。
続く1003番地では、ブロック42を参照します。しかし、ブロック42は1006番地で置き換えられているため、キャッシュミスになります。直前の参照状況は、古い順にブロック43、44、41です。したがって、最も古いブロック43が置き換えられ、ディレクトリ1にブロック42が読み込まれます。読み込んだ直後なのでフラグは0です。表2のfは「42、0」に当たるウです。
誤りやすいポイント
- 順位の意味を取り違えないようにします。この設問の新しい更新ロジックでは、順位1が最も長く参照されていないブロックです。
- 1004番地で置き換えるのは、ブロック番号が最も小さいブロックではありません。参照された時刻が最も古いブロック45です。
- STORE命令では、ブロックが新しく読み込まれた場合でも、内容を書き換えた後はフラグが1になります。1006番地のブロック44も、読み込み直後は0ですが、STOREによって1になります。
- 2回目のループで参照する配列要素は変わりますが、配列Aの要素はすべてブロック41にあります。そのため、1002番地はブロック41を参照します。
FAQ
Q: 1005番地では、なぜブロック41のフラグが1になるのですか？
A: 1005番地はSTORE命令で、計算結果をA[i]に格納します。ブロック41の内容が変更されるため、フラグが1になります。
A: 1005番地はSTORE命令で、計算結果をA[i]に格納します。ブロック41の内容が変更されるため、フラグが1になります。
Q: 1006番地で、なぜブロック42が置き換えられるのですか？
A: 1006番地の直前では、ブロック43、41、42のうち、ブロック42が最も古く参照されています。そのため、ブロック42が置き換え対象になります。
A: 1006番地の直前では、ブロック43、41、42のうち、ブロック42が最も古く参照されています。そのため、ブロック42が置き換え対象になります。
Q: 2回目のループでも、ブロック41がキャッシュにあるのはなぜですか？
A: Aの配列領域は4000〜4099番地で、ブロック番号は41です。A[98]もこの範囲内にあるため、1002番地はブロック41を参照します。
A: Aの配列領域は4000〜4099番地で、ブロック番号は41です。A[98]もこの範囲内にあるため、1002番地はブロック41を参照します。
関連キーワード: キャッシュメモリ、キャッシュヒット、キャッシュミス、LRU方式、更新フラグ
