ics期中整理

可以说是巧妙地避开了考点吧,觉得还是对大家有点帮助的(

范围是 csapp 的 2-6 章。

upd: hcl 背错了,身败名裂

第二章

0:
image

补码:最高有效位是 -2^{w-1}
反码:最高有效位是 -(2^{w-1}-1)
原码:最高有效位是符号位,决定其余位的正负

short -> unsigned 先改变大小,再完成有符号数到无符号数 —> (unsigned)sx == (unsigned)(int)sx

算术右移补最高位,逻辑右移补 0

检测无符号数加法的溢出 P62

1
2
3
4
int uok (unsigned x, unsigned y) {
unsigned sum = x + y;
return sum >= x;
}

有符号数

1
2
3
4
5
6
int tok(int x, int y) {
int sum = x + y;
int neg_over = x < 0 && y < 0 && sum >= 0;
int pos_over = x >= 0 && y >= 0 && sum < 0;
return !neg_over && !pos_over;
}

补码加法构成阿贝尔群,可交换可结合

减法溢出

1
2
3
4
5
6
7
8
9
10
11
// 注意测试 TMIN
int tsub(int x, int y) {
int res = 1;
(y == INT_MIN) && (res = 0);
// if (y == INT_MIN) res = 0;
int sub = x - y;
int pos_over = x > 0 && y < 0 && sub < 0;
int neg_over = x < 0 && y > 0 && sub > 0;
res = res && !(pos_over || neg_over);
return res;
}

-x == ~x+1 对任意整数值一样

无符号和补码乘法,虽然完整的乘积的位级表示可能会不同,但是截断后乘积的位级表示是相同的

image

无论无符号还是补码、是否溢出,(x << 4) - (x << 1) 都和 (x << 3) + (x << 2) + (x << 1)相等

补码除法 x >> k 产生 下取整 x/2^k
正常除法应该对负数上取整

image

符号、尾数、阶码
1 8 23 (float)
1 11 52 (double)
image

规格化
(1+f)2^{exp-127}
非规格化
f
2^(-126)
正无穷:s = 0, exp=1111111, f = 0;
负无穷:s = 1, exp=1111111, f = 0;

可表示数越靠近原点约稠密

P80
最小的非规格化数 exp = 0, f = 1;
最大的非规格化数 exp = 0, f = 1111;
最小的规格化数 exp = 1, f = 0;
最大的规格化数 exp = 1110, f = 111;
无穷大 0 exp = 1111, f = 0;

image

P83 - 2.49
P84 - 2.52
P87 - 2.54

第三章

P118 ATT与 intel汇编代码格式
float 4 double 8
P121 操作数格式
传送指令的两个操作数不能都指向内存位置
movz 把目的中的剩余字节填充为0,movs则是符号扩展
任何为寄存器生成32位值的指令都会把该寄存器的高位部分设为0,比如 movl,而其他时候只会更新目的操作数指定的那些寄存器字节或内存位置。
cltq: 把 eax 符号扩展到 rax 编码更紧凑
movabsq 传送绝对的四字
指示地址寄存器必须是 r开头,不能 movb $1, (%eax)
movsbl 符号扩展
movzbl 0扩展
char -> int: movsbl
int -> char: movb
栈向下增长,栈顶元素地址最低
leaq直接操作 x,而movq操作地址 x 处的值
移位量可以是一个立即数,或者放在单字节寄存器 %cl中:sarq算术移位(填符号位),shrq逻辑移位(填0)
对应的 salq
移位操作的目的操作数可以使寄存器/内存地址
cqto
image
一个参数存在 rax,另一个作为操作数给出,然后乘积:高64位在rdx,低64位在rax。

1
2
3
4
5
#include <inttypes.h>
typedef unsigned __int128 uint128_t;
void upord(uint128 *dest, uint64_t x, uint64_t y) {
*dest = x * (uint128_t) y;
}

cqto,把 rax的符号扩展到rdx的所有位

image
leaq 不改变条件吗,inc和deq会设置溢出和零标志,但不改变进位。移位操作的仅为标志设置为最后一个被移除的位,溢出标志设为 0

cmp s1, s2 ==> s2 - s1
test s1, s2 ==> s1 & s2
这两个只设置条件吗,不改变任何其他寄存器

image

条件跳转只能是直接跳转

直接跳转??间接??

T_ran = T_ok + 0.5T_MP(MP是预测错误)

cmove 条件传送

continue 会跳到当前循环迭代的结尾

&& 创建一个指向代码为止的指针

函数调用时,通过寄存器,过程可以传递最多6个整数值
P调用Q时,把返回地址当做是 P的栈帧的一部分,因为它存放的是与P相关的状态
char 1字节 8位 short 2字节 16位 int 4字节 32位
switch ……
long至少要和int一样大,书上似乎认为 long 是8
用 leaq 生成到某个位置的指针
%rbx, %rbp, %r12-%r15为被调用者保存寄存器,当P调用Q时,Q必须保存这些寄存器的值
其他寄存器除了 %rsp,都是调用者保存寄存器,意味着任何函数都能修改他们,P调用Q的时候Q可以随意修改这个寄存器
返回数组值:操作类型为int,涉及四字节操作;movl和%eax
返回指针:操作类型为int*,涉及八字节:leaq,%rax

1
2
typedef int r3[3];
r3 a[5];

二维数组
$&d[i][j] = x_d + L(Ci+j)$

sal 算术右移(填符号位),shl 逻辑右移(填0)
数据对齐:要求k字节类型对象的地址必须是k的倍数

malloc 返回一个通用指针 void*

1
2
int fun(int x, int *p);
int (*fp)(int, int*); // 函数指针。

rsp不能放第二个位置
(xxx, %rsp) 不合法

指针的差结果是两个地址之差除以该数据类型的大小

第四章

程序员可见的状态:
image
pushq %rsp放的是原值
popq %rsp等价于

1
2
3
addq $8, %rsp
mrmovq 8(%rsp), %rsp
//如果后加的话就把 rsp的值又改了

pushq %rsp

1
2
3
movq REG, -8(%rsp)
subq $8, %rsp
// 先减的话就不能把正确的值塞到栈里

向寄存器的写入受时钟信号控制
寄存器文件有内部存储

valP在取指阶段得到
执行阶段设置条件码。写回阶段最多可以写两个结果到寄存器文件

程序寄存器的新值取自:vapP,下一条指令的地址,valC,调用指令或跳转指令指定的目标地址,valM,从内存读取的返回地址
组合逻辑不需要任何时序或控制,只要输入变化了,值就通过逻辑门网络传播
每个时钟周期,程序计数器都会装载新的指令地址。只有在执行整数运算指令时,才会装载条件码寄存器。只有在执行rmmovq,pushq,call时,才会写数据内存。
只有 popq 会用到寄存器文件的两个写端口,为了把值放到 %esp,M端口优先级高于E
alu的输出是valE的信号
从头到尾执行一条指令所需时间为延迟,吞吐量为倒数
流水线的延迟是最大的一部分的延迟加上流水线寄存器的延迟
SEQ的延迟是各阶段之和加上流水线寄存器的延迟
转发:5个源:e_valE,m_valM,M_valE,W_valM,W_valE;2个转发目的:valA, valB
由流水线中最深的指令引起的异常,优先级最高
访存/写回阶段的指令异常时,流水线控制逻辑禁止更新条件码寄存器或是数据内存
出现异常时,信息只是简单地存放在流水线寄存器的状态字段中,异常事件不会对流水线中的指令流有任何影响。在写回阶段,流水线控制逻辑发现出现了异常,并停止执行。
只有 call 和跳转指令需要 valp 而这些指令不需要valA
image
处于最早流水线阶段中的转发源具有较高的优先级,因为它保持着程序序列中设置该寄存器的最近的指令
只有 popq %rsp 关心访存和写回的转发优先级,因为只有他同时写两个寄存器

image

image
CPI是流水线平均吞吐量的倒数,单位是时钟周期,不是微微秒

第五章

关键路径是在循环的反复执行过程中形成的数据相关链
CPE 镁元素的周期数
编译器回家社函数有副作用,程序员需要显示完成代码移动
减少过程调用
消除不必要的内存引用
延迟界限:下一条指令开始前,这条必须结束 — 数据相关
吞吐量界限:处理器功能单元的原始计算能力
循环寄存器之间的操作链决定了限制性能的数据相关
比较和分支操作不直接影响程序中的数据流
练习题5.6 n次乘法,n次加法,i--不在关键路径上
循环展开
使用多个累计变量 —- 多路并行
重新结合变换,增加了可以并行执行的操作数量
大多数编译器不会尝试的对浮点运算做重新结合,因为这些运算不保证是可结合的

1
2
3
4
// 慢
acc = (acc OP data[i]) OP data[i + 1];
// 快
acc = acc OP (data[i] OP data[i + 1]);

练习题 5.8 最快的是 A3A4
寄存器溢出
分支预测和预测错误出发
不要过分关心可预测的分支
书写适合用条件传送实现的代码
消除连续的函数调用,将计算移到循环外
消除不必要的内存引用,引入临时变量来保存中间结果
低级优化,结构化代码以利用硬件功能

  • 展开循环
  • 使用多个累计变量、重新结合,提高指令级并行
  • 用功能性的风格重写条件操作,使得编译采用条件数据传送

image

B不对是因为可能A和B指向的是同一块内存区域

第六章

寻道时间和旋转延迟 4ms,传送时间 0.02ms(1/RPM/(每磁道平均扇区数)*60)
读SSD比写要快,随机读写的性能差别由底层闪存基本属性决定
数据以页为单位读写,只有在一页所属的块整个被擦除之后,才能写这一页。一个快在 100000 次重复写之后会磨损坏。
SRAM比DRAM快,DRAM比磁盘快,SRAM比DRAM贵,DRAM比磁盘贵,SSD位于DRAM和磁盘之间
循环有很好地时间(循环体会被执行多次)和空间局部性
数组有空间局部性
数据以块为大小在第k层和k+1层之间来回复制的
随机替换策略、LRU策略(最近最少被使用)

image
image
E=1 — 直接映射高速缓存

1
2
jmp *%rax #目标为寄存器中的值
jmp *(%rax) #以寄存器中的值作为读地址,从内存中读出跳转目标

CISC指令数量较多,有些指令的执行周期很长 ,
编码是可变长度的,支持复杂的寻址方式,栈密
集的过程链接,代码长度一般较短,取址部件更复杂。
RISC指令较少,没有执行周期很长的指令,编码固定长度,
只有简单的寻址方式,寄存器密集的过程链接,代码长度
较长,没有条件码
image