第二章 指令系统

数据表示，数据类型

采用标识符数据表示的优点？（三简化，硬件(一致性检查，数据类型转换)，软件，数据库）缺点？（三个，数据，指令，硬件）

标识符数据表示与数据描述符描述的差别？

浮点数表示rm增大，带来的影响（6个）；

尾数下溢的处理方法（4种），各自的优缺点

编址方式（4种），==对齐方式==，大小端；高位/低位交叉编址；寻址方式（四种）

定位方式（3），各自的含义，为什么要定位（4）

操作码设计（3种），信息冗余度计算

RISC基本思想（定义/目的），RISC特点（指令（4），硬，优化编译）

RISC关键技术（延时转移，指令取消，寄存器窗口重叠，指令流调整技术，高速缓冲寄存器Cache，优化设计编译系统；）

数据表示与数据类型的定义和区别

标志符数据表示,数据描述符

标志符数据表示

==采用标志符数据表示方法的优点：==

  1. 简化了指令系统。

  2. 由硬件实现一致性检查和数据类型转换。

  3. 简化程序设计，缩小了人与计算机之间的语义差距。

  4. 简化编译器，使高级语言与机器语言之间的语义差距大大缩短。

  5. 支持数据库系统，一个软件不加修改就可适用于多种数据类型。

  6. 方便软件调试，在每个数据中都有陷井位。

==主要缺点：==

  1. 数据和指令的长度可能不一致

    可以通过精心设计指令系统来解决。

  2. 指令的执行速度降低

    但是，程序的运行时间是由设计时间、编译时间和调试时间共同组成的。

    采用标志符数据表示方法，程序的设计时间、编译时间和调试时间可以缩短。

  3. 硬件复杂度增加

    由硬件实现一致性检查和数据类型的转换。

数据描述符

对于一列数据进行相同的操作,它们具有共同的特征或者说标志。

区别

标志符只作用于一个数据，而数据描述符要作用于一组数据。

==浮点数的表示方法==

image-20220624214820583 image-20220624215146422

变化特征

随着$r_m$的增大，可以表示的最小值减小，可以表示的最大值增大，也就是

image-20220624221940586

尾数下溢的处理方法

注意每种方法的误差计算

  1. 截断法，直接抛弃

    优点：实现简单，不需要增加硬件，不需要处理时间。

    缺点：误差较大，无法调节

  2. 舍入法，四舍五入

    在机器运算的规定字长之外增设一位附加位，存放溢出部分的最高位，每当进行尾数下溢处理时，将附加位加1。

    优点：实现简单，增加硬件少，最大误差小，平均误差为0.

    缺点：处理速度慢，需要花费在附加位上加1以及因此产生的进位时间。

  3. 恒置“1”法

    将有效字长的最低一个位置，设置为$r_m/2$

    优点：实现简单，不需要增加硬件和处理时间，平均误差接近0

    缺点：最大误差比较大

  4. 查表舍入法

    用ROM或者PLA存放下溢处理表。

    优点：速度快，平均误差可以调节到0

    缺点：硬件量大

image-20220625004836952

基本的编址方式,寻址方式和定位方式

编址方式

常见的有位编址,字节编址,字编址,块编址

编址之独立编址：零地址空间的个数

通用寄存器，主存，输入输出设备

  1. 三个零地址空间：各自独立编址
  2. 两个：主存+输入输出，通用寄存器
  3. 一个：最低端是通用寄存器，高端是输入输出设备，中间主存
  4. 隐含编址：Cache与堆栈

交叉编制：高位交叉N/低位交叉Z

给定(i,j)，其中i从0开始，j从0开始，求其所处线性位置；

给定线性位置，求其对应二维位置；

寻址方式

定位方式

定义：研究程序的主存物理地址什么时候确定，采用什么方式实现（也就是逻辑地址和物理地址的转换）

程序为啥需要定位？

直接定位

在程序装入主存储器之前，程序中的指令和数据的主存物理就已经确定了。（一次装入一整个程序，整个系统的地址完全为该程序服务）。

静态定位

在程序装入主存储器的过程中随即进行地址变换，确定指令和数据的主存物理地址。

动态定位

在程序执行过程中，当访问到相应的指令或数据时才进行地址变换，确定指令和数据的主存物理地址。

对应需要增加基址寄存器和地址加法器硬件。基址寄存器存储装入程序的起始地址，加法器硬件将基址寄存器内容与逻辑地址相加，形成物理地址。可在指令中加入相应的标志位来指明指令地址是否需要加基址。

操作码优化设计（也就是减少指令长度）

指令系统优化设计的主要目标是：节省程序的存储空间，指令格式尽量规整，便于译码

对于指令所占内存大小来说，固定长度> 扩展编码> Huffman编码

==信息冗余量的计算：==

$R=\frac{当前长度-最短平均长度}{当前长度}$

固定长操作码

优点：规整，译码简单

缺点：浪费信息量（操作码总长位数增加）

Huffman编码

对发生概率最高的事件用最短的位数（时间）来表示（处理），而对出现概率较低的事件允许使用较长的位数（时间）来表示（处理），使表示（处理）的平均位数（时间）缩短

操作码的==最短平均长度==通过公式计算：其中pi代表第i种操作码在程序中出现的概率。

image-20220625130054037

优点：信息冗余量小

缺点：长度不规整，译码困难；与地址码共同组成固定长的指令比较困难。

扩展编码

长度不是定长，但是只有有限几种码长。仍采用高概率指令短码，低概率指令长码。

附带内容：指令字格式的优化

  1. 扩展编码；2. 多种寻址方式以缩短地址码长度；3. 采用多种地址制；4. 在同种地址制内采用多种地址形式；5. 使用多种不同的指令字长度

RISC 的基本原理和思想、实现的关键技术

RISC基本思想：通过减少指令种类和简化指令功能来降低硬件设计的复杂度，提高指令执行速度

RISC定义与特点：

RISC思想精华：减少CPI

关键技术

延时转移，指令取消，寄存器窗口重叠，指令流调整技术，高速缓冲寄存器Cache，优化设计编译系统；

  1. 延时转移技术：为了流水线不断流，在转移指令后插入一条没有数据相关和控制相关的有效指令，儿转移指令被延迟执行；这一过程由编译器负责。

    限制条件：被移动指令与经过的指令无数据相关；被移动指令不破坏条件码；

  2. 指令取消技术：分两种情况，向后转移（循环程序）+向前转移（条件指令）

    • 向后转移：循环体第一条指令安放在两个位置：循环体之前与循环体条件判断之后。转移成功不取消。（因为循环，希望其转移成功）

      image-20220625151922521

    • 向前转移：转移成功则取消。（因为执行的是不成功的指令）

      image-20220625152111964

  3. 重叠寄存器窗口技术：设置一个数量比较大的寄存器堆，并把它划分成很多个窗口。 在每个过程使用的几个窗口中：

    • 有一个窗口是与前一个过程共用
    • 有个窗口是与下一个过程共用
    image-20220625152405907

  4. 指令流调整技术：通过变量重新命名消除数据相关，提高流水线效率

  5. 采用高速缓冲寄存器Cache：指令Cache和数据Cache

  6. 优化设计编译系统：寄存器优化，指令序列调整，子程序库

第三章 存储系统

存储系统的定义?(组织成一个)

命中率H如何计算?访问周期T和命中率的关系(一路飙升)? 存储系统访问效率e?

啥是并行存储器?有什么显著缺点(4).

交叉访问存储器的加速比N的计算(与转移概率g相关)?两种交叉访问的目的?

虚拟存储器的三种方式的各自的优缺点?

加快内部地址变换的方法?(多级页表,目录表,快慢表,散列函数),如何计算一个给定虚拟地址空间,页面大小和页表项大小的系统需要的多级页表层级数?

如何评价页面替换算法?(命中率,实现难度)有几种?(4),各自的描述?

主存命中率的影响因素有啥?(存,页,调度)各自如何影响的?
与Cache相关的,三种地址映像的绘图?如何计算?

Cache的一致性问题出现的情况?(两种),处理方式,各自的优缺点?(简,可靠,通信次数,硬件)

Cache的预取算法?三种各自的描述?

存储系统定义和评价标准（价格、容量和速度）

命中率的计算H，访问周期与命中率的关系T，存储系统的访问效率e

并行存储器的加速比N=平均有效字的期望

组成存储系统的关键：将速度，容量，价格不同的多个物理存储器组织成一个存储器，其速度最快，容量最大，单位容量价格最便宜。

存储系统的定义

两个或两个以上速度、容量和价格各不相同的存储器用硬件、软件、或软件与硬件相结合的方法连接起来成为一个存储系统。这个存储系统对程序员透明，并且该存储器速度接近速度最快的那个存储器，存储容量与容量最大的那个存储器相等，单位容量的价格接近最便宜的那个存储器。

一般计算机系统有两种存储系统：Cache存储系统（Cache与主存）和虚拟存储系统（主存与外存）。前者目的是加快存储器速度，后者为了扩大存储器容量。

评价标准

  1. 容量：要求提供尽量大的地址空间，可以随机访问

    • 只对系统中存储容量大的编址，其他存储器内部编制/不编址（如Cache）
    • 设计容量很大的逻辑空间，将相关存储器都映射到这个大空间（虚拟存储系统）

  2. 价格：

    计算公式：image-20220625163437857

  3. 速度：访问周期/存取周期/存储周期/存取时间/命中率

    • 在一轮存储器访问过程中，命中率在M1存储器访问到的概率image-20220625163634133

    • 访问周期与命中率的关系

      $$
      T=H \cdot T_1+(1-H)\cdot T_2
      $$
      当命中率趋近于1，T趋近于T1

    • 存储系统的访问效率（与命中率和两级存储器的速度之比有关系）

      image-20220625165802130

      关系图：

      • 当r过大时,前期提高命中率对整个存储系统的效率提升不大
      • 提高存储系统访问效率的方法：提高命中率H，两个存储器的速度相差不要太大。
      • image-20220625170145564

存储系统的层次结构

多层次寄存器：寄存器堆，先行缓冲站，高速缓冲存储器Cache，主存，联机存储器，脱机存储器

并行存储器

指的是将原本m字w位的存储器改变成为m/n字n*w位的存储器。

逻辑上来看,就是指将地址码分为两个部分，一部分负责存储存储器的地址，另一部分选择数据。

缺点：

  1. 取指令冲突：遇到转移指令且转移成功时，一个存储周期内读到的n条指令，后面的几条将无用
  2. 读操作数冲突：一次性读出n个，不一定都有用
  3. 写数据冲突：需要凑齐n个数据之后才一起写入存储器（如果只写一个，需要读入n个，修改一个，写回n个）
  4. 读写冲突：要读入的字和要写入的字同在一个存储器内，无法在一个存储周期完成

交叉访问存储器

  1. 高位交叉访问存储器（使用高位区分存储体）

    目的：扩大存储器容量

  2. 低位交叉访问存储器（使用低位区分存储体）

    目的：提高存储器访问速度

    为了提高速度，通过n个存储体分时启动，近似实现并行存储的读写操作。

并行存储器的加速比N的计算

N也是每个存储周期能够访问到的平均有效字的个数

image-20220625191727648

假设转移概率为g：存储体越多，转移概率越小，加速比越大！

但是随着存储体个数不断增大，存储体个数对有效字长的影响会逐渐减小，例如g=0.2，每五条出现一条转移,即便提高存储体个数,前五个也应当会出现一个转移指令,那么后面的指令冗余

image-20220625192526088

虚拟存储器工作原理（页，段，段页式）

地址组成：

image-20220625192814639

段式虚拟存储器

  1. 地址变换所花费的时间长，两次加法（先找到该用户的段表，找到后做一次加法得到段的起始地址，再做一次加法得到对应段内的具体位置）
  2. 主存储器的利用率往往比较低。
image-20220625193716075

页式虚拟存储器

image-20220625194515080

段页式

image-20220625195102120

加快内部地址变换的方法

解决方法：多级页表

页表级数的计算公式：需要多少个页面(log转换为比特位)/一个页面能够存储多少页表项(log转换为bit位)

image-20220625195516965

内存中必须保留一级页表，把调入到内存中的程序的相关页表保留在内存中，其他存储在磁盘中即可。但由此产生问题：访问内存的次数增加，需要加快查表速度。

页面替换算法

评价算法的指标：

  1. 命中率
  2. 算法是否容易实现

页面替换使用场合：

  1. 虚拟存储器中，主存页面的替换，一般用软件实现。

  2. Cache中的块替换，一般用硬件实现。

  3. 虚拟存储器的快慢表中，快表存储字的替换，用硬件实现。

  4. 虚拟存储器中，用户基地址寄存器的替换，用硬件实现。

  5. 在有些虚拟存储器中，目录表的替换。

随机替换算法

优点：算法简单，容易实现

缺点：没有利用历史信息，没有反映程序的局部性，命中率低

最优替换算法：理想算法，仅用作评价其它页面替换算法好坏的标准。

近期最少用算法LRU：选择近期最少访问的页

优点： 能够比较正确反映程序的局部性，把最久未被访问的页作为被替换页

先进先出算法FIFO：选择最早装入主存的页作为被替换的页

优点：容易实现，利用了历史信息但是没有利用局部性。

主存命中率影响

页面大小

当页面大小为某个值，结果存在最值。

image-20220625204430706

页面大小导致的其他结果：

主存容量

image-20220625204811203

页面调度

请求式：当使用到的时候，再调入主存

预取式：在程序重新开始运行之前，把上次停止运行前一段时间内用到的页面先调入到主存储器，然后才开始运行程序。其主要优点是可以避免在程序开始运行时，频繁发生页面失效的情况；

其主要缺点：如果调入的页面用不上，浪费了调入的时间，占用了主存的资源。

Cache存储系统基本工作原理

image-20220625205447342

地址映像

直接映像

主存储器中一块只能映象到Cache的一个特定的块中，通常是对Cache的块数进行取模。因此，Cache地址与主存储器地址的低位部分完全相同。

用主存地址中的块号B去访问区号存储器，把读出来的区号与主存地址中的区号E进行比较。只有比较相等并且有效位为1，才访问Cache，获得块内内容。为了提高Cache速度，可以将区号存储器和Cache合并成一个存储器。

优点：硬件简单，不需要相联访问存储器；访问速度快实际上不需要进行地址变换。

缺点：块的冲突率比较高。

image-20220625212215158image-20220625212202795

全相联

主存中的任意一块到Cache中的任意一块。

优点：块冲突概率低，空间利用率高。

缺点：相联存储器成本高，查表速度慢。

image-20220625210359843

组相联

主存和Cache划分为大小相同的块和组。组间直接映射，组内全相联映射。

优点：冲突率较低，块的利用率大幅度提高，块的失效率明显降低。

缺点：实现难度和造价比较高。

image-20220625212737832image-20220625212747181

Cache的一致性问题

造成Cache与主存内容不一致的原因：

Cache的更新算法：

写Cache的两种方法：

Cache的预取算法

  1. 按需取。当出现Cache不命中时，才把需要的一个块取到Cache中。

  2. 恒预取。无论Cache是否命中，都把下一块取到Cache中。

  3. 不命中预取。当出现Cache不命中，把本块和下一块都取到Cache中。

主要考虑命中率是否提高，采用恒预取，不命中率降低很多75-85

不命中预取也能降低30-40