パタヘネ学習#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
省略
