情報・アルゴリズムのテーマ一覧へ

基礎科目・情報・アルゴリズム

キャッシュとCPU時間

よく出る大学

5問H23・H25・H28・H29・R2

キャッシュメモリのヒット率から実効アクセス時間を求める計算と、CPIとクロック周波数からCPU実行時間を求める計算が出ます。

よく出る形

  • キャッシュと主記憶のアクセス時間，ヒット率から，平均の読み出し時間（実効アクセス時間）を求める
  • 一次キャッシュと二次キャッシュの2段になった場合の実効アクセス時間を求める
  • 命令の種類ごとの個数と CPI，クロック周波数から，プログラムの CPU 実行時間を求める
  • 2つの型がほぼ交互に出る：実効アクセス時間と，CPIからCPU時間。同じ型どうしは数字の入れ替えが多く，令和2は何倍速いかも問う

覚えること

  • キャッシュメモリは CPU の近くにある，小さくて速いメモリ。主記憶は大きいけれど遅いメモリ
  • ヒット率は，欲しいデータがキャッシュにある確率
  • 実効アクセス時間 ＝ ヒット率 × キャッシュの時間 ＋ (1 − ヒット率) × 主記憶の時間
  • 2段の場合は，まず「二次キャッシュと主記憶の平均時間」を求め，それを一次キャッシュが外れたときの時間として同じ式に入れる
  • CPI は1つの命令にかかるクロックの数
  • CPU 実行時間 ＝（命令の個数 × CPI を種類ごとに足した合計クロック数）÷ クロック周波数
  • 2.0GHz は1秒に 2.0×109 回のクロック，1クロックは 0.5ns。1クロックの時間 ＝ 1 ÷ 周波数（2.5GHz なら 0.4ns）
  • 平均 CPI ＝ 合計クロック数 ÷ 命令の総数
  • MIPS 値（1秒に何百万個の命令を実行できるか）＝ クロック周波数 ÷ 平均 CPI ÷ 106

解き方

  • 実効アクセス時間の例：キャッシュ 50ns，主記憶 450ns，ヒット率 90% のとき
0.9 × 50 ＋ 0.1 × 450 ＝ 45 ＋ 45 ＝ 90ns
  • 主記憶だけなら 450ns なので，450 ÷ 90 ＝ 5 倍速くなる
  • ヒット率を逆に求める時は，h を使って式を立て，不等号のまま h について解く
  • CPU 時間は，まず種類ごとに「個数 × CPI」を出して合計クロック数を求める
  • 合計クロック数をクロック周波数で割る。ns などの単位をそろえてから選択肢と比べる

ひっかけ

  • ヒットしたときの分（ヒット率 × キャッシュの時間）だけで止めず，外れたときの分を足す
  • 「何倍速いか」は，主記憶だけの時間 ÷ 実効アクセス時間（主記憶とキャッシュの時間の比ではない）
  • 一部の命令のCPIだけ下げても，全体の時間は同じ割合では減らない（合計クロック数で比べる）
このテーマの想定問題を解く

想定問題：1・2・3

このテーマの過去問（このサイトに解説がある 1問）

X で共有LINE で送る

平成に出た同じテーマ（4問）

このサイトにはまだ解説がありません。年度と題だけです。