『コンピュータの構成と設計第5版』演習問題解答集第2章

“パタヘネ本” でおなじみの『コンピュータの構成と設計第5版』の解答集です。読者は書籍を保有していることを前提として解答・解説を記載します。
訂正案などありましたら本ブログ記事のリポジトリへPull-Requestくだされば幸いです😊

この記事2章では、ひたすらMIPSアセンブリと戯れます。

各章の解答集

『コンピュータの構成と設計第5版』演習問題解答集第1章（執筆中）
『コンピュータの構成と設計第5版』演習問題解答集第2章（この記事）
『コンピュータの構成と設計第5版』演習問題解答集第3章
『コンピュータの構成と設計第5版』演習問題解答集第4章
『コンピュータの構成と設計第5版』演習問題解答集第5章（執筆中）
『コンピュータの構成と設計第5版』演習問題解答集第6章（執筆中）

問題・解答・解説へジャンプ

2.1
2.2
2.3
2.4
2.5
2.6
- 2.6.1
- 2.6.2
2.7
2.8
2.9
2.10
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.15
2.16
2.17
2.18
- 2.18.1
- 2.18.2
- 2.18.3
2.19
- 2.19.1
- 2.19.2
- 2.19.3
2.20
2.21
2.22
2.23
2.24
2.25
- 2.25.1
- 2.25.2
2.26
- 2.26.1
- 2.26.2
- 2.26.3
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.41
2.42
2.43
2.44
2.45
2.46
- 2.46.1
- 2.46.2
2.47
- 2.47.1
- 2.47.2
- 2.47.3

2.1

問題

下のCステートメントに対応するMIPSアセンブリ・コードを示せ．変数f，g，h，iは与えられており，32ビットの整数としてCプログラム内に宣言されている，と想定する．最小限の数のMIPSアセンブリ命令を使用するようにせよ．

1	f = g + ( h - 5 );

解答

# 各変数のレジスタへの割付:
#   $s0 = f
#   $s1 = g
#   $s2 = h

addi $s0, $s2, -5
add  $s0, $s1, $s0

解説

変数のレジスタへの割付は仮定するしかない。Callee-saveの汎用レジスタ $s0 ~ $s7 を使っても良いし、保存の必要のない一時レジスタの $t0 ~ $t7 を使っても良い。
sub 命令は即値を取れないので addi を使う。
最終的に f を格納する $s0 を、一時的に (h - 5) を格納するのに使用しているのが使用レジスタ数を少なくするポイント。
MIPSの算術命令は基本的に2つまでしか入力値（レジスタ, 即値）を取れないので、3つの入力値 g, h, -5 が絡むこのCコードは最小でも2命令を必要とする。

2.2

問題

下のMIPSアセンブリ命令に対応するCステートメントを示せ．

1 2	add f, g, h add f, i, f

解答

1 2	f = g + h; f = i + f;

または

1	f = i + (g + h);

解説

アセンブリを愚直にCに落とすと1つめのコードになる。
普通は2つめのように書く。
どちらで書いてもCからMIPSアセンブリへのコンパイル過程で同じアセンブリになることが期待できる。

2.3

問題

下のCステートメントに対応するMIPSアセンブリ・コードを示せ．変数f，g，h，i，jは与えられており，レジスタ$s0，$s1，$s2，$s3，$s4にそれぞれ割り当てられている，と想定する．また，配列AおよびBのベース・アドレスはレジスタ$s6と$s7にそれぞれ収められている，と想定する．

1	B[8] = A[ i - j ];

解答

# 各変数のレジスタへの割付:
#   $s3 = i (問題文で指定)
#   $s4 = j (問題文で指定)
#   $s6 = A (問題文で指定)
#   $s7 = B (問題文で指定)

sub $t0, $s3, $s4  # $t0 <- i - j
sll $t0, $t0, 2    # $t0 <- $t0 << 2 == $t0 * 4
add $t0, $s6, $t0  # $t0 <- $t0 + A == A + (i - j) == &A[i - j]
lw  $t0, 0($t0)    # $t0 <- A[i - j]
sw  $t0, 32($s7)   # *(B + 8) == B[8] <- $t0

解説

まず A の添字の i -j を最初の sub で計算。
A を1語、すなわち4バイトの値の配列と仮定する（第2章全般で断りなければ1語の変数を使っているので）。
C言語は、ポインタの加算や配列の添字計算では、ポインタの指す値や配列の要素の値のバイト数を勝手に考慮してくれる。 A + 1 と &A[1] はともに「Aのアドレス + 4バイト」を表す。
MIPSはバイトアドレッシングなので、 A + (i - j) を計算するために 4 * (i - j) がほしい。そのために sll で左シフトする。
add で A + (i - j) を計算し、 $t0 にそのアドレスを格納。
lw で $t0 のアドレスの値を読み取る。 lw は、結果を格納するレジスタとメモリアドレスのベース値を指すレジスタで同じものを使える。
B も4バイトの値の配列と仮定する。 &B[8] == B + 8 は「Bのアドレス + 4*8バイト」であり、 B のベースアドレスは $s6 なので、格納先は 32($s7) になる。

2.4

問題

下のMIPSアセンブリ命令に対応するCステートメントを示せ．変数f，g，h，i，jはレジスタ$s0，$s1，$s2，$s3，$s4にそれぞれ割り当てられている，と想定する．また，配列AおよびBのベース・アドレスはレジスタ$s6と$s7にそれぞれ収められている，と想定する．

sll  $t0, $s0, 2    # $t0 = f * 4
add  $t0, $s6, $t0  # $t0 = &A[f]
sll  $t1, $s1, 2    # $t1 = g * 4
add  $t1, $s7, $t1  # $t1 = &B[g]
lw   $s0, 0($t0)    # f = A[f]
addi $t2, $t0, 4
lw   $t0, 0($t2)
add  $t0, $t0, $s0
sw   $t0, 0($t1)

解答

1	B[g] = A[f] + A[f + 1];

解説

まずは、問題のMIPSを各行対応で愚直にCコードに落としていく。ただし、

一時変数はすべて int 型を使う。 int * 型を持ち出すと、バイトアドレッシングのためにMIPSで行っている * 4 の計算がCで現れなくなり対応が難しくなるため。
一時変数は、レジスタと名前を合わせる。 $t0 に対応する一時変数は t0 とする。ただし、同じレジスタに値を上書きするケースでは、 t0_v2 のように、何度目の上書きかをバージョン表記した命名を使う。

int t0 = f << 2;              // sll  $t0, $s0, 2
int t0_v2 = (int)A + t0;      // add  $t0, $s6, $t0
int t1 = g << 2;              // sll  $t1, $s1, 2
int t1_v2 = (int)B + t1;      // add  $t1, $s7, $t1
int s0_v2 = *((int *)t0_v2);  // lw   $s0, 0($t0)
int t2 = t0_v2 + 4;           // addi $t2, $t0, 4
int t0_v3 = *((int *)t2);     // lw   $t0, 0($t2)
int t0_v4 = t0_v3 + s0_v2;    // add  $t0, $t0, $s0
*((int *)t1_v2) = *t0_v4;     // sw   $t0, 0($t1)

はじめの2行は、

1	int t0_v2 = (int)A + (f << 2);

と書き直せる。 int * 型の A をわざわざ int 型にキャストしなければ、これは

1	int t0_v2 = (int)(A + f);

すなわち

1	int t0_v2 = (int)(&A[f]);

と同じである。

次の2行も同様にして

1	int t1_v2 = (int)(&B[g]);

とできる。

1	int s0_v2 = ((int )t0_v2);

の箇所は、最初の2行で t0_v2 に格納した &A[f] の指す値を s0_v2 に格納しているだけである。
つまり、最初の5行はこのように短縮化できる。

1
2
3

int t1_v2 = (int)(&B[g]);
int t0_v2 = (int)A[f];
int s0_v2 = A[f];

6行目では、 t0_v2 + 4 == ((int)A + 4*f) + 4 == (int)A + 4*(f + 1) == (int)(&A[f + 1]) を計算している。
7行目で、これが指す値を t0_v3 へ代入しているので、結局 int t0_v3 = A[f + 1] となる。
つまり、7行目まではこのように短縮化できる。

int t1_v2 = (int)(&B[g]);
int t0_v2 = (int)A[f];
int s0_v2 = A[f];
int t0_v3 = A[f + 1];

そして8行目で s0_v2 と t0_v3 、すなわち A[f] と A[f + 1] を足している。

最後の9行目で、その足した結果を t1_v2 のアドレス &B[g] に格納している。

以上より、最終的に

1	B[g] = A[f] + A[f + 1];

まで短縮化することができる。

2.5

問題

問題2.4のMIPSアセンブリ命令と同じ機能を果たすのに必要な，（可能であれば）MIPSの命令の数を最小にするように，アセンブリ・コードを書き直せ．

解答

# $t0 = &A[f]
sll  $t0, $s0, 2
add  $t0, $s6, $t0

# $s0 = A[f]
lw   $s0, 0($t0)

# $t0 = A[f + 1]
lw   $t0, 4($t0)

# $t0 = A[f] + A[f + 1]
add  $t0, $s0, $t0

# $t1 = &B[g]
sll  $t1, $s1, 2
add  $t1, $s7, $t1

# *(&B[g]) = A[f] + [f + 1]
sw   $t0, 0($t1)

解説

2.4 のアセンブリでは、添字 f + 1 を計算するのに addi $t2, f, 4 を使っていた。しかし添字の中の +1 では、アドレスのオフセットを表現したいだけなので、 lw 命令で 4($?) とオフセットを使えばよい。
余分な addi が減らせて、9命令が8命令になった。
これが最小の命令数であることを証明するのは難しいので割愛😅

2.6

下の表はメモリ内に格納されている配列の32ビットの値を示す．

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

2行目のアドレスは本には38と表記されていたが、4バイトずつにアラインされるべきなので28の誤植と判断した。

2.6.1

問題

上の表に関して，データを昇順にソートして，最小の値を最小のメモリ・ロケーションに収める，Cコードを書け．示されたデータは，Arrayという名のC変数であり，int型の配列を構成し，配列中に示されている最初の数値は配列の最初の要素である，と想定する．また，このマシンはバイト・アドレス方式であり，1語は4バイトで構成される，と想定する．

解答

int tmp;

// Array[0]
tmp = Array[0];
Array[0] = Array[4];
Array[4] = tmp;

// Array[1]
tmp = Array[1];
Array[1] = Array[4];  // はじめ Array[0] だった値
Array[4] = tmp;

// Array[2] : 不要

// Array[3]
tmp = Array[3];
Array[3] = Array[4];  // はじめ Array[1] だった値
Array[4] = tmp;

// Array[4] : Array[3] の処理で、はじめ Array[3] だった値に既になっている

解説

題意がわかりにくいが、 &Array[0] == (int *)24 なのだと解釈する。そして、 Array 配列を in-place で昇順ソートする問題だと解釈する。

表に添字の列も加えると、元の配列は下記。

アドレス	添字	データ
24	0	2
28	1	4
32	2	3
36	3	6
40	4	1

データの昇順でソートすると下記。

アドレス	添字	データ
40	4	1
24	0	2
32	2	3
28	1	4
36	3	6

つまり、下記のようにしてやれば良い。

newArray[0] = Array[4]
newArray[1] = Array[0]
newArray[2] = Array[2]  // 省略可
newArray[3] = Array[1]
newArray[4] = Array[3]

一時変数を1つ用意し、2要素の交換に用いれば、配列の in-place ソートは可能である。

2.6.2

問題

上の表に関して，データを昇順にソートして，最小の値を最小のメモリ・ロケーションに収める，MIPSコードを書け．最小の数のMIPS命令を使用するようにせよ．Arrayのベース・アドレスはレジスタ$s6に収められているものとする．

解答

# 各変数のレジスタへの割付:
#   $s6 = A    (問題文で指定)

lw  $t0, 0($s6)
lw  $t1, 4($s6)
lw  $t3, 12($s6)
lw  $t4, 16($s6)

sw  $t4, 0($t0)
sw  $t0, 0($t1)
sw  $t1, 0($t3)
sw  $t3, 0($t4)

解説

この問題では命令数の最小化が求められる。
先のCのコードでは一時変数の数を最小化したが、それ故に毎回 Array[4] = tmp のような書き戻しが必要になっていた。それを防ぐため、一時レジスタをふんだんに使う。

まずはCでコードを書く。一時変数 t0 は、後でMIPSコードを考えるときに一時レジスタ $t0 に割付けられる。

int t0, t1, t3;

// Array[0]
t0 = Array[0];
Array[0] = Array[4];

// Array[1]
t1 = Array[1];
Array[1] = Array[0];

// Array[2] : 不要

// Array[3]
t3 = Array[3];
Array[3] = Array[1];

// Array[4]
Array[4] = Array[3];

MIPSではメモリからメモリへのコピーはできないので、 Array[0] = Array[4] などはレジスタを使うように書き換える必要がある。

int t0, t1, t3, t4;

t0 = Array[0];
t1 = Array[1];
t3 = Array[3];
t4 = Array[4];

// Array[0]
Array[0] = t4;

// Array[1]
Array[1] = t0;

// Array[2] : 不要

// Array[3]
Array[3] = t1;

// Array[4]
Array[4] = t3;

随分シンプルになった。これを愚直にMIPSに落とし込んで解答を得る。

命令数は8になったが、これは最小である。MIPS Reference Dataによると、以下が言えるため。

メモリ上の4バイトの値をレジスタにロードするためには lw 1命令が必要。
レジスタの4バイトの値をメモリににストアするためには sw 1命令が必要。
メモリ同士のアドレッシングモードは存在しないので、配列の値を読んで配列の値に代入するには、 lw, sw の2命令が必要。
配列の4つの要素に関してメモリのロード・ストアが必要なので、最低でも8命令が必要。

2.7

問題

値0xabcdef12がリトル・エンディアン方式およびビッグ・エンディアン方式のマシンのメモリにどのように収められるかを示せ．データを格納するアドレスは0から始まるものとする．

解答

ビッグエンディアン: 1010 1011 1100 1101 1110 1111 0001 0010
リトルエンディアン: 0001 0010 1110 1111 1100 1101 1010 1011

解説

16進数は1桁で4ビット、2桁で1バイトなので、 0xabcdef12 は4バイトである。

左から書き下せるビッグエンディアンの方から。

0xab : 0xa は10進数で 10, 2進数で 1010。 0xb は2進数で 1011。したがって、 0xab は2進数で 1010 1011 。
0xcd : 2進数で 1100 1101。
0xef : 2進数で 1110 1111。
0x12 : 2進数で 0001 0010。

以上より、 0xabcdef12 をビッグエンディアンで2進数表記すると 1010 1011 1100 1101 1110 1111 0001 0010 。

リトルエンディアンは、これを各バイトごとに区切って反転すれば良いので、 0001 0010 1110 1111 1100 1101 1010 1011

2.8

問題

0xabcdef12を10進数に変換せよ．

解答

2882400018

解説

0xabcdef12 == 0xab * 16^6 + 0xcd * 16^4 + 0xef * 16^2 + 0x12 * 16^0 == 2882400018

2.9

問題

下のCコードをMIPSに変換せよ．変数f，g，h，i，jはレジスタ$s0，$s1，$s2，$s3，$s4にそれぞれ割り当てられている，と想定する．また，配列AおよびBのベース・アドレスはレジスタ$s6と$s7にそれぞれ収められている，と想定する．配列AおよびBの要素は4バイトからなる語であるものとする．

1	B[8] = A[i] - B[j];

解答

# $t0 = A[i]
sll  $t0, $s3, 2
add  $t0, $s6, $t0
lw   $t0, 0($t0)

# $t1 = B[j]
sll  $t1, $s4, 2
add  $t1, $s7, $t1
lw   $t1, 0($t1)

# $t1 = A[i] - B[j]
sub  $t1, $t0, $t1

# B[8] = A[i] - B[j]
sw  $t1, 32($s7)

解説

2.3 と同様。

2.10

問題

下のMIPSコードをCに変換せよ．変数f，g，h，i，jはレジスタ$s0，$s1，$s2，$s3，$s4にそれぞれ割り当てられている，と想定する．また，配列AおよびBのベース・アドレスはレジスタ$s6と$s7にそれぞれ収められている，と想定する．

addi $t0, $s6, 4
add  $t1, $s6, $zero
sw   $t1, 0($t0)
lw   $t0, 0($t0)
add  $s0, $t1, $t0

2行目のaddの第3オペランドは、本には $0 とあるが、わかりやすさのために $zero と表記（レジスタ指定子0はゼロレジスタに対応）。

解答

1 2	A[1] = (int)A; f = 2 * (int)A;

解説

2.4 と同様に、問題のMIPSを各行対応で愚直にCコードに落としていく。

int t0 = (int)A + 4;       // addi $t0, $s6, 4
int t1 = (int)A;           // add  $t1, $s6, $zero
*((int *)t0) = t1;         // sw   $t1, 0($t0)
int t0_v2 = *((int *)t0);  // lw   $t0, 0($t0)
f = t1 + t0_v2;            // add  $s0, $t1, $t0

各行をより自然にする。

int *t0 = &A[1];
int *t1 = &A[0];
A[1] = (int)&A[0];
int t0_v2 = A[1];             // A[1] == (int)&A[0]
f = (int)&A[0] + (int)&A[0];  // &A[0] == A

発生している副作用は A[1] への代入と f への代入（それ以外は一時変数への代入）なので、その2行だけにまとめると下記。

1 2	A[1] = (int)A; f = 2 * (int)A;

2.11

問題

MIPSの各命令について，命令操作コード（OP），ソース・レジスタ（SR），ターゲット・レジスタ（TR）の各フィールドの値を示せ．I形式命令については，即値フィールドの値を示せ．R形式命令については，デスティネーション・レジスタ（DR）フィールドの値を示せ．

「MIPSの各命令」が何を指すか曖昧だが、原著によると、2.10の5つの命令のことを指している模様。

解答

各フィールドのエンコーディングはビッグエンディアンとする。

| 命令 | 命令形式 | OP
bin | SR
bin | TR
bin | DR
bin | 即値
bin |
|——|———-|—-|—-|—-|—-|
| addi $t0, $s6, 4 | I | addi
000100 | $s6
10110 | $t0
00100 | - | 4
00000000 00000100 |
| add $t1, $s6, $zero | R | add
000000 | $s6
10110 | $zero
00000 | $t1
00101 | - |
| sw $t1, 0($t0) | I | sw
000010 | $t0
00100 | $t1
00101 | - | 0
00000000 00000000 |
| lw $t0, 0($t0) | I | lw
010111 | $t0
00100 | $t0
00100 | - | 0
00000000 00000000 |
| add $s0, $t1, $t0 | R | add
000000 | $t1
00101 | $t0
00100 | $s0
10000 | - |

解説

MIPS Reference Data と照らし合わせていく。

最初の addi に関し、Referenceから読み取れること:
- 命令形式がI
- opcode は 0x8。opcodeは31~26ビット目の6桁で表されるので、 000100 。
- R[rt] = R[rs] + SignExtImm なので、 $s6 がrs, $t0 がrt。
- rsは25~~21ビット目の5桁、rtは20~~15ビット目の5桁。
- “REGISTER NAME, NUMBER, USE, CALL CONVENTION” によると、$s0 - $s7 は 16 - 23 で表されるので、 $s6 は10進数で22であり、 10110 。
- $t0 - $t7 は 8 - 15 で表されるので $t0 は 00100 。
- I形式の即値は15~0ビット目の16桁で表されるので、10進数の4をビッグエンディアンで表すと 00000000 00000100 。

これと同様に各命令を符号化していく。

2.12

レジスタ$s0と$s1にそれぞれ値0x80000000と0xD0000000が保持されているとする．

2.12.1

問題

下記のアセンブリ・コード中の$t0の値はいくつか．

1	add $t0, $s0, $s1

解答

0x50000000

解説

桁あふれを考えなければ、 0x80000000 + 0xD0000000 == 0x150000000 。
レジスタは4バイトまでしか保持できないので、最左の 0x1 はあふれ、結果として 0x50000000 となる。

2.12.2

問題

$t0中の結果は期待どおりか，それともオーバフローが発生したか．

解答

オーバーフローが発生した。

解説

特になし。

2.12.3

問題

上に示されたレジスタ$s0と$s1を使用した，下記のアセンブリ・コード中の$t0の値はいくつか．

1	sub $t0, $s0, $s1

解答

0xB0000000

解説

sub 命令は、オペランドを符号付き整数として扱う。
0xD0000000 == 0b 1101 0000 00000000 00000000 00000000 を符号反転する。2の補数をとって、 0x30000000 == 0b 0011 0000 00000000 00000000 00000000 。
- 1の補数 0b 0010 1111 11111111 11111111 11111111 に 0b1 を足して2の補数が得られる。
sub $t0, 0x80000000, 0xD0000000 は add $t0, 0x80000000, 0x30000000 と同じなので、 $t0 = 0xB0000000 を得る。

2.12.4

問題

$t0中の結果は期待どおりか，それともオーバフローが発生したか．

解答

期待通り。

解説

0x80000000 を符号付き4バイト整数とみなし10進数表現すると、 -2,147,483,648
- 先頭ビットが1なので負数。
- 絶対値を考えるために2の補数を取ると 0b 1000 0000 00000000 00000000 00000000 となり、また先頭ビットが1となってしまうが、32ビット符号付き整数において 0b 1000 0000 00000000 00000000 00000000 は最小の負数 -2^31 == -2,147,483,648 であることを思い出そう。
0xD0000000 を符号付き4バイト整数とみなし10進数表現すると、 -805,306,368
- 先頭ビットが1なので負数。
- 絶対値を考えるために2の補数を取ると 0x30000000 。したがって10進数表現すると - 3 * (16^7) == -805,306,368となる。
-2,147,483,648 - (-805,306,368) == -1,342,177,280 であり、これを符号付き4バイト変数として16進数表現すると 0B0000000 となる。
したがって、2.12.3 の回答の 0xB0000000 は期待通りの計算値である。

2.12.5

問題

上に示されたレジスタ$s0と$s1を使用した，下記のアセンブリ・コード中の$t0の値はいくつか．

1 2	add $t0, $s0, $s1 add $t0, $t0, $s0

解答

0xD0000000

解説

add $t0, $s0, $s1 は add $t0, 0x80000000, 0xD0000000 なので、 0x50000000 (オーバーフローしている)
add $t0, $t0, $s0 は add $t0, 0x50000000, 0x80000000 なので、 0xD0000000 (オーバーフローしていない)

2.12.6

問題

$t0中の結果は期待どおりか，それともオーバフローが発生したか．

解答

オーバーフローが発生した

解説

桁あふれを気にしなければ、

0x80000000 + 0xD0000000 == 0x150000000
0x150000000 + 0x80000000 == 0x1D0000000

2.12.5 の結果と比べ、オーバーフローしていることがわかる。

2.13

$s0に値 $(128)_{10}$ が保持されているものとする．

2.13.1

問題

命令add $t0,$s0,$s1に関して，結果がオーバフローを起こすのは，$s1の値の範囲がどういうときか．

解答

$2^{31} - 128 \le $s1 \le 2^{31} - 1$ の場合にオーバーフロー。

解説

$(128)_{10}$ は正の数なので、 add でオーバーフローが起こるのは $s1 が正の数の場合のみ。
符号付き4バイト整数が扱える上限値は $(01111111\ 11111111\ 11111111\ 11111111)_2 == (2^{31} - 1)_{10}$ 。
$128 + $s1 > 2^{31} - 1$ つまり $$s1 > 2^{31} - 129$ ならばオーバーフロー。

2.13.2

問題

命令sub $t0,$s0,$s1に関して，結果がオーバフローを起こすのは，$s1の値の範囲がどういうときか．

解答

$-2^{31} \le $s1 \le -2^{31} + 128$ の場合にオーバーフロー。

解説

$(128)_{10}$ は正の数なので、 sub でオーバーフローが起こるのは $s1 が負の数の場合のみ。
符号付き4バイト整数が扱える値の範囲は $[-2^{31}, 2^{31} - 1]$ 。
$128 - $s1 > 2^{31} - 1$ つまり $$s1 < -2^{31} + 129$ ならばオーバーフロー。

2.13.3

問題

命令sub $t0,$s1,$s0に関して，結果がオーバフローを起こすのは，$s1の値の範囲がどういうときか．

解答

$-2^{31} \le $s1 \le -2^{31} + 127$ の場合にオーバーフロー。

解説

sub $t0, $s1, 128 は add $t0, $s1, -128 と同じ。
$(-128)_{10}$ は負の数なので、 sub でオーバーフローが起こるのは $s1 が負の数の場合のみ。
符号付き4バイト整数が扱える値の範囲は $[-2^{31}, 2^{31} - 1]$ 。
$$s1 - 128 < 2^{31}$ つまり $$s1 < -2^{31} + 128$ ならばオーバーフロー。

2.14

問題

2進値 0000 0010 0001 0000 1000 0000 0010 0000 のアセンブリ言語命令と形式を示せ．

解答

add $s0, $s0, $s0, R形式。

解説

MIPS Reference Data と照らし合わせていく。

31 ~ 26ビット目のopcodeは 000000 。この時点で可能性のある命令は add, addu, and, jr, nor, or, slt, sltu, sll, srl, sub, subu 。
- 2章まででは “CORE INSTRUCTION SET” しか扱っていないので、 “ARITHMETIC CORE INSTRUCTION SET” は無視😏
これらはいずれもR形式なので、5 ~ 0ビット目はfunct。その値は $(100000)_2 == (20)_{16}$ 。 add がこれに該当。
add はR形式なので、
- 25 ~ 21ビット目はrsで、 $(10000)_2 == (16)_{10}$ 。つまり $s0 。
- 20 ~ 16ビット目はrtで、 $(10000)_2 == (16)_{10}$ 。つまり $s0 。
- 15 ~ 11ビット目はrdで、 $(10000)_2 == (16)_{10}$ 。つまり $s0 。
- 10 ~ 6ビット目はshamtで、 00000 。 add においてはshamtは使われない。
- 5 ~ 0 ビット目はfunctで、 100000 。

2.15

問題

命令sw $t1,32($t2)の16進数表現と形式を示せ．

解答

0xAD490020, I形式。

解説

MIPS Reference Data と照らし合わせていく。

sw はI形式命令なので、
- 31 ~ 26ビット目はopcodeで、 0x2b == 0b101011 。
- 25 ~ 21ビット目はrsで $t2 。エンコーディングは 10 == 0b01010 。
- 20 ~ 16ビット目はrtで $t1 。エンコーディングは 9 == 0b01001 。
- 15 ~ 0ビット目はimmediateで 32 。エンコーディングは 32 == 0b 00000000 00100000 。
- 全体で 0b 1010 1101 0100 1001 0000 0000 0010 0000 == 0x A D 4 9 0 0 2 0

2.16

問題

下記のMIPSのフィールドによって表される命令の，形式，アセンブリ言語命令，および2進数表現を示せ．

1	op=0, rs=3, rt=2, rd=3, shamt=0, funct=34

解答

R形式, sub $v1, $v1, $v0, 0b 0000 0000 0110 0010 0001 1000 0010 0010

解説

MIPS Reference Data と照らし合わせていく。

functがあるのでR形式。
アセンブリ言語命令:
- op=0, funct=34 (0b10 0010 == 0x22) の命令は sub 。
- rs=3 は $v1 に対応。
- rt=2 は $v0 に対応。
- rd=3 は $v1 に対応。
- したがって sub $v1, $v1, $v0
2進数表現:
- 31 ~ 26ビット目はopで、 $(0)_{10} == (000000)_2$ 。
- 25 ~ 21ビット目はrsで、 $(3)_{10} == (00011)_{2}$ 。
- 20 ~ 16ビット目はrtで、 $(2)_{10} == (00010)_{2}$ 。
- 15 ~ 11ビット目はrdで、 $(3)_{10} == (00011)_{2}$ 。
- 10 ~ 6ビット目はshamtで、$(0)_{10} == (00000)_2$ 。
- 5 ~ 0 ビット目はfunctで、$(34)_{10} == (100010)_2$ 。
- 全体で 0b 000000 00011 00010 00011 00000 100010 。

2.17

問題

下記のMIPSのフィールドによって表される命令の，形式，アセンブリ言語命令，および2進数表現を示せ．

1	op=0x23, rs=1, rt=2, const=0x4

解答

I形式, lw $v0, 4($at), 0b 0101 1100001 00010 00000000 00000100

解説

MIPS Reference Data と照らし合わせていく。

constがあるのでI形式。
アセンブリ言語命令:
- op=0x23 の命令は lw 。
- rs=1 は $at に対応。
- rt=2 は $v0 に対応。
- const=0x4 は即値 4 に対応。
- したがって lw $v0, 4($at)
2進数表現:
- 31 ~ 26ビット目はopで、 $(23)_{16} == (010111)_2$ 。
- 25 ~ 21ビット目はrsで、 $(1)_{10} == (00001)_{2}$ 。
- 20 ~ 16ビット目はrtで、 $(2)_{10} == (00010)_{2}$ 。
- 15 ~ 0ビット目はconstで、 $(4)_{10} == (00000000\ 00000100)_{2}$ 。
- 全体で 0b 010111 00001 00010 00000000 00000100 。

2.18

MIPSのレジスタ・ファイルの数を128に拡大し，命令セット中の命令の数を４倍に拡大したとする．

2.18.1

問題

R形式命令中の各ビット・フィールドのサイズは，上記の変更によって，どのような影響を受けるか．

解答

（設計方針次第なので複数の回答があり得る）

	opcode	rs	rt	rd	shamt	funct
今のサイズ [bit]	6	5	5	5	5	6
拡大後のサイズ [bit]	8	7	7	7	3	0

解説

MIPS Reference Data と照らし合わせていく。

レジスタファイルが32個の今、5bitを使ってレジスタを指定していた。128個になると7bitが必要となる。
命令数が4倍になった場合、opcodeを2bit増やして8bitにすれば対応はできる。
- ただし、増える命令がR形式だけならば、functを2bit増やすという手もあり得る。ここでは常識的に、どの形式の命令も4倍程度増えると仮定。
今の命令数は、 “CORE INSTRUCTION SET” と “ARITHMETIC CORE INSTRUCTION SET” を合わせて55個。opcode 6bitで64個表現できるので、 命令の区別のためには、6bitのopcodeだけで十分で、functフィールドは不要である。
- 4章で、opcodeによりパイプラインの各ステージ全体の制御が成され、functでR命令に関するALU制御が成されることが説明される。考察が浅いが、6bitのopcodeだけにするとID (Instruction Decode)ステージのレイテンシが大きくなりすぎるのかな？
命令長を32bitのまま維持すると仮定すると、opcodeの +2bit とrs, rt, rdの 3 * +2bit の合計 + 8bit を、shamtとfunctから減らす必要がある。
- 55 * 4 個の命令を区別するためには8bitで十分。ここでもfunctは不要。funct分 -6bit 削減できる。
  - 今の命令セットと互換性は捨てる方針。
- shamt でも2bit削減する必要がある。

2.18.2

問題

I形式命令中の各ビット・フィールドのサイズは，上記の変更によって，どのような影響を受けるか．

解答

| | opcode | rs | rt | immediate |
|——|——–|—-|—-|—-|——-|——-|
| 今のサイズ [bit] | 6 | 5 | 5 | 16 |
| 拡大後のサイズ [bit] | 8 | 7 | 7 | 10 |

解説

2.18.1 と同様、opcode, rs, rtはそれぞれ2bit拡大。
命令長を32bitのまま維持すると仮定すると、immediateは6bit削減する必要がある。

2.18.3

問題

上記の２つの変更のそれぞれは，MIPSのアセンブリ・プログラムのサイズを小さくする方向に，どのように働くか．逆に，MIPSのアセンブリ・プログラムのサイズを大きくする方向には，どのように働くか．

解答

小さくする方向:
- 命令の種類が増えたため、今までは複数種類の命令を組み合わせて行った演算が、新しい1つの演算でできるようなケースが期待できる。
- レジスタの個数が増えたため、レジスタをスタックに退避するためのロード・ストア命令を減らすことができる。
- レジスタの個数が増えたため、一時変数をスタック上に領域確保せずに直接レジスタ割当できるケースが多くなり、ロード・ストア命令を減らすことができる。
大きくする方向:
- R命令でshamtが削減されたため、1命令で済んでいたシフトが2命令必要になることがある。
- I命令でimmediateが削減されたため、1命令で済んでいたI命令が2命令必要になることがある。

解説

特になし

2.19

レジスタの内容が下記のようになっているとする．

1	$t0 = 0xAAAAAAAA, $t1 = 0x12345678

2.19.1

問題

上記のレジスタを使用して下記の一連の命令を実行したら，$t2の値はどうなるか．

1 2	sll $t2, $t0, 4 or $t2, $t2, $t1

本にはsllのshamtが44とあったが、5bitで表せる数値ではないため、4の誤植と判断。

解答

0b 1011 1010 1011 1110 1111 1110 1111 1000

解説

まず sll $t2, $t0 == 0xAAAAAAAA, 4 。

\[
\begin{eqnarray}
$t2 &\leftarrow& {\rm 0x}AAAAAAAA << 4 \\
&==& {\rm 0b}\ 1010\ 1010\ 1010\ 1010\ 1010\ 1010\ 1010\ 1010 << 4 \\
&==& {\rm 0b}\ 1010\ 1010\ 1010\ 1010\ 1010\ 1010\ 1010\ 0000
\end{eqnarray}
\]

次に or $t2, $t2 == 0b 10101010 10101010 10101010 10100000, $t1 == 0x12345678 。

\[
\begin{eqnarray}
$t2 \leftarrow &{\rm 0b}& 1010\ 1010\ 1010\ 1010\ 1010\ 1010\ 1010\ 0000\ {\rm or}\ {\rm 0x}12345678 \\
== &{\rm 0b}& 1010\ 1010\ 1010\ 1010\ 1010\ 1010\ 1010\ 0000\ {\rm or}\ \\
&{\rm 0b}& 0001\ 0010\ 0011\ 0100\ 0101\ 0110\ 0111\ 1000 \\
== &{\rm 0b}& 1011\ 1010\ 1011\ 1110\ 1111\ 1110\ 1111\ 1000
\end{eqnarray}
\]

2.19.2

問題

上記のレジスタを使用して下記の一連の命令を実行したら，$t2の値はどうなるか．

1 2	sll $t2, $t0, 4 andi $t2, $t2, -1

解答

0b 1010 1010 1010 1010 1010 1010 1010 0000

解説

sll は 2.19.1 と全く同じ。

andi $t2, $t2 == 0b 10101010 10101010 10101010 10100000, -1 == 0b 1111 1111 1111 1111 1111 1111 1111 1111 を考える。
-1 は全ビットが 1 なので、これとANDを取ると、元の値のままになる。したがって、

\[
$t2 \leftarrow $t2\ {\rm and}\ -1 == $t2 == {\rm 0b}\ 1010\ 1010\ 1010\ 1010\ 1010\ 1010\ 1010\ 0000
\]

2.19.3

問題

上記のレジスタを使用して下記の一連の命令を実行したら，$t2の値はどうなるか．

1 2	srl $t2, $t0, 3 andi $t2, $t2, 0xFFFF

解答

0b 0000 0000 0000 0000 0101 0101 0101 0101

解説

まず srl $t2, $t0 == 0xAAAAAAAA, 3 。

\[
\begin{eqnarray}
$t2 &\leftarrow& {\rm 0x}AAAAAAAA >> 3 \\
&==& {\rm 0b}\ 1010\ 1010\ 1010\ 1010\ 1010\ 1010\ 1010\ 1010 >> 3 \\
&==& {\rm 0b}\ 0001\ 0101\ 0101\ 0101\ 0101\ 0101\ 0101\ 0101
\end{eqnarray}
\]

0xFFFF とのANDは、下位2バイトだけを残すマスクと考えられるので、 $t2 の上位2バイトが0になり、下位2バイトが保存された値となる。

2.20

問題

レジスタ$t0のビット16から11までを抽出し，その値でレジスタ$t1のビット31から26までを，残りの26ビットを変更せずに，置き換える，一連の最短の命令を示せ．

解答

andi $t0, $t0, 0b 00000000 00000001 11111000 00000000
sll  $t0, $t0, 15

andi $t1, $t1, 0b 00000011 11111111 11111111 11111111

or $t0, $t0, $t1

解説

$t0 の 16~11ビット目を抽出するために、 $t0 AND 0b 00000000 00000001 11111000 00000000 を計算。
それを $t1 の31~26ビット目にぶつけるために15ビット左シフトし、 ($t0 AND 0b 00000000 00000001 11111000 00000000) << 15 を計算。
$t1 の元々の31~26ビット目を0クリアし、残りの26ビットを保持するために、 $t1 AND 0b 00000011 11111111 11111111 11111111 を計算。
(($t0 AND 0b 00000000 00000001 11111000 00000000) << 15) OR ($t1 AND 0b 00000011 11111111 11111111 11111111) が最終的に得たい数。
これが最小の命令数であることを証明するのは難しいので割愛😅

2.21

問題

下記の疑似命令を実現する，最小のMIPS命令セットを示せ．

1	not $t1, $t2 // ビット単位の反転

解答

1	nor $t1, $t2, $zero

解説

NOT x 演算は、例えば NOR x, 0 で実現できる。
MIPSには not 命令はないが nor 命令と $zero レジスタがあるので、シンプルにNOT演算が実現できる。

2.22

問題

下記のCステートメントと同じ機能を果たす，一連の最短のMIPSアセンブリ命令を示せ．$t1=A，$t2=B，$s1は配列Cのベース・アドレスであるとする．

1	A = C[0] << 4;

解答

1 2	lw $t0, 0($s1) # C[0] をレジスタにロード sll $t1, $t0, 4 # A = C[0] << 4

解説

特になし

2.23

問題

$t0に値0x00101000が保持されているとする．下記の一連の命令を実行すると，$t2の値はどうなるか．

      slt  $t2, $zero, $t0
      bne  $t2, $zero, ELSE
      j    DONE
ELSE: addi $t2, $t2, 2
DONE:

書籍中の $0 は $zero (ゼロレジスタ) と表記を変えた。

解答

解説

slt $t2, $zero, $t0 で、 0 < 0x00101000 の真偽値が $t2 にセットされる。 0x00101000 は正の数なので $t2 = 1 となる。
bne $t2 == 1, $zero, ELSE では “not-equal” が成り立つケースなので、ELSEへ分岐。
addi $t2, $t2 == 1, 2 が実行され、 $t2 == 3 となる。

2.24

問題

プログラム・カウンタ（PC）が0x20000000と設定されているとする．アドレス0x40000000をPCに設定するために，MIPSアセンブリ命令のjump(j)を使用することが可能か．それと同じ操作を行うために，MIPSアセンブリ命令のbranch-on-equal(beq)を使用することが可能か．

解答

j 命令の使用は不可。
beq 命令の使用は不可。

解説

j 命令:
- 本文2.10節の “分岐とジャンプにおけるアドレシング” の項目に記載してあることを要約すると、ジャンプ先のアドレス（バイトアドレッシング）は、
  1
  2
  現在のPCの上位4ビット j命令のオペランド 00
  31 28 27 2 1 0
- PCが 0x20000000 のとき、「現在のPCの上位4ビット」は 0x2 なので、ジャンプできるのは高々 0x2FFFFFF まで。
- 今回のジャンプ先の 0x40000000 には届かない。
beq 命令:
- 本文2.10節の “分岐とジャンプにおけるアドレシング” の項目に記載してあることを要約すると、
  - PC相対アドレシングを使い、現在のPCから $[-2^{15}, 2^{15} - 1]$ 語離れた命令にジャンプできる。
- 現在のPCが 0x20000000 のとき、そこから前方にジャンプできるのは 0x2000FFFF まで。 0x40000000 には届かない。

2.25

MIPSの命令セットには，下記の命令は含まれていない．

1 2	rpt $t2, loop # R[rs] > 0 であれば、 # R[rs] = R[rs] - 1, PC = PC + 4 + 分岐先アドレス

2.25.1

問題

MIPSの命令セットにこの命令を組み込むならば，どの命令形式が最も適切であるか．

解答

I形式。

解説

（ラベルの名前や、R[rs] をカウントダウンして0と比較し、0より大きければ分岐先アドレスの直後に戻ることから、 rpt は repeat の略称と思われる）
beq と近しい機能なので、 beq と同じくI形式。

2.25.2

問題

この機能を果たすMIPSの一連の命令で最短のものを示せ．

解答

1
2
3

loop:  ...                 # ループ内処理
       addi $t0, $t0, -1
       bne  $t0, $zero, loop

解説

$t0 をカウントダウン用のレジスタとしている。

2.26

下記のMIPSのループがあるとする．

LOOP:  slt  $t2, $zero, $t1
       beq  $t2, $zero, DONE
       subi $t1, $t1, 1
       addi $s2, $s2, 2
       j    LOOP
DONE:

書籍中の $0 は $zero と表記を変えた。

2.26.1

問題

レジスタ$t1の値が10に初期化されているとする．$t2の初期値がゼロであったならば，レジスタ$t2の値はどうなるか．

解答

解説

DONE へジャンプするのは、 $t2 が0になったとき。
ループ内で $t1 がデクリメントされるので、 $t1 の初期値が0以上であれば、必ず DONE へジャンプする。

2.26.2

問題

上記のループに相当する，Cコード・ルーチンを書け．ただし，レジスタ$s1，$s2，$t1，$t2はそれぞれ整数A，B，i，tempとする．

解答

1	for ( ; i != 0; ++i) { B += 2; }

解説

アセンブリから、カウンタ変数は $t1 で、カウントダウンに使われている。 $t1 は i に割当てられている。
ループが終了する条件は i == 0 になったとき。
ループ内では、 i のデクリメントと $s2 == B の +2 が行われている。
for 文を使って自然に書ける。

2.26.3

問題

MIPSのアセンブリ・コードで書かれた上記のループに関して，レジスタ$t1の値がNに初期化されているとする．実行されるMIPSの命令の数はいくつになるか．

解答

5 * N + 2

解説

beq の条件が不成立のとき、1回のループあたりの命令数は5個。
beq の条件が不成立なのはN回なので、 5 * N 個の命令が実行される。
beq の条件が成立するときは、2個の命令が実行される。

2.27

問題

下記のCコードをMIPSのアセンブリ・コードに翻訳せよ．使用する命令の数を最小限にせよ．値a，b，i，jはそれぞれレジスタ$s0，$s1，$t0，$t1に収められているものとする．また，レジスタ$s2に配列Dのベース・アドレスが収められているものとする．

1
2
3

for (i = 0; i < a; i++)
  for (j = 0; j < b; j++)
    D[4*j] = i + j;

解答

         add  $t0, $zero, $zero   # i = 0
LOOP_i:  slt  $t2, $t0, $s0       # $t2 = i < a
         beq  $t2, $zero, DONE_i
         add  $t1, $zero, $zero   # j = 0
LOOP_j:  slt  $t2, $t1, $s1       # $t2 = j < b
         beq  $t2, $zero, DONE_j
         add  $t2, $t0, $t1       # $t2 = i + j
         sll  $t3, $t1, 4         # $t3 = (4*j) * 4
         add  $t3, $s2, $t3       # $t3 = D + (4*j) * 4
         sw   $t2, 0($t3)
         addi $t1, $t1, 1         # j++
         j    LOOP_j
DONE_j:  addi $t0, $t0, 1         # i++
         j    LOOP_i
DONE_i:

解説

特になし

2.28

問題

問題2.27のCコードを実現するためには，MIPSの命令がいくつ必要か．変数のaとbがそれぞれ10と1に初期化されており，配列Dのすべての要素が0に初期化されていたならば，ループが完了するまでにMIPSの命令がいくつ実行されるか．

解答

命令数は14個。
命令実行回数は153回。

解説

命令数は、2.27のものを数えて14個。
内側のループの条件分岐 j < b が成立する回数は $a \times b$ 回。その際に実行される命令列は $[LOOP\_j, DONE\_j)$ の8個。
内側のループの条件分岐 j < b が成立しなくなったとき、 LOOP_j で始まる slt, beq の2命令だけが実行される。その回数は $a$ 回。
外側のループの条件分岐 i < a が成立する回数は $a$ 回。その際に実行される $[LOOP\_i, LOOP\_j), [DONE\_j, DONE\_i)$ の命令数は5個。
外側のループの条件分岐 i < a が成立しなくなったとき、 LOOP_j で始まる slt, beq の2命令だけが実行される。その回数は1回。
外側のループの初期化は、 add $t0, $zero, $zero 1命令のみ。
したがって、合計の実行回数は $8ab + 2a + 5a + 2 + 1 == 8ab + 7a + 3$

2.29

問題

下記のループをCコードに翻訳せよ．Cレベルの整数iがレジスタ$t1に保持されており，resultという名前のCレベルの整数がレジスタ$s2に保持されており，整数MemArrayのベース・アドレスがレジスタ$s0に保持されているものとする．

       addi $t1, $zero, 0
LOOP:  lw   $s1, 0($s0)
       add  $s2, $s2, $s1
       addi $s0, $s0, 4
       addi $t1, $t1, 1
       slti $t2, $t1, 100
       bne  $t2, $zero, LOOP

1行目の命令は本では addi $t1, $0, $0 となっていたが、意図を汲み取って訂正。また、bneのrtは $s0 となっていたが、MemArrayのポインタと直近の条件分岐結果の 0/1 とを比較するのはあまりにナンセンスなので、 $zero と解釈した。

解答

for (i = 0, int *p = MemArray; ; ) {
  result += *(p++);
  if (++i >= 100) break;
}

または

for (i = 0; ; ) {
  result += MemArray[i++];
  if (i >= 100) break;
}

解説

$t1 に割付けられている i に着目すると、 addi $t1, $zero, 0 でゼロに初期化され、 addi $t1, $t1, 1 でインクリメントされ、 slti $t2, $t1, 100 で i < 100 と比較される、100回のループを実現するためのカウンタ変数であることがわかる。
- slti の条件分岐が LOOP の先頭に来ていないので、 for 文の2番目のパラメータに i < 100 と書くことはできない。
- addi のインクリメントが LOOP の末尾に来ていないので、for 文の3番目のパラメータに i++ と書くことはできない。
$s0 に着目すると、一番初めは MemArray の先頭アドレスを指しており、 addi $s0, $s0, 4 で配列の次要素を指すようになっている。$s0 は int *p の一時変数に対応付けて、ループ内でポインタをインクリメントすると自然な処理になる。

元のアセンブリからCを書くと int *p = MemArray を使ったコードが自然だが、できあがったCコードを見ると、 i を添え字として使うアイディアも自然に思いつく。

2.30

問題

実行されるMIPSの命令の数を減らすように，問題2.29のループを書き直せ．

解答

lw   $s1, 0($s0)    # $s1 = MemArray[0]
add  $s2, $s2, $s1  # result += MemArray[0]

lw   $s1, 4($s0)    # $s1 = MemArray[1]
add  $s2, $s2, $s1  # result += MemArray[1]

# ...

lw   $s1, 396($s0)    # $s1 = MemArray[99]
add  $s2, $s2, $s1  # result += MemArray[99]

解説

2.29で得たCコードから、起こすべき副作用は「 result に MemArray[0], MemArray[1], ..., MemArray[99] の和を格納すること」と分かっている。
ループアンローリングを使えば、以下の理由で実行命令数が削減できる。
- ループ変数に関する命令実行が不要になる。
- MemArray のベースアドレスからのオフセットが即値で指定できるので、アドレス計算が不要になる。

2.31

問題

下記のCコードをMIPSのアセンブリ・コードに翻訳せよ．この関数を実行するために必要な，MIPSの命令の数は全部でいくつか．

int fib(int n) {
  if (n == 0)
    return 0;
  else if (n == 1)
    return 1;
  else
    return fib(n - 1) + fib(n - 2);
}

解答

fib:
           # if (n == 0)
           beq  $a0, $zero, return_0

           # if (n == 1)
           addi $t0, $zero, 1
           beq  $a0, $t0, return_1

           # else

           # 以下のコードから、スタックに退避する値は
           # $a0, $ra (関数呼び出しに関する caller-save レジスタ) と、
           # $s0 (汎用的に使える caller-save レジスタ) の3つ。
           # スタックポインタを予め12バイト伸ばしておく。
           addi $sp, $sp, -12
           sw   $a0, 8($sp)
           sw   $ra, 4($sp)
           sw   $s0, 0($sp)

           # call fib(n - 1)
           addi $a0, $a0, -1
           jal  fib

           # fib(n - 1) の戻り値を $v0 に入れたまま fib(n - 2) を呼び出すと値が破壊されるので、
           # caller-save レジスタの $s0 に退避しておく。
           addi $s0, $v0, 0

           # 退避していたnの値をスタックからロード。
           lw   $t0, 4($sp)

           # call fib(n - 2)
           addi $a0, $t0, -2
           jal fib

           # return fib(n - 1) + fib(n - 2)
           add  $v0, $s0, $v0

           # スタックから callee-save レジスタをpop
           lw   $s0, 0($sp)
           lw   $ra, 4($sp)
           lw   $a0, 8($sp)
           addi $sp, $sp, 12

           jr   $ra
return_0:
           addi $v0, $zero, 0
           jr   $ra
return_1:
           addi $v0, $zero, 1
           jr   $ra

命令数は20個。

解説

まずは、条件分岐によらない決め事をいくつか。

引数 n は $a0 を割付ける。
戻り値は $v0 を使う。

条件分岐ごとに順を追ってアセンブリを書いていく。

n == 0 のケース

分岐自体は、ゼロレジスタと比較する形で beq $a0, $zero, return_0 と容易に書ける。
分岐先で行うべき処理は、戻り値に 0 をセットし、return するだけ。

           beq  $a0, $zero, return_0
return_0:
           addi $v0, $zero, 0
           jr   $ra

n == 1 のケース

n == 0 と比べて面倒なのは、常に値が1であるレジスタが存在しないので、 beq 命令の前に一時レジスタに1をセットする必要がある点だけ。

           addi $t0, $zero, 1
           beq  $a0, $t0, return_1
return_1:
           addi $v0, $zero, 1
           jr   $ra

else のケース

（末尾再帰ではない）関数呼び出しが出てくるので、スタックの利用が必要になる。
まずはじめに、必ず使う caller-save レジスタをスタックに退避させるコードを書く。今回は関数呼び出しの引数・戻り値に対応する $a0 と $ra が対象。
1
2
3
addi $sp, $sp, -8 # スタックを変数2個分下に伸ばす
sw $a0, 4($sp)
sw $ra, 0($sp)
fib(n - 1) を呼び出す。この時点では n の値は $a0 に入っているので、 $a0 = $a0 - 1 してから jal で再帰呼び出し。
1
2
addi $a0, $a0, -1
jal fib
$v0 に fib(n - 1) の戻り値が格納されている。 $v0 は caller-save レジスタなので、次の fib(n - 2) 呼び出しの中で破壊される可能性がある（実際される）ので、
- $v0 の値をスタックに退避
- $v0 の値を別の caller-save レジスタにコピー
のいずれかを行う。今回は後者で $s0 を使う。はじめのスタック退避コードを修正し、
1
2
3
4
addi $sp, $sp, -12 # スタックを変数3個分下に伸ばす
sw $a0, 8($sp)
sw $ra, 4($sp)
sw $s0, 0($sp)
そして $s0 = $v0 する。
1
addi $s0, $v0, 0
fib(n - 1) の戻り値も無事 $s0 にコピーできたので、 fib(n - 2) を呼び出す。その前に n - 2 を計算するが、元々 n の値が入っていた $a0 は caller-save レジスタなので、 fib(n - 1) 呼び出しの中で破壊されている可能性がある（実際再帰呼び出しの中で、 $a0 == 1 まで減らされている）。スタックに退避していた n をロードし、 fib(n - 1) を呼び出す。
1
2
3
lw $t0, 4($sp)
addi $a0, $t0, -2
jal fib
もうこれ以上関数呼び出しはない（ fib(n - 2) はリーフ呼び出しである）ので、 $v0 を退避させる必要はない。 fib(n - 1) の返り値は $s0 にコピーしていたので、これと $v0 の和が fib(n - 1) + fib(n - 2) となり、 fib(n) が戻り値とすべきもの。
1
add $v0, $s0, $v0

return する前に、スタックから callee-save レジスタをpopしておく。

# スタックから callee-save レジスタをpop
lw   $s0, 0($sp)
lw   $ra, 4($sp)
lw   $a0, 8($sp)
addi $sp, $sp, 12
jr   $ra

以上を組み合わせると解答のコードができる。

2.32

問題

コンパイラによって，関数が「インライン」実装されることがよくある．それは，関数の本体をプログラムの中にコピーすることである．それによって，関数を呼び出すオーバヘッドなくすことができる．上記のCコードのインライン版をMIPSのアセンブリ・コードで作成せよ．その関数を完了させるのに必要なMIPSのアセンブリ命令の数が全部でいくつ削減されるか．ただし，Cの変数nは5に初期化されているものとする．

解答

複数通りの考え方があるので、解説から見ることを推奨。

fib:
           # if (n == 0)
           beq  $a0, $zero, return_0

           # if (n == 1)
           addi $t0, $zero, 1
           beq  $a0, $t0, return_1

           # else

           # 以下のコードから、スタックに退避する値は
           # $a0, $ra (関数呼び出しに関する caller-save レジスタ) と、
           # $s0, $s1 の4つ。
           # スタックポインタを予め16バイト伸ばしておく。
           addi $sp, $sp, -16
           sw   $a0, 12($sp)
           sw   $ra, 8($sp)
           sw   $s0, 4($sp)
           sw   $s1, 0($sp)

           # call fib(n - 1)
           addi $a0, $a0, -1
           jal  fib

           # fib(n - 1) の戻り値を caller-save レジスタの $s0 に退避しておく。
           addi $s0, $v0, 0

           # 退避していたnの値をスタックからロード。
           lw   $t0, 4($sp)

           # ここから、インライン展開した fib(n - 2) のコード。
           # int f2;
           # {
           #   int n2 = n - 2;
           #   if (n2 == 0)
           #     f2 = 0;
           #   else if (n2 == 1)
           #     f2 = 1;
           #   else
           #     f2 = fib(n2 - 1) + fib(n2 - 2);
           # }
           #
           # n2 は $t0, f2 は $t2 に割付ける。
           addi $t0, $t0, -2  # n2 = n - 2

           # n2 == 0
           beq  $t0, $zero, f2_0

           # n2 == 1
           addi $t1, $zero, 1
           beq  $t0, $t1, f2_1

           # else

           # call fib(n2 - 1)
           addi $a0, $t0, -1
           jal  fib

           # fib(n2 - 1) の戻り値を caller-save レジスタの $s1 に退避しておく。
           addi $s1, $v0, 0

           # call fib(n2 - 1)
           addi $a0, $t0, -2
           jal  fib

           # f2 = fib(n2 - 1) + fib(n2 - 2)
           add  $t2, $s1, $v0

           j    f2_done
f2_0:
           addi $t2, $zero, 0  # f2 = 0
           j    f2_done
f2_1:
           addi $t2, $zero, 1  # f2 = 1
           j    f2_done
f2_done:
           # return fib(n - 1) + fib(n - 2)
           add  $v0, $s0, $t2

           # スタックから callee-save レジスタをpop
           lw   $s1, 0($sp)
           lw   $s0, 4($sp)
           lw   $ra, 8($sp)
           lw   $a0, 12($sp)
           addi $sp, $sp, 16

           jr   $ra
return_0:
           addi $v0, $zero, 0
           jr   $ra
return_1:
           addi $v0, $zero, 1
           jr   $ra

n == 5 で呼び出したとき、2.31のコードだと実行命令数は120, このインライン版のコードだと実行命令数は131。

解説

妥協点が難しい問題である。

一般の再帰関数は停止性が実行時にしかわからない場合があり、インライン展開を完全に行おうとしたとき、コード長が無限大になり得る。
今回のフィボナッチ数に関して言えば停止性は人間の目から見ると自明であり、コンパイル時計算でインライン展開もできそうだが、それを言ってしまうと

\[
\begin{eqnarray}
{\rm fib}(5) &==& {\rm fib}(4) + {\rm fib}(3) \\
&==& ({\rm fib}(3) + {\rm fib}(2)) + ({\rm fib}(2) + {\rm fib}(1)) \\
&==& (({\rm fib}(2) + {\rm fib}(1)) + ({\rm fib}(1) + {\rm fib}(0))) + (({\rm fib}(1) + {\rm fib}(0)) + {\rm fib}(1)) \\
&==& ((({\rm fib}(1) + {\rm fib}(0)) + {\rm fib}(1)) + ({\rm fib}(1) + {\rm fib}(0))) + (({\rm fib}(1) + {\rm fib}(0)) + {\rm fib}(1)) \\
&==& 1 + 0 + 1 + 1 + 0 + 1 + 0 + 1 \\
&==& 5
\end{eqnarray}
\]

という風にコンパイル時に答えが出せてしまう。

今回は妥協点として、 fib(n - 2) 呼び出しを一段階だけインライン展開した下記のコードをMIPSコードに翻訳することを考える。

int fib(int n) {
  if (n == 0)
    return 0;
  else if (n == 1)
    return 1;
  else {
    int f1 = fib(n - 1);

    int f2;
    {
      int n2 = n - 2;
      if (n2 == 0)
        f2 = 0;
      else if (n2 == 1)
        f2 = 1;
      else
        f2 = fib(n2 - 1) + fib(n2 - 2);
    }
    return f1 + f2;
  }
}

MIPSコードは解答のもの。

実行命令数を数える。まずは2.31のコードから。

else句に入るケース (n = 5, 4, 3, 2) では、実行命令数は各々16個。
n = 1 のケースでは、実行命令数は5個。
n = 0 のケースでは、実行命令数は3個。
関数呼び出しの回数を数えると、
- fib(5): 1回
- fib(4): 1回
- fib(3): 2回
- fib(2): 3回
- fib(1): 5回
- fib(0): 3回
合計実行命令数は $(1 + 1 + 2 + 3) \times 16 + 5 + 3 = 120$

次に2.32のコードの実行命令数を数える。そのために、インライン展開を反映した式展開を書き下す。

\[
\begin{eqnarray}
{\rm fib}(5) &==& {\rm fib}(4) + ({\rm fib}(2) + {\rm fib}(1)) \\
&==& ({\rm fib}(3) + ({\rm fib}(1) + {\rm fib}(0))) + (({\rm fib}(1) + 0) + {\rm fib}(1)) \\
&==& (({\rm fib}(2) + 1) + ({\rm fib}(1) + {\rm fib}(0))) + (({\rm fib}(1) + 0) + {\rm fib}(1)) \\
&==& ((({\rm fib}(1) + 0) + 1) + ({\rm fib}(1) + {\rm fib}(0))) + (({\rm fib}(1) + 0) + {\rm fib}(1))
\end{eqnarray}
\]

n = 5, 4 のケースでは、2箇所の条件分岐において、両方ともelse句に入る。このときの実行命令数は26個。
n = 3 のケースでは、最初の条件分岐はelse句、次の条件分岐は n2 == 1 のpath。このときの実行命令数は20個。
n = 2 のケースでは、最初の条件分岐はelse句、次の条件分岐は n2 == 0 のpath。このときの実行命令数は18個。
n = 1 のケースでは、最初の条件分岐で n == 1 のpathに入って終わる。このときの実行命令数は5個。
n = 0 のケースでは、最初の条件分岐で n == 0 のpathに入って終わる。このときの実行命令数は3個。
関数呼び出しの回数を数えると、
- fib(5): 1回
- fib(4): 1回
- fib(3): 1回
- fib(2): 2回
- fib(1): 4回
- fib(0): 1回
合計実行命令数は $(1 + 1) \times 26 + 20 + 2 \times 18 + 4 \times 5 + 3 = 131$

インライン展開なしのものよりも実行命令数が増えてしまった。

2.33

問題

各関数呼び出しに関して，関数呼び出しがなされた後の，スタックの内容を示せ．スタック・ポインタは当初はアドレス0x7ffffffcを指しており，図2.11に示されているレジスタ規約に従っているものとする．

「各関数呼び出し」は、2.31における関数呼び出しを指すものと想定する。

解答

fib(4) 呼び出しを考える。

解説

2.31 のコードを見ると、
- n == 1, 0 の場合、スタックの拡大は行わない。
- n > 2 の場合、「スタックの拡大」「fib(n - 1) 呼び出し」「fib(n - 2) 呼び出し」の順序で行っている。
  - 各呼び出しでは、高位から低位に向けて $a0, $ra, $s0 の順にスタックにpushしている。

以上のことから、解答の図がかける。

2.34

問題

下記の関数fをMIPSのアセンブリ・コードに翻訳せよ．レジスタ$t0から$t7までを使用する必要があれば，番号が小さいものから順に使用せよ．funcの関数宣言はint f(int a,int b)となっているものとする．関数fのコードは下記のとおりである．

1
2
3

int f(int a, int b, int c, int d) {
  return func(func(a, b), c + d);
}

解答

f:
    # caller-save レジスタの退避。
    addi $sp, -8
    sw   $ra, 0($sp)
    sw   $s0, 4($sp)

    # $s0 = c + d
    add $s0, $a2, $a3

    # 内側の func 呼び出し。既に $a0 = a, $a1 = b と割当てられているので、引数セットは不要。
    jal func

    # 外側の func 呼び出し
    addi $a0, $v0, 0  # $a0 = func(a, b)
    addi $a1, $s0, 0  # $a1 = c + d
    jal  func

    # 外側の func 呼び出し後は $v0 に戻り値が入っていて、それをそのまま返せば良いので、戻り値セットは不要。

    # スタックから callee-save レジスタをpop
    lw   $s0, 4($sp)
    lw   $ra, 0($sp)
    addi $sp, 8

    jr   $ra

解説

f の引数 a, b, c, d はそれぞれレジスタ $a0, $a1, $a2, $a3 に割り当てられているとする。
外側の func 呼び出しの第一引数を決定するために、まずは内側の func を呼び出す必要がある。内側の func を呼び出したあとは a, b を使わないので、 $a0, $a1 はスタックに退避する必要はない。
内側の func を呼び出した結果、後ほど c + d で使う $a2, $a3 の値が破壊される可能性があるので、これらはスタックに退避する必要がある。
- ただし、 c と d それぞれをスタックに退避するよりは、 c + d の結果を一つだけ callee-save レジスタの $s0 に格納するほうが効率が良いのでそうした。

2.35

問題

この関数において，末尾呼出し最適化を適用できるか．もし，適用できない場合は，その理由を説明せよ．適用できる場合は，最適化した場合としない場合とで，f内の実行される命令の数はどれだけ異なるか．

「この関数」は、2.34の f だと解釈する。

解答

適用できる。命令数は3個削減できる。

解説

末尾呼び出し最適化を適用したアセンブリを示す。

f:
    # caller-save レジスタの退避。
    # fのcallerへ戻る役割は外側のfuncに任せるので、 $ra を退避する必要がなくなった。
    addi $sp, -4
    sw   $s0, 0($sp)

    # $s0 = c + d
    add $s0, $a2, $a3

    # 内側の func 呼び出し。既に $a0 = a, $a1 = b と割当てられているので、引数セットは不要。
    jal func

    # 外側の func を呼び出す前に、この時点でスタックから callee-save レジスタをpop
    lw   $s0, 0($sp)
    addi $sp, 4

    # 外側の func へジャンプする。
    # ただし、ここに制御を戻す必要はなく、fのcallerへ一気に戻れば良いので、jal ではなく j を使う。
    addi $a0, $v0, 0  # $a0 = func(a, b)
    addi $a1, $s0, 0  # $a1 = c + d
    j    func

ポイントは以下。

$ra のスタックへの退避が不要になる。
jr 命令が不要になる。
末尾呼び出しをする前に忘れずにスタックを縮めておく。

2.24 では命令数が12個、ここでは命令数が9個である。

2.36

問題

問題2.34の関数fから戻る直前の，レジスタ$t5，$s3，$ra，$spの内容はどうなっているか．関数fについては内容が分かっているが，関数funcについては関数宣言しか分かっていないことに，留意せよ．

解答

$t5 : 不明。
$s3 : f の caller が f を呼び出した時点の $s3 の値。
$ra : f の caller が f を呼び出した命令の次の命令アドレス。
$sp : f の caller が f を呼び出した時点の $sp の値。

解説

$t5 : caller-save レジスタなので、 func 内でどのような値に書き換えられていても不思議ではない。
$s3 : callee-save レジスタなので、 func から返ってくる時点で必ず元の値に戻っている。 f 自体はそもそも書き換えていない（もし書き換えていたら元に戻してからreturnする義務がある）。
$ra : f の初めにスタックに退避したものを、 f から戻る前にpopしているので、 f の初め時点の値になっている。それは f のcallerが（おそらく jal 命令で）セットした、 f 呼び出しの直後の命令アドレス。
$sp : f から戻る直前にスタックを元通り縮めている。

2.37

問題

正および負の整数の10進数字列が含まれる１つのASCII数字列を，１つの整数に変換する，プログラムをMIPSアセンブリ言語で書け．数字0から9までの何らかの組み合わせが含まれる，終端がゼロで区切られた数字列のアドレスが，レジスタ$a0に保持されているものとする．その数字列に対応する整数値を算出して，結果をレジスタ$v0に収めよ．その数字列内に数字以外の文字が含まれていた場合には，レジスタ$v0に-1を収めて，プログラムを停止せよ．たとえば， $50_{10}$ と $52_{10}$ と $0_{10}$ の3バイトの数字列（終端がゼロで区切られた数字列「24」）をレジスタ$a0が指している場合，プログラムが終了したときに，レジスタ$v0には値 $24_{10}$ が収められているはずである．

解答

問題文で曖昧な箇所に以下の制約を設ける。

文字列の1文字目は、ASCIIの数字だけでなく、 '-' も許容される。一文字目が '-' であった場合には負の数として扱う。
結果は32ビット符号付き整数として扱う。
オーバーフローは考慮しない。
数字列が0文字である場合は結果は0とする。

    addi $t0, $a0, 0     # $t0 は文字をたどるポインタとして使う
    addi $t1, $zer0, 0   # $t1 は、先頭文字が '-' であるかのフラグ
    addi $t2, $zero, 0   # $t2 は結果を格納

    # 一文字目を取り出し、 '-' であるかを判定
    lbu  $t3, 0($t0)
    addi $t4, $zero, 45  # 45は '-' に対応
    bne  $t3, $t4, LOOP_START:

    # 一文字目が '-' であった場合は、 $t1 のフラグを立てて、一文字先に進める。
    addi $t1, $zero, 1
    addi $t0, $t0, 1    # ASCIIを一文字先に進めるのは、4バイトではなく1バイトの加算であることに注意。

LOOP_START:
    lbu  $t3, 0(t0)            # $t3 = *$t0

    slti $t4, $t3, 48          # $t4 = $t3 < '0'
    bne  $t4, $zero, LOOP_END  # goto LOOP_END if $t3 < '0'

    addi $t5, $zero, 58        # '9' == 58
    slti $t4, $t3, $t5         # $t4 = $t3 < '9' + 1
    beq  $t4, $zero, LOOP_END  # goto LOOP_END if $t3 >= '9' + 1

    # 新しい桁が見つかったので、 result = 10 * result する。
    # 10回足し算するよりは、
    # - r2 = result + result
    # - r4 = r2 + r2
    # - r8 = r4 + 4f
    # - r10 = r8 + r2
    # と計算したほうが早い。
    add  $t5, $t2, $t2  # $t5 = result + result == 2 * result
    add  $t4, $t5, $t5  # $t4 = $t5 + $t5 == 4 * result
    add  $t4, $t4, $t4  # $t4 = $t4 + $t4 == 8 * result
    add  $t2, $t4, $t5  # result = 8 * result + 2 * result

    # 新しい桁を足す
    addi $t3, $t3, -48  # $t3 = $t3 - '0'
    add  $t2, $t2, $t3  # result = result + $t3

    # 次の桁を指すように $t0 を1バイト進める
    addi $t0, $t0, 1

    j    LOOP_START
LOOP_END:

    # NULL文字以外のASCII数字以外が現れた場合は異常終了
    bne $t3, $zero, ERROR

    # 負数の場合は、最後に符号反転する
    beq  $t1, $zero, SUCCESS
    sub  $t2, $zero, $t2
    j    SUCCESS

ERROR:
    addi $v0, $zero, -1
    j    END

SUCCESS:
    addi $v0, $t2, 0

END:

解説

（筆者はいきなりアセンブリは厳しいので😭）まずはCで書いていく。

int v0;
char *a0;

char *p = a0;

int is_negative = 0;
int result = 0;

// 正負判定
if (*p == '-') {
  is_negative = 1;
  p++;
}

// 左の桁から順に足し合わせていく。
while ('0' <= *p && *p <= '9') {
  // 新しい桁が見つかったので、 result = 10 * result する。
  // 10回足し算するよりは、
  // - r2 = result + result
  // - r4 = r2 + r2
  // - r8 = r4 + 4f
  // - r10 = r8 + r2
  // と計算したほうが早い。
  int r2 = result + result;
  int r4 = r2 + r2;
  int r8 = r4 + r4;
  result = r8 + r2;

  result += *p - '0';  // 新しい桁を足す
  p++;
};

// NULL文字以外のASCII数字以外が現れた場合は異常終了
if (*p != 0) {
  v0 = -1;
  goto END;
}

// 負数の場合は、最後に符号反転する。
result = 0 - result;

v0 = result;

END:

あとはこれをMIPSアセンブリに変換して、解答を得る。
レジスタ割付は、 $t0: p, $t1: is_negative, $t2: result としている。

2.38

問題

下記のコードがある．

1 2	lbu $t0, 0($t1) sw $t0, 0($t2)

レジスタ$t1にはアドレス0x10000000が保持されており，レジスタ$t2にはアドレス0x10000010が保持されているものとする．MIPSアーキテクチャでは，ビッグ・エンディアン・アドレシング方式が取られていることに，留意すること．アドレス0x10000000に収められているデータ（16進数）は0x11223344であるとする．レジスタ$t2によって指されるアドレスには，どんな値が収められるか．

書籍には「アドレス0x10000010に収められているデータ（16進数）は0x11223344であるとする」とあるが、これは「アドレス0x10000000に収められているデータ（16進数）は0x11223344であるとする」の誤植と判断する（原著など参照の結果）。

解答

0x00000011

解説

命令列実行前のメモリレイアウトは下記。

アドレス	データ
0x1000001C	??
0x10000018	??
0x10000014	??
0x10000010	??
0x1000000C	0x44
0x10000008	0x33
0x10000004	0x22
0x10000000	0x11

lbu $t0, 0(0x10000000) を実行すると、 $t0 = 0x00000011 となる。
sw $t0, 0(0x10000010) を実行すると、メモリレイアウトは下記のようになる。

アドレス	データ
0x1000001C	0x11
0x10000018	0x00
0x10000014	0x00
0x10000010	0x00
0x1000000C	0x44
0x10000008	0x33
0x10000004	0x22
0x10000000	0x11

$t2 が指すアドレス 0x0000010 は、32ビットで考えると、値 0x00000011 が収められている。

2.39

問題

32ビットの定数 $0010\ 0000\ 0000\ 0001\ 0100\ 1001\ 0010\ 0100_2$ を作成して，その結果をレジスタ$t1に収める，MIPSのアセンブリ・コードを書け．

解答

1	addi $t1, $zero, 536955172

解説

特になし

2.40

問題

PCの現在の値が0x00000000であるならば，単一のジャンプ命令を使用して，問題2.39に示されているような，PCのアドレスを入手することができるか．

解答

できない。

解説

最も遠くにジャンプできる単一のジャンプ命令は j 。
2.24に記載の通り、ジャンプ先のアドレス（バイトアドレッシング）は

1 2	現在のPCの上位4ビット j命令のオペランド 00 31 28 27 2 1 0

である。

2.39 のアドレスの上位4ビットは 0010 で、これはPCの現在値の上位4ビットの 0000 と異なるため、単一ジャンプ命令では到達できない。

2.41

問題

PCの現在の値が0x00000600であるならば，単一の分岐命令を使用して，問題2.39に示されているような，PCのアドレスを入手することができるか．

解答

できない。

解説

2.40 と同じ理由につき不可。

2.42

問題

PCの現在の値が0x1FFFF000であるならば，単一の分岐命令を使用して，問題2.39に示されているような，PCのアドレスを入手することができるか．

解答

できない。

解説

2.40 と同じ理由につき不可。

2.43

問題

下記のCコードを実現する，MIPSのアセンブリ・コードを書け．

1
2
3

lock(lk);
shvar = max(shvar, x);
unlock(lk);

変数lkのアドレスは$a0に，変数shvarのアドレスは$a1に，変数xの値は$a2に，それぞれ収められているものとする．中核部分には，関数呼び出しを含んではならない．lock()操作を行うためには，ll/sc命令を使用する．unlock()操作は単なる通常の格納命令である．

書籍中の明らかなtypoを修正。”1k -> lk”, “shcar -> shvar”。

解答

解説に合わせたコメントを付ける。

    addi $t0, $zero, 1   # $t0 に、ロック変数にセットする 1 をセット。

AGAIN:
    ll  $t1, 0($a0)       # $t1 = lk
    beq $t1, $t0, AGAIN   # すでにロック変数が 1 だったら、他のプロセッサがロック中なので、最初に戻る
    sc  $t0, 0($a0)       # *($t1) = 1

    # scの成功フラグを確認し、失敗だったら最初に戻る
    beq $t0, $zero, AGAIN

    # ここからクリティカルセクション

    # $t0 = max(shvar, x)
    lw   $t0, 0($a1)           # $t0 = shvar
    slt  $t1, $t0, $a2         # $t1 = shvar < x
    beq  $t1, $zero, MAX_DONE  # shvar >= x ならば、 $a1 の指す値 (shvar) は書き換える必要なし
    sw   $a2, 0($a1)           # shvar = x

MAX_DONE:
    # クリティカルセクション終了。unlockをかける。
    sw   $zero, 0($a0)

解説

「shvar の値を書き換えるコードpathに突入できるプロセッサを1個に限定しよう」という ミューテックス ロックの考え方。
ロックが取れる条件は、「他のプロセッサに邪魔されず、 0 であるロック変数を 1 にできる」ことと設計する。
ロックを取りたいプロセッサは、 lock() 命令を通じて以下のことを行う:
- レジスタに、 ll 命令でロック変数の値をロードする。
- ロック変数の値が既に 1 であったら他のプロセッサがロック中ということ。最初に戻る。
- sc 命令で、ロック変数に 1 を書き込む。
  - sc 命令で指定したレジスタには成功フラグが格納されている。それが 0 だったら、「他のプロセッサも同時期にロックを取りたがっていて、そちらのほうが早く sc に成功した」と判断できる（これ以外にも割り込みなどの理由はあり得るが、とにかくロックは失敗したと判断すれば良い）。
  - 成功フラグが 1 だったら、このプロセッサがロックに成功した。ここから先はクリティカルセクション。
ロックを取れたプロセッサは、クリティカルセクションでやるべき処理実行。
ロックを取れたプロセッサは、 unlock() 命令を通じて以下のことを行う。
- ロック変数に 0 をストアする。これにより、他のプロセッサがロックを取ることを許す（クリティカルセクションを終了する）。

2.44

問題

問題2.43と同様の処理を行え．ただし，この問題では，lock()およびunlock()を使用しないで，ll/scを使用して，変数shvarの不可分な更新を直接行うものとする．この問題では，変数lkがないことに注意．

解答

AGAIN:
    ll  $t0, 0($a0)  # $t0 = shvar

    # $t0 = max(shvar, x)
    slt  $t1, $t0, $a2         # $t1 = shvar < x
    beq  $t1, $zero, MAX_DONE  # shvar >= x ならば、 $t0 は shvar のまま書き換える必要なし
    addi $t0, $a2, 0           # $t0 = x

MAX_DONE:
    sc   $t0, 0($a0)           # try: *($a0) = max(shvar, x)
    beq  $t0, $zero, AGAIN     # sc までに $a0 の指す値が別プロセッサに書き換えられていたら、AGAINに処理を戻す

解説

「shvar をまず書き換えようとしてみて、書き換える前に他のプロセッサからの更新を検知したら書き換えをやめる」という 楽観ロック の考え方。
ll, sc 命令で対象にする $a0 が指すアドレスには、 shvar の値を格納する。
ll の時点では、アセンブリプログラマは特にケアすることはない。ハードウェア側で「プロセッサXがこのメモリアドレスを予約したぞ」ということが記録される。
- プロセッサXが sc を行う前に、別のプロセッサYが同じメモリアドレスに対して変更を加えた場合、上記の「予約」マークは消される
- プロセッサXが sc を行う際に「予約」マークを確認し、まだ残っていた場合にのみメモリ更新を成功させる。

2.45

問題

問題2.43で書いたコードを例に使用して，2つのプロセッサが同時にその中核部分の実行を開始したときには，何が起こるかを説明せよ．だたし，どちらのプロセッサもサイクル当たり1命令だけを実行するものとする．

解答

2つのプロセッサが全く同時に同じ sc 命令を成功実行することはできない（同一メモリアドレスへの書き込み時点で処理が直列化される）ことは仮定する。

また、第3のプロセッサがロックを取得していることもないとする。

プロセッサAとプロセッサBが、2.43のコードの1~4行目( addi ~ sc )までを、全く同時刻の4サイクルで、実行したとする。
sc 実行直前では、両方のプロセッサのレジスタは、 $t0 == 1, $t1 == 0 となっている。
sc 実行開始は同時刻でも、メモリ書き込みで直列化されるので、この時点で時間的な前後関係が出てくる。最初にメモリへ書き込みにいけたプロセッサをAとする。
sc 実行直後、プロセッサAのレジスタは $t0 == 1 (更新成功)、プロセッサBのレジスタは t0 == 0 (更新失敗) となる。
したがって、次の beq 命令時実行した結果、プロセッサAのPCはその次の lw 命令に移り、プロセッサBのPCは再び ll に戻る。
プロセッサAがunlockのコード、すなわち sw $zero, 0($a0) を完了させるまで、プロセッサBは最初の3行の命令を繰り返すことになる。

解説

特になし

2.46

算術命令のCPIが1，ロード／ストア命令のCPIが10，分岐命令のCPIが3である，プロセッサがあるとする．このプロセッサ上で実行されるあるプログラムの命令数の内訳が，算術命令が５億，ロード／ストア命令が３億，分岐命令が１億であるとする．

2.46.1

問題

新しいもっと強力な算術命令が命令セットに追加された，と仮定する．それらの新しくて強力な算術命令を使用すると，プログラムを実行するのに必要な算術命令の数を，平均して25%削減できる．他方，そのコストとして，クロック・サイクル時間が10%長くなる．これは良い設計案であるか．その理由はなぜか．

解答

（本来は、「あるプログラム」の実行時間の変化だけを見て設計案の良し悪しは語れないが、）「あるプログラム」の実行クロック数の変化を考える。

もとのプロセッサでは、 $1 \times 5億 + 10 \times 3億 + 3 \times 1億 = 38億$ クロックを要する。新しいプロセッサでは、 $1.1 \times (0.75 \times 5億) + 11 \times 3億 + 3.3 \times 1億 = 40.425億$ クロックを要する。

実行クロック数が伸びているので、良い設計案とは言えない。

解説

特になし。

2.46.2

問題

算術命令の性能を倍増させる方法を見つけた，と仮定する．プロセッサ全体では，どれだけ速度が向上するか．算術命令の性能を10倍向上させる方法を見つけた場合は，どうなるか．

解答

ここでも「あるプログラム」の実行クロック数の変化で速度向上を測る。

算術命令の性能が倍増とは、算術命令のCPIが半減したと考えられるので、

\[
\frac{1 \times 5億 + 10 \times 3億 + 3 \times 1億}{0.5 \times 5億 + 10 \times 3億 + 3 \times 1億} = \frac{38億}{35.5億} = 1.07 倍
\]

同様に、算術命令の性能が10倍向上したときは、

\[
\frac{1 \times 5億 + 10 \times 3億 + 3 \times 1億}{0.1 \times 5億 + 10 \times 3億 + 3 \times 1億} = \frac{38億}{35.5億} = 1.13 倍
\]

解説

「あるプログラム」の実行時間において支配的なのはロード・ストア命令の時間なので、算術命令がいかに早くなろうと、プログラム全体での性能向上はたかが知れている。

2.47

あるプログラムを実行したときの命令数の内訳が，算術命令が70%，ロード／ストア命令が10%，分岐命令が20%であるとする．

2.47.1

問題

上記のプログラムを実行するプロセッサの命令当たりのサイクル数が，算術命令の場合は2，ロード／ストア命令の場合は6，分岐命令の場合は3であるとする．平均CPIはいくつか．

解答

2.6

解説

$0.7 \times 2 + 0.1 \times 6 + 0.2 \times 3 = 2.6$

2.47.2

問題

ロード／ストア命令と分岐命令はまったく改善されないとして，性能を25%向上させるためには，算術命令の命令当たりのサイクル数は平均いくつであるべきか．

解答

1.07

解説

\[
\begin{eqnarray}
0.7 \times CPI_A + 0.1 \times 6 + 0.2 \times 3 &=& 0.75 \times 2.6 \\
CPI_A &=& 1.07
\end{eqnarray}
\]

2.47.3

問題

ロード／ストア命令と分岐命令はまったく改善されないとして，性能を50%向上させるためには，算術命令の命令当たりのサイクル数は平均いくつであるべきか．

解答

0.142

解説

\[
\begin{eqnarray}
0.7 \times CPI_A + 0.1 \times 6 + 0.2 \times 3 &=& 0.5 \times 2.6 \\
CPI_A &=& 0.142
\end{eqnarray}
\]