FE22春後問1

FE22春後問1

基本情報技術者試験平成22年度春午後問1


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


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

f:id:tamagopanda:20100728213022p:image


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

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

f:id:tamagopanda:20100728213023p:image

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

〔繰返し処理〕

f:id:tamagopanda:20100726221029p:image


(1) 配列 A,B,C 及び D は 100 個の要素から成り,1 要素は 1 語である。添字は 0 から始まるものとする。

(2) データ領域の主記憶への割付けは,次のとおりとする。

[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)

(3) 変数 i はレジスタを使用し,主記憶への割付けは行わない。

(4) プログラム領域の内容は表 1 のとおりとする。参照ブロックの数値は,その命令を実行するときに CPU が参照するデータのブロック番号を示す。


表 1 プログラム領域の内容
番地 命令 処理の内容 参照ブロック
1000 LOAD R1,4400 -1 を R1 に設定 45
1001 LOAD R2,4401 i の初期値(99)を R2 に設定 45
1002 LOAD R3,4000,R2 A[i] の内容を R3 に設定 41
1003 ADD  R3,4100,R2 B[i] の内容を R3 に加算 42
1004 ADD  R3,4200,R2 C[i] の内容を R3 に加算 43
1005 STORE R3,4000,R2 R3 の内容を A[i] に格納 41
1006 STORE R3,4300,R2 R3 の内容を D[i] に格納 44
1007 ADDR R2,R1 i ← i-1 -
1008 JNM  1002 i≧0 ならば 1002 番地にジャンプ -


命令の形式は次のとおりとする。

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)プログラム実行開始時は,キャッシュ内にデータが入っていないものとする。

f:id:tamagopanda:20100728213024p:image

f:id:tamagopanda:20100728213020p:image

解答群
ア 0
イ 41
ウ 42
エ 43
オ 44
カ 45

設問2

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

〔新しいキャッシュ新ロジック〕

 参照されていない時間が最も長いブロックが格納されているバッファに参照ブロックを読み込む。

 なお,この新ロジックでは,順位の付け方も変されていて,キャッシュ内で参照されていない時間が最も長いブロックから順に 1,2,3 と番号が振られる。

f:id:tamagopanda:20100728213021p:image

解答群

 ブロック番号フラグ
410
411
420
421
430
431
440
441
450
451



問題掲載者による注意書き

  • 実際の問題文をテキスト化するにあたり,表記の難しい部分を以下のように置き換えている。
    • 丸 1,丸 2 (○の中に数字が入っている)で表記されていた文字は,機種依存文字のため, [1] ,[2] の様に置き換えた。(下線 [1],[2]等)
    • 空欄[ a ][ b ][ c ]等は,実際の問題文中では,四角で囲まれた,a,b,c だったが,[ ]で置き換えた。