20155318 《信息安全系统设计基础》第十四周学习总结

20155318 《信息安全系统设计基础》第十四周学习总结

• 找出全书你认为学得最差的一章，深入重新学习一下，要求（期末占5分）：

• 总结新的收获

• 给你的结对学习搭档讲解或请教，并获取反馈

• 我选择教材第四章《处理器体系结构》 的内容来深入学习，在之前的学习中，由于各种原因，对那一章的教材学习和实践学习都有欠缺，这里决定重新学习一下。该章主要讲解了如下几个方面的问题：

1. Y86-64指令集体系结构
2. 逻辑设计和硬件控制语言HCL
3. Y86-64的顺序实现
4. Y86-64的流水线实现

基本知识

• 处理器：执行一系列指令完成相应功能
• 指令体系结构：处理器支持的指令和指令的字节级编码
• 指令集在机器型号上有着一定要求（不同型号相互兼容）
• 通过处理多条指令的不同部分（流水线）提高性能

Y86-64指令集体系结构

与x86-64相比，Y86-64指令集的数据类型、指令和寻址方式更少，字节级编码也比较简单，机器代码没有相应的x86-64代码紧凑

程序员可见状态

• Y86程序中的每条指令都会读取或者修改处理器状态的某些部分。这称为程序员可见状态

• 程序员可见状态为：

  • 15程序寄存器（RF）：%rax、%rcx、%rdx、%rbx、%rsp、%rbp、%rsi、%rdi、%r8-%r14（每个程序寄存器存储一个64位的字）
  • 3个条件码（CC）：ZF、SF、OF，保存着最近的算数或逻辑指令所造成影响的有关信息。
  • 程序状态（Stat）：AOK、HLT、ADR、INS，表明程序执行的总体状态

  名字	含义
  AOK	正常操作
  HLT	遇到器执行halt指令
  ADR	遇到非法地址
  INS	遇到非法指令

  • 程序计数器（PC）：存放当前正在执行指令的地址
  • 内存（DMEM）

• 指令模拟器，称为YIS，他的目的是模拟Y86-64机器代码程序的执行，而不用试图模拟任何具体处理器实现的行为

Y86-64指令

• 是x86-64指令集的一个子集，寻址方式较少，操作数也较少

• halt：该指令占1个字节，用十六进制表示为「00」，用于停止指令的执行
• nop：该指令占1个字节，用十六进制表示为「10」，占位指令
• movq：第一个字母就表明了源的类型，第二个字母指明了目的的类型

  • irmovq V rB：该指令占10个字节，用十六进制表示为「30 FrB V」，将立即数V放入寄存器rB中

  • 

  • rrmovq rA,rB：该指令占2个字节，用十六进制表示为「20 rArB」，指令作用是将rA寄存器中的值放入rB寄存器中

  • 

  • .mrmovq D(rB),rA：该指令占10个字节，用十六进制表示为「50 rArB D」，将以“rB+D”为地址的内存单元中的数放入寄存器rA中

  • 

  • rmmovq rA,D(rB)：该指令占10个字节，用十六进制表示为「40 rArB D」，将rA寄存器中的值放入以“rB+D”为地址的内存单元中

  • 

两个内存传送指令中的存储器引用方式是简单的基址和偏移量形式。在地址计算中，我们不支持第二变址寄存器和任何寄存器值的伸缩。不允许从一个内存地址直接传送到另一个内存地址。也不允许将立即数传送到内存

• OPq rA,rB：整数操作指令（4个），将寄存器rA和寄存器rB中的值做整数运算，并把结果存入rB寄存器中

  • addq
  • subq
  • andq
  • xorq
    

• jXX Dest：跳转指令（7个），跳转到以Dest为地址的代码处，该指令占9个字节

  • jmp
  • jle
  • jl
  • je
  • jne
  • jge
  • jg
    

• cmovXX rA,rB为条件传送指令（6个），其指令格式同rrmovq指令，不同点是只有当条件码满足需要的约束时才会更新目的寄存器的值。该指令占2个字节

  • cmovle
  • cmovl
  • cmove
  • cmovne
  • cmovge
  • cmovg

• call Dest指令：将返回地址入栈，然后跳到Dest指向的目的地址
  

• ret指令：从call指令的调用中返回。
  

• pushq rA：入栈指令，将rA寄存器中的值压入栈顶

• popq rA：出栈指令，将栈顶元素弹出到rA寄存器中
  

指令编码

• 每条指令的第一个字节表明指令的类型。这个字节分为两个部分，每部分4位：
  • 高4位：代码部分
  • 低4位：功能部分（功能值只有在一组相关指令共用一个代码时才会有用）
• 指令的字节级编码规则：每条指令的第一个字节表明指令的类型。分为两个部分，高4位是代码部分，低4位是功能部分。代码值为0~0xB，功能值只有在一组相关指令共用一个代码时才有用。
• 15个程序寄存器当中，每个都有一个相对应的0~0xE之间的寄存器标识符。
• 程序寄存器存在CPU中的一个寄存器文件中，这个寄存器文件就是一个小的、以寄存器ID作为地址的随机访问存储器。
• 分支指令和call指令，就没有寄存器指示符字节。
• 只需要一个寄存器操作数的指令（irmovq、pushq、popq）将另一个寄存器指示符设为0xF。
• 指令集的一个重要性质就是字节编码必须有唯一的解释。

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

为实现一个数字系统需要三个主要的组成部分：

• 计算对位进行操作的函数的组合逻辑
• 存储位的存储单元
• 控制存储器单元更新的时钟信号

逻辑门

• 是数字电路的基本计算单元
• 输出=输入位值的某个布尔函数。
• 只对单个位的数进行操作，而不是整个字
• 对应HCL表达式

  1. AND:&&
  2. OR:||
  3. NOT:！
  

• 逻辑门总是活动的，一旦输入变化，极短的时间内，输出就会相应变化

组合电路和HCL布尔表达式

HCL中多路复用函数是用情况表达式来描述的，其通用格式如下：

[
    select 1 : expr 1
    select 2 : expr 2
    .
    .
    .
    select k : expr k
]

select i表示第i种情况的布尔表达式（表明什么时候选择这种情况），expr i表示在这种情况下的表达式（表明得到的值）。

• 用情况表达式来描述下图字级多路复用选择电路为：

word Out = [
    s: A;
    1: B;//选择表达式为“1”，表示如果前面没有情况被选中，那就选择这种情况
];

• 很多逻辑门组合成一个网构建的计算块。注意两个或多个输出不能连接在一起，并且必须无环。

• HCL表达式与C语言中的表达式的区别如下：

  1. 由于组合电路是由一系列的逻辑门组成。HCL中输出会持续随着输入变化而变化。而C语言中只有在程序执行到的时候才进行求值。
  2. C语言中，0是FLASE，除了0以外的所有整数都是TRUE，而HCL只对0和1操作。
  3. C中&&和||这两种，是优先求值，（&和|并不是）第一个值就能确定结果的话，它不会去计算第二个值。但是HCL中并没有这样的规则。

• HCL中，将所有字级的信号都声明为int，不指定字的大小，HCL允许比较字是否相等

• 多路复用函数是用情况表达式来描述的。与C不同其不要求不同的选择表达式之间互斥

• 组合电路从本质上讲，不存储任何信息。他们只是简单地响应输入信号，产生属于输入的某个函数的输出。

存储器和时钟

• 时序电路：有状态并在这个状态上进行计算的系统
• 时钟寄存器：存储单个位或字，时钟信号控制寄存器加载输入值
• 随机访问存储器（存储器）存储字，用地址来选择该读或该写那个字。
• 寄存器作为电路不同部分中的组合逻辑之间的屏障，每当每个时钟到达上升沿的时候，值才会从寄存器的输入传送到输出

集合关系

我们可以用下面这种形式简化的表示集合关系：

iexpr in {iexpr1,iexpr2,…,iexprk}//iexpr为被测试的值，iexpr1~iexprk位待匹配的值，他们均为整数表达式

Y86的顺序实现

• 处理一条指令包括很多的操作。将他们组织成某个特殊的阶段序列，即使指令的动作差异很大，但所有的指令都遵循统一的序列。
  六个阶段内执行的操作：

  • 取指：取指阶段从存储器读取指令字节，地址为程序计数器（PC）的值。
  • 译码：译码阶段从寄存器文件读入最多两个操作数,得到val A/val B.
  • 执行：执行阶段，算术/逻辑单元要么执行指令明确的操作（根据ifun的值），计算存储器引用的有效地址，要么增加或减少栈指针。得到的值称为valE
  • 访存：访存阶段可将数据写入存储器或从存储器读出数据
  • 写回：最多可写两个结果到存储器。
  • 更新PC：将PC设置成下一指令的地址。

• 处理器无限循环，执行这些阶段，在简化的实现中，一旦发生任何异常，处理器就会停止。
  

• 程序计数器放在寄存器中，位于左下角PC。

• 信息随着线流动，方向是先向上再向右

• 反馈先祖在右边向下

• 所有硬件单元的处理都在一个时钟周期内完成。

• 浅灰色方块表示硬件单元

• 控制逻辑块是用灰色圆角矩形表示的

• 线路的名字在白色椭圆中说明

• 宽度为字长或更窄的数据连接用细线

• 单个位的连接用虚线。

SEQ的时序

• SEQ的实现包括组合逻辑和两种存储器设备：

  1. 时钟寄存器、程序计数器和条件码寄存器，随机访问存储器。
  2. 程序计数器、条件码寄存器。数据内存和寄存器文件。
     

• SEQ阶段的实现：

  1. 取指阶段（包括指令内存硬件单元）：以PC为第一个字节的地址，一次从内存读10个字节。根据icode的值我们可以确定下面三个一位的信号:

  instr_valid：用于发现不合法的指令
  need_regids：是否包含寄存器指示符字节
  need_valC：是否包括常数字
  

  2. 译码和写回阶段：寄存器文件有四个端口，支持同时进行两个读和两个写。每个端口有一个地址连接（寄存器ID）和一个数据连接（64根线路），既可以作为寄存器文件的输出字，又可以作为它的输入字。
  3. 执行阶段：包括算数/逻辑单元（ALU），输出为valE信号。
  4. 访存阶段：读或者写程序数据。两个控制块产生内存地址和内存输入数据的值。另外两个块产生表明应该执行读还是写操作的控制信号。当执行读操作时，数据内存产生valM。
  5. 更新PC阶段：SEQ的最后一个阶段会产生程序计数器的新值，依据指令的类型和是否要选择分支，新的PC可能是valC、valM或者valP。

流水线

1. 由时钟信号控制，使多条指令不同阶段可以同时执行，增加了延迟，提升吞吐量
2. 问题：流水阶段长度不一，流水线深度过大插入寄存器影响性能
3. 因为存在反馈的流水线（即一条指令可能需要多次执行某个操作，或使用某个数据，访问某个存储器或寄存器）导致流水线冒险（数据，控制）
4. 数据冒险解决方案：暂停（系统判断是否会产生冒险，会则插入气泡，延迟下条指令执行），转发（使产生的结果理解送入需要的位置，避免暂停），加载使用（当存储器读发生较晚时需要暂停和转发机制同时使用）
5. 异常处理
6. 控制逻辑和机制
   • 处理return：暂停流水线直到ret指令到达写回阶段
   • 加载/使用冒险：在对存储器读和使用之间需要暂停一个周期
   • 预测错误分支：当预测失败时应该可以返回到之前状态，去掉错误指令
   • 异常：出现异常时，停止后序指令执行，并避免当前异常指令写回
7. 性能分析
   • CPI=1+处罚项（预测错误+返回+暂停）
   • 目标：使CPI=1；一个周期执行一条指令

教材习题学习

• 4.2

• 确定下列每个字节序列所编码的Y86-64指令序列。如果序列中有不合法的字节，指出指令序列中不合法值出现的位置。每个序列都先给出了起始地址，冒号，然后是字节序列。
  

• 解析：本题考察“字节序列与Y86-64指令之间的转换”。此题关键要根据“代码部分”（即指令编码的前4位）确定其指令编码长度，从而将一个整体的编码划分为不同的指令。

• A.根据“30”找到“irmovq”指令，由指令结构可知接下来的8个字节为相应的立即数；同理，取40为“rmmovq”指令；最后的“00”为停止执行指令。

• B.代码包含函数调用。其余分析方式与A类似，也是根据指令编码寻找指令；再根据指令的结构选取合适的位数进行切割。由于此代码涉及到了系统调用，所以需要有函数的相关信息（proc），如起始地址等。

• C.代码包含非法指令字节0xf0。查询Y86-64的指令集，我们并没有找到f0对应的指令。

• 4.3

• 解析：有了iaddq指令，我们可以省去P251页Y86-64代码中的第2-3行，直接用iaddq $8,%rdi和iaddq $-1,%rsi两条指令替换10-11行。

• 4.4

• 解析：此题涉及到我们常用的几种操作：

• xorq %rax,%rax：用异或来给某个数置零

• andq %rsi,%rsi: 自身相与来设置条件码，判断一个数是否为0

• 用pushq ……和popq ……来保护某个寄存器中的值

• 用xorq %r11,%r11和subq %r10,%r11加上跳转语句jle……来取一个数的绝对值:当前%r11中的值为%r10的值的相反数，如果执行subq %r10,%r11后%r11小于等于0，则说明%r10中的值为正数，绝对值为其本身，如果%r11的值大于0，则说明%r10的值为负，用rrmovq %r11,%r10给%r10取反。

• 此外，我们还经常用“x∧0”来给一个数置0，用“x∨1”来给一个数置1.

• 4.9

• 解析：EXCLUSIVE-OR函数要求两个位有相反的值

bool xor = (!a&&b)||(a&&!b);

（通常信号eq和xor是互补的，一个为1，另一个就为0）

• 4.10
• 解析：EXCLUSIVE-OR电路的输出是位相等值的互补。根据德摩根定律，我们能用OR和NOT实现AND。
• 4.11
• 解析：将第二行判断换成“A<=C:B”或“B<=C:B”，因为进入到第二行的前提是A不是最小的如果在此基础上A还小于等于C，则说明B是最小的，换个角度思考，如果A不是最小的，那么B和C中较小的就是最小的；
• 4.12
• 解析：这个题除了可以像答案中那样分每种情况讨论，也可以结合“&&”和“||”等符号，将同时输出“B”的情况连接在一起，如“(A<=B && B<=C) || (C<=B && B<=A) : B;”
• 4.24
• 解析：这里我们要改编dstE的HCL代码来实现条件传送指令，其实只需要在rrmovq对应的分支加一个判断Cnd信号的操作，如下所示：

int dstE = [
    icode in { IRRMOVQ } && Cnd: rB;
    icode in { IIRMOVL, IOPL } : rB;
    icode in { IPUSHQ, IPOPL, ICALL, IRET } : RESP;
    1 : RNONE; # Don’t need register
];

• 4.47&4.48&4.49题目链接

代码托管

上周考试错题总结

错题解析：对于E选项，书本P270旁注部分对于jxx命令访存部分是空着的，因此jxx命令没有访存操作

错题解析：对于D选项，书本关于磁盘操作写道：在任何时刻，所有的读/写头都位于同一个柱面上，因此D选项正确

错题解析：对于C选项，DRAM是动态随机存储器。SRAM是静态随机存取存储器，且工作时需要刷新。与动态RAM比，静态RAM的读写速度要快，集成度也较低。

结对及互评

本周结对学习情况

• 20155227

其他（感悟、思考等）

课程的学习接近尾声，老师布置的重学自认为学的最差的一章，让我发现了自己在之前学习中的许多疏漏和不足，，希望通过这周的学习能够查漏补缺，尽快补齐老师之前所要求的学习内容。

学习进度条

	代码行数（新增/累积）	博客量（新增/累积）	学习时间（新增/累积）	重要成长
目标	5000行	30篇	400小时
第一周	0/0	1/1	3/3
第二周	100/100	1/2	3/6
第三周	300/400	1/3	4/10
第四周	0/400	2/5	2/12
第五周	25/425	1/6	4/16
第六周	181/606	3/9	10/26
第七周	201/807	2/11	7/33
第八周	-（包括脚本无意义）/6719	2/13	7/40
第九周	396/7115	3/16	4/44
第十周	1160/8275	2/18	4/49
第十一周	135/8410	3/21	5/54
第十三周	317/8727	1/22	8/62
第十四周	105/8832	1/23	5/67

尝试一下记录「计划学习时间」和「实际学习时间」，到期末看看能不能改进自己的计划能力。这个工作学习中很重要，也很有用。
耗时估计的公式
：Y=X+X/N ，Y=X-X/N，训练次数多了，X、Y就接近了。

参考：软件工程软件的估计为什么这么难，软件工程 估计方法

• 计划学习时间:5小时

• 实际学习时间:5小时

• 改进情况：

(有空多看看现代软件工程 课件
软件工程师能力自我评价表)

参考资料

• 《深入理解计算机系统V3》学习指导
• ...