計算問題の解き方・9/20
キャッシュ付き主記憶の実効アクセス時間とヒット率の逆算
キャッシュメモリのアクセス時間・ヒット率・主記憶のアクセス時間が表や文章で与えられ、実効アクセス時間（平均アクセス時間）を求めて比べるか、反対に実効アクセス時間からヒット率を求める形で出題されます。どちらも同じ 1 本の式を使って解きます。
公開過去問での出題：本試験系 10 回・免除試験 18 回（観測値）
覚える式
- 実効アクセス時間 ＝ ヒット率 h × キャッシュのアクセス時間 ＋ (1 − h) × 主記憶のアクセス時間
- ヒット率 h ＝ (主記憶のアクセス時間 − 実効アクセス時間) ÷ (主記憶のアクセス時間 − キャッシュのアクセス時間)
解き方の手順
- 問題文や表から、キャッシュのアクセス時間・主記憶のアクセス時間・ヒット率（または実効アクセス時間）を書き出します。ヒット率が % で書かれていたら、0.6 のような小数に直します。
- キャッシュが「なし」の構成は、主記憶のアクセス時間がそのまま実効アクセス時間になります。
- キャッシュが「あり」の構成は、h × キャッシュ時間 ＋ (1 − h) × 主記憶時間 で計算します。外れた割合 (1 − h) は主記憶の時間に掛けます。
- ヒット率を聞かれたら、h を未知数にして「式 ＝ 与えられた時間」とおき、1 次方程式として解きます。2 つの構成の時間が等しいと書かれていれば、2 つの式を等号でつなぎます。
- ヒット率が変わる問題は、まず今のヒット率を逆算し、変わった後のヒット率で式に入れ直します。「何%以上」と聞かれたら不等式にして、条件を満たす選択肢のうちいちばん小さい値を選びます。
- 最後に、求めたものがヒット率なのかミス率なのか、比べる順番が「短い順」なのか「長い順」なのかを問題文で確かめます。
例題
A～D を，主記憶の実効アクセス時間が短い順に並べたものはどれか。
| キャッシュメモリ 有無 | キャッシュメモリ アクセス時間（ナノ秒） | キャッシュメモリ ヒット率（%） | 主記憶 アクセス時間（ナノ秒） | |
|---|---|---|---|---|
| A | なし | − | − | 15 |
| B | なし | − | − | 30 |
| C | あり | 20 | 60 | 70 |
| D | あり | 10 | 90 | 80 |
ア A, B, C, D
イ A, D, B, C
ウ C, D, A, B
エ D, C, A, B
出典：平成31年度 春期 基本情報技術者試験 午前 問10（解き方は当サイト作成）
解き方と答えを見る
- A はキャッシュなしなので、実効アクセス時間 ＝ 15 ナノ秒です。
- B はキャッシュなしなので、実効アクセス時間 ＝ 30 ナノ秒です。
- C：0.6 × 20 ＋ (1 − 0.6) × 70 ＝ 12 ＋ 28 ＝ 40 ナノ秒です。
- D：0.9 × 10 ＋ (1 − 0.9) × 80 ＝ 9 ＋ 8 ＝ 17 ナノ秒です。
- 短い順に並べると A(15) → D(17) → B(30) → C(40) です。
答え：A, D, B, C（イ）
ひっかけ
- 「キャッシュがあれば必ず速い」と思い込んで C・D を前に並べる誤りです（例題のウ・エ）。キャッシュありでも主記憶が遅いと、キャッシュなしより遅くなることがあります。必ず数値を出して比べます。
- 主記憶のアクセス時間だけを見て並べる誤りです（例題のア）。キャッシュありの構成は、主記憶の時間ではなく式で出した実効アクセス時間で比べます。
- (1 − h) を掛け忘れて「h × キャッシュ時間 ＋ 主記憶時間」と足してしまう誤りです。ヒットした分は主記憶にアクセスしないので、主記憶の時間に掛けるのは外れた割合だけです。
- ヒット率を求める問題で、ミス率 (1 − h) を答えてしまう誤りです。方程式の未知数を h（当たる割合）にしたことを確かめ、h が 1 に近いほど実効時間がキャッシュの時間に近くなるかで検算します。
類題（手順を使って解く）
類題 1
2 種類の CPU の実効アクセス時間をそれぞれ h の式で書き、「処理時間が等しい」を等式にして h を解く手順（手順 4）が試されます。
図に示す構成で，表に示すようにキャッシュメモリと主記憶のアクセス時間だけが異なり，他の条件は同じ 2 種類の CPU X と Y がある。あるプログラムを CPU X と Y とでそれぞれ実行したところ，両者の処理時間が等しかった。このとき，キャッシュメモリのヒット率は幾らか。ここで，CPU 以外の処理による影響はないものとする。
図 構成: CPU に キャッシュメモリ（256kバイト）と 主記憶（256Mバイト）が接続された構成
表 アクセス時間（単位 ナノ秒）
| CPU X | CPU Y | |
|---|---|---|
| キャッシュメモリ | 40 | 20 |
| 主記憶 | 400 | 580 |
出典：令和6年度 基本情報技術者試験 科目A 公開問題 問3（問題文は IPA の公開問題。答えと解説はリンク先）
類題 2
今の平均応答時間から今のヒット率を逆算し、半分になったヒット率で式に入れ直す 2 段階の手順（手順 5）が試されます。
キャッシュサーバを利用した検索処理の平均応答時間は，キャッシュサーバでヒットした場合には 0.2 秒，ヒットしない場合には 2.2 秒である。現在の平均検索応答時間は，1.0 秒である。3 年後のキャッシュサーバのヒット率は，検索量の増加によって現状の半分になると予測されている。3 年後の平均検索応答時間は何秒か。ここで，その他のオーバヘッドは考慮しない。
出典：基本情報技術者試験 科目A免除 修了試験 20200614 実施分 問15（問題文は IPA の公開問題。答えと解説はリンク先）
類題 3
実効アクセス時間を与えてヒット率を未知数とする 1 次方程式を立て、ヒット率とミス率を取り違えずに答える手順（手順 4・6）が試されます。
主記憶のアクセス時間が 60 ナノ秒，キャッシュメモリのアクセス時間が 10 ナノ秒であるシステムがある。キャッシュメモリを介して主記憶にアクセスする場合の実効アクセス時間が 15 ナノ秒であるとき，キャッシュメモリのヒット率は幾らか。
出典：平成26年度 春期 基本情報技術者試験 午前 問10（問題文は IPA の公開問題。答えと解説はリンク先）