基本情報技術者過去問題平成22年春期午後問1(ハードウェア)

基本情報技術者過去問題平成22年春期午後問1

問1　ハードウェア

キャッシュメモリに関する次の記述を読んで，設問1，2に答えよ。

　キャッシュメモリとは，主記憶とCPUの間に置く高速アクセスが可能なメモリである。キャッシュメモリとCPU及び主記憶との関係を図1に示す。データをキャッシュメモリに保持しておくことによって，CPUは速度の遅い主記憶に直接アクセスしなくて済むので，処理の高速化が図れる。

　ここでは，ハードウェアのアーキテクチャを次のように仮定する。

主記憶はブロック(1ブロックは100語から成る)に分割されている。各ブロックには，その先頭番地が小さいものから順に1，2，3，… とブロック番号が振られている。主記憶とキャッシュメモリ間はブロック単位でデータが転送される。
キャッシュメモリには，命令を保持しておく命令キャッシュと，データを保持しておくデータキャッシュの2種類がある。ここでは，データキャッシュ(以下，キャッシュという)だけを考える。
キャッシュの構成は，図2のとおりとする。
1. キャッシュは，ディレクトリ部とデータ部から成る。
2. データ部はバッファ1～3の三つのバッファから成り，各バッファは1ブロック分の主記憶の内容を保持できる。
3. ディレクトリ部は，データ部のバッファ1～3に対応したディレクトリ1～3から成る。それぞれのディレクトリは次の内容を保持する三つのフィールドから成る。
　なお，データ部のバッファが未使用の場合は，対応するディレクトリの三つのフィールドすべてに0が入っている。
(イ)ブロック番号：
対応するデータ部のバッファが保持する主記憶のブロック番号
(ロ)順位：
キャッシュ内に最も古くから存在するブロックから順に1，2，3と番号が振られる。
(ハ)フラグ：
対応するデータ部のバッファにブロックを読み込んだとき，0に初期化される。対応するデータ部のバッファに保持されている内容がCPUの処理によって変更されると，1に変わる。

　擬似言語で表現された次の繰返し処理を実行する場合について考える。

配列A，B，C及びDは100個の要素から成り，1要素は1語である。添字は0から始まるものとする。
データ領域の主記憶への割付けは，次のとおりとする。
1. Aの配列領域：4000～4099 番地(ブロック番号41)
  A[0]は4000番地，A[1] は4001番地という順に割り付けられる。
2. Bの配列領域：4100～4199 番地(ブロック番号42)
3. Cの配列領域：4200～4299 番地(ブロック番号43)
4. Dの配列領域：4300～4399 番地(ブロック番号44)
5. 定数－1と 99 の格納領域：4400，4401番地(ブロック番号45)
変数iはレジスタを使用し，主記憶への割付けは行わない。
プログラム領域の内容は表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に示す。　に入れる正しい答えを解答群の中から選べ。

参照ブロックがキャッシュ内にある場合は，キャッシュ内のデータが使用される。
参照ブロックがキャッシュ内にない場合(以下，ミスという)は，参照ブロックが主記憶からキャッシュに読み込まれ，対応するディレクトリのフラグの内容は0に初期化される。
CPUが参照ブロックに対してSTORE命令を実行した場合は，対応するディレクトリのフラグの内容は1に変わる。
ミスが起こったときにキャッシュ内に未使用のバッファがある場合は，未使用のバッファの中で最も番号が小さいバッファに参照ブロックを読み込み，順位を更新する。
ミスが起こったときにキャッシュ内に未使用のバッファがない場合は，次のキャッシュ更新ロジックを用いる。
　キャッシュ内に最も古くから存在するブロックが格納されているバッファに，参照ブロックを読み込み，順位を更新する。ただし，対応するディレクトリのフラグの内容が1だったときは，そのブロックを主記憶に書き戻してから，参照ブロックを読み込み，順位を更新する。
プログラム実行開始時は，キャッシュ内にデータが入っていないものとする。

a，b，c に関する解答群

解答選択欄

解答

a=カ
b=エ
c=ウ

解説

設問1は、キャッシュの更新アルゴリズムにFIFO(先入先出し)を採用した場合のデータの入れ替えについて問う問題です。

〔aについて〕
プログラム開始時は、すべてのキャッシュ内にデータが入っていない状態です。
プログラム開始直後のLOAD命令「LOAD R1, 4400」は、レジスタR1に主記憶4400番地のデータを読み込む命令ですが、主記憶4400番地のデータはキャッシュに存在しない(ミスヒット)ので、一旦主記憶からキャッシュに読み込む処理が必要になります。

このときデータを読込む場所は、(4)「ミスが起こったときにキャッシュ内に未使用のバッファがある場合は、未使用のバッファの中で最も番号が小さいバッファに参照ブロックを読み込み、順位を更新する」の記述より、未使用領域の中で最も番号が小さいデータ部のバッファ1です。よって、バッファ1に4400番地のデータが存在するブロック番号45番を読込むことになります。

この読込みによって、ディレクトリ1の内容は「ブロック番号45、順位1、フラグ0」に更新されます。

∴a＝カ：45

〔b、cについて〕
1006番地の命令までについて参照ブロック、及びディレクトリ部の内容を図表で表してみるとよくわかります。キャッシュ更新アルゴリズムはFIFO方式なので、単純に古いものから入れ替わっていくことになります。

命令ごと主記憶とキャッシュの入替えを説明すると、

命令1000番地: ブロック45を未使用域バッファ1に読込む
命令1001番地: ブロック45は、バッファ1に存在するのでそのまま
命令1002番地: ブロック41を未使用域バッファ2に読込む
命令1003番地: ブロック42を未使用域バッファ3に読込む
命令1004番地: キャッシュがすべて埋まっているので更新処理が発生する。ロードされたのが最も古いバッファ1のブロック45とブロック43を入れ替える。
命令1005番地: ブロック41は、バッファ2に存在するのでそのまま
命令1006番地: キャッシュがすべて埋まっているので更新処理が発生する。
ロードされたのが最も古いバッファ2のブロック41とブロック44を入れ替える

∴b＝エ：43
　c＝ウ：42

設問2

設問1の(5)のキャッシュ更新ロジックを，次に示す新しいキャッシュ更新ロジックに変えた場合の，ディレクトリ部のブロック番号とフラグの内容の変化を，表2に示す。　に入れる正しい答えを，解答群の中から選べ。

〔新しいキャッシュ更新ロジック〕
　参照されていない時間が最も長いブロックが格納されているバッファに，参照ブロックを読み込む。
　なお，この更新ロジックでは，順位の付け方も変更されていて，キャッシュ内で参照されていない時間が最も長いブロックから順に1，2，3と番号が振られる。

d，e，f に関する解答群

解答選択欄

解答

d=イ
e=ク
f=ウ

解説

設問2では、キャッシュの更新時に「参照されていない時間が最も長いブロックが格納されているバッファに、参照ブロックを読み込む」というLRU方式(Least Recently Used)のロジックを採用しています。

問題文中にディレクトリ部の変化の様子をまとめた表2「ディレクトリ部の内容の変化」が与えられていますので、この表に順位の欄を追加し、網掛け部分を書き加えていくことで　に入るものを導きます。

以下は、表2「ディレクトリ部の内容の変化」にLRU方式の更新ロジックを採用したときの順位と読み込まれたブロック番号の遷移を書き入れたものです。表中の"in"は、バッファが保持するブロックの入れ替えが起こったことを表しています。

表をたどりながら空欄を埋めていくと、
　d＝イ：ブロック番号41，フラグ1
　e＝ク：ブロック番号44，フラグ1
　f＝ウ：ブロック番号42，フラグ0
が適切です。

平成22年春期午後問題一覧

問1　問2　問3　問4　問5　問6　問7　問8　問9　問10　問11　問12　問13　採点講評