基本情報技術者試験の過去問と解説
[TOP] [午前分野別] [午後分野別] [キーワード索引] [令和元年秋午前] [令和元年秋午後]

平成22年 春期 基本情報技術者 午後 問01
問01   5問選択

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

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

図1 キャッシュメモリと CPU 及び主記憶との関係

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

(1) 主記憶はブロック(1ブロックは 100 語から成る)に分割されている。 各ブロックには,その先頭番地が小さいものから順に 1, 2, 3, … とブロック番号が振られている。 主記憶とキャッシュメモリ間はブロック単位でデータが転送される。

(2) キャッシュメモリには,命令を保持しておく命令キャッシュと, データを保持しておくデータキャッシュの2種類がある。ここでは,データキャッシュ(以下, キャッシュという)だけを考える。

(3) キャッシュの構成は,図2のとおりとする。

@ キャッシュは,ディレクトリ部とデータ部から成る。

A データ部はバッファ1〜3の三つのバッファから成り,各バッファは1ブロック分の 主記憶の内容を保持できる。

B ディレクトリ部は,データ部のバッファ1〜3に対応したディレクトリ1〜3から成る。 それぞれのディレクトリは次の内容を保持する三つのフィールドから成る。

 なお,データ部のバッファが未使用の場合は,対応するディレクトリの三つの フィールドすべてに0が入っている。

(イ) ブロック番号:対応するデータ部のバッファが保持する主記憶のブロック 番号

(ロ) 順位 :キャッシュ内に最も古くから存在するブロックから順に 1, 2, 3 と 番号が振られる。

(ハ) フラグ:対応するデータ部のバッファにブロックを読み込んだとき,0に初期化される。 対応するデータ部のバッファに保持されている内容が CPU の処理によって変更されると,1に変わる。

           図2 キャッシュの構成

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

[繰返し処理]

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

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

@ Aの配列領域:4000 〜 4099 番地(ブロック番号 41)
    A[0]は 4000 番地,A[1] は 4001 番地という順に割り付けられる。
A Bの配列領域:4100 〜 4199 番地(ブロック番号 42)
B Cの配列領域:4200 〜 4299 番地(ブロック番号 43)
C Dの配列領域:4300 〜 4399 番地(ブロック番号 44)
D 定数 -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) プログラム実行開始時は,キャッシュ内にデータが入っていないものとする。

  図3 1000 番地の LOAD 命令を実行した直後のディレクトリ部

 図4 1006 番地の STORE 命令を最初に実行した直後のディレクトリ部

解答群

ア 0        イ 41        ウ 42

エ 43        オ 44        カ 45

解答 a ←クリックすると正解が表示されます

解答 b ←クリックすると正解が表示されます

解答 c ←クリックすると正解が表示されます

基本情報技術者試験


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

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

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

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

表2 ディレクトリ部の内容の変化

解答群

 ブロック番号フラグ
 ア    41   0
 イ    41   1
 ウ    42   0
 エ    42   1
 オ    43   0
 カ    43   1
 キ    44   0
 ク    44   1
 ケ    45   0
 コ    45   1
解答 d ←クリックすると正解が表示されます

解答 e ←クリックすると正解が表示されます

解答 f ←クリックすると正解が表示されます


[←前の問題] [次の問題→] [問題一覧表] [分野別] [基本情報技術者試験TOP ]