パタヘネ学習#4 第4〜6章の読了
第4〜6章および付録A〜E章を読了した。
第3章まではプログラミング言語の低層理解のために多少時間がかかっても演習問題を解いてきたが、 第4章以降は理解の及んでいないハードウェア寄りの内容が色濃くなり、順番に内容を修めて問題を解くというスタイルでは効率的にもモチベーション的にも時間がもったいないなと感じた。
なので、最初は要点を押さえつつ流し読みをして、後で定期的に読み返しつつ、問題をつまみ食いして記憶に定着させていこうというスタイルに方針転換した。
如何せん働いている身なので、順番に一変に全部に時間をかけ過ぎるとすぐ連続性を失ってしまうというのは言い訳になるだろうか。
内容としては第4章、第5章のプロセッサの内部構成と命令実行の仕組みおよびキャッシュの仕組みとDGEMMへの応用が興味深かった。
また、ネット付録2−15節のJavaのMIPSコードも興味深く、JVMについてもそのうち学んでみたいと思った。
気が向いたら更新していくとして、ひとまず、パタヘネはここで一区切り。
パタヘネ学習#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進数で27 - 1 = 127 であるから185を変換する時点でオーバーフローが発生する
3.8
やはり185を変換する時点でオーバフローが発生する
符号付きの8ビットという指定の範囲では問題として意図が不明なように思われる
3.9
8ビットの符合付き2進数の最大値は10進数で27 - 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つとなる
また、整数の長さが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を底とした乗数レジスタ(=被乗数レジスタ)長の対数であることから乗算を行うのに必要な時間は以下となる
× 4(単位時間) = 8単位時間
3.17
与えられた二つの符合なし16進整数を10進数に変換すると以下となる
0x33 = 51 = 32 + 16 + 2 + 1 = 25 + 24 + 21 + 1
0x55 = 85 = 64 + 16 + 4 + 1 = 26 + 24 + 22 + 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)0 × (1 + .1111 1010 0000 0000 0000 000) × 2122 - 127
よって63.25を単精度の浮動小数点形式で表現すると以下となる
0 01111010 1111 1010 0000 0000 0000 000
3.24
前問 3.23の解答を途中から引継ぐき63.25を倍精度の浮動小数点の一般形式に当てはめると以下となる
(-1)0 × (1 + .1111 1010 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000) × 21018 - 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の基数の計算を繰り返すことで、桁の重みや補数について感覚的にわかるようになったが、浮動小数点の精度については実装においてどこまで数値として、また表示として信頼できるのか、どんなときに使うべきなのか改めて整理しておきたい
設問が不明瞭だったので勝手に仮定したが、正しいかったのか確証が持てないのでもう少し知識もとい常識を得てから振り返りたい
教養のためのC言語学習と参考書
パタヘネでは所々MIPSとC言語とを読み比べながら学ぶ箇所がある。
アルゴリズムは別としてコード自体は文法的に簡潔であるため読めなくはないのだけれども、これまでC言語についてまとまった時間を割いて勉強したことがなかったので、今後の学習効率向上やスキルに幅を持たせるために少し立ち止まって勉強してみた。
学習に当たっては以下の本を読んだ。内容の整理というより書評になってしまった。
やさしいC
- 作者: 高橋麻奈
- 出版社/メーカー: SBクリエイティブ
- 発売日: 2007/08/30
- メディア: 単行本
- この商品を含むブログ (6件) を見る
プログラミングを独学し始めた時期に手を出した本のうちの一冊でこの機会に再読。
練習問題を通して文法をバランス良く学ぶことができる。
後述のC言語教科書は文法をそこまで細かく解説しないので、概要を掴むのに役立つ。
C言語教科書 入門編
- 作者: 川俣晶
- 出版社/メーカー: 日経BP社
- 発売日: 2009/03/25
- メディア: 単行本
- クリック: 4回
- この商品を含むブログ (5件) を見る
コマンドラインの使い方や処理系の違いといった環境面の解説が手厚く、またバイナリ・テキスト、文字コードといったデータの取り扱いやバブルソートを例にしたアルゴリズムへの示唆が自然に含まれておりC言語だけでなくプログラミング初学者におすすめできると思った。
ただ、環境としてはWindows前提なのでmacを使っている人は適宜、読み替える必要がある。
C言語を試用するという面ではかなりの充実度だが、構文をきっちりかっきり抑えたい人には物足りないかもしれないので別途、上述の『やさしいC』などの文法寄りの参考書と読み合わせると理解が深まると思う。
C言語教科書 上達編 誰でもわかる!C言語ベテラン技
- 作者: 川俣晶
- 出版社/メーカー: 日経BP社
- 発売日: 2010/01/21
- メディア: 単行本
- 購入: 1人 クリック: 3回
- この商品を含むブログ (4件) を見る
『C言語教科書 入門編』の続編でビット操作や様々なキャストを通して各データ型のバイト数とメモリ配置への意識が向上する一冊。 また、「第7章 言語仕様」のコンパイルエラーは発生しないけれども、結果が保障されない「副作用」の未定義的な観点は心に留めておく必要がある。
C言語ポインタ完全制覇
- 作者: 前橋和弥
- 出版社/メーカー: 技術評論社
- 発売日: 2001/01
- メディア: 単行本
- 購入: 22人 クリック: 147回
- この商品を含むブログ (75件) を見る
a[i]とi[a]が同じ値を示すといった、かなり極端な書き換え例を通して配列とポインタの文法上の考え方、読み替え方がとにかくよくわかる。 さらに「第2章 実験してみようーCはメモリをどう使うのか」ではパタヘネの実行ファイルのメモリ配置周りの解説に記憶域期間の具体的な視点を付与してくれる。 const修飾子や、関数ポインタ・ポインタの配列といった複雑なポインタ宣言の読解の仕方や利用に当たってのメリットも解説している。かなり有名な定番中の定番。
メモ
『C言語教科書 入門編』で以下のようなサンプルコード(一部抜粋)がある。
このコードをコンパイルした実行ファイルに空ファイルをリダイレクトで標準入力として渡したときにのみ分岐の内に入ることを意図しているようだが、実際に実行する(MinGWでコンパイル)と内容のあるファイルでも分岐の内に入ってしまう。feof関数はFILE構造体(sdtinをはじめとした標準ストリームはFILE構造体のポインタ)のファイル終了表示子を参照するため、この動作は正しいように思われる。詳しくはファイル終了表示子やgets(今となっては実用皆無であるが)、feof関数がどのように実装されているか、処理系の定義であるstdio.hを見れば良いのだろうが、制御文字を含めた入出力系はどの範囲をどういう勉強をすればいいか整理してから取り掛かりたいので一旦は課題に留めておく。
パタヘネ学習#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ビット
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・rt の各フィールド長は7ビットへ拡張する必要がある
また、op のフィールド長は8ビットへ拡張する必要がある
よって、constant or adress のフィールド長は残りの10ビットとなる
2.18.3
プログラムのサイズを小さくする方向
R形式の変更 … 命令の多様化により1命令で2つ以上の既存命令を置換する
I形式の変更 … レジスタ・ファイルの増加および命令の多様化によりメモリアクセス回数を削減する
プログラムのサイズを大きくする方向
R形式の変更 … シフト指定可能数の減少により計算が冗長化する、機能コードの減少により多様化で補えない命令は冗長化する
I形式の変更 … 定数・アドレスフィールドの減少により定数・アドレス指定の範囲が狭まるため210以上の値を使用したい場合は命令が冗長化する
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 × 109 | 0.3 × 109 | 0.1 × 109 |
CPU実行時間 = = プログラムの実行命令数 × CPI × クロック・サイクル時間
2.46.1
強化前のプログラム実行命令数 = (0.5 + 0.3 + 0.1) × 109 = 0.9 × 109
強化前のCPI = =
強化前のCPU実行時間 = 強化前のプログラムの実行命令数 × 強化前のCPI × クロック・サイクル時間 = 0.9 × 109 × × クロック・サイクル時間 = 3.8 × 109 × クロック・サイクル時間
強化後のプログラム実行命令数 = (0.5 × (1 - 0.25) + 0.3 + 0.1) × 109 = (0.375 + 0.3 + 0.1) × 109 = 0.775 × 109
強化後のCPI = =
強化後のCPU実行時間 = 強化後のプログラムの実行命令数 × 強化後のCPI × クロック・サイクル時間 × (1 + 0.1) = 0.775 × 109 × × クロック・サイクル時間 × 1.1 = 3.675 × 109 × クロック・サイクル時間 × 1.1 = 4.0425 × 109 × クロック・サイクル時間
以上よりCPU実行時間が強化前後で増加するため、良い設計案とは言えない
2.46.2
性能を倍増させるとあるが、命令数とCPIをどのような割合で向上させるのか不明である
改善率の上限を掴むために算術命令をすべて削減した場合を想定すると、クロック・サイクル数は3.3 × 109となり、クロック周波数が変わらないと仮定したうえでCPU実行時間の改善率は最大13%程度を見込めることがわかる
2.47
省略
第2章の課題
パタヘネ学習#1 第1章のまとめと問題演習
第1章のまとめ
コンピュータの性能諸元のうちCPUの性能に着目する
CPUの性能の指標として任意のプログラムのCPU実行時間(区別が困難であるためOSのコストも含む)を絶対的なものとする
CPU実行時間 = プログラムの実行命令数 × ×
=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 = =
P1のMIPS … = 2.0 × 103
P2のMIPS … = 2.5 × 103
P3のMIPS … = 1.82 × 103
秒当たりの命令数で表した場合、P2の性能が最高
b.
クロックサイクル数 = CPU実行時間 × クロック周波数 実行命令数 = クロックサイクル数 ÷ CPI
P1のサイクル数 … 10 × 3.0 × 109 = 30 × 109
P1の命令数 … 30 × 109 ÷ 1.5 = 20 × 109
P2のサイクル数 … 10 × 2.5 × 109 = 25 × 109
P2の命令数 … 25 × 109 ÷ 1.0 = 25 × 109
P3のサイクル数 … 10 × 4.0 × 109 = 40 × 109
P3の命令数 … 40 × 109 ÷ 2.2 = 18.18 × 109
c.
CPIおよびクロック周波数の増大に対して実行命令数は変化しないものと仮定すると以下の等式が成り立つ
実行時間 × (1 - 0.3) =
改善後のクロック周波数 =
P1の改善後のクロック周波数 … = 5.14 × 109 = 5.14 GHz
P2の改善後のクロック周波数 … = 4.29 × 109 = 4.29 GHz
P3の改善後のクロック周波数 … = 6.86 × 109 = 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 = =
CPUの実行時間 =
P1のクロックサイクル数 … (1 × 0.1 × 106) + (2 × 0.2 × 106) + (3 × 0.5 × 106) + (3 × 0.2 × 106) = 2.6 × 106
P1のグローバルCPI … = 2.6
P1のCPU実行時間 … = 1.04 × 秒
P2のクロックサイクル数 … (2 × 0.1 × 106) + (2 × 0.2 × 106) + (2 × 0.5 × 106) + (2 × 0.2 × 106) = 2.0 × 106
P2のグローバルCPI … = 2.0
P2のCPU実行時間 … = 0.67 × 秒
P2の実装形態の方が速い
1.7
動的命令数 | 実行時間 | |
---|---|---|
コンパイラA | 1.0E9 | 1.1 秒 |
コンパイラB | 1.2E9 | 1.5 秒 |
a.
平均CPI =
コンパイラAでコンパイルしたプログラムの平均CPI … = 1.1
コンパイラBでコンパイルしたプログラムの平均CPI … = 1.25
b.
CPU実行時間 = 動的命令数 × 平均CPI × クロックサイクル時間
実行するプロセッサの種類がa.のものとはそれぞれ異なると思われるが、平均CPIは変化しないものと仮定すると以下の等式が成り立つ
1.0 × 109 × 1.1 × Aのクロックサイクル時間(ACT) = 1.2 × 109 × 1.25 × Bのクロックサイクル時間(BCT)
= = 1.36
コンパイラAによって生成されたコードを実行したプロセッサのクロックはコンパイラBによって生成されたコードを実行したプロセッサのクロックよりも1.36倍遅い
c.
動的命令数 | 平均CPI | |
---|---|---|
新しいコンパイラ | 0.6E9 | 1.1 |
元のプロセッサのクロックサイクル時間 … 1ns = 秒
新しいコンパイラで生成されたコードのCPU実行時間 = 0.6 × 109 × 1.1 × = 0.66 秒
コンパイラAとの比較 … = 1.67
新しいコンパイラで生成されたコードの方がコンパイラAで生成されたコードより1.67倍速い
コンパイラBとの比較 … = 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の実行時間 =
クロックサイクル数 = (各命令クラスの実行命令数 × 各命令クラスのCPI) の総和
コアの数が1の場合のクロックサイクル数 = 2.56 × 109 × 1 + 1.28 × 109 × 12 + 0.256 × 109 × 5 = 2.56 × 109 + 15.36 × 109 + 1.28 × 109 = 19.2 × 109
コアの数が1の場合のCPUの実行時間 = = 9.6 秒
コア数がの場合のクロックサイクル数 = 2.56 × 109 × 1 ÷ 0.7+ 1.28 × 109 × 12 ÷ 0.7 + 0.256 × 109 × 5 = (2.56 × 109 + 15.36 × 109) ÷ 0.7 + 1.28 × 109 = + 1.28 × 109
コア数がの場合のCPU実行時間 = = + 0.64 秒
コアの数が2の場合のCPUの実行時間 = + 0.64 = 7.04 秒
コアの数が2の場合の相対速度向上率 = (9.6 ÷ 7.04 - 1) × 100 = (1.36 - 1) = 36 %
コアの数が4の場合のCPUの実行時間 = + 0.64 = 3.84 秒
コアの数が4の場合の相対速度向上率 = (9.6 ÷ 3.84 - 1) × 100 = (2.5 - 1) = 150 %
コアの数が8の場合のCPUの実行時間 = + 0.64 = 2.24 秒
コアの数が8の場合の相対速度向上率 = (9.6 ÷ 2.24 - 1) × 100 = (4.29 - 1) = 329 %
1.9.2
以下、算術命令のCPIが倍になった場合の計算
コアの数が1の場合のクロックサイクル数 = 2.56 × 109 × 2 + 1.28 × 109 × 12 + 0.256 × 109 × 5 = 5.12 × 109 + 15.36 × 109 + 1.28 × 109 = 21.76 × 109
コアの数が1の場合のCPUの実行時間 = = 10.88 秒
コア数がの場合のクロックサイクル数 = 2.56 × 109 × 2 ÷ 0.7+ 1.28 × 109 × 12 ÷ 0.7 + 0.256 × 109 × 5 = (5.12 × 109 + 15.36 × 109) ÷ 0.7 + 1.28 × 109 = + 1.28 × 109
コア数がのCPU実行時間 = = + 0.64 秒
コアの数が2の場合のCPUの実行時間 = + 0.64 = 7.96 秒
コアの数が4の場合のCPUの実行時間 = + 0.64 = 4.3 秒
コアの数が8の場合のCPUの実行時間 = + 0.64 = 2.47 秒
コア数が増えるにつれて算術命令のCPI倍増によるCPU実行時間の増加は緩和される
1.9.3
コアの数が4の場合のCPUの実行時間 = + 0.64 = 3.84 秒
ロード/ストア命令のCPIをと置くと以下の等式が成り立つ
3.84 = 2.56 × 109 + 1.28 × 109 + 1.28 × 109 = (3.84 + 1.28) × 109
1.28 = 3.84 × -3.84
< 0
CPIが負数となるため実現不可能
1.10
省略
1.11
命令数 | 実行時間 | 参照時間 |
---|---|---|
2.389E12 | 750s | 9650s |
1.11.1
CPI = = = 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 × 1012 × (1 + 0.1) × 0.94 × 333 × = 823 秒
増加率 = (823 ÷ 750 - 1) × 100 = 9.73 %
1.11.4
CPU実行時間 = 命令数 × CPI × クロックサイクル時間 = 2.389 × 1012 × (1 + 0.1) × 0.94 × (1 + 0.05) × 333 × = 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) × 1012 = 2.031 × 1012
CPI = = = 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実行時間 = = 1.125 秒
P2のCPU実行時間 = = 0.25 秒
同じプログラムを実行していると仮定すると、P2の方が性能が高い
よってクロック周波数が最大のコンピュータの性能が最も高いとは言い切れない
1.12.2
問題文より以下の等式が成り立つ
=
P2の命令数 = = 0.75 × 109
1.12.3
MIPS = =
P1のMIPS = = 4.44 × 103
P2のMIPS = = 4.00 × 103
1.12.1で求めたP1とP2のCPU実行時間よりMIPS値の大きいプロセッサの方が性能が高いとは言えない
1.12.4
P1のMFLOPS = = = = 1.78 × 103
P1のMFLOPS = = = = 1.6 × 103
1.13
省略
1.14
浮動小数点命令 | 整数命令 | ロード/ストア命令 | 分岐命令 | |
---|---|---|---|---|
命令数 | 50 × 106 | 110 × 106 | 80 × 106 | 16 × 106 |
CPI | 1 | 1 | 4 | 2 |
1.14.1
CPIの改善によりプログラムの実行速度を2倍に高めるためにはクロック周波数と命令数が不変であると仮定してクロックサイクル数を半減させる必要がある
浮動小数点命令のCPIをと置くと以下の等式が成り立つ
50 × 106 × + 110 × 106 × 1 + 80 × 106 × 4 + 16 × 106 × 2 =
(50 + 462) × 106 = 256
=
< 0
CPIが負数となるため実現不可能
1.14.2 〜 1.14.3
省略
1.15
省略
第1章の課題
CPUおよびプログラムの性能測定について概念は理解できたが、肌感というか腹落ち感がまだあまりないので実際に計測実験をして理解を深めたい
単位のスケール感がまだ直感的に掴めていないので学習や経験を積みながらイメージを深めたい
パタヘネを読み解く
パターソン&ヘネシー コンピュータの構成と設計 第5版
低レイヤーの知識について勉強したことがなかったので、巷で有名なパタヘネ本に手を出してみる。 通読して演習問題を解いていくが、類似問題や現時点で解く必要のない問題は省略して時間を節約する。 模範解答が付属していないので設問の意図が不明なものはこちら側で仮定する。
第1章 コンピュータの抽象化とテクノロジ
第2章 命令:コンピュータの言葉
第3章 コンピュータにおける算術演算
第4章 プロセッサ
保留
第5章 容量と速度の両立:記憶階層の利用
保留
第6章 クライアントからクラウドまでの並列プロセッサ
保留
A アセンブラ、リンカ、SPIMシミュレータ
保留
B 論理設計の基礎
保留
ブログを開設しました
主にプログラミングを中心とした学習・生活全般のノートとして更新していきます。
書くとき、書いたあとのモチベーション維持のためにも修正・加筆を積極的に行っていくつもりです。
※記載する情報の正確性については細心の注意を払いますが、
その内容によって万が一、不利益が生じた場合については保障し兼ねますのであしからず。