考完就不看の组原笔记!

Cp1.Introduction

1.冯诺依曼结构

  • 冯诺依曼硬件结构:主机+外设+总线
  • 思想:程序存储在存储器中;按照指令地址访存并取出指令。
  • 硬件系统的五大部分:
    • 运算器:做实际的计算
    • 控制器:产生控制信号(硬布线,微程序)
    • 存储器:读、写两种模式。容量与地址线的数量相对应。
    • 输入设备、输出设备
  • 冯诺依曼软硬件之间的关系:相互依存,逻辑等效(有的功能既可以硬件实现,也可软件实现),协同发展。
  • 计算机不同层次:自顶向下分别为:应用程序,高级语言,汇编语言,操作系统,指令集架构(软硬的分界线),微代码,硬件。

2.计算机系统性能的评价指标

  • 机器字长:机器一次能处理的二进制位数。
  • 总线宽度:数据总线一次传递的最大的信息位数。
  • 主存容量&存储带宽:带宽指主存的读写速度
  • CPU 的主频、时钟周期
  • 外频:CPU 和主板之间同步的时钟频率
  • 倍频:主频除以外频
  • CPI:执行一条指令需要的平均时钟周期数目(注意,单位不是时间,是周期数目)\(CPI=程序中所有指令的时钟周期之和 \div 程序中的指令总数=程序中各类指令的CPI加权求和\)
  • MIPS:每秒钟CPU能执行指令的总条数,单位是百万条每秒
  • 全性能公式:\(MIPS = \frac{f}{CPI\times 10^6}\)
  • 程序执行时间=CPU时间+IO时间+访存时间+排队时延
  • \(CPU时间=指令总条数\times CPI / f=\frac{指令总条数}{MIPS\times 10^6}\)

Cp2.Data Representation

  • 机器数:二进制串
  • 源码、反码、补码是三种不同的表示方法
  • 反码加法要回卷(进位位要加到末尾)
  • 移码表示:在补码的基础上,符号位取反。
  • 定点数:定点小数可以表示\([-1, 1-2^{9n}]\)内的小数;定点整数可以表示\([-2^n, 2^n-1]\)内整数。
  • 浮点数:分开表示数据的范围和精度。格式:\(2^{阶码}\times 尾数\),阶码和尾数均使用补码表示,各自带有自己的符号位。
  • IEEE754格式:规定了阶码和尾数各自的位长。只有一个符号位,表示整个真值的符号(第一位)
    • 单精度:32bit,1位符号,8位阶码,后23位尾数;
    • 双精度:64bit,1位符号,11位阶码,后52位尾数
    • 另外,阶码在保存时,加上了偏移量。因此在解读阶码时,结果应该减去127(单精度)或1023(双精度)
    • 另外,尾数部分,默认是1.xxxxx
  • 给定IEEE754二进制表示,还原真值:\((-1)^{符号位}\times 2^{8位阶码-127} \times 1.后23位尾数\)
  • 给定真值,写出IEEE浮点数:先转换为二进制,然后变成\((-1)^s \times 2^e \times 1.M\)的形式,则\(e+127\)为阶码,M为尾数。
  • 特殊数字:
    • 阶码为0,尾数为0:机器0
    • 阶码为255,尾数为0:无穷(X/0)
    • 阶码为255,尾数不为0:NaN(0/0)

数据校验

  • 在信息位后加入\(r\)位校验位。
  • 码距:在一种编码下,相邻合法编码之间的差值。
  • 码距\(\geqslant e+1\)时,具有检测\(e\)个错误的能力
  • 码距\(\geqslant 2t+1\)时,具有纠正\(t\)个错误的能力
  • 码距\(\geqslant e+t+1\)时,具有检测\(e\)个错误,并纠正\(t\)个错误的能力
  • 奇偶校验:校验位只有1位,描述信息位中1的个数是否是偶数/奇数。偶校验是各位异或,奇校验是各位异或后再取非。
  • 奇偶校验的码距为2。
  • 改进:双向校验:把一串二进制串拆成多个小段,叠成二维,在两个方向上进行奇偶校验。

CRC校验

  • CRC校验:信息位数\(k\)和校验位数r要求\(k+r\leqslant2^r - 1\)
  • 发送方:给定生成多项式\(G\),求校验码\(r\):用待传输数据和\(G\)做模二运算,得到的余数即为校验码。
  • 接收方校验:用收到的整个二进制串和\(G\)做模二除法,看余数不是0则说明有错。
  • 当有1位错时,不同位出错得到的余数是不同的。因此可以根据具体的余数值纠错:具体做法是:
    • 针对一个特定的\(G\),首先要看,当左边第一位出错时,对应的余数是什么。这里假设是\(a'\)
    • 接收方得到二进制串,做除法得到非零余数\(a\)后,看是否\(a=a'\),是则说明第一位出错,直接纠错。不是则接下来想办法让出错位移到第一位。
    • 具体办法是:在\(a\)后补一个0,继续除\(G\),得到的新余数后继续补0,继续除\(G\)…每补一次0,我们就把收到的二进制串循环左移1位,直到得到的余数为\(a'\)。此刻,位于当前二进制串最左边的一位就是出错位。

海明校验

  • 有一点与CRC相同,海明校验信息位数\(k\)和校验位数r要求\(k+r\leqslant2^r - 1\)
  • 与CRC不同,海明校验是校验位穿插在信息位之间。校验位的位置为\(1, 2, 4...2^i\)

\[{\color{red}1}, {\color{red}2}, 3, {\color{red}4}, 5, 6, 7, {\color{red}8}, 9, 10, 11\]

  • 校验位的计算:某个校验位是由某些信息位的偶校验(异或得到)。对第\(i\)位,假如该位是信息位,将\(i\)表示为尽量少的校验位的和,例如\(6=4+2\),则将第6位加入到第2位和第4位的校验分组中。对所有的信息位都进行这样的操作,就可以得到各个校验位分别负责的校验分组。 (啊啊啊啊啊这里文字说不清楚啊 自己意会好惹
  • 纠错:为了能够纠错,再设置\(r\)个指错字,每个指错字是一位校验位和它负责的分组进行异或得到。

Cp3.Calculator

  • 补码加减法要丢掉进位。
  • 补码求和补码(x+y) = 补码(x) + 补码(y)
  • 有符号数溢出检测方法:
    • 正+正=负;负+负=正时,即对加数符号位\(f_0, f_1\)以及结果符号位\(f_s\),有\(f_0f_1\bar f_s + \bar f_0 \bar f_1 f_s =1\)
    • 看最高一位数据位的进位和符号位的进位是否相同,不相同即为溢出。
    • 使用双符号位,计算后两个符号位若不同,说明溢出。(本质和方法2相同)
  • 无符号数溢出检测:加法看进位,有进位即为溢出。减法相反,进位为0说明溢出。
  • 原码一位乘法:符号单独运算,数据的绝对值进行运算。与手工运算相比,区别是:得到部分积后,将部分积右移到乘数寄存器中(而不是左移)。
  • 补码一位乘法:\((X\cdot Y)_补 = X_补\cdot \sum_i(y_{i+1} - y_i)2^{-i}\)
  • 具体来说,首先求出\(X, -X, Y\)的补码,然后对\(Y\),首先令\(Y_{i+1}=0\),然后从最低位开始到最高位,重复进行:
    • 如果\(y_i = y_{i+1}\),部分积\(+0\),且部分积算数右移一位
    • 如果\(y_{i+1}y_i = 10\),部分积\(+X_补\),且部分积算数右移一位
    • 如果\(y_{i+1}y_i = 01\),部分积\(+(-X_补)\),且部分积算数右移一位
    • (啊啊啊啊这里也好乱 请直接康mooc后半部分的实例
  • 原码乘法设计:使用与门阵列
  • 补码一位乘法器:算前求补和算后求补。
  • 定点除法器:恢复余数法,不恢复余数法。啊淦这里我不复习啦jojo!
  • 浮点数加减法:
    • 规格化浮点数:尾数用双符号位,尾数的最高数据位和符号位不同。即尾数为\(00.1....., 11.0......\)的浮点数。
    • 可以使用左移的方法规格化一个浮点数。这里注意左移时,阶码也要同步改变。
    • 浮点数加减:分为五步:提出大的阶码,修改小阶码浮点数的尾数(对阶),尾数加减,规格化,舍入,溢出处理。
    • 如果规格化后,阶码双符号位不同,说明发生了溢出。
  • 本章难点:乘除法的计算过程。

Cp4.Storage

  • 存储体系:\(CPU\rightarrow cache\rightarrow 主存\rightarrow 辅存(disk)\)
  • 存储字长:一个存储单元包含的二进制位数。例32位系统的含义是,一个字长度为32。
  • 数据对齐:例如在32位系统,双字长数据地址二进制串的末三位一定是\(000\)(长度为8字节,因此地址为8的整数倍)
  • 数据不对齐存储:节省了空间,但增加了访存次数。
  • 大端方式:地址从大到小存放数据,首地址是数据的最高字节地址。小段反之。
  • SRAM(静态存储单元):啊啊啊啊啊模电杀我 这里太难了
  • 存储扩展:位扩展:\(M \times N \rightarrow M\times kN\)。使用\(k\)个存储器,每个存储器负责二进制串中不同的\(N\)位。连接时,数据线分线,地址线和控制线直接连接。
  • 字扩展:\(M \times N \rightarrow kM\times N\)。使用\(k\)个存储器,数据线直接相连,地址线由于cpu比存储器多,高位的多余的地址线连到片选译码器,片选译码器产生控制线连到片选段。
  • 片选信号的作用:在字扩展中,每个芯片负责整个地址空间中的一部分(类比段式存储),片选用来选择是哪一片寄存器。例如,假如一共有8个芯片,那么需要3位片选信号(\(2^3 = 8\))
  • 多体交叉存储器:和字扩展类似,只不过使用低位作为片选信号(而非高位),即相邻地址在不同的芯片中,可以并行访问。这时需要为每个芯片配置地址寄存器。
  • 对这种存储器,要想以流水线方式存取,需要满足:\(存储周期=总线传送周期\times 芯片数\)(即最后一个芯片中取出数据后,刚好可以再回到第一个芯片取数据)

cache

  • cpu访问cache以字为单位,cache和主存交换数据以块为单位。
  • 读:cpu访问cache,如果命中,直接取;若不命中,则去主存取数据,并且主存将该数据所在的整个块都搬到cache中。
  • 写:写穿:cpu同时向cache和主存写数据;写回:cpu只写cache,整个写操作完成后,再把cache数据写到主存。
  • 地址映射:主存地址划分为二维:块地址+偏移地址。其中块地址由标记(该块是否在cache中)和索引(该块在cache哪个位置)组成。
  • cache的存储空间划分为若干行,每一行的大小可以存储主存中的一块数据。此外,每一行还有tag(数据是否在cache),valid(该数据是否有效),dirty(主存中数据是否最新)三个标志信息。
  • 地址映射:由此可见,cache中一行和主存中一块相对应。具体的映射方式有:
    • 全相连:主存中一块可映射到任一行。
    • 直接相连:根据cache的行数\(n\)给主存分区,使得每个区里有\(n\)个块。主存中一个块在映射时,它是所在分区的第几块,就只能映射到cache的第几行。也就是说,现在把块地址再分为两级:分区地址和cache行。到时候就根据cache行地址去cache的对应行查找。这里有个问题,对cache某一行而言,有很多块都有可能向自己搬迁数据。那么在访问该行时,如果该行有数据,不能直接读,而是需要同时看要访问数据的分区地址(标记)和该cache行内填入的标记是否一样,一样的话才能访问;如果不一样的话,仍然去主存访问,并使用本次访问的块替换调之前占据该行的数据。
    • \(k\)路组相连:cache也分组,\(k\)路的含义是,要求每组内的都有\(k\)行。主存地址仍然分3级,只不过原来的第二级地址(cache行地址)改为表示cache的组号。在映射时,一个主存块地址可以映射到它对应的cache组的任一行,兼顾了全相连和直接相连。如果当cache某一组已经放满,且这时又需要放入新的组,此时就需要从该组中选一行进行替换,下面再讲怎么替换。
  • 替换算法:
    • 先进先出FIFO:按顺序来,替换最早进cache的一行。设计时需要为每一行设一个计数器,记录每一行停留在cache中的轮数。每访问一次cache,组内所有行计数值都+1
    • 近期最少使用LRU:设计数器,新加入的行的计数值为0,之后每次访问,所有没有命中的行计数+1。一旦被命中,计数值就清0.
    • 最不经常使用LRU:设计数器,新加入的行的计数值为0,之后每命中一次计数+1。
    • 随机替换:字面意思w
  • 替换算法的抖动:不断地顶掉又调入某个块
  • 做题:注意cache总容量包括标记和有效位。
  • 虚拟存储器:类比swap分区。分为段式、页式、段页式。将主存和辅存中的部分空间共同视为一个虚拟存储器。
  • MMU:页表寄存器。记录逻辑页号到物理页号的映射。其中每一项也有有效位。
  • 地址划分:虚页号&页内偏移,页表放在主存中。
  • 工作过程:CPU用虚拟地址访问MMU,MMU得到该地址的物理地址,去访问cache或主存。
  • 后备缓冲器TLB:快表,缩短了访问主存的次数。

Cp5. Command System

  • 指令字长:有单字长、双字长、半字长等。长度和机器字长对应。
  • 根据操作数数目分类:
    • 三地址指令:A1 OP A1 -> A3
    • 两地址指令:A1 OP A2 -> A1
    • 一地址指令:AC OP A1 -> AC
  • 指令格式:操作码字段+寻址方式+地址码字段,其中地址码根据操作数数目,再分为多个操作数的地址。 > 这里注意,多操作数的情况下,需要为每个地址都分配该地址所使用的寻址方式字段。
  • 指令的寻址方式:
    • 顺序寻址:找到顺序存放的一系列指令的第一条指令的地址,然后pc不断+1得到后续指令。注意这里的+1指的是加一条指令所占的字长。
    • 跳跃寻址:遇到jmp之类的转移指令时,直接将要跳转的指令地址放入pc
  • 操作数寻址:汇编里那一套。
    • 立即数寻址:操作数就是给出的立即数本身。
    • 寄存器寻址:操作数在寄存器中。数据长度
    • 直接寻址:操作数是所给出的立即数地址里的内容
    • 间接寻址:地址码给出操作数地址的地址。例如mov ax, [200h],首先访问200h单元,将其中的内容看做地址,再访问该地址,再得到的内容才是操作数。
    • 寄存器间接寻址:寄存器中存操作数地址的地址。mov ax, bx
    • 相对寻址:操作数的地址由pc的值+一个基地址d得到。这种方式中,由于pc的值会不断累加,因此实际操作数的地址是d+pc+指令字长
    • 基址寻址:基址寄存器中的值+一个偏移值得到最终地址。
    • 变址寻址:一个基地址+变址寄存器中的值。
  • 指令格式设计:
  • 注意,在研究执行一条指令访问多少次主存时,一定要注意不止取操作数、保存结果要访问主存,取这条指令本身也要访问主存。当前指令长度跨多少个机器字,取指令时就要访问几次主存。

MIPS

  • mips指令:无内部互锁の流水线指令集。
  • 三种指令格式:
    • R型:三地址指令。6位操作码(始终为0)+3x5位地址码\(R_sR_tR_d\)+5位shamt码+6位funct码。寻址方式由unct字段隐式说明。这里操作数和结果的地址都是寄存器(所有只有5位,32个寄存器)。由于op全0,funct才真正起到操作码的功能。shamt指示在移位指令中要移动的位数。
    • I型:三地址指令。6位op+2x5位地址码\(R_sR_t\)+16位立即数。分为四类:运算型(Rs op imm -> Rt),访存型(读主存lw: Rs+imm -> Rt; 写主存sw: Rt -> Rs+imm),移位,条件转移(bne, beq: pc+(imm<<2) -> pc)。
    • J型:6位op+26位立即数。有两种:
      • 无条件转移:高四位(pc++)和imm<<2拼接 -> pc
    • IJ型指令的寻址方式都由op隐式说明。支持立即数、寄存器、基址、相对寻址,以及伪直接寻址。

CP.6 CPU

  • cpu组成:
    • 运算器(状态寄存器、通用寄存器、ALU)
    • 控制器(取指令、执行指令),程序控制、操作控制、时序控制、异常控制
  • 特殊寄存器:
    • PC
    • IR:指令寄存器,存当前正执行的指令
    • AR:锁存访问内存的地址
    • DR:锁存主存取出的数据
    • AC:累加寄存器
    • PSW:程序状态字,类比x86里的flag。
  • 取指令:Mem[pc++] -> IR(指令寄存器)
  • 操作控制器:控制取指令执行指令。
  • 数据通路:考虑在两个寄存器之间传输数据的情形。数据从a通过组合逻辑电路传到b。时钟周期到来时,a的值经过一个寄存器延迟clk_to_Q后更新它的值。新值通过组合逻辑电路到达b的最长路径时间为关键路径实验l,b更新值需要建立时间setuptime,那么cpu的时钟周期应当大于这三个时延的和。
  • 另外,ab时钟同时到来,而b在刚刚获得一个新值以后要求保持该值一段时间holdtime,如果a到b传输的最快时间(最短路径时延+clk_to_Q)比holdtime小,就会破坏b的保持。因此要求这两个值的和>holdtime
  • 单总线结构:要防止总线争用,需要分时并锁存出入总线的信号。执行一条加法指令需要3个时钟周期
  • 双总线:执行指令时可以并行地传送两个操作数。加法需要2个时钟周期
  • 三总线结构:没有锁存器,加法只需要一个时钟周期。
  • 单周期mips:要求一条指令在一个周期内完成。
  • cpu控制器输出的控制信号的产生:首先时序产生器周期地产生时序信号,不同的时序信号和指令译码得到的信号通过组合逻辑,就可以得到控制器的控制信号。
  • 控制器设计:
    • 传统三级时序:三级分别是:一个指令周期内有若干时钟周期,一个时钟周期内又有若干节拍。当前处于哪个时钟周期、哪个节拍这些时序信号由时序产生器来产生。我们将一个指令的不同时钟周期看做不同状态,做出状态图,就可以通过组合逻辑产生控制信号。
    • 变长指令周期:把不同的指令在执行周期的所有节拍都认为是不同的状态。(而之前是,认为所有指令都有同样多的节拍,把不同的节拍看做不同的状态)。把这些不同状态输入一个fsm,生成次态。
    • 微程序控制器:不同的指令中的不同时钟周期对应不同的状态,这里和上面都一样。但是注意到在每个状态下,要产生的控制信号是固定的,因此可以直接将其存储到一个存储器中,根据不同的状态直接取用即可。这里,一条指令对应的操作我们称为微程序;不同状态下,对应的固定的控制信号,将其拼接成一个二进制串,称为微指令;微指令在存储器中的地址称为微地址。那么我们只要在的状态下,用微地址访问存储器,得到微指令,也就得到了要输出的控制信号。
    • 微指令内除了各个控制信号的拼接部分(操作控制字段),末尾还有顺序控制字段:包括判别字段和下址字段。下址字段给出下一跳微指令在控存中的地址。判别字段中的\(p_1\)为0时,下一微指令直接就是下址字段的微指令;为1说明下址字段无效,要根据地址转移逻辑来获得下一个微地址(这种情况往往是取指令微程序的最后一条微指令中会出现,因为对它而言,下一个微地址需要根据具体的指令类型来跳转到相应的微程序)
    • 不同的机器指令,在取指令阶段的状态是相同的,只是在执行阶段根据指令的不同分支为了不同的若干状态,因此不同机器指令的取指令部分,可以共用微程序。
    • 因此现在,我们从IR中取出指令后,不需要使用复杂逻辑生成控制信号,而只需要一个地址转移逻辑,生成对应微程序的微地址即可。
  • 微指令的设计:微指令中的控制字段往往很长,希望可以压缩:
    • 对微命令(控制信号)分类:将互斥型的微命令(不会同时为1)进行编码(而不是onehot方式)。例如,有七个微命令互斥,那么可以使用二进制编码压缩为3位。 > 这里注意,3位编码最多只能表示7位而不是8位。因为要预留一个000来表示没有任何信号。

    • 压缩下址字段:约定位微指令都顺序存放,那么就不需要下址字段,直接顺序执行即可。
    • 垂直微指令:和机器指令有点类似。原来的一个时钟周期对应一条微指令,可能执行多条机器指令,现在让其中的每一个机器指令对应一条微指令(就是把原来一条长的微指令拆成几个短的)。不过有一说一,这个好像实际中性能太差已经被淘汰了。

  • 要看的:性能评价指标计算(cpi,mips),原码补码一位乘法,双符号位浮点数加减 ,恢复余数法,不恢复余数法,定点数 浮点数数据表示范围,字位扩展