エンベデッドシステムスペシャリスト 2009年午前2 問04

問題文

容量64kバイト、ブロックサイズ32バイトのキャッシュメモリをもつ32ビットMPUが、主記憶から1Mバイトの32ビット整数型配列データを連続して読み出した。このとき、キャッシュメモリのミスヒット率は何％か。ここで、配列データ以外のデータはレジスタに割り当てられているものとし、kは

2^{10}

、Mは

2^{20}

を表す。

🖊️ 解答を隠して解いてみる

ア：0.006

イ：0.05

ウ：6.4

エ：12.5（正解）

🔒 解説は解答すると表示されます

配列の整数型は32ビットなので、1要素の大きさは4バイトです。キャッシュのブロックサイズは32バイトのため、1ブロックには整数型配列の要素が8個入ります。

配列を先頭から順に読み出すと、各ブロックの最初の要素を読むときにミスし、同じブロック内の残り7要素を読むときはヒットします。したがって、8回のメモリアクセスにつき1回ミスします。

ミスヒット率 = \frac{1}{8} \times 100 = 12.5%

よって、エが正解です。

ア：0.006
ブロックサイズと要素サイズから求める「8要素に1回」という関係を使えていません。ミスヒット率は配列全体の容量比ではなく、メモリアクセスのうちミスした回数の割合です。
イ：0.05
ブロック内の要素数を正しく求められていない場合に生じやすい値です。32バイトのブロックには、4バイトの整数型要素が8個入ります。
ウ：6.4
キャッシュ容量と配列データの容量を比べた割合などと、ミスヒット率を混同した値と考えられます。ミスヒット率はブロックサイズと1要素の大きさから求めます。
エ：12.5
8回の読み出しにつき1回ミスするため、ミスヒット率は12.5％です。

キャッシュ容量が大きいほど、今回のミスヒット率も下がると考える
この問題では、連続読み出し時にブロック内の何要素を使うかがポイントです。1ブロックを8要素で利用するため、ミスヒット率は12.5％になります。
配列データ全体の容量に対するキャッシュ容量の割合を、ミスヒット率とする
ミスヒット率は、メモリアクセス回数に対するミス回数の割合です。容量同士の比ではありません。
ブロックを読み込んだ後も、同じブロック内の要素を読むたびにミスすると考える
ブロック単位でキャッシュに取り込まれるため、同じブロック内の後続要素はヒットします。

配列全体の大きさは1MiBですが、この問題では各ブロックの最初のアクセスで1回ミスし、そのブロックに含まれる残りの要素ではヒットします。実際には、1MiBの配列から32バイトずつブロックを読み込むため、ブロック数は

\frac{1 MiB}{32 B} = 32, 768

です。配列要素へのアクセス回数は

\frac{1 MiB}{4 B} = 262, 144

なので、ミスヒット率は

32, 768 \div 262, 144 \times 100 = 12.5%

と確認できます。

Q. キャッシュ容量64KiBは計算に使わないのですか？
A. この問題のミスヒット率を求める計算には、直接使いません。ブロックサイズと配列要素の大きさから、1ブロックあたりのアクセス回数を求めます。

Q. 配列がキャッシュ容量より大きくても、ミスヒット率は12.5％ですか？
A. このように配列を先頭から順に一度読み出す場合、ブロックごとに最初のアクセスでミスし、残りでヒットする関係は変わらないため、12.5％です。

関連キーワード: キャッシュメモリ、ブロックサイズ、ミスヒット率、局所性

\ せっかくなら /

エンベデッドシステムスペシャリストを
クイズ形式で学習しませんか？

すぐに利用可能！