パタヘネ学習#1 第1章のまとめと問題演習

第1章のまとめ

コンピュータの性能諸元のうちCPUの性能に着目する
CPUの性能の指標として任意のプログラムのCPU実行時間(区別が困難であるためOSのコストも含む)を絶対的なものとする
CPU実行時間 = プログラムの実行命令数 × ${\displaystyle\frac{クロックサイクル数}{命令}}$ × ${\displaystyle\frac{秒}{クロックサイクル}}$
= ${\displaystyle\frac{プログラムの実行命令数 × CPI}{クロック周波数}}$
CPUの性能比較に際して実行命令数・CPI・クロック周波数のそれぞれについて命令セットアーキテクチャや命令ミックスといった相互作用の関係を理解し、比較条件を十分に考慮しなければならない
CPIはプログラムを構成する命令に必要なクロック数の平均をより大枠の命令グループ(クラス)毎に集約し、抽象化していったもの
CPIの考え方は「p.36 例題コード系列の比較」である程度理解できた

1.13 演習問題

※結果の見易さおよび計算の簡略化のため適宜、小数点以下の値を丸めている

1.1

省略

1.2

a. 自動車製造における組み立てライン

　… 各作業工程の分業による生産効率向上 = 「パイプライン処理を通じた性能の向上」

b. 吊り橋のケーブル

　… ケーブルの多重化による負担の分散 = 「並列処理を通じた性能の向上」

c. 風情報を組み入れた航空システムおよび航海システム

　… 予測による安全性・燃費向上 = 「予測を通じた性能の向上」

d. 高層ビルの高速エレベータ

　… 最速の移送経路の速度向上 = 「一般的な場合を高速化する」

e. 図書館の予備の机

　… 書架を外部記憶装置と見立てた場合の補助記憶装置 = 「記憶階層」

f. 切替時間を短縮するための、CMOS トランジスタ上のゲート領域の増大

　… 集積度の向上を見越した設計方針 = 「Mooreの法則に則って設計する」

g. 新しい原子炉技術によってもたらされた発電量の増大によって可能となった、電磁式の航空機射出機を追加すること（現在のものの動力源は蒸気であるのに対して、電気を動力源とする）

　… 別系統の動力源による代替システムの追加 = 「冗長性を通じた信頼性」

h. 走行車線監視システムや自動走行制御システムのような、既に基本的に車に装備されている既存のセンサー・システムを部分的に利用して制御する、自動運転自動車の製造

　… 既存のシステムの拡張 = 「設計を単純化するために抽象化する」

1.3

高水準言語プログラム → コンパイラ → (アセンブリ言語命令 → アセンブラ →) 機械語命令

1.4

a.

フレームバッファの最小サイズ = 1フレーム当たりのピクセル数 × 1ピクセル当たりのビット数 ÷ 8

1フレーム当たりのピクセル数 = 1280 × 1024 ピクセル

1ピクセル当たりのビット数 = 8 ビット

フレームバッファの最小サイズ = 1280 × 1024 × 8 ÷ 8 = 1,310,720 バイト

b.

フレームの送信時間 = フレームバッファの最小サイズ ÷ 1秒当たりの送信ビット

1秒当たりの送信ビット = 100Mビット / 秒 = 12,500,000 バイト

フレームの送信時間 = 1,310,720 ÷ 12,500,000 = 0.1048576 秒

1.5

	クロック周波数	CPI
P1	3.0 GHz	1.5
P2	2.5 GHz	1.0
P3	4.0 GHz	2.2

a.

秒当たりの命令数 = MIPS = ${\frac{実行命令数}{実行時間 × 10^6}}$ = ${\frac{クロック周波数}{CPI × 10^6}}$

P1のMIPS … ${\frac{3.0 × 10^9}{1.5 × 10^6}}$ = 2.0 × 10³

P2のMIPS … ${\frac{2.5 × 10^9}{1.0 × 10^6}}$ = 2.5 × 10³

P3のMIPS … ${\frac{4.0 × 10^9}{2.2 × 10^6}}$ = 1.82 × 10³

秒当たりの命令数で表した場合、P2の性能が最高

b.

クロックサイクル数 = CPU実行時間 × クロック周波数実行命令数 = クロックサイクル数 ÷ CPI

P1のサイクル数 … 10 × 3.0 × 10⁹ = 30 × 10⁹

P1の命令数 … 30 × 10⁹ ÷ 1.5 = 20 × 10⁹

P2のサイクル数 … 10 × 2.5 × 10⁹ = 25 × 10⁹

P2の命令数 … 25 × 10⁹ ÷ 1.0 = 25 × 10⁹

P3のサイクル数 … 10 × 4.0 × 10⁹ = 40 × 10⁹

P3の命令数 … 40 × 10⁹ ÷ 2.2 = 18.18 × 10⁹

c.

CPIおよびクロック周波数の増大に対して実行命令数は変化しないものと仮定すると以下の等式が成り立つ

実行時間 × (1 - 0.3) = ${\frac{実行命令数 × CPI × (1 + 0.2)}{改善後のクロック周波数}}$

改善後のクロック周波数 = ${\frac{実行命令数 × CPI × 1.2}{10 × 0.7}}$

P1の改善後のクロック周波数 … ${\frac{20 × 10^9 × 1.5 × 1.2}{7}}$ = 5.14 × 10⁹ = 5.14 GHz

P2の改善後のクロック周波数 … ${\frac{25 × 10^9 × 1.0 × 1.2}{7}}$ = 4.29 × 10⁹ = 4.29 GHz

P3の改善後のクロック周波数 … ${\frac{18.18 × 10^9 × 2.2 × 1.2}{7}}$ = 6.86 × 10⁹ = 6.86 GHz

1.6

	クロック周波数	AのCPI	BのCPI	CのCPI	DのCPI
P1	2.5 GHz	1	2	3	3
P2	3.0 GHz	2	2	2	2

	A	B	C	D
各クラスの命令数	0.1E6	0.2E6	0.5E6	0.2E6

a. & b.

グローバルCPI = ${\frac{クロックサイクル数}{実行命令数}}$ = ${\frac{(各クラスCPI × 各命令数)の総和}{実行命令数}}$

CPUの実行時間 = ${\frac{クロックサイクル数}{クロック周波数}}$

P1のクロックサイクル数 … (1 × 0.1 × 10⁶) + (2 × 0.2 × 10⁶) + (3 × 0.5 × 10⁶) + (3 × 0.2 × 10⁶) = 2.6 × 10⁶

P1のグローバルCPI … ${\frac{2.6 × 10^6}{1.0 × 10^6}}$ = 2.6

P1のCPU実行時間 … ${\frac{2.6 × 10^6}{2.5 × 10^9}}$ = 1.04 × $10^{-3}$ 秒

P2のクロックサイクル数 … (2 × 0.1 × 10⁶) + (2 × 0.2 × 10⁶) + (2 × 0.5 × 10⁶) + (2 × 0.2 × 10⁶) = 2.0 × 10⁶

P2のグローバルCPI … ${\frac{2.0 × 10^6}{1.0 × 10^6}}$ = 2.0

P2のCPU実行時間 … ${\frac{2.0 × 10^6}{3.0 × 10^9}}$ = 0.67 × $10^{-3}$ 秒

P2の実装形態の方が速い

1.7

	動的命令数	実行時間
コンパイラA	1.0E9	1.1 秒
コンパイラB	1.2E9	1.5 秒

a.

平均CPI = ${\frac{CPU実行時間}{動的命令数 × クロックサイクル時間}}$

コンパイラAでコンパイルしたプログラムの平均CPI … ${\frac{1.1}{1.0 × 10^9 × 1 × 10^{-9}}}$ = 1.1

コンパイラBでコンパイルしたプログラムの平均CPI … ${\frac{1.5}{1.2 × 10^9 × 1 × 10^{-9}}}$ = 1.25

b.

CPU実行時間 = 動的命令数 × 平均CPI × クロックサイクル時間

実行するプロセッサの種類がa.のものとはそれぞれ異なると思われるが、平均CPIは変化しないものと仮定すると以下の等式が成り立つ

1.0 × 10⁹ × 1.1 × Aのクロックサイクル時間(ACT) = 1.2 × 10⁹ × 1.25 × Bのクロックサイクル時間(BCT)

${\frac{ACT}{BCT}}$ = ${\frac{1.2 × 10^9 × 1.25}{1.0 × 10^9 × 1.1}}$ = 1.36

コンパイラAによって生成されたコードを実行したプロセッサのクロックはコンパイラBによって生成されたコードを実行したプロセッサのクロックよりも1.36倍遅い

c.

	動的命令数	平均CPI
新しいコンパイラ	0.6E9	1.1

元のプロセッサのクロックサイクル時間 … 1ns = $10^{-9}$ 秒

新しいコンパイラで生成されたコードのCPU実行時間 = 0.6 × 10⁹ × 1.1 × $10^{-9}$ = 0.66 秒

コンパイラAとの比較 … ${\frac{1.1}{0.66}}$ = 1.67

新しいコンパイラで生成されたコードの方がコンパイラAで生成されたコードより1.67倍速い

コンパイラBとの比較 … ${\frac{1.5}{0.66}}$ = 2.27

新しいコンパイラで生成されたコードの方がコンパイラBで生成されたコードより2.27倍速い

1.8

省略

1.9

	算術命令	ロード／ストア命令	分岐命令
あるプロセッサのCPI	1	12	5

	算術命令	ロード／ストア命令	分岐命令
あるプログラムの命令数	2.56E9	1.28E9	0.256E9

プロセッサ当たりの算術命令とロード／ストア命令の数は0.7 × p (pはプロセッサの数)になる (問題文より)

→ 問題の意味が少々不明だが、プロセッサ当たりの命令数はプロセッサの数で割るのが妥当であることから0.7 × pで除した値をプロセッサ当たりの命令数と仮定する

1.9.1

CPUの実行時間 = ${\frac{クロックサイクル数}{クロック周波数}}$

クロックサイクル数 = (各命令クラスの実行命令数 × 各命令クラスのCPI) の総和

コアの数が1の場合のクロックサイクル数 = 2.56 × 10⁹ × 1 + 1.28 × 10⁹ × 12 + 0.256 × 10⁹ × 5 = 2.56 × 10⁹ + 15.36 × 10⁹ + 1.28 × 10⁹ = 19.2 × 10⁹

コアの数が1の場合のCPUの実行時間 = ${\frac{19.2 × 10^9}{2.0 × 10^9}}$ = 9.6 秒

コア数が $n (n>1)$ の場合のクロックサイクル数 = 2.56 × 10⁹ × 1 ÷ 0.7 $n$ + 1.28 × 10⁹ × 12 ÷ 0.7 $n$ + 0.256 × 10⁹ × 5 = (2.56 × 10⁹ + 15.36 × 10⁹) ÷ 0.7 $n$ + 1.28 × 10⁹ = ${\frac{25.6 × 10^9}{n}}$ + 1.28 × 10⁹

コア数が $n (n>1)$ の場合のCPU実行時間 = ${\frac{\frac{25.6 × 10^9}{n} + 1.28 × 10^9}{2.0 × 10^9}}$ = ${\frac{12.8}{n}}$ + 0.64 秒

コアの数が2の場合のCPUの実行時間 = ${\frac{12.8}{2}}$ + 0.64 = 7.04 秒

コアの数が2の場合の相対速度向上率 = (9.6 ÷ 7.04 - 1) × 100 = (1.36 - 1) = 36 %

コアの数が4の場合のCPUの実行時間 = ${\frac{12.8}{4}}$ + 0.64 = 3.84 秒

コアの数が4の場合の相対速度向上率 = (9.6 ÷ 3.84 - 1) × 100 = (2.5 - 1) = 150 %

コアの数が8の場合のCPUの実行時間 = ${\frac{12.8}{8}}$ + 0.64 = 2.24 秒

コアの数が8の場合の相対速度向上率 = (9.6 ÷ 2.24 - 1) × 100 = (4.29 - 1) = 329 %

1.9.2

以下、算術命令のCPIが倍になった場合の計算

コアの数が1の場合のクロックサイクル数 = 2.56 × 10⁹ × 2 + 1.28 × 10⁹ × 12 + 0.256 × 10⁹ × 5 = 5.12 × 10⁹ + 15.36 × 10⁹ + 1.28 × 10⁹ = 21.76 × 10⁹

コアの数が1の場合のCPUの実行時間 = ${\frac{21.76 × 10^9}{2.0 × 10^9}}$ = 10.88 秒

コア数が $n (n>1)$ の場合のクロックサイクル数 = 2.56 × 10⁹ × 2 ÷ 0.7 $n$ + 1.28 × 10⁹ × 12 ÷ 0.7 $n$ + 0.256 × 10⁹ × 5 = (5.12 × 10⁹ + 15.36 × 10⁹) ÷ 0.7 $n$ + 1.28 × 10⁹ = ${\frac{29.26 × 10^9}{n}}$ + 1.28 × 10⁹

コア数が $n (n>1)$ のCPU実行時間 = ${\frac{\frac{29.26 × 10^9}{n} + 1.28 × 10^9}{2.0 × 10^9}}$ = ${\frac{14.63}{n}}$ + 0.64 秒

コアの数が2の場合のCPUの実行時間 = ${\frac{14.63}{2}}$ + 0.64 = 7.96 秒

コアの数が4の場合のCPUの実行時間 = ${\frac{14.63}{4}}$ + 0.64 = 4.3 秒

コアの数が8の場合のCPUの実行時間 = ${\frac{14.63}{8}}$ + 0.64 = 2.47 秒

コア数が増えるにつれて算術命令のCPI倍増によるCPU実行時間の増加は緩和される

1.9.3

コアの数が4の場合のCPUの実行時間 = ${\frac{12.8}{4}}$ + 0.64 = 3.84 秒

ロード／ストア命令のCPIを $X$ と置くと以下の等式が成り立つ

3.84 = 2.56 × 10⁹ + 1.28 $X$ × 10⁹ + 1.28 × 10⁹ = (3.84 + 1.28 $X$ ) × 10⁹

1.28 $X$ = 3.84 × $10^{-9}$ -3.84

$X$ < 0

CPIが負数となるため実現不可能

1.10

省略

1.11

命令数	実行時間	参照時間
2.389E12	750s	9650s

1.11.1

CPI = ${\frac{CPU実行時間}{命令数 × クロックサイクル時間}}$ = ${\frac{750}{2.389 × 10^{12} × 333 × 10^{-12}}}$ = 0.94

1.11.2

SPECratioは、SPECから提供された基準時間を測定された実行時間で割っただけのものである. (p.47 図1.18 註より)

問題文およびp.47 図1.18 よりbzip2の基準時間 = 9,650 秒

SPECratio = 基準時間 ÷ 実行時間 = 9650 ÷ 750 = 12.87

1.11.3

実行するプログラムの命令数の増加はクロックサイクル時間には影響しないと仮定する

（CPIの変化なしは一部の命令のクロックサイクル数の増加で均衡したと考えられる）

CPU実行時間 = 命令数 × CPI × クロックサイクル時間 = 2.389 × 10¹² × (1 + 0.1) × 0.94 × 333 × $10^{-12}$ = 823 秒

増加率 = (823 ÷ 750 - 1) × 100 = 9.73 %

1.11.4

CPU実行時間 = 命令数 × CPI × クロックサイクル時間 = 2.389 × 10¹² × (1 + 0.1) × 0.94 × (1 + 0.05) × 333 × $10^{-12}$ = 864 秒

増加率 = (864 ÷ 750 - 1) × 100 = 15.2 %

1.11.5

1.11.2のSPECratio = 9650 ÷ 823 = 11.72

1.11.2のSPECratioの減少率 = (1- 11.72 ÷ 12.87) × 100 = 8.94 %

1.11.3のSPECratio = 9650 ÷ 864 = 11.17

1.11.3のSPECratioの減少率 = (1- 11.17 ÷ 12.87) × 100 = 13.2 %

1.11.6

クロック周波数	命令数	実行時間	SPECratio
4GHz	2.031E12	700s	13.7

命令数 = 2.389 × (1 - 0.15) × 10¹² = 2.031 × 10¹²

CPI = ${\frac{CPU実行時間 × クロック周波数}{命令数}}$ = ${\frac{700 × 0.004 × 10^{12}}{2.031 × 10^{12}}}$ = 1.38

1.11.7

クロック・サイクル数を減らす方向の技法は、クロック・サイクル時間を延ばすように作用することが多い (p.34より)

クロック周波数はクロック・サイクル時間の逆数であることから似ているとは言わないまでも二律相反の関係性にはあると言える

1.11.8 〜 1.11.10

省略

1.12

	クロック周波数	平均CPI	命令
P1	4 GHz	0.9	5.0E9
P2	3 GHz	0.75	1.0E9

1.12.1

P1とP2のCPU実行時間を求める

P1のCPU実行時間 = ${\frac{5.0 × 10^{9} × 0.9}{4 × 10^9}}$ = 1.125 秒

P2のCPU実行時間 = ${\frac{1.0 × 10^{9} × 0.75}{3 × 10^9}}$ = 0.25 秒

同じプログラムを実行していると仮定すると、P2の方が性能が高い

よってクロック周波数が最大のコンピュータの性能が最も高いとは言い切れない

1.12.2

問題文より以下の等式が成り立つ

${\frac{1.0 × 10^{9} × CPI}{4 × 10^9}}$ = ${\frac{ P2の命令数× CPI}{3 × 10^9}}$

P2の命令数 = ${\frac{1.0 × 10^{9} × 3 × 10^9}{4 × 10^9}}$ = 0.75 × 10⁹

1.12.3

MIPS = ${\frac{実行命令数}{実行時間 × 10^6}}$ = ${\frac{クロック周波数}{CPI × 10^6}}$

P1のMIPS = ${\frac{4 × 10^9}{0.9 × 10^6}}$ = 4.44 × 10³

P2のMIPS = ${\frac{3 × 10^9}{0.75 × 10^6}}$ = 4.00 × 10³

1.12.1で求めたP1とP2のCPU実行時間よりMIPS値の大きいプロセッサの方が性能が高いとは言えない

1.12.4

P1のMFLOPS = ${\frac{実行命令数 × 0.4}{実行時間 × 10^6}}$ = ${\frac{クロック周波数 × 0.4}{CPI × 10^6}}$ = ${\frac{4.0 × 0.4 × 10^9}{0.9 × 10^6}}$ = 1.78 × 10³

P1のMFLOPS = ${\frac{実行命令数 × 0.4}{実行時間 × 10^6}}$ = ${\frac{クロック周波数 × 0.4}{CPI × 10^6}}$ = ${\frac{3.0 × 0.4 × 10^9}{0.75 × 10^6}}$ = 1.6 × 10³

1.13

省略

1.14

	浮動小数点命令	整数命令	ロード／ストア命令	分岐命令
命令数	50 × 10⁶	110 × 10⁶	80 × 10⁶	16 × 10⁶
CPI	1	1	4	2

1.14.1

CPIの改善によりプログラムの実行速度を2倍に高めるためにはクロック周波数と命令数が不変であると仮定してクロックサイクル数を半減させる必要がある

浮動小数点命令のCPIを $X$ と置くと以下の等式が成り立つ

50 × 10⁶ × $X$ + 110 × 10⁶ × 1 + 80 × 10⁶ × 4 + 16 × 10⁶ × 2 = ${\frac{50 × 10^6 × 1 + 110 × 10^6 × 1 + 80 × 10^6 × 4 + 16 × 10^6 × 2}{2}}$

(50 $X$ + 462) × 10⁶ = 256

$X$ = ${\frac{256 × 10^{-6} -462}{50}}$