阪大 情報科学研究科 専門科目（情報工学） 2020年度 院試 過去問 解答例・解説（全7問）

(1-1) 数の表現

科学技術計算では値の範囲が広いことが重要なので浮動小数点表現を用いる。一方，小型機器の制御では回路規模や処理の単純さが重要なので固定小数点表現を用いることが多い。2 進表現では，分母に $5$ を含む十進小数は有限桁にならない。

(1-2-1) 正の最大値

正規化数で指数部は $e=1,\ldots,14$ を用いる。最大は $e=14$，仮数部がすべて $1$ の場合である。 $$(1.111111111)_2\,2^{14-7} = \left(2-2^{-9}\right)2^7 = 256-\frac14 = 255.75.$$

(1-2-2) 正の最小値

非正規化数を用いないので，最小の正規化数は $e=1$，仮数部 $0$ の場合である。 $$1.000000000_2\,2^{1-7} = 2^{-6} = 0.015625.$$

(1-2-3) $-36.66$ のビット列

$36.66$ は $$36.66 = 1.145625\times 2^5$$ と正規化できる。指数部は $e=5+7=12=(1100)_2$。仮数部は $0.145625$ を 2 進小数に直し，9 ビットで切り捨てる。 $$0.145625 \simeq (0.001001010)_2.$$ したがって $$s=1,\qquad e=1100,\qquad m=001001010.$$

(1-2-4) 切り捨て丸めの問題

切り捨ては丸め誤差の向きが偏る。特に繰り返し計算では，毎回の小さな誤差が相殺されずに蓄積し，真値から系統的にずれていく。反復法の収束判定，差分計算，長い総和ではこの偏りが大きな誤差として現れやすい。

(2-1) 仮想記憶の語句

(2-2) LRU と FIFO

参照列を左から順に処理する。初期状態ではページ枠が空なので，最初の 3 回は必ずページフォールトである。

$$\begin{aligned} \text{LRU のフォールト位置} &=\{1,2,3,5,6,7,9,11,13\},\\ \text{FIFO のフォールト位置} &=\{1,2,3,5,7,11,12\}. \end{aligned}$$

(2-3) 許容されるページフォールト確率

ページフォールトがないとき，1 命令あたりのメモリアクセス時間は $$2\ \text{回}\times 2\ \mu\mathrm{s}=4\ \mu\mathrm{s}$$ である。1 回のメモリアクセスでページフォールトが確率 $p$ で発生すると，追加時間は $8000p\ \mu\mathrm{s}$ なので $$2(2+8000p)\le 1.1\times 4.$$ よって $$4+16000p\le 4.4,\qquad p\le 2.5\times 10^{-5}.$$

(2-4) ページフォールト削減策

参照列を変えない条件では，プロセスに割り当てるページ枠数を増やすのが直接的である。物理メモリを増やす，または同時実行プロセス数を抑えて各プロセスの常駐集合を大きくすれば，LRU で追い出されるページが減る。