2016-10-02

パタヘネ学習#4 第4〜6章の読了

パタヘネ

第4〜6章および付録A〜E章を読了した。

第3章まではプログラミング言語の低層理解のために多少時間がかかっても演習問題を解いてきたが、第4章以降は理解の及んでいないハードウェア寄りの内容が色濃くなり、順番に内容を修めて問題を解くというスタイルでは効率的にもモチベーション的にも時間がもったいないなと感じた。

なので、最初は要点を押さえつつ流し読みをして、後で定期的に読み返しつつ、問題をつまみ食いして記憶に定着させていこうというスタイルに方針転換した。

如何せん働いている身なので、順番に一変に全部に時間をかけ過ぎるとすぐ連続性を失ってしまうというのは言い訳になるだろうか。

内容としては第4章、第5章のプロセッサの内部構成と命令実行の仕組みおよびキャッシュの仕組みとDGEMMへの応用が興味深かった。

また、ネット付録2−15節のJavaのMIPSコードも興味深く、JVMについてもそのうち学んでみたいと思った。

気が向いたら更新していくとして、ひとまず、パタヘネはここで一区切り。

2016-09-11

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

パタヘネ

第3章のまとめ

四則演算は基本的にシフトと加算に分解される
浮動小数点数の加算には精度に限界がある為、加算順序の結合則が当てはまらない

3.12 演習問題

3.1〜2.2

省略

3.3

16進数から2進数への変換は各桁の数を4bitの2進数で表したものを連結すれば良い

0x5ED4 = 0101 1110 1101 0100

基数が16であるメリットは2桁で1byteを表現でき、処理単位のうえで2進数のニーモニックに最適である点

3.4〜3.5

省略

3.6

与えられた二つの符合なし10進数を8ビットの2進数に変換すると以下となる

185 = 1011 1001

122 = 0111 1010

185 - 122 = 0011 1111

以上より最上位ビットの桁借りは発生しないため、オーバーフローもアンダーフローも発生しない

3.7

8ビットの符合付き2進数の最大値は10進数で2⁷ - 1 = 127 であるから185を変換する時点でオーバーフローが発生する

3.8

やはり185を変換する時点でオーバフローが発生する

符号付きの8ビットという指定の範囲では問題として意図が不明なように思われる

3.9

8ビットの符合付き2進数の最大値は10進数で2⁷ - 1 = 127 であるから151を変換する時点でオーバーフローが発生する

151(-105) = 1001 0111

214(-42) = 1101 0110

上記に目をつぶり、強引にこの2数を加算すると以下となる

151 + 214 = 1 0110 1101

9ビット目に桁借りが発生し、オーバーフローしていることから飽和演算結果は以下となる

1000 0000 = -128

3.10

減算につき、前問3.9の符合付き214とした値の2の補数を求める

-214(42) = 0010 1010

151(-105) - 214(-42) = 1100 0001

桁借りが発生していないことから、飽和は発生しない

結果を前述までの強引な読替えを無視して純粋な8ビットの符合付き整数として捉えると以下となる

1100 0001 = -63

3.11

前問3.9より与えられた8ビットの符合なし整数の2数を加算すると以下となる

151 + 214 = 1 0110 1101

9ビット目に桁上がりが発生し、オーバーフローしていることから飽和演算結果は以下となる

1111 1111 = 255

3.12

与えられた二つの符合なし8進数を6ビットの2進数に変換すると以下となる

062 = 110 010 (= 50)

012 = 001 010 (= 10)

処理サイクル	ステップ	乗数	被乗数	積
0	初期値	001 010	110 010	000 000
1	1a：0 → 演算なし	001 010	110 010	000 000
1	2：被乗数を左へシフト	001 010	110 100	000 000
1	3：乗数を右へシフト	000 101	110 100	000 000
2	1a：1 → 積 = 積 + 被乗数	000 101	110 100	110 100
2	2：被乗数を左へシフト	000 101	101 000	110 100
2	3：乗数を右へシフト	000 010	101 000	110 100
3	1a：0 → 演算なし	000 010	101 000	110 100
3	2：被乗数を左へシフト	000 010	010 000	110 100
3	3：乗数を右へシフト	000 001	010 000	110 100
4	1a：1 → 積 = 積 + 被乗数	000 001	010 000	000 100
4	2：被乗数を左へシフト	000 001	100 000	000 100
4	3：乗数を右へシフト	000 000	100 000	000 100
5	1a：0 → 演算なし	000 000	100 000	000 100
5	2：被乗数を左へシフト	000 000	000 000	000 100
5	3：乗数を右へシフト	000 000	000 000	000 100
6	1a：0 → 演算なし	000 000	000 000	000 100
6	2：被乗数を左へシフト	000 000	000 000	000 100
6	3：乗数を右へシフト	000 000	000 000	000 100
7	1a：0 → 演算なし	000 000	000 000	000 100
7	2：被乗数を左へシフト	000 000	000 000	000 100
7	3：乗数を右へシフト	000 000	000 000	000 100
8	1a：0 → 演算なし	000 000	000 000	000 100
8	2：被乗数を左へシフト	000 000	000 000	000 100
8	3：乗数を右へシフト	000 000	000 000	000 100

処理サイクル 1のステップ 2：被乗数を左シフトする時点でオーバーフローが発生する

よって設問として答えを6ビットで表現しようというのなら、オーバーフローが発生し、正しい答えを成さない

3.13

省略

3.14

判定処理を除くと、乗算を行うのに必要なステップは以下の3つとなる

被乗数またはゼロを積に加算
被乗数レジスタを1ビット左にシフト
乗数レジスタを1ビット右にシフト

また、整数の長さが8ビットであることから積レジスタの最大長を8ビットと解釈仮定すると、乗数レジスタの最大長は4ビットとなる

よって本問の解答にあたり、乗算ループの回数は4回と仮定する

乗算処理をハードウェアで行う場合、被乗数と乗数のシフトを同時に実行できることから1回の乗算ループで必要なステップ数は2回となり、乗算を行うのに必要な時間は以下となる

2（ステップ） × 4（単位時間） × 4（ループ回数） = 32単位時間

乗算処理をソフトウェアで行う場合、被乗数と乗数のシフトを順に実行しなければならないことから1回の乗算ループで必要なステップ数は3回となり、乗算を行うのに必要な時間は以下となる

3（ステップ） × 4（単位時間） × 4（ループ回数） = 48単位時間

3.15

省略

3.16

整数の長さが8ビットであることから積レジスタの最大長を8ビットと解釈仮定すると、乗数レジスタと被乗数レジスタの最大長は4ビットなる

図3.7に示されている方法より、処理にかかる時間は2を底とした乗数レジスタ（＝被乗数レジスタ）長の対数であることから乗算を行うのに必要な時間は以下となる

$log{2}(4)$ × 4（単位時間） = 8単位時間

3.17

与えられた二つの符合なし16進整数を10進数に変換すると以下となる

0x33 = 51 = 32 + 16 + 2 + 1 = 2⁵ + 2⁴ + 2¹ + 1

0x55 = 85 = 64 + 16 + 4 + 1 = 2⁶ + 2⁴ + 2² + 1

シフト回数を鑑みると以下の展開が最適となる

51 × 85 = (2 × 2 × 2 × 2 × 2 + 2 × 2 × 2 × 2 + 2 + 1) × 85

85を左に5回シフトした結果と85を左に4回シフトした結果と85を左に1回シフトした結果と1をすべて加算することにより計算する

3.18

問題文にある入力データとは被除数と除数を指すものと思われる

であれば、与えられた被除数と除数はそれぞれ10進数の74と21であり、74については6ビットの符号なし整数で表現することはできない

よって設問として不備があると判断する

以下、入力データはキリの良さをを考慮して8ビットの符号なし整数として与えられたものとする

その際、被除数・除数はシフトする都合上、レジスタは16ビット長を想定する

74 = 0100 1010

21 = 0001 0101

処理サイクル	ステップ	商	除数	剰余
0	初期値	0000 0000	0001 0101 0000 0000	0000 0000 0100 1010
1	1：剰余 = 剰余 - 除数	0000 0000	0001 0101 0000 0000	1110 1011 0100 1010
1	2b：剰余 < 0 → 剰余を戻し、商を左シフト、商 0 = 0	0000 0000	0001 0101 0000 0000	0000 0000 0100 1010
1	3：除数を右へシフト	0000 0000	0000 1010 1000 0000	0000 0000 0100 1010
2	1：剰余 = 剰余 - 除数	0000 0000	0000 1010 1000 0000	1111 0101 1100 1010
2	2b：剰余 < 0 → 剰余を戻し、商を左シフト、商 0 = 0	0000 0000	0000 1010 1000 0000	0000 0000 0100 1010
2	3：除数を右へシフト	0000 0000	0000 0101 0100 0000	0000 0000 0100 1010
3	1：剰余 = 剰余 - 除数	0000 0000	0000 0101 0100 0000	1111 1011 0000 1010
3	2b：剰余 < 0 → 剰余を戻し、商を左シフト、商 0 = 0	0000 0000	0000 0101 0100 0000	0000 0000 0100 1010
3	3：除数を右へシフト	0000 0000	0000 0010 1010 0000	0000 0000 0100 1010
4	1：剰余 = 剰余 - 除数	0000 0000	0000 0010 1010 0000	1111 1101 1010 1010
4	2b：剰余 < 0 → 剰余を戻し、商を左シフト、商 0 = 0	0000 0000	0000 0010 1010 0000	0000 0000 0100 1010
4	3：除数を右へシフト	0000 0000	0000 0001 0101 0000	0000 0000 0100 1010
5	1：剰余 = 剰余 - 除数	0000 0000	0000 0001 0101 0000	1111 1110 1100 1010
5	2b：剰余 < 0 → 剰余を戻し、商を左シフト、商 0 = 0	0000 0000	0000 0001 0101 0000	0000 0000 0100 1010
5	3：除数を右へシフト	0000 0000	0000 0000 1010 1000	0000 0000 0100 1010
6	1：剰余 = 剰余 - 除数	0000 0000	0000 0000 1010 1000	1111 1111 1010 0011
6	2b：剰余 < 0 → 剰余を戻し、商を左シフト、商 0 = 0	0000 0000	00000 0000 1010 1000	0000 0000 0100 1010
6	3：除数を右へシフト	0000 0000	0000 0000 0101 0100	0000 0000 0100 1010
7	1：剰余 = 剰余 - 除数	0000 0000	0000 0000 0101 0100	1111 1111 1111 0110
7	2b：剰余 < 0 → 剰余を戻し、商を左シフト、商 0 = 0	0000 0000	0000 0000 0101 0100	0000 0000 0100 1010
7	3：除数を右へシフト	0000 0000	0000 0000 0010 1010	0000 0000 0100 1010
8	1：剰余 = 剰余 - 除数	0000 0000	0000 0000 0010 1010	0000 0000 0010 0000
8	2a：剰余 >= 0 → 商を左シフト、商 0 = 1	0000 0001	0000 0000 0010 1010	0000 0000 0010 0000
8	3：除数を右へシフト	0000 0001	0000 0000 0001 0101	0000 0000 0010 0000
9	1：剰余 = 剰余 - 除数	0000 0001	0000 0000 0001 0101	0000 0000 0000 1011
9	2a：剰余 >= 0 → 商を左シフト、商 0 = 1	0000 0011	0000 0000 0001 0101	0000 0000 0000 1011
9	3：除数を右へシフト	0000 0011	0000 0000 0000 1010	0000 0000 0000 1011

以上より、結果は以下となる

商 = 0000 0011 = 3

剰余 = 0000 0000 0000 1011 = 11

3.19〜3.22

省略

3.23

与えられた10進小数を2進小数にすると以下となる

63.25 = 111111.01

正規化すると以下となる

1.1111101 × 2^-5

単精度の場合の浮動小数点の一般形式に当てはめると以下となる

(-1)⁰ × (1 + .1111 1010 0000 0000 0000 000) × 2^{122 - 127}

よって63.25を単精度の浮動小数点形式で表現すると以下となる

0 01111010 1111 1010 0000 0000 0000 000

3.24

前問 3.23の解答を途中から引継ぐき63.25を倍精度の浮動小数点の一般形式に当てはめると以下となる

(-1)⁰ × (1 + .1111 1010 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000) × 2^{1018 - 1023}

よって63.25を倍精度の浮動小数点形式で表現すると以下となる

0 01111111010 1111 1010 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000

3.25〜3.41

省略

3.42

以下、単精度の浮動小数点形式にて回答する

1/4 = 1 01111101 0000 0000 0000 0000 0000 000

よって正確に表すことができる

3.43

以下、単精度の浮動小数点形式にて回答する

- 1/4を4回加算した答えは仮数の指数調整となり、以下となる

1 00000000 0000 0000 0000 0000 = -1

(- 1/4) × 4の答えについて単精度の浮動小数点数同士の積であるとして、4を単精度の浮動小数点形式で表現すると以下となる

4 = 0 10000011 0000 0000 0000 0000 0000 000

答えは指数の加算（ゲタ履き）を考慮し、以下となる

（- 1/4の指数部）：01111101 + （4の指数部）：10000011 + = 00000000

1 00000000 0000 0000 0000 0000 = -1

3.44～3.47

省略

第3章の課題

2～16の基数の計算を繰り返すことで、桁の重みや補数について感覚的にわかるようになったが、浮動小数点の精度については実装においてどこまで数値として、また表示として信頼できるのか、どんなときに使うべきなのか改めて整理しておきたい
設問が不明瞭だったので勝手に仮定したが、正しいかったのか確証が持てないのでもう少し知識もとい常識を得てから振り返りたい

2016-08-11

教養のためのC言語学習と参考書

C言語

f:id:taKyshu98:20160811223226j:plain

パタヘネでは所々MIPSとC言語とを読み比べながら学ぶ箇所がある。

アルゴリズムは別としてコード自体は文法的に簡潔であるため読めなくはないのだけれども、これまでC言語についてまとまった時間を割いて勉強したことがなかったので、今後の学習効率向上やスキルに幅を持たせるために少し立ち止まって勉強してみた。

学習に当たっては以下の本を読んだ。内容の整理というより書評になってしまった。

やさしいC

やさしいC 第4版 (「やさしい」シリーズ)

作者: 高橋麻奈
出版社/メーカー: SBクリエイティブ
発売日: 2007/08/30
メディア: 単行本
この商品を含むブログ (6件) を見る

プログラミングを独学し始めた時期に手を出した本のうちの一冊でこの機会に再読。

練習問題を通して文法をバランス良く学ぶことができる。

後述のC言語教科書は文法をそこまで細かく解説しないので、概要を掴むのに役立つ。

C言語教科書入門編

C言語教科書(入門編)

作者: 川俣晶
出版社/メーカー: 日経BP社
発売日: 2009/03/25
メディア: 単行本
クリック: 4回
この商品を含むブログ (5件) を見る

コマンドラインの使い方や処理系の違いといった環境面の解説が手厚く、またバイナリ・テキスト、文字コードといったデータの取り扱いやバブルソートを例にしたアルゴリズムへの示唆が自然に含まれておりC言語だけでなくプログラミング初学者におすすめできると思った。

ただ、環境としてはWindows前提なのでmacを使っている人は適宜、読み替える必要がある。

C言語を試用するという面ではかなりの充実度だが、構文をきっちりかっきり抑えたい人には物足りないかもしれないので別途、上述の『やさしいC』などの文法寄りの参考書と読み合わせると理解が深まると思う。

C言語教科書上達編誰でもわかる！C言語ベテラン技

C言語教科書(上達編) 誰でもわかる! C言語ベテラン技

作者: 川俣晶
出版社/メーカー: 日経BP社
発売日: 2010/01/21
メディア: 単行本
購入: 1人クリック: 3回
この商品を含むブログ (4件) を見る

『C言語教科書入門編』の続編でビット操作や様々なキャストを通して各データ型のバイト数とメモリ配置への意識が向上する一冊。また、「第7章言語仕様」のコンパイルエラーは発生しないけれども、結果が保障されない「副作用」の未定義的な観点は心に留めておく必要がある。

C言語ポインタ完全制覇

C言語ポインタ完全制覇 (標準プログラマーズライブラリ)

作者: 前橋和弥
出版社/メーカー: 技術評論社
発売日: 2001/01
メディア: 単行本
購入: 22人クリック: 147回
この商品を含むブログ (75件) を見る

a[i]とi[a]が同じ値を示すといった、かなり極端な書き換え例を通して配列とポインタの文法上の考え方、読み替え方がとにかくよくわかる。さらに「第2章実験してみようーCはメモリをどう使うのか」ではパタヘネの実行ファイルのメモリ配置周りの解説に記憶域期間の具体的な視点を付与してくれる。 const修飾子や、関数ポインタ・ポインタの配列といった複雑なポインタ宣言の読解の仕方や利用に当たってのメリットも解説している。かなり有名な定番中の定番。

メモ

『C言語教科書入門編』で以下のようなサンプルコード（一部抜粋）がある。

このコードをコンパイルした実行ファイルに空ファイルをリダイレクトで標準入力として渡したときにのみ分岐の内に入ることを意図しているようだが、実際に実行する（MinGWでコンパイル）と内容のあるファイルでも分岐の内に入ってしまう。feof関数はFILE構造体（sdtinをはじめとした標準ストリームはFILE構造体のポインタ）のファイル終了表示子を参照するため、この動作は正しいように思われる。詳しくはファイル終了表示子やgets（今となっては実用皆無であるが）、feof関数がどのように実装されているか、処理系の定義であるstdio.hを見れば良いのだろうが、制御文字を含めた入出力系はどの範囲をどういう勉強をすればいいか整理してから取り掛かりたいので一旦は課題に留めておく。

2016-07-25

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

パタヘネ

第2章のまとめ

CPU系統（x86・ARM）ごとに命令セットが異なる
演算処理における一まとまりのビット長を単位としたものを語（word）と呼ぶ
メモリのアドレスはバイト単位で割り振られるが、プログラム側では語（word）を意識した操作が必要
コンパイラ→アセンブラ→リンカを経て作成された実行ファイルはアドレス参照先が絶対完全に解決されている
実行ファイルの絶対アドレスを重複がないようにマネージするのがMMU（メモリ管理機構）の役目
実行ファイルはメモリ上にスタック・ヒープ・静的データ（定数・静的変数）・テキスト（機械語）の大きく4つの部位に分けて配置される
スタックには引数レジスタ・戻りアドレス・退避レジスタの値およびローカルな配列と構造体が格納される
ヒープには入力によって動的に変わるデータ構造が格納される

2.22 演習問題

以下に示すMIPS アセンブリ・Cソースコードは概念的なものであり、実行を想定していない

2.1〜2.2

省略

2.3

与えられた変数 f, g, h, i, j のうち、使用するのは i, j のみである

よってレジスタ$s0, $s1, $s2, $s3, $s4のうち、使用するのは$s3, $s4のみとなる

また、手続き呼び出しではないため、スタックへの退避は不要である

2.4

6行目でレジスタ$t2には$t0に読み込まれたアドレスの1語先のアドレスが読み込まれる

2.5

2.4のMIPS アセンブリ命令は6行目のオフセットの演算が冗長である

2.6

アドレス	データ
24	2
38	4
32	3
36	6
40	1

※整列化制約からアドレス38は28の誤植であると思われる

2.6.1

一般的なソート・アルゴリズムではなく、条件特化であると仮定する。また代入は最小限を想定する

2.6.2

配列はメモリに保持される。MIPS アセンブラではメモリ間転送はできないことに注意する

2.7

与えたれた値のバイト単位の格納順序に留意すればよい

リトル・エンディアン方式

アドレス	データ
12	a b
8	c d
4	e f
0	1 2

ビッグ・エンディアン方式

アドレス	データ
12	1 2
8	e f
4	c d
0	a b

2.8〜2.11

省略

2.12

$s0 = 0x80000000

$s1 = 0xD0000000

与えられた値をそれぞれ2進数に変換すると以下の通りになる

$s0 = 1000 0000 0000 0000 0000 0000 0000 0000

$s1 = 1010 0000 0000 0000 0000 0000 0000 0000

2.12.1

加算であるため、$s0と$s1が符合付き整数または符合なし整数であるかどうかは回答の観点からは考慮する必要がない

$t0 = $s0 + $s1 より2値を加算すると、33ビット目への繰上げが発生し、オーバーフローとなる

$t0 = 1 0101 0000 0000 0000 0000 0000 0000

オーバーフローした値を切り捨て、16進数に変換すると$t0の値は以下に求められる

$t0 = 0x50000000

2.12.2

2.12.1よりオーバーフローが発生した

2.12.3

$t0 = $s0 - $s1

減算であるため、$s0と$s1が符合付き整数または符合なし整数であるかどうかを考慮する必要がある

$s0と$s1が符合付き整数である場合

有効な負数同士の減算のため、解は必ず有効となる

2進数で計算すると以下の通りとなる。2の補数表現は有効最大桁の1ビット桁上がりを概念的に利用するが、それはオーバーフローではない

$t0 = 1110 0000 0000 0000 0000 0000 0000 0000

16進数に変換すると $t0の値は以下に求められる

$t0 = 0xE0000000

$s0と$s1が符合なし整数である場合

$t0が負数になることは自明であるため、オーバーフロー（桁借り）となる

2.12.4

2.12.3より$s0と$s1が符合付き整数でない場合、オーバーフローが発生した

2.12.5〜2.12.6

省略

2.13

$s0 = 128

レジスタ長が明言されていないため、MIPSの32ビットレジスタであると仮定する

10進数で考えるとMIPSのレジスタの取り得る値は符合なし整数の場合、0〜4,294,967,295であり、符合付き整数の場合、-2,147,483,648〜2,147,483,647となる

2.13.1

$t0 = $s0 + $s1

符合なし整数の場合

4,294,967,295 - 128 = 4,294,967,167

$s1 > 4,294,967,167 のとき、$t0はオーバーフローを起こす($s1 < 4,294,967,295)

符合付き整数の場合

2,147,483,647 - 128 = 2,147,483,519

$s1 > 2,147,483,519 のとき、$t0はオーバーフローを起こす($s1 < 2,147,483,647)

2.13.2

$t0 = $s0 - $s1

符合なし整数の場合

$s1 > 128 のとき、$t0はオーバーフロー（桁借り）を起こす。($s1 < 4,294,967,295)

符合付き整数の場合

2,147,483,647 - 128 = 2,147,483,519

-$s1 > 2,147,483,519 のとき、すなわち$s1 < -2,147,483,519 のとき、$t0はオーバーフローを起こす($s1 > -2,147,483,648)

2.13.3

$t0 = $s1 - $s0

符合なし整数の場合

$s1 < 128 のとき、$t0はオーバーフロー（桁借り）を起こす。(0 < $s1)

符合付き整数の場合

-2,147,483,648 - (-128) = -2,147,483,520

-$s1 > 2,147,483,520 のとき、すなわち$s1 < -2,147,483,520 のとき、$t0はオーバーフローを起こす($s1 > -2,147,483,648)

2.14〜2.17

省略

2.18

レジスタ・ファイルの数を128に拡大し、命令セット中の、命令の数を4倍に拡大(問題文より)

2.18.1

MIPSのR形式命令は以下の6フィールド合計32ビットで構成される

op：命令操作コード　6ビット
rs：第1のソース・オペランドのレジスタ　5ビット
rt：第2のソース・オペランドのレジスタ　5ビット
rd：デスティネーション・オペランドのレジスタ　5ビット
shamt：シフト量　5ビット
funct：機能コード　6ビット

レジスタ・ファイルの数の拡大はレジスタの指定に用いられる、rs・rt・rd のフィールド長に影響する

具体的には128通りのレジスタ指定に対応するため各7ビットへ拡張する必要がある

命令の数の拡大は命令操作コード op のフィールド長に影響する

具体的にはこれまでの63命令（付録カードより）の4倍の命令数に対応するために8ビットへ拡張する必要がある

レジスタ長は変わらないため、残りの3ビットをshamt・funct で按分することになる

2.18.2

MIPSのI形式命令は以下の4フィールド合計32ビットで構成される

op：命令操作コード　6ビット
rs：第1のソース・オペランドのレジスタ　5ビット
rt：第2のソース・オペランドのレジスタ　5ビット
constant or address：定数 or アドレス・オペランドのレジスタ　16ビット

前問よりrs・rt の各フィールド長は7ビットへ拡張する必要がある

また、op のフィールド長は8ビットへ拡張する必要がある

よって、constant or adress のフィールド長は残りの10ビットとなる

2.18.3

プログラムのサイズを小さくする方向

R形式の変更 … 命令の多様化により1命令で2つ以上の既存命令を置換する

I形式の変更 … レジスタ・ファイルの増加および命令の多様化によりメモリアクセス回数を削減する

プログラムのサイズを大きくする方向

R形式の変更 … シフト指定可能数の減少により計算が冗長化する、機能コードの減少により多様化で補えない命令は冗長化する

I形式の変更 … 定数・アドレスフィールドの減少により定数・アドレス指定の範囲が狭まるため2¹⁰以上の値を使用したい場合は命令が冗長化する

2.19

省略

2.20

特定範囲のビットを一方の値で上書きするようなMIPS（論理演算）命令は存在しないため、シフトを駆使してビットが干渉しないようにする

2.21

MIPSにnot命令は存在しないため、nor命令で代替する

2.22

2.23

省略

2.24

PCの値を2進数に変換すると以下となる

0010 0000 0000 0000 0000 0000 0000 0000

移動先のアドレス値を2進数に変換すると以下となる

0100 0000 0000 0000 0000 0000 0000 0000

MIPSのjump命令は擬似直接アドレシングなのでPCの上位4ビットにオペランドの26ビットを2ビット左論理シフトした28ビットを連結した32ビット値が移動先のアドレス値となる

しかしながら、すべてのビットが立ったオペランドを連結したとしても上位4ビットの差は埋められないため、jump命令での移動は不可能である

beq命令についてもオペランドの16ビットを2ビット左論理シフトした18ビットのオフセットでPCから移動先のアドレスを計算することは不可能である

2.25

変数の対応関係が明確でないため、好意的に解釈すれば以下の対応になると思われるが、問題で与えられた条件とloopという名称に整合性がなく、意図が理解できない

$t2 = R[rs]のアドレス値

loop = 分岐先のアドレス値

2.25.1

問題文によるとオペコード、1つのレジスタ、アドレスが指定できれば良いようなので、I形式が妥当であると考えられる

2.25.2

省略

2.26

省略

2.27

2.28

前問回答よりそれぞれのループ処理についてMIPSの命令数を整理すると以下の通りとなる

初期化に必要な命令数：1命令

Loop1の命令数：3命令 / 2命令（条件終了時）

Loop2の命令数：8命令 / 2命令（条件終了時）

Loop3の命令数：2命令

b = 0より1回の外側ループ処理で実行される命令数 = 3 + (8 + 2) + 2 = 15

a = 10より全体で実行されるMIPの命令数 = 1 + 15 × 10 + 2 = 153

2.29〜2.30

省略

2.31

回答に当たり以下のレジスタを使用することとする

スタック・ポインタ：$sp

引数レジスタ：$a0

一時レジスタ：$t0

退避レジスタ：$s0

結果レジスタ：$v0

戻りアドレスレジスタ：$ra

定数値ゼロ：$zero

2.32

再帰関数は必ず入れ子となる同じ再帰関数を処理に含むため、引数が終了条件を満たす終端の呼び出しにおいて条件分岐上その再帰関数を呼び出さないとしても、最初の引数が5であることを前提に再帰関数の処理を書き換えるため、置き換えが不可能となる。そのため、終端の不要な再帰関数はインライン化の対象から除外し、命令自体からも削除する必要がある

また、一部の戻りアドレスレジスタと退避レジスタへのロード・ストア命令は不要となるため削除する必要がある

n = 5としたときの削減前の命令数は概算で223命令であり、削減後の命令数は68命令となった。インライン化実装に伴い命令数は約70%削減された

2.33

省略

2.34

func関数は別定義されているとする。$t0〜$t7の一時レジスタは不要である

2.35

末尾呼び出しの最適化は基本的に完了条件を持つ再帰関数をイテレーションによって置き換えることである。(p104より)

前問のプログラムは再帰関数ではないため、末尾呼び出しによる最適化は不適であると判断する

2.36

$t5 … 不使用の一時レジスタのため任意の値が保存されている

$s3 … 不使用の退避レジスタのためf関数呼び出し時に保時していた値が保存されている

$sp … プログラムは配列や構造体を持たないため呼び出し時に使用していた分だけの退避レジスタがスタックの末尾に保存されている

$ra … プログラムの呼び出しアドレス+4が保存されている

2.37

省略

2.38

アドレス0x1000 0010は$t2が保持する値であり、題意から察するに与えられたデータ(16進数)0x11223344は正しくは$t1の保持するアドレス0x1000 000に収められていると仮定する

アドレス	データ
0x1000 0003	4 4
0x1000 0002	3 3
0x1000 0001	2 2
0x1000 0000	1 1

ビッグ・エンディアン・アドレシング方式は上位ビットをアドレス下位から格納するため、1バイト単位で保持される値は上記のようになる

よって$t0には0x0000 0011が格納され、sw命令によってこの値がそのまま$t2に格納されることになる

2.39

1命令に保持できるMIPSの定数はR形式の16ビットが限界なので32ビットの定数は演算によって算出する

2.40〜2.45

省略

2.46

	算術命令	ロード／ストア命令	分岐命令
CPI	1	10	3
命令数	0.5 × 10⁹	0.3 × 10⁹	0.1 × 10⁹

CPU実行時間 = ${\displaystyle\frac{プログラムの実行命令数 × CPI}{クロック周波数}}$ = プログラムの実行命令数 × CPI × クロック・サイクル時間

2.46.1

強化前のプログラム実行命令数 = (0.5 + 0.3 + 0.1) × 10⁹ = 0.9 × 10⁹

強化前のCPI = ${\displaystyle\frac{1 × 0.5 × 10^9 + 10 × 0.3 × 10^9 + 3 × 0.1 × 10^9}{0.9 × 10^9}}$ = ${\displaystyle\frac{3.8 × 10^9}{0.9 × 10^9}}$

強化前のCPU実行時間 = 強化前のプログラムの実行命令数 × 強化前のCPI × クロック・サイクル時間 = 0.9 × 10⁹ × ${\displaystyle\frac{3.8 × 10^9}{0.9 × 10^9}}$ × クロック・サイクル時間 = 3.8 × 10⁹ × クロック・サイクル時間

強化後のプログラム実行命令数 = (0.5 × (1 - 0.25) + 0.3 + 0.1) × 10⁹ = (0.375 + 0.3 + 0.1) × 10⁹ = 0.775 × 10⁹

強化後のCPI = ${\displaystyle\frac{1 × 0.375 × 10^9 + 10 × 0.3 × 10^9 + 3 × 0.1 × 10^9}{0.9 × 10^9}}$ = ${\displaystyle\frac{3.675 × 10^9}{0.775 × 10^9}}$

強化後のCPU実行時間 = 強化後のプログラムの実行命令数 × 強化後のCPI × クロック・サイクル時間 × (1 + 0.1) = 0.775 × 10⁹ × ${\displaystyle\frac{3.675 × 10^9}{0.775 × 10^9}}$ × クロック・サイクル時間 × 1.1 = 3.675 × 10⁹ × クロック・サイクル時間 × 1.1 = 4.0425 × 10⁹ × クロック・サイクル時間

以上よりCPU実行時間が強化前後で増加するため、良い設計案とは言えない

2.46.2

性能を倍増させるとあるが、命令数とCPIをどのような割合で向上させるのか不明である

改善率の上限を掴むために算術命令をすべて削減した場合を想定すると、クロック・サイクル数は3.3 × 10⁹となり、クロック周波数が変わらないと仮定したうえでCPU実行時間の改善率は最大13%程度を見込めることがわかる

2.47

省略

第2章の課題

どの言語で書かれたソースコードでもあろうとも最終的にはCPUの命令セットに依存した実行ファイルに落とし込まれることや実行ファイルのメモリ割当て構成を学んだことで低レベルでの共通性のイメージが深まり、プログラミングへの見識が広まったが、図や説明を見るだけでなく実際に確認してみたいので機会をみて低レベルを意識した観点からCやJavaといった適当な言語で感覚を養いたい（特にスタック・ヒープ周りについて）
実行ファイル単体の構成は理解することができたが、それがどのように実行されるのかソフト・ハード面での仕組みのイメージがまだまだ掴めないので学習していきたい

2016-07-03

パタヘネ学習#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}}$

$X$ < 0

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

1.14.2 〜 1.14.3

省略

1.15

省略

第1章の課題

CPUおよびプログラムの性能測定について概念は理解できたが、肌感というか腹落ち感がまだあまりないので実際に計測実験をして理解を深めたい
単位のスケール感がまだ直感的に掴めていないので学習や経験を積みながらイメージを深めたい

2016-06-26

パタヘネを読み解く

パタヘネ

パターソン&ヘネシーコンピュータの構成と設計第5版

f:id:taKyshu98:20160626203518j:plain:w480

低レイヤーの知識について勉強したことがなかったので、巷で有名なパタヘネ本に手を出してみる。通読して演習問題を解いていくが、類似問題や現時点で解く必要のない問題は省略して時間を節約する。模範解答が付属していないので設問の意図が不明なものはこちら側で仮定する。

第1章コンピュータの抽象化とテクノロジ

takyshu98.hatenadiary.jp

第2章命令：コンピュータの言葉

takyshu98.hatenadiary.jp

第3章コンピュータにおける算術演算

takyshu98.hatenadiary.jp

第4章プロセッサ

保留

第5章容量と速度の両立：記憶階層の利用

保留

第6章クライアントからクラウドまでの並列プロセッサ

保留

A アセンブラ、リンカ、SPIMシミュレータ

保留

B 論理設計の基礎

保留

2016-06-25

ブログを開設しました

主にプログラミングを中心とした学習・生活全般のノートとして更新していきます。

書くとき、書いたあとのモチベーション維持のためにも修正・加筆を積極的に行っていくつもりです。

※記載する情報の正確性については細心の注意を払いますが、
その内容によって万が一、不利益が生じた場合については保障し兼ねますのであしからず。

第3章のまとめ

3.12 演習問題

3.1〜2.2

3.3

3.4〜3.5

3.6

3.7

3.8

3.9

3.10

3.11

3.12

3.13

3.14

3.15

3.16

3.17

3.18

3.19〜3.22

3.23

3.24

3.25〜3.41

3.42

3.43

3.44～3.47

第3章の課題

やさしいC

C言語教科書 入門編

C言語教科書 上達編 誰でもわかる！C言語ベテラン技

C言語ポインタ完全制覇

メモ

第2章のまとめ

2.22 演習問題

2.1〜2.2

2.3

2.4

2.5

2.6

2.6.1

2.6.2

2.7

2.8〜2.11

2.12

2.12.1

2.12.2

2.12.3

2.12.4

2.12.5〜2.12.6

2.13

2.13.1

2.13.2

2.13.3

2.14〜2.17

2.18

2.18.1

2.18.2

2.18.3

2.19

2.20

2.21

2.22

2.23

2.24

2.25

2.25.1

2.25.2

2.26

2.27

2.28

2.29〜2.30

2.31

2.32

2.33

2.34

2.35

2.36

2.37

2.38

2.39

2.40〜2.45

C言語教科書入門編

C言語教科書上達編誰でもわかる！C言語ベテラン技

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

パターソン&ヘネシーコンピュータの構成と設計第5版

第1章コンピュータの抽象化とテクノロジ

第2章命令：コンピュータの言葉

第3章コンピュータにおける算術演算

第4章プロセッサ