Senの競技プログラミング備忘録

こけた問題を自分用の解説で載せる。けんちょんさんのブログを目指したい。質的にも量的にも。こけた問題だけに限定するけど

パタヘネ第6版 第1章演習問題解答

6th editionについての解答。

解答がおかしいとかがありましたらSen(@nonpro3)TwitterアカウントにDMやリプライ飛ばしてください。

大体ここにある。 ただし、これは最新の6th editionではないので、下に対応表と乗ってない問題の回答を載せる。

6th edition old
1.1 1.1
1.2 1.2
1.3 1.3
1.4 1.4
1.5 1.5
1.6 なし
1.7 1.6
1.8 1.7
1.9 1.8
1.10 1.9
1.11 1.10
1.12 1.11
1.13 1.12
1.14 なし
1.15 1.13
1.16 1.14

以下の者はすべて6th editionのもので新規追加された問題の回答。

1.6

平均改善率を$ a $とすると、$ \log _ 2 a $が9年にあたるので、答えは$ \frac{\log _ 2 2}{\log _ 2 a} \times 9 $

改善率は$ 100 - \sqrt[9](100 - 9年での改善) $で求めている。

指標 9年での改善 改善率 性能倍増に必要な年数
技術 56.25% 6.2% 7.569年
最高クロック周波数 1.471倍 4.38% 16.16年
整数IPC/コア 2倍 8.01% 9年
コア数 4倍 16.65% 4.5年
最大BRAMバンド幅 2.497倍 10.7% 6.817年
SP浮動小数 5.860倍 21.70% 3.528年
L3キャッシュ 3倍 12.98% 5.678年

1.9

ごめんなさい。わからないです。多分院試に出ないのでスキップさせていただきます……

1.11

$$ ウエーハあたりのダイの数 \approx \frac{ウエーハの面積}{ダイの面積} $$

$$ 歩留まり = \frac{1}{(1 + (\frac{単位面積の欠陥数 \times ダイの面積}{2})) ^ 2} $$

この2つの式を使う。後者は経験則。円周率は3.14とした。

1.11.1

直径15cm->$ \frac{1}{1.02207 ^ 2} = 95.73 $%

直径20cm->$ \frac{1}{1.04867 ^ 2} = 90.93 $%

1.11.2

良品のダイあたりのコストは、$ \frac{ウェーハあたりのコスト}{ダイの数×歩留まり率} $。

直径15cm->$ \frac{12}{84 \times 0.9573} \simeq 0.14922 $

直径20cm->$ \frac{15}{100 \times 0.9093} \simeq 0.16496 $

1.11.3

ダイの面積は、ウェーハあたりのダイを増やすので小さくなり、90.9%の縮小となる。

ダイの歩留まりは、計算式から、$ \frac{1}{1 + (1 \times 1)} ^ 2 = 0.25 $

と比べて、$ \frac{1}{1 + (1.15 \times 0.909)} = 0.2390 $

よって、下がる。

1.11.4

先ほどの式から逆算する。

改善前: $ 0.92 = \frac{1}{(1 + \frac{200 \times x}{2}) ^ 2}, x = 4.257 \times 10 ^ {-4} $

改善後: $ 0.95 = \frac{1}{(1 + \frac{200 \times x}{2}) ^ 2}, x = 2.598 \times 10 ^ {-4} $

1.14

浮動小数 ロードストア 分岐 その他
70s 80s 40s 60s

1.14.1

全体では$ 250-70 \times 0.2 = 250 - 14 = 234 \frac{234}{250} = 0.936 $ 6.4%

1.14.2

問題文が意味不明なのでスキップ(整数命令という言葉は問題文には出てきてないし、かかった時間の割合も当然不明)

1.14.3

分岐命令は40sだが、全体の250sの20%は50s。どうあがいても無理。

1.16

台数 実際の時間(s) 何倍速いか OHがない場合何倍速いか
2 54 1.85倍 2倍
4 29 3.45倍 4倍
8 16.5 6.06倍 8倍
16 10.25 9.76倍 16倍
32 7.125 14.04倍 32倍
64 5.5625 17.98倍 64倍
128 4.78125 20.91倍 128倍