【阅读笔记】深入理解计算机系统

计算机系统漫游

信息的处理及表示

2.1 信息存储

练习 2.2

$n$	$2^n$ （十进制）	$2^n$ （十六进制）
9	512	0x200
19	524288	0x80000
14	16384	0x4000
17 16	131072 65536	0x10000
17	131072	0x10000 0x20000
5	32	0x10
11	2048	0x800

练习 2.3

十进制	二进制	十六进制
0	0000 0000	0x00
167	1010 0111	0xA7
62	0100 0011	0x43
188	1011 1100	0xBC
55	0011 0111	0x37
	1000 1000
	1111 0011
52 5 $\times$ 16 $+$ 2 $=$ 82	0101 0010	0x52
		0xAC
		0xE7

练习 2.4

十六进制加减法，不得使用进制转换。

A. 0x503c + 0x8 = 0x5044

B. 0x503c - 0x40 = 0x499c 0x503c - 0x40 = 0x4ffc

C. 0x503c + 64 = 0x507c

D. 0x50ea - 0x503c = 0xAD 0x50ea - 0x503c = 0xAE

寻址和字节顺序

练习题 2.5

int val = 0x87654321

	小端法	大端法
A	21	87
B	21 43	87 65
C	21 43 65	87 65 43
val	21 43 65 87	87 65 43 21

练习题 2.6

0x00359141 = 0000 0000 0011 0101 1001 0001 0100 0001

0x4A564504 = 0100 1010 0101 0110 0100 0101 0000 0100

0   0   3   5   9   1   4   1
00000000001101011001000101000001
           *********************
  01001010010101100100010100000100
     4   A   5   6   4   5   0   4

练习题 2.7

"abcdef" -> (ASCII) 65 66 67 68 69 70
->	(printf) 61 62 63 64 65 66

练习题 2.8

运算	结果
a	01101001
b	01010101
~a	10010110
~b	10101010
a & b	01000001
`a	b`	01111101
a ^ b	00111100

练习题 2.10

步骤	*x	*y
	$a$	$b$
	$a$	$a \oplus b$
	$b$	$a \oplus b$
		$a$

练习题 2.11

A. first == last == k

B. inplace_swap(&a[k], &a[k]); 第一行等价于 a[k] = a[k] ^ a[k];

C. void inplace_swap(int* x, int* y); 第一行加上 if(*x == *y) return;

或 line 4 改为 first < last

练习题 2.12

A. x & 0xFF

B. (~x & ~0xFF) | (x & 0xFF)

C. x | 0xFF

练习题 2.13

int bis(int x, int m);	//x | m;
int bic(int x, int m);	//x & ~m;
                        //~x = 1 & ~m
int bool_or(int x, int y)
{
    int result = bis(x, y);
    return result;
}

int boo_xor(int x, int y)	//x xor y = x & ~y | ~x & y;
{
    int result = bis(bic(x, y), bic(y, x));
    return result;
}

练习题 2.15

int bool_equal(int x, int y)
{
    return ~((x & ~y) | (~x & y));
}

C 语言中的移位运算

• 左移：

  x << n 表示二进制位向左移动 $n$ 位，低位补 $0$ 。

• 右移：

  • 逻辑右移：x >> n 表示二进制位向左移动 $n$ 位，高位补 $0$ 。
  • 算术右移：x >> n 表示二进制位向左移动 $n$ 位，若 $x$ 最高位是 $0$ ，则高位补 $0$ ；若 $x$ 最高位是 $1$ ，则高位补 $1$ ；。

练习 2.16

x	x	x<<3	x<<3	x>>2（逻辑）	x>>2（逻辑）	x>>2（算术）	x>>2（算术）
十六进制	二进制	二进制	十六进制	二进制	十六进制	二进制	十六进制
0xC3	1100 0011	0001 1000		0011 0000		1111 0000
0x75	0111 0101	1010 1000		0001 1101		1101 1101`` 0001 1101
0x87	1000 0111	0011 1000		0010 0001		1110 0001
0x66	0110 0110	0011 0000		0001 1001		0001 1001

2.2 整数表示

无符号数编码

对向量 $\overrightarrow{x} = [x_{w-1}, x_{w-2}, \dots, x_0]$

$$\tag{2.1} B2U_w(\overrightarrow{x}) \doteq \displaystyle\sum_{i=0}^{w-1} x_i 2^i$$

补码编码

对向量 $\overrightarrow{x} = [x_{w-1}, x_{w-2}, \dots, x_0]$

$$\tag{2.3} B2T_w( \overrightarrow{x} ) \doteq x_{w-1}2^{w-1} + \displaystyle\sum_{i=0}^{w-2} x_i 2^i$$

练习题 2.17

$\overrightarrow(x)$		$B2U_4(\overrightarrow{x}))$	$B2T_4(\overrightarrow{x})$
十六进制	二进制
0xE	$1110$	$2^3 + 2^2 + 2^1 = 14$	$-2^3 + 2^2 + 2^1 = -2$
0x0	$0000$	$0$	$0$
0x5	$0101$	$4+1=5$	$4+1=5$
0x8	$1000$	$8$	$-8$
0xD	$1101$	$8 + 4 + 1 = 13$	$-8 + 4 + 1 = -3$
0xF	$1111$	$8 + 4 + 2 + 1 = 15$	$-8 + 4 + 2 + 1 = -1$

练习题 2.18

十六进制	二进制	补码
0x2e0	$0000\ 0010\ 1110\ 0000$	$2^{10} + 2^8 + 2^7 + 2^6 $2^{9} + 2^7 + 2^6 + 2^5 = 736$
-0x58	$0000\ 0000\ 0101\ 1000$	2^7 + 2^5 + 2^4<br>$-(2^6 + 2^4 + 2^3) = -40$
0x28
0x30
0x78
0x88
0x1f8
0x8
0xc0
0x48

有符号数与无符号数之间的转换

$$T2U_w(x) \doteq B2U_w(T2B_w(x))$$

练习题 2.19

$x$	$T2U_4(x)$
$-8$	$8$
$-3$	$13$
$-2$	$14$
$-1$	$15$
$0$	$0$
$5$	$5$

$\forall x, TMin_w \le x \le TMax_w$

$$\tag{2.5} T2U_w(x) = \begin{cases} x + 2^w &\text{if } x < 0 \\ x &\text{if } x \ge 0 \end{cases}$$

$\forall u, 0 \le u \le UMax_w$

$$\tag{2.7} U2T_w(x) = \begin{cases} u - 2^w &\text{if } u > UMax_w \\ u &\text{if } u \le UMax_w \end{cases}$$

练习题 2.21

表达式	类型	求值
-2147483647-1 == 2147483648U<br>``0x8000 == 0x8000	无符号	0 1
	有符号	1
	无符号	0
	有符号	1
	无符号	1

扩展一个数字的位表示

无符号数转换为一个更大的数据类型：零扩展

补码数数转换为一个更大的数据类型：高位使用 $x_{w-1}$ 填充

证明（数学归纳法）：

$$B2T_{w+1}([x_{w-1}, x_{w-1}, \dots, w_1, w_0]) = B2T_w([x_{w-1}, x_{w-2}, \dots, w_1, w_0])$$

short x = -12345;
unsigned y = x;	// -> y = (unsigned) (int) x;

练习题 2.23

A.

w	fun1(w)	fun2(w)
0x00000076	0x00000076	0X00000076
0x87654321	0x00000021	0x00000021
0x000000C9	0x000000C9	0xFFFFFFC9
0xEDCBA987	0x00000087	0xFFFFFF87

B.

fun1 实现将 32 位无符号 int 转换为 8 位无符号 int ，即无符号数对 $8$ 取模。

fun2 实现将 32 位有符号 int 转换为 8 位有符号 int ，有符号数的二进制表示取低 $8$ 位，然后进行有符号扩展。

截断数字

• 无符号数截断：

  令向量 $\overrightarrow{x} = [x_{w-1}, x_{w-2}, \dots, x_0]$ ， $\overrightarrow{x}' = [x_{k-1}, \dots, x_0]$ 是将 $\overrightarrow{x}$ 截断 $k$ 位的结果。令 $x = B2T_w(\overrightarrow{x})$ ， $x' = B2T_k(\overrightarrow{x}')$ ，则 $x' = x \ mod \ 2^k$

  $$\tag{2.9} B2T_k([x_{k-1}, x_{k-2}, \dots, x_0]) = B2U_w([x_{w-1}, x_{w-2}, \dots, x_0]) \ mod \ 2^k$$

• 有符号数截断：

  $$\tag{2.10} B2T_k([x_{k-1}, x_{k-2}, \dots, x_0]) = U2T_k(B2U_w([x_{w-1}, x_{w-2}, \dots, x_0]) \ mod \ 2^k)$$

  其中， $B2U_w([x_{w-1}, x_{w-2}, \dots, x_0]) \ mod \ 2^k$ 先将有符号数转换成无符号数并用无符号方法截断，然后把无符号数转换成有符号数。

练习题 2.24

十六进制		二进制		无符号		补码
原始值	截断值	原始值	截断值	原始值	截断值	原始值	截断值
0	0	0000	000	0	0	0	0
2	2	0010	010	2	2	2	2
9	1	1001	001	9	1	-7	1
B	3	1011	011	11	3	-5	3
F	7	1111	111	15	7	-1	-1

都先将二进制表示转换为无符号数，然后对 $2^k$ 取模截断，所得结果视作 $k$ 位有/无符号数。

练习题 2.25

传入的 length 为 $0$ 时，length - 1 为无符号数，值为 ~0x0 ，比较 i 与 length - 1 的大小时，i 会被转换为无符号数将其比较，设 length 是一个 k 位无符号数，则 i 若视作无符号数，表示范围为 $[0, 2^k - 1]$ 或 $[0, 2^32 - 1]$ ，总之 a[i] 将出现越界访问，导致内存错误。

解决方法是第 $4$ 行修改为 for(int i=0; i <= (int)length - 1; i++)

练习 2.26

A.

s 比 t 短时，结果不正确。

B.

在 A. 的条件下， strlen(s) - strlen(t) 仍是一个无符号正整数 ，右边的 0 将被视作无符号数，返回真。

int strLonger(char *s, char *t)
{
        return strlen(s) > strlen(t);
}

2.3 整数的运算

练习 2.27

int uadd_ok(unsigned x, unsigned y)
{
        return x + y >= x;
}

练习题 2.28

$x$		$-_4^ux$
十六进制	十进制	十进制	十六进制
0	0	16 0	0
5	5	11	B
8	8	8	8
D	13	13 3	D
F	15	1	1

练习题 2.29

$x$	$y$	$x+y$	$x + _t^5y$	情况
		$[100101]$<br>$-27$	$[00101]$	情况3 1
		$[110000]$<br>$-16$	$[10000]$	情况 2
		$[011111]$ $[111111]$<br>$31$ $-1$	$[11111]$	情况1 2
		$[000111]$<br>$7$	$[00111]$	情况 3
		$[010000]$<br>$16$	$[10000]$	情况 4

练习题 2.30

int tadd_ok(int x, int y)
{
    return !((x > 0 && y > 0 && x + y < 0) || (x < 0 && y < 0 && x + y > 0))
}

练习题 2.31

假设发生正溢出，则 sum = x + y - 2^k ， sum - x = y - 2^k ，在模 $k$ 意义下就是 $y$ ，对 $x$ 同理，所以正溢出时仍然返回真；同理，负溢出也返回真。

练习题 2.32

用 tadd_ok(int x, int y) 来判断 $x - y$ 是否溢出：

int tsub_ok(int x, int y)
{
	return tadd_ok(x, -y);
}

这种写法是在假设：对任意 $x - ^t_wy$ ，若 tsub_ok(x, y) 判断没有溢出，即 $x + ^t_w(-y)$ 由 tadd_ok(x, -y) 判断没有溢出，这要求 $-^t_wy = -y$ ，但其实不然。

$y = TMin_w = -2^{w-1}$ 时， $-^t_wy = TMin_w = y$ ，若 $x < 0$ ，则 $x - y = x + 2^{w-1} \ge 0$ ，没有发生溢出，但是 $x + TMin_w = x - 2^{w-1} < 2^{w-1}$ ，将被 tadd_ok() 判断为负溢出；若 $x > 0$ ， $x - y = x + 2^{w-1} > 2^{w-1} - 1$ ，发生正溢出，而 $x + TMin_w = x - 2^{w-1} > 2^{w-1}$ ，被 tadd_ok() 判断为没有溢出。

解决方法：

int tsub_ok(int x, int y)
{
    if(y == -y) return x < 0;
	else return tadd_ok(x, -y);
}

练习题 2.33

$x$		$-^t_4x$
十六进制	十进制	十进制	十六进制
0	0	0	0
5	5	-5	B
8	8 -8	8 -8	8
D	-3	3	3
F	-1	1	1

无符号乘法

对满足 $0 \le x,\ y \le UMax_w$ 的 $x$ 和 $y$ ：

$$\tag{2.16} x * ^u_wy = (x \cdot y)\ mod\ 2^w$$

有符号乘法

对满足 $TMin_w \le x,\ y \le TMax_w$ 的 $x$ 和 $y$ ：

$$\tag{2.17} x * ^t_wy = U2T_w ((x \cdot y)\ mod\ 2^w )$$

练习题 2.34

模式	$x$	$y$	$x \cdot y$	截断
	$[100]$	$[101]$
无符号	$4$	$5$	$20$<br>$[010100]$	$[100]$
有符号	$-4$	$-3$	$12$<br>$[001100]$	$[100]$
	$[010]$	$[111]$
有符号	$2$	$7$	$14$<br>$[001110]$	$[110]$
无符号	$2$	$-1$	$-2$<br>$111110$	$[110]$
	$[110]$	$[110]$
有符号	$6$	$6$	$36$<br>$[100100]$	$[100]$
无符号	$-2$	$-2$	$4$<br>$[000100]$	$[100]$

练习题 2.35

1. 由有符号数乘法的定义，设 $z = x \cdot y$ ， $T2B_{w}(z\ mod\ 2^w) = [x_{w-1}, \dots , x_0]$ ，则 $p = (z\ mod\ 2^w) - x_{w-1} 2^{w}$ ，所以 $p + x_{w-1} 2^{w} = z\ mod\ 2^w$ ，即 $x \cdot y = z = k 2^w + p + x_{w-1}2^w = p + t2^w$ 。

若计算溢出，则 $k \neq 0$ ，又 $x_{w-1} \in \{0, 1\}$ ，故 $t = k + x_{w-1} \neq 0$

若 $t = k + w_{w-1} \neq 0$ ，由于 $k \ge 0$ ，且 $x_{w-1} \in \{0, 1\}$ ，有 $k \neq 0$ ，所以 $z \ge 2^w$ ，计算溢出。

2. 若 $p \le x$ ，则令 $q = 1$ ， $\exist\ r = x - p , \ s.t. p = xp + r$ .

   若 $p > x$ ，则令 $r = p\ mod\ x$ ， $\exist\ r = x - p , \ s.t. p = xp + r$ .

3. 若 $q = y$ ，则由 $|r| < |x|$ ，且 $|x| < 2^w$ ，所以 $t = 0$ ，$p = x \cdot y$ ，$r = 0$ 。

   若 $r = t = 0$ ，则 $p = x \cdot y$ ，易得 $q = y$ 。

综上，若没有溢出，则 $t = 0$ ，此时 $p = x \cdot y$ ，!x || p / x == y 为真。

练习 2.36

int tmult_ok(int x, int y)
{
    int64_t p = x * y;
    return p == (int) p;
}

练习 2.37

使用 uint64_t 保存 ele_cnt * ele_size 的结果，防止溢出导致分配的空间过小，进而防止循环复制时超出缓冲区界限。

A. 这个改动没有帮助，因为 malloc 只能接收 int32_t 作为参数，仍然可能溢出。

B.

if(asize != (unit32_t)asize) return NULL;

乘以常数

$$x<<k = x \cdot 2^k$$

将 $K$ 分解为二进制序列 $[x_{w-1}, \dots, x_0]$ ，则有：

$$x \cdot K = x * \displaystyle\sum_{i=0}^{w-1}x_{i} \cdot 2^i = \displaystyle\sum_{i=0}^{w-1}x<<(x_i \cdot i)$$

练习题 2.38

可以计算 $a \cdot 2^k$ ， $a \cdot (2^k + 1)$ 等，即 $1, 2, 3, 4, 5, 8, 9$

练习题 2.39

$n$ 为最高位时， x<<(n + 1) = $x \cdot (2^{n + 1}) = x \cdot 2^{n} \cdot x$ $n+1 = w-1+1 = w$ ， $x<<(n+1) = x<<w$ ，溢出截断后为 $x$ $0$ 本身。故改为 x - (x << m) - (x << m)

练习题 2.40

$K$	移位	加法/减法	表达式
			(x<<3) - (x<<1)
			(x<<5) - x
			(x<<1) - (x<<3)
			(x<<6) - (x<<3) - x

练习题 2.41

视加减法、移位计算的开销决定，选择综合开销最小的那种。

除以 2 的幂

若 $x$ 是无符号数：

$$x>>k = \lfloor x / 2^k \rfloor$$

此处使用逻辑右移。

若 $x$ 是有符号数且大于 $0$ ，操作与无符号数相同，但使用算术右移。

若 $x$ 是有符号数且小于 $0$ ，除以 $2^k$ 时，要先加上偏置位 $2^k-1$，再算术右移：

$$(x+(1<<k)-1)>>k = \lceil x/2^k \rceil$$

练习题 2.42

int div16(int x)
{
    return !(x & (1 << 31)) * (x >> 4) + (x & (1 << 31)) * ((x + (1 << 4) - 1) >> 4);
}

练习题 2.43

x * M = x * (2^5 - 1)

y = (y < 0 ? (y + (1 << 3) - 1) : y) >> 3 = y / 3

所以 M = 31, N = 2^3 = 8

练习 2.44

A. 若 x > 0 == true ，则为 true

若 x > 0 == false ，则 x <= 0 ，即 ((x - 1) < 0) == true

B. 若 (x & 7) ==7 ，则 x 最低三位是 111 ，x 是 $32$ 位 int ，x << 29 的最高三位是 111 ，故其小于 $0$

C. $x \cdot x$ 的最高位恒为 $0$ ，因此 x * x >= 0

D. 若 x >= 0 ，则根据有符号数的逆元定义，-x <= 0

E. 若 $x = TMin_w$ ，$-x = TMin_w < 0$ ，故为假

F. $x = y = 2^{31} - 1$ 时，不成立

G. $?$

2.4 浮点数

二进制小数

练习题 2.45

小数值	二进制	十进制
$\frac 1 8$	$0.001$
$\frac 3 4$
$\frac {43} {16}$	$10.1011$	$2.6875$
	$1.001$
$\frac {63} 8$	$101.111$	$5.875$
		$3.1875$

练习题 2.46

A. 是 0.000000000000000000000[0011]

B. $\frac 3 {15 \cdot 2^{21}}$

C. $0.0171661377s$

D. $34.3322753906m$

浮点数的表示

$IEEE$ 用 $V = (-1)^s \times M \times 2^E$ 表示一个浮点数。

• $s$ 编码符号位， $0$ 为正， $1$ 为负。
• $k$ 位阶码，表示一个二进制整数 $e = e_{k-1} \dots e_0$ ，用来编码 $E$
• $n$ 位小数字段，表示一个二进制小数 $f = \overline{0.f_{n-1} \dots f_0}$ ，用来编码 $M$

情况 1：规格化的值

• $e$ 的所有位不全为 $1$ 或 $0$
• $E = e - Bias$ ， 其中 $Bias = 2^{k-1} - 1$ ，使得双精度指数范围为 $-1022 \backsim 1023$ ，单精度为 $-126 \backsim 127$
• $M = 1+ f = \overline{1.f\_{n-1} \dots f_0}$

情况 2：非规格化的值

• 阶码字段 $e$ 所有位全为 $0$ ，即 $e = 0$

• $E = 1 - Bias$
• $M = f = \overline{0.f_{n-1} \dots f_0}$

$M = f = 0$ 时根据 $s$ 的取值决定表示 $+0.0$ 或 $-0.0$ ，二者有时候是不同的。

$M = f \neq 0$ 时用来表示非常接近 $0$ 的数。

情况 3：特殊值

• 阶码字段 $e$ 所有位全为 $1$

• 若 $f = 0$ ，表示 $+\infin$ 或 $-\infin$
• $f \neq 0$ 表示 $NaN$ （Not a number）

练习题 2.47

位	$e$	$E$	$2^E$	$f$	$M$	$2^E \times M$	$V$	十进制
0 00 00	$0$	$-1$	$\frac 1 2$	$\frac 0 4$	$\frac 0 4$	$\frac 0 8$	$0$	$0$
0 00 01	$0$	$-1$	$\frac 1 2$	$\frac 1 4$	$\frac 1 4$	$\frac 1 8$	$\frac 1 8$	$0.125$
0 00 10	$0$	$-1$	$\frac 1 2$	$\frac 2 4$	$\frac 2 4$	$\frac 2 8$	$\frac 1 4$	$0.25$
0 00 11	$0$	$-1$	$\frac 1 2$	$\frac 3 4$	$\frac 3 4$	$\frac 3 8$	$\frac 3 8$	$0.375$
0 01 00	$1$	$0$	$1$	$\frac 0 4$	$\frac 4 4$	$\frac 4 4$	$1$	$1$
0 01 01	$1$	$0$	$1$	$\frac 1 4$	$\frac 5 4$	$\frac 5 4$	$\frac 5 4$	$1.25$
0 01 10	$1$	$0$	$1$	$\frac 2 4$	$\frac 6 4$	$\frac 6 4$	$\frac 3 2$	$1.5$
0 01 11	$1$	$0$	$1$	$\frac 3 4$	$\frac 7 4$	$\frac 7 4$	$\frac 7 4$	$1.75$
0 10 00	$2$	$1$	$2$	$\frac 0 4$	$\frac 4 4$	$\frac 8 2$	$4$	$4$
0 10 01	$2$	$1$	$2$	$\frac 1 4$	$\frac 5 4$	$\frac {10} 2$	$5$	$5$
0 10 10	$2$	$1$	$2$	$\frac 2 4$	$\frac 6 4$	$\frac {12} 2$	$6$	$6$
0 10 11	$2$	$1$	$2$	$\frac 3 4$	$\frac 7 4$	$\frac {14} 2$	$7$	$7$
0 11 00	$-$	$-$	$-$	$-$	$-$	$-$	$-$	$-$
0 11 01	$-$	$-$	$-$	$-$	$-$	$-$	$-$	$-$
0 11 10	$-$	$-$	$-$	$-$	$-$	$-$	$-$	$-$
0 11 11	$-$	$-$	$-$	$-$	$-$	$-$	$-$	$-$

练习题 2.49

A. $2^{n+1} + 1$

B. $2^{24} + 1$

舍入

练习题 2.50

A. $10.0_2$

B. $10.0_2$ $10.1_2$

C. $11.00_2$ $11.0_2$

D. $11.0_2$

练习题 2.51

A. $0.00011001100110011001100[1100]_2$ 精确到小数点右边 $23$ 位，使用舍入到偶数方法得 $0.0.00011001100110011001101$

B. $x' - 0.1 = 0.00000000000000000000000[0011] = 0.1 \cdot 2^{-22}$

C. $60 \cdot 60 \cdot 100 \cdot 10 0.2 \cdot 2^{-22} = 0.086$

D. $0.086 \cdot 2000 = 171.67$

练习题 2.52

格式 A		格式 B
位	值	位	值
011 0000	$1$	0111 000	$1$
101 1110	$2^{2} \times 1.1110_2$	1001 111	$2^2 \times 1.111_2$
010 1001	$2^{-1} \times 1.1001_2$	0110 100	$2^{-1} \times 1.100_2$
110 1111	$2^3 \times 1.1111_2$	1011 000	$2^{4} \times 1.000_2$
000 0001	$2^{-2} \times 0.0001$	0001 000	$2^{-6} \times 1.000_2$

练习题 2.53

#define POS_INFINITY 0x7FF0000000000000
#define NEG_INFINITY 0xFFF0000000000000
#define NEG_ZERO 0x8000000000000000

练习题 2.54

A. int 转 double 没有精度丢失，再转回来也没事

B. x = 0x7fffffff 时，转成 float 会舍入，精度下降，甚至比 x 大的值，再转回 int 会溢出

C. double 转 float 精度会丢失

D. float 转 double 精度不会丢失

E. 浮点数取加法逆元只需要把符号位取反即可，取两次加法逆元符号不变

F. 两侧都会变成 double/double ，且 int 转 double 精度不丢失，所以值相等

G. 浮点数取平方，一定为正数，且大于等于 $0$

H. 若 f + d 溢出 double 最大规格化数值成 inf ，则 f + d - f 为 inf

第 3 章 程序的机器级表示

3.4 访问信息

x86_64 寄存器：

格式为 $Immm(r_b, r_i, s)$ 的操作数格式表示的操作数为 $M[Imm + R[r_b] + R[r_i] \cdot s]$

练习题 3.1

操作数	值
%rax	0x100
0x104	0xAB
0x108	0x13
(%rax)	0xFF
4(%rax)	0xAB
9(%rax, %rdx)	0x11
260(%rcx, %rdx)	0x13
0xFC(, %rcx, 4)	0xFF
(%rax, %rdx, 4)	0x11

练习题 3.2

movl %eax, (%rsp)

movw (%rax), %dx

movb $0xFF, %bl

movb (%rsp, %rdx, 4), %dl

movq (%rdx), %rax

movw %dx, (%rax)

练习题 3.3

movb $0xF, (%ebx) ：%ebx 不可以作为内存引用

movl %rax, (%rsp) ：%rax 是四字，应该用 movq

movw (%rax), 4(%rsp) ：两个操作数都指向内存

movb %al, %sl ：似乎不存在 %sl 寄存器

movq %rax, $0x123 ：目的操作数不能是立即数

movl %eax, %rdx：目的寄存器大小应该和 %rax 保持一致，即 edx

movb %si, 8(%rbp)：%si 是双字，应该用 movw

练习题 3.4

movzbl (%rdi), %eax

movb %eax, (%rsi)

movzbl (%rdi), %eax movsbl (%rdi), %eax

movb %eax, (%rsi)

movzbq (%rdi), %rax

mob %rax, (%rsi)

movl (%rdi), %eax

movb %al, (%rsi)

movl (%rdi), %eax

movb %al, (%rsi)

movzbw (%rdi), %ax

movw %ax, (%rsi)

练习题 3.5

void decode1(long *xp, long *yp, long *zp)
{
    long *ap = *xp;
    long *bp = *yp;
    long *cp = *zp;
    yp = ap;
    zp = bp;
    xp = cp;
}

练习题 3.6

6 + (x mod 2^16)

x + y

x + 4y

7 + 9x

0xA + 4y

9 + x + 2y

练习题 3.7

5x + 2y + 8z

练习题 3.8

0x100 0x11

0x108 0xA8

0x118 0x110

0x110 0x14

%rcx 0x0

%rax 0xFD

练习题 3.9

movl %rdi, %rax

salq $4, %rax

movb (%rsi), %cl movq (%esi), %rcx

sarq %cl, %rax

练习题 3.10

long t1 = x | y;
long t2 = t1 >> 3;
long t3 = ~t2;
long t4 = z - t3;

练习题 3.11

A. 将 %rdx 所有位置 0

B. movq $0, %rdx

C.

练习题 3.12

urerndiv:
	movq %rdx, %r8
    movq $rdi, %rax
    movq $0, %rdx
    divq %rsi
    movq %rax, (%r8)
    movq %rad, (%rcx)
    ret

练习题 3.13

A. int <

B. short >=

C. unsigned char <=

D. long long !=

练习题 3.14

A. long long >=

B. short/unsigned short ==

C. unsign char <=

D. int !=

练习题 3.15

A. 0x4003fe

B. 0x400521

C. 0x400543 0x400545

D. 0x400560

练习题 3.16

void cond_goto(long a, long *p)
{
    if(!p) goto p_nq_zero;
    if(!(a > *p)) goto a_g_p;
    *p = a;
p_nq_zero:
a_g_p:
    return;
}

该判断条件由两个子条件构成，任意一个条件不满足函数都将返回，因此需要两个分支语句。

练习题 3.17

long gotodiff_se2(long x, long y)
{
    long result;
    if(x >= y) goto _true;
    else goto _false;
_true:
    lt_cnt++;
    result = y - x;
    goto: end_if
_false:
    ge_cnt++;
    result = x - y;
end_if:
    return result;
}

选用本例中的方法代码更加清晰易读，但是可能产生额外的转跳。

练习题 3.18

long test(long x, long y, long z)
{
    long val = x + y + z;
    if(x < -3)
    {
        if(y < z)
            val = x * y;
        else
            val = y * z;
    }
    else if(x > 2)
        val = x * z;
    return val;
}

练习题 3.19

A. $T_{mp} = 2 \times (T_{ran} - T_{ok}) , \ T_{ok} = 16, \ T_{ran} = 31 \to T_{mp} = 30$

B. $30 + 16 = 46$

练习题 3.20

long arith(long x)
{
    long v = x + 7;
    if(x) v = x;
    v >>= 3;
    return v;
}
// =>
long arith(long x)
{
	return (x < 0 ? x + 7 : x) / 8;
}

OP 表示除法 /

练习题 3.21

long test(long x, long y)
{
    long val = 8x;
	long val2 = y - x;
    long val3 = x & y;
    long val4 = x + y;
    if(y <= 0)
    {
        if(y <= -2) val = val4;
    }
    else
    {
        val = val2;
        if(x - y >= 0) val = val3;
    }
}

long test(long x, long y)
{
    long val = 8x;
	long val2 = y - x;
    long val3 = x & y;
    long val4 = x + y;
	if(y > 0)
    {
        if(x - y >= 0) val = x & y;
        else val = y - x;
    }
    else if(y <= -2) val = x + y;
    return val;
}

练习题 3.23

A.

%rax -> x
%rcx -> y
%rdx -> n

B.

(*p)++ 表示令 x+=1 ，则在第 7 行与 x += y 一起计算.

C.

dw_loop:
    movq %rdi, %rax
    movq %rdi, %rcx
    imulq %rdi, %rcx	// y = x * x
    leaq (%rdi,%rdi), %rdx	// n = 2 * x
.L2:
    leaq 1(%rcx,%rax), %rax	// x += y; (*p)++
    subq $1, %rdx	// n--;
    testq %rdx, %rdx	//if(n > 0) goto dw_loop:
    jg .L2
    rep; ret 	// return x;

练习题 3.24

long loop_while(long a, long b)
{
    long result = 1;
    while(a > b)
    {
        result *= a + b;
        a++;
    }
    return result;
}

练习题 3.25

long loop_while2(long a, long b)
{
    long result = b;
    while(b > 0)
    {
        result *= a;
        b -= a;
    }
    return result;
}

练习题 3.26

long fun_a(unsigned long x)
{
    long val = 0;
    while(x != 0)
    {
        val ^= x;
        x >>= 1;
    }
    return val & 0x1;
}

练习题 3.27

long fact_for(long n)
{
    long i;
    long result = 1;
    for(i = 2; i <= n; i++)
    {
        result += i;
    }
    return result;
}

long fact_for_while(long n)
{
    long result = 1;
    long i = 2;
    while(i <= n)
    {
        result += i;
        i++;
    }
    return result;
}

long fact_for_while_guarded_do(long n)
{
    long i = 2;
    long result = 1;
    if(i > n) goto done;
loop:
    result *= i;
    i++;
    if(i <= n) goto loop:
done:
    return result;
}

练习题 3.28

long fun_b(unsigned long x)
{
    long val = 0;
    long i;
    for(i = 64; i > 0; i--)
    {
        val *= 2;
        val |= x & 1;
        x >>= 1;
    }
    return val;
}

练习题 3.29

A.

long sum = 0;
long i = 0;
while(i < 10)
{
    if(i & 1) continue;
    sum += i;
    i++;
}

B.

long sum = 0;
long i = 0;
if(i >= 10) goto done;
loop:
if((i & 1) && (i<10)) goto update;
sum += i;
update:
i++;
if(i < 10) goto loop;
done:

练习题 3.30

A.

void switch2(long x, long *dest)
{
    long val = 0;
    switch(x) {
        case -1:
            goto L9;
            break;
        case 0:
        case 7:
            goto L5;
            break;
        case 1:
            goto L6;
            break;
        case 2:
        case 4:
            goto L7;
            break;
        case 3:
        case 6:
            goto L2;
            break;
        case 5:
            goto L8;
            break;
        default:
            goto L2;
            break;
    }
}

B. L5 L7 L2 均有多个标号。

练习题 3.31

void switcher(long a, long b, long c, long *dest)
{
    long val;
    switch(a)
    {
        case 5:
            c = b ^ 15;
        case 0:
            val = 112 + c;
        	break;
        case 2:
        case 7:
            val = (b + c) << 2;
            break;
        case 4:
            val = a;
            break;
        default:
            val = b;
    }
    *dest = val;
}

3.7 过程

练习题 3.32

指令			状态值	（指令	执行	前）
标号	PC	指令	%rdi	%rsi	%rax	%rsp	*%rsp	描述
M1	0X400560	callq	10	--	--	0x7fffffffe820	--	调用first(10)
F1	0x400548	lea	10	--	--	0x7fffffffe828	0x400565	调用lea
F2	0x40054c	sub	10	11	--	0x7fffffffe828	0x400565
F3	0x400550	callq	9	11	--	0x7fffffffe828	0x400565
L1	0x400540	mov	9	11	--	0x7fffffffe830	0x400555
L2	0x400543	imul	9	11	11	0x7fffffffe830	0x400555
L3	0x400547	retq	9	11	99	0x7fffffffe830	0x400555
F4	0x400555	repz	9	11	99	0x7fffffffe828	0x400565
M2	0x400565	mov	9	11	99	0x7fffffffe820	--

练习题 3.33

(int a, short b, long long *u, char*v)

(int b, short b, long long *v, char*u)

练习题 3.34

A. a0 ... a5 存储在被调用者保存及寻求

B. a6, a7 存储在栈上

C. 因为被调用者保存寄存器总共只有 $6$ 个

练习题 3.35

A. 是参数 x

B.

long rfun(unsigned long x)
{
    if(x == 0) 
        return 0;
    unsigned long nx = x;
    long rv = rfun(nx);
    return nx * rv;
}

3.8 数组

练习 3.36

数组	元素大小	整个数组的大小	起始地址	元素 $i$
s	$2$	$14$	$x_s$	$x_s + 2i$
T	$8$	$24$	$x_T$	$x_T + 8i$
U	$8$	$48$	$x_U$	$x_U + 8i$
V	$4$	$32$	$x_V$	$x_v+4i$
w	$8$	$32$	$x_w$	$x_w+8i$

练习题 3.37

	short*	$x_s+2$	leal 2(%rdx), %rax
	short	$M[x_s+6]$	mov 6(%rdx), %al
	short*	$x_s+2i$	leal (%rdx, %rcx, 2), %rax
	short	$M[x_s+8i+2]$	mov 2(%rdx, %rcx, 8), %al
	short*	$x_s+2i-10$	leal -10(%rdx, %rcx, 2), %rax

练习题 3.38

M(P + 8(7i + 5j)) + M(Q + 8(i + 5j))

得 N = 7 M = 1

练习题 3.39

T D[R][C]$\to$ D[i][j] = *(D + L(C * i + j))

&A[i][0] = A + 4 * (16 * i) = 64i

&B[0][k] = B + 4 * (k) = B + 4k

&B[N][k] = B + 4 * (N * 16 + k) = B + 4k + 1024

练习题 3.40

void fix_set_diag_opt(fix_matrix A, int val, int N)
{
    int *Aend = A + N * (N + 1);
    do
    {
        *A = val;
        A += N + 1;
    } while(A != Aend);
}

3.9 异质的数据结构

练习题 3.41

A.

p: 0

s.x: 8

s.y: 12

next: 16

B.

24

C.

void sp_init(struct prob *sp)
{
    sp->s.x = sp->s.y;
    sp->p = &(sp->s.x);
    sp->next = sp;
}

练习题 3.42

A.

long fun(struct ELE *ptr)
{
    int result = 0;
    while(ptr != NULL)
    {
        result += ptr->v;
        prt = ptr->p;
    }
    return result;
}

B.

遍历以 ELE 为头节点的链表，求 v 的和。

练习题 3.43

$expr$	$type$	代码
	short	movw 8(%rdi), %ax movw %ax, (%si)
	char*	addq \$10, %rdi movq %rdi, (%rsi)
	int*	movq %rdi, (%rsi)
	int	movq (%rdi), %rax movl (%rdi, %rax, 4), %eax movl %eax, (%rsi)
	char	movq 8(%rdi), %rax movb (%rax), %al movb %al, (%rsi)

练习题 3.44

A.

0	4	8	12
i	c	j	d

B.

0	4	5	8
i	c	d	j

C.

0		2		4		6		7		8
w[0]	w[1]	w[2]	c[0]	c[1]	c[2]

D.

0		2		4		6		8		16		24		32
w[0]	w[1]	w[2]	w[3]	w[4]	c[0]	c[1]	c[2]

E.

0		10		24
a[0]	a[1]	t

练习题 3.45

A.

a	b	c	d	e	f	g	h
8	2	8	1	4	1	8	4
0	8	16	24	28	32	40	48

B.

$52$

C.

a	c	g	e	h	b	d	f
8	8	8	4	4	2	1	1
0	8	16	24	28	32	34	35

优化后需要填充至 $40$ 确保下一个实例内存对齐，故大小为 $40$

3.10 在机器级程序中将控制与数据结合起来

练习题 3.46

A.

00 00 00 00 00 40 00 76		返回地址
01 23 45 67 89 AB CD EF		%rbx
							
							<- buf = %rsp

B.

00 00 00 00 00 40 00 34		返回地址
33 32 31 30 39 38 37 36		%rbx
35 34 33 32 31 30 39 38
37 36 35 34 33 32 31 30	<- buf = %rsp

C.

返回到 0x00 40 00 34

D.

%rbx 被破坏了，它的值会被加载为 0x33 32 31 30 39 38 37 36

E.

malloc函数调用时应该分配 len(buf)+1 长度的内存来容纳字符串结尾的 \0 ，同时还应该检查 result 是否为 NULL

练习题 3.47

A. 大约 $2^{13}$ 个

B. 128 字节即 $2^7$ ，使得只需要 $2^6 = 64$ 次尝试。

练习题 3.48

A.

不带保护：

buf 在 %rsp ，v 在 %rsp+24

带保护：

buf 在 %rsp+16 ，v 在 %rsp+8 ，金丝雀值在 %rsp+40

B.

v 比 buf 更靠近栈顶，使得溢出更不容易影响到 buf

练习题 3.49

A.

首先将 %rax 设为 $8n+22$ ，接着让它 & -16 ，等价于让其向下舍入到最接近的 16 的倍数，保证内存对齐。得到 $s_2$ 的值

B.

先将 %rsp 加 $7$ ，而后除以 $8$ 再乘以 $8$ ，可向上舍入到最近的 $8$ 的倍数，得到 p 的值。

C.

对应最大化与最小化 $e_1$ $e_2$ 的情况。

D.

实现 $s_2$ 的 $16$ 字节对齐，$p$ 的 $8$ 字节对齐。

第 4 章 处理器的体系结构

4.1 Y86-64 指令集体系结构

练习题 4.1

0x100: 30f30f00000000000000
0x10a: 2031
0x10c: 4013fdffffffffffffff
0x116: 6231
0x118: 70c010000000000000

练习题 4.2

A.

0x100: 30f3fcffffffffffffff	irmovq $-4, %rbx
0x10c: 40630008000000000000	rmmovq %rsi, 0x800(%rbx)
0x114: 00					halt

B.

0x200: a06f					push %rsi
0x202: 800c0200000000000000	call proc
0x20b: 00					halt
0x20c: 						proc.
0x20c: 30f3a000000000000000	irmovq $10, %rbx
0x216: 90					ret

练习题 4.4

.x86-64
rsum(long*, long):
        push    rbp
        mov     rbp, rsp
        push    rbx
        sub     rsp, 24
        mov     QWORD PTR [rbp-24], rdi
        mov     QWORD PTR [rbp-32], rsi
        cmp     QWORD PTR [rbp-32], 0
        jg      .L2
        mov     eax, 0
        jmp     .L3
.L2:
        mov     rax, QWORD PTR [rbp-24]
        mov     rbx, QWORD PTR [rax]
        mov     rax, QWORD PTR [rbp-32]
        lea     rdx, [rax-1]
        mov     rax, QWORD PTR [rbp-24]
        add     rax, 8
        mov     rsi, rdx
        mov     rdi, rax
        call    rsum(long*, long)
        add     rax, rbx
.L3:
        mov     rbx, QWORD PTR [rbp-8]
        leave
        ret

.y86
		pushq	%rsp
		rrmovq	%rsp, %rbp
		pushq	%rbx
		irmovq	$24, %r8
		subq	%r8, %rsp
		mrmovq	-24(%rbp), %r8
		mrmovq	(%r8), %rdi
		mrmovq	-32(%rbp), %r8
		mrmovq	(%r8), %rsi
		andq	%rsi, %rsi
		jg		.L2
.L2:
		...

练习题 4.5

sum:
	irmovq	$8, %r8
	irmovq	$1, %r9
	xorq	%rax, %rax
	andq	%rsi, %rsi
	jmp		test
loop:
	mrmovq	(%rdi), %r10
	irmovq	$0, %r11
	subq	%r10, %r11
	andq 	%r10, %r10
	jg endif
	rrmovq	%r11, %r10
endif:
	addq	%r10, %rax
	addq	%r8, %rdi
	subq	%r9, %rsi
test:
	jne		loop
	ret

练习题 4.6

sum:
	irmovq	$8, %r8
	irmovq	$1, %r9
	xorq	%rax, %rax
	andq	%rsi, %rsi
	jmp		test
loop:
	mrmovq	(%rdi), %r10
	irmovq	$0, %r11
	subq	%r10, %r11
	andq	%r10, %r10
	cmovl	%r11, %r10
	addq	%r10, %rax
	addq	%r8, %rdi
	subq	%r9, %rsi
test:
	jne		loop
	ret

4.2 逻辑设计和硬件语言控制 HCL

练习题 4.9

bool xor = (!a && b) || (a && !b);
// eq == (xor == 0)

练习题 4.10

按位 xor ，将所有结果取 and，再取 not .

练习题 4.11

word Min3 = [
    A <= B && A <= C: A;
    B <= C : B;
    1 : C;
]

练习题 4.12

word Mid3 = [
	(A <= B && B <= C) || (C <= B && B <= A) : B;
    (A <= C && C <= B) || (B <= C && C <= A) : C;
    (B <= A && A <= C) || (C <= A && A <= B) : A;
]

4.3 Y86-64 的顺序实现

练习题 4.13

阶段	通用	具体
	irmoq V, rB	irmovq $128, %rsp
取指		icode:ifun <- M_1[0x016] = 3:0 rA:rB <- M_1[0x017] = f:4 valC <- M_8[0x018] = 128 valP <- 0x020
译码
执行		valE <- 128
访存
写回		R[rB] <- 128
更新 PC		PC <= 0x020

练习题 4.14

0x02c: b00f

%rsp = 0x120

阶段	通用	具体
	popq rA	popq %rax
取指		icode:ifun <- M_1[0x02c] = b:0 rA:rB <- m_1[0x02d] = 0:f valP <- 0x02e
译码		valA <- R[%rsp] = 0x120 valB <- R[5rsp] = 0x120
执行		valE <- valB + 8 = 0x128
访存		valM <- M_8[0x120] = 9
写回		R[%rsp] <- valE = 0x128 R[rA] <- valM = 9
更新 PC		PC <- valP = 0x02e

练习题 4.15

将 %rsp 变更前 %rsp 的值写入%rsp 变更后指向的栈顶内存中

练习题 4.16

将 %rsp 变更前栈顶的值写入 %rsp

练习题 4.17

阶段	cmovXX rA, rB
取指	icode:ifun <- M_1p[PC] rA:rB <- M-1[PC+1] valP <- PC + 2
译码	valA <- R[rA]
执行	valE <- 0 + valA Cnd <- Cond(CC, ifun)
写回	R[rB] <- valE
更新 PC	PC <- valP

练习题 4.18

0x037: 804100000000000000

阶段	通用	具体
	call Dest	call 0x041
取指		icode:ifun <- M_1[0x037] = 8:0 valC <- 0x041 valP <- 0x037+9 = 0x040
译码		valB <- R[%rsp] = 0x128
执行		valE <- valB + (-8) = 0x120
访存		M_8[valE] <- valP = 0x040
写回		R[%rsp] <- valE = 0x120
更新 PC		PC <- valC = 0x041

练习题 4.19

bool need_valC = icode in {IIRMIVQ, IRMMOVQ, IMRMOVQ, ICALL, IJXX}

练习题 4.20

word srcB = [
    icode in { IOPQ, IRMMOVQ, IMRMOVQ} : rB;
    icode in { IPUSHQ, ICALL, IPOPQ, IRET} : RRSP;
    1 : RNONE;
]

练习题 4.22

由 练习题 4.8 知 popq %rsp 最终将写入内存的值，因此 M 口的优先级应该更高.

练习题 4.24

word dstE = [
  	icode in { IRRMOVQ } && cnd : rB;
    icode in { IRMMOVQ, IPOPQ } : rB;
    icode in { IPUSHQ, IPOPQ, ICALL, IRET } : RRSP;
    1 : RNONE；
];

4.4 流水线的通用原理

练习题 4.28

A. C 与 D 之间，延迟为 $380ns$ ，一个时钟周期为 $190ns$

B.

练习题 4.29

A.

$Y(k) = 300 + 20k (ns)$

$T(k) = 1s / (300 / k + 20)ns$

B.

$1 / 20 * 10^9 = 50\ GIPS$

4.5 Y86-64 d的流水线实现

第 5 章 优化程序性能

5.1 优化编译器的能力和局限性

练习题 5.1

若 xp 和 yp 在同一个位置。

void swap(long *xp, long *xp)
{
    *xp = *xp + *xp;	// 2 * *xp;
    *xp = *xp - *xp;	// 0
    *xp = *xp - *xp;	// 0
    
}

5.4 消除循环的低效率

练习题 5.3

代码	min	max	incr	square
A	$1$	$91$	$90$	$90$
B	$91$	$1$	$90$	$90$
C	$1$	$1$	$90$	$90$

练习题 5.4

A. 在第一个循环中 %xmm0 是临时值，被初始化为 %rbx 的值，每次循环结束后写回 %rbx ，第二个循环中 %xmm0 是累计值。

B. 与 combine3 行为相同。

C. 因为除了每次循环开头没有 将 %rbx 指向内存传给 %xmm0 ，其他都一样，而 %xmm0 本身就是累计值，在循环开始前就初始化为 IDENT 了。

练习题 5.5

A.

加法：$n$ 次

乘法： $2n$ 次

B.

乘法： $n$ 次

5.9 提高并行性

**练习题 5.8 ? **

A1: $15.0$

A2: $10.0$

A3: $5.0$

A4: $5.0$

A5: $10.0$

5.11 一些限制因素

练习题 5.9

int take = src1[i1] < src2[i1];
dest[id++] = src1[i1] < src2[i1] ? src1[i1] : src2[i2];
i1 += take;
i2 += 1 - take;

练习题 5.10

A.

将数组变为： 2, ..., 1000

B.

将数组变为： 1, ..., 1

C.

A 情况中所有循环不想关，可以独立执行； B 情况中，前后迭代存在读/写相关，将导致性能下降。

D.

与情况 A 相同，因为相邻迭代不存在数据相关。

练习题 5.11

相邻的迭代存在数据相关，因此形成了 “存储——加载——加法” 的关键路径，导致性能下降。

练习题 5.12

void psumv(float *a, int len, float *p)
{
    float acc = 0;
    for(int i=0; i<len; i++)
    {
    	acc += a[i];
        p[i] = acc;
    }
}

第 6 章 存储器层次结构

6.1 存储技术

练习题 6.1

越接近正方形需要的地址位越少。

组织	$r$	$c$	$b_r$	$b_c$	max(b_r, b_c)
	$4$	$4$	$2$	$2$	$2$
	$4$	$4$	$2$	$2$	$2$
	$16$	$8$	$4$	$3$	$4$
	$32$	$16$	$5$	$4$	$5$
	$32$	$32$	$5$	$5$	$5$

练习题 6.2

$512 \times 400 \times 10000 \times 2 \times 2 = 8.192GB$

练习题 6.3

平均旋转延迟： $1/2 \times (60/15000) \times 1000ms = 2ms$

平均传送时间：$(60/15000) / 500 \times 1000ms = 0.008ms$

总时间： $8 + 2 + 0.008 = 10ms$

练习题 6.4

A.

读 $1 \times 1024 \times 1024 / 512 = 2048$ 个逻辑块，这也是扇区数，最优情况是寻到后立刻开始读取数据，且数据在同一个柱面上，需要旋转两圈来读取所有数据。

旋转一圈时间： $60 / 10000 \times 1000ms = 6ms$

总时间：$5 + 6/2 + 2 \times 6 = 20ms$

B.

每个块都随机分布在磁盘上，每次都要 $5 + 3 = 8ms$

共 $8 \times 2000 = 16000ms$

练习题 6.5

A. $(10^9 \times 128) \times (1 / 470) \times (1 / (86400 \times 365)) = 8 years$

B. $(10^9 \times 128) \times (1 / 330) \times (1 / (86400 \times 365)) = 13 years$

C. $(10^9 \times 128) \times (1 / 20000) \times (1/365) = 17.535 years$

练习题 6.6

$1PB = 10^6GB$

每 GB 价格 $500 / 10^6$

大约 $2025$ 年可以实现。

6.2 局部性

练习题 6.7

sum += a[i][j][k]

练习题 6.8

设 $N = 2$

数据布局为：

地址	0	4	8	12	16	20	24	28	32	36	40	44
元素	v0	v1	v2	a0	a1	a2	v0	v1	v2	a0	a1	a2	

clear1

地址	0	4	8	12	16	20	24	28	32	36	40	44
元素	v0	v1	v2	a0	a1	a2	v0	v1	v2	a0	a1	a2	
访问	1	2	3	4	5	6	7	8	9	10	11	12

clear2

地址	0	4	8	12	16	20	24	28	32	36	40	44
元素	v0	v1	v2	a0	a1	a2	v0	v1	v2	a0	a1	a2	
访问	1	3	5	2	4	6	7	9	11	8	10	12

clear3

地址	0	4	8	12	16	20	24	28	32	36	40	44
元素	v0	v1	v2	a0	a1	a2	v0	v1	v2	a0	a1	a2	
访问	1	5	9	3	7	11	2	6	10	4	8	12

空间局部性从好到差：clear1 clear2 clear3

clear1 顺序访问，clear2 以步长为 $3$ 转跳，clear3 以步长为 $6$ 转跳。

6.4 高速缓存存储器

练习题 6.9

高速缓存	$m$	$C$	$B$	$E$	$S$	$t$	$s$	$b$
1.					$256$	$22$	$8$	$2$
2.					$64$	$23$	$5$	$3$
3.					$1$	$27$	$0$	$5$

练习题 6.10

由于消除了抖动，下列标记为 $1$ 的是命中的，$0$ 为不命中。

	0	1	2	3	4	5	6	7
x	0	1	1	1	0	1	1	1
y	0	1	1	1	0	1	1	1

因此命中率为 $75\%$

练习题 6.11

A. 相同组索引的块被映射到同一个高速缓存，缓存内每个块的标记位有 $t$ 位，因此一个 chunk 有 $2^t$ 个块。

B. $S = 512， B = 32$ ，因此 $s = 9， b = 5$ ，当使用高 $s$ 位来作为组索引时，数组中所有块都会被映射到组 $0$ ，任意时刻缓存中数组的块数都是 $1$

练习题 6.12

12	11	10	9	8	7	6	5	4	3	2	1	0
CT	CT	CT	CT	CT	CT	CT	CT	CI	CI	CI	CO	CO

练习题 6.13

A.

12	11	10	9	8	7	6	5	4	3	2	1	0
0	1	1	1	0	0	0	1	1	0	1	0	0

B.

参数	值
CO	0x0
CI	0x5
CT	0x71
命中？	是
返回字节	0xB

练习题 6.14

A.

12	11	10	9	8	7	6	5	4	3	2	1	0
0	1	1	0	1	1	1	0	1	0	1	0	1

B.

参数	值
CO	0x1
CI	0x5
CT	0x6E
命中？	否
返回字节	--

练习题 6.15

A.

12	11	10	9	8	7	6	5	4	3	2	1	0
1	1	1	1	1	1	1	1	0	0	1	0	0

B.

参数	值
CO	0x0
CI	0x1
CT	0xFF
命中？	否
返回字节	--

练习题 6.16

0000 0110 0100 1100	0x064C
0000 0110 0100 1101	0x064D
0000 0110 0100 1102	0X064E
0000 0110 0100 1103	0X064F

6.5 编写高速缓存友好的代码

练习题 6.27

A.

dst

	0	1
0	m	m
1	m	m

src

	0	1
0	m	m
1	m	h

B.

dst

	0	1
0	m	h
1	m	h

src

	0	1
0	m	h
1	m	h

练习题 6.19

A. $512$

B. 缓存一行能存储两个元素，每隔两次读就会出现一次缓存不命中，共 $256$ 次。

C. $50\%$

练习题 6.20

A. $512$

B. 读取每一个 grid[j][i].x 都会缓存不命中，读取 grid[j][i].y 缓存会命中，共不命中 $256$ 次。

C. $50\%$

D. 能存下整个数组，只存在冷不命中，不命中率为 $25\%$

练习题 6.21

A. $512$

B. 每两次读取 grid[i][j].x 会出现一次缓存不命中，而读取所有的 grid[i][j].y 缓存命中，不命中 $128$ 次。

C. $25\%$

D. 能存下整个数组，只存在冷不命中，不命中率为 $25\%$

6.6 综合：高速缓存对程序性能的影响

练习题 6.21

由图可知， $L1$ 峰值为 $12000MB/s$ ，每秒读 $12000 / 8$ 次，每秒周期数 $2100M$ ，得 $21000 / 12000 * 8 = 1.4$

第 7 章 链接

7.5 符号和符号表

练习题 7.1

	是	外部	m.c	.data
	是	全局	swap.c	.data
	是	全局	swap.c	COMMON
	是	全局	swap.c	.text
	否	--	--	--

7.6 符号解析

练习题 7.2

A.

(a) -> DEF(main.1)

(b) -> DEF(main.1)

B.

a -> DEF(错误)

(b) -> DEF(错误)

C.

(a) -> DEF(x.2)

(b) -> DEF(x.2)

练习题 7.3

A.

gcc p.o libx.a

B.

gcc p.o lilbx.a liby.a

C.

gcc p.o libx.a liby.a libx.a

练习题 7.4

A. 0x4004e8

B. 0x5

练习题 7.5

refaddr = ADDR(.text) + r.offset = 0x4004da

*refptr = (unsigned)ADDR(swap) + r.addend - refaddr = 0x400e8 - 4 - 0x4004da = 0xa

重定位的值为 4004d9 e8 0a 00 00 00 callq 4004e8 <swap>

第 8 章 异常控制流

8.2 进程

练习题 8.1

	是
	否
	是

8.4 进程控制

练习题 8.2

A

p1: x = 2

p1 x = 1

B

p2: x = 0

练习题 8.3

bacc 或 abcc 或 acbc

练习题 8.4

A. $6$ 行

B.

设子进程id为123

Hello
0
Bye
1
2
Bye

练习题 8.5

#include <unistd.h>
#include <stdio.h>

unsigned int snooze(unsigned int secs)
{
    int snoozeTime = sleep(secs);
    printf("Slept for %d of %d secs\n", secs - snoozeTime, secs);
    return snoozeTime;
}

int main()
{
    snooze(5);
}

练习题 8.6

#include <stdio.h>

int main(int argc, char *argv[], char *envp[])
{

    for (int i = 0; argv[i] != NULL; i++)
    {
        printf("argv[ %d]: %s\n", i, argv[i]);
    }

    for (int i = 0; envp[i] != NULL; i++)
    {
        printf("envp[ %d]: %s\n", i, envp[i]);
    }

    return 0;
}

练习题 8.7

#include <unistd.h>
#include <stdio.h>
#include <stdlib.h>
#include "../lib/csapp.h"

unsigned int snooze(unsigned int secs)
{
    int snoozeTime = sleep(secs);
    printf("Slept for %d of %d secs\n", secs - snoozeTime, secs);
    return snoozeTime;
}

void handler(int sig)
{
    return;
}

int main(int argc, char *argv[])
{
    if (signal(SIGINT, handler) == SIG_ERR)
        unix_error("signal error");

    snooze(atoi(argv[1]));

    return 0;
}

练习题8.8

213

第 9 章 虚拟内存

9.2 地址空间

练习题 9.1

虚拟地址位数	虚拟地址数	最大可能虚拟地址数
	$2^8 = 256$	$255$
$16$		$2^{16} - 1$
$32$	$2^{32} = 4G$
$48$		$2^{48} - 1$
$64$	$2^{64} = 16E$	$2^{64} - 1$

9.3 虚拟内存作为缓存的工具

练习题 9.2

$n$	$P = 2^p$	PTE数量
		16
		32
		$2^{20}$
		$2^{19}$

9.6 地址翻译

练习题 9.3

$P$	$VPN$ 位数	$VPO$ 位数	$PPN$ 位数	$PPO$ 位数
	$22$	$10$	$14$	$10$
	$21$	$11$	$13$	$11$
	$20$	$12$	$12$	$12$
	$19$	$13$	$11$	$13$

练习题 9.4

A.

13	12	11	10	9	8	7	6	5	4	3	2	1	0
0	0	0	0	1	1	1	1	0	1	0	1	1	1
|			VPN				  |		VPO				|

B.

参数	值
VPN	0xf
	0X03
	0X03
	是
	0x0D
	0x357

C

11	10	9	8	7	6	5	4	3	2	1	0
0	0	1	1	0	1	0	1	0	1	1	1

D

参数	值
	0x11
	0x5
	0xD
	是
	0x1D

9.8 内存映射

练习题 9.5

附录

x86寄存器对照表

63	31	15	7
%rax	%eax	%ax	%al	返回值
%rbx	%ebx	%bx	%bl	被调用者保存
%rcx	%ecx	%cx	%cl	第4个参数
%rdx	%edx	%dx	%dl	第3个参数
%rsi	%esi	%si	%sil	第2个参数
%rdi	%edi	%di	%dil	第1个参数
%rbp	%ebp	%bp	%bpl	被调用者保存
%rsp	%esp	%sp	%spl	栈指针
%r8	%r8d	%r8w	%r8b	第5个参数
%r9	%r9d	%r9w	%r9b	第6个参数
%r10	%r10d	%r10w	%r10b	调用者保存
%r11	%r11d	%r11w	%r11b	调用者保存
%r12	%r12d	%r12w	%r12b	被调用者保存
%r13	%r13d	%r13w	%r13b	被调用者保存
%r14	%r14d	%r14w	%r14b	被调用者保存
%r15	%r15d	%r15w	%r15b	被调用者保存

二进制、十进制、十六进制对照表

二进制	十进制	十六进制	二进制	十进制	十六进制
0000	0	0	1000	8	8
0001	1	1	1001	9	9
0010	2	2	1010	10	A
0011	3	3	1011	11	B
0100	4	4	1100	12	C
0101	5	5	1101	13	D
0110	6	6	1110	14	E
0111	7	7	1111	15	F