数据表示、寻址方式、指令系统

本章涉及的公式有

1. 浮点计算公式
2. ROM 查表舍入法
3. 指令格式优化（固、哈、扩）码长公式

真题

简答题（15） ^

【数据表示篇】

简述标志符数据表示的概念和标志符数据表示存在的两个问题 2210

简述数据描述符和标志符的差别 1510 1710 2110

简述标志符数据表示的优点 1610

简述引入数据表示的原则 1604

简述数据表示和数据结构之间的关系及引入高级数据表示的基本原则 1404

简述堆栈计算机的概念及其特点 1804 2204 x

【寻址技术篇】

简述程序的静态再定位和动态再定位的含义及实现方法 1204

【指令系统篇】

简述编译程序设计者要求指令系统应具有的特性。 1810 x

简述CISC存在的问题。0504 0607 1304 1504

简述面向高级语言的优化实现改进CISC指令系统的途径。1710

简述设计RISC的基本原则 2104 1910 1904 1704 0904 0504 0404 x2

简述设计RISC结构采用的基本技术。 2010 1204 1004 0807 x1

简述设计RISC结构的重叠寄存器窗口技术。1410

简述RISC的优缺点。 1107 1104

简述指令字格式优化措施 1604

应用题

尾数下溢-ROM查表舍入法

image-20230305154700715

image-20230306212427696

尾数计算 ** **

image-20230305154420434

image-20230305154540621

image-20230402154912066

image-20230305154728498

image-20230305154746693

image-20230305154840872

指令格式优化

1204、2104、2204、2210

image-20230319154548356

image-20230319154445488

image-20230319154651965

1、数据表示 ^ *

简简述标志符数据表示的概念和标志符数据表示存在的两个问题 2210

简简述数据描述符和标志符的差别 1510 1710 2110

简简述标志符数据表示的主要优点 1610

简简述引入数据表示的原则 1604

简简述数据表示和数据结构之间的关系及引入高级数据表示的基本原则 1404

数据表示：能由计算机硬件识别和引用的数据类型。它里头有可对数据进行操作的指令和运算部件。计算机的运算类指令和运算器结构主要是按计算机有什么样的数据表示来确定的。 ^

数据结构：串、队、栈、向量、阵列、链表、树、图等由软件处理的数据结构，反映应用中要用到的各种数据元素或信息单元之间的结构关系。 ·

image-20230207215722811

高级数据表示

1. 标志符数据表示 *
2. 数据描述符 *
3. 向量、数组数据表示
4. 堆栈数据表示

标志符数据表示 ^ *

标志符数据表示：将数据类型和数据放在一起。

图标志符数据表示的表示形式

IMG_9708

标志符数据表示的主要优点：

1. 简化指令系统、程序设计以及编译程序；
2. 由硬件实现一致性检查和数据类型转换；
3. 便于软件调试且支持数据库系统。

标志符数据表示可能带来两个问题：

1. 增加程序占用的主存空间。
2. 降低指令的执行速度。

数据描述符

为进一步减少标志符所占用的存储空间，对向量、数据、记录等数据，采用数据描述符，因为他们的元素属性相同。

图数据描述符的表示形式

image-20230207220205894

image-20230207220445277

标志符与数据描述符的区别 ^*

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

标志符与数据存放在一起，而描述符与数据分开存放。

向量、数组数据表示 ·

为向量、数组数据结构的实现和快速运算提供更好的硬件支持的方法是增设向量数据表示，组成向量机，如 CRAY-1。有向量数据表示的处理机就是向量处理机，如向量流水机、阵列机、相联处理机。

图

image-20230207221205738

堆栈数据表示 ^ *

堆栈数据结构在编译和子程序调用中很有用，为高效实现，很多机器都设置有堆栈数据表示。有堆栈数据表示的计算机称为堆栈计算机。

通用寄存器型机器对堆栈数据结构实现的支持较差，所以出现了堆栈计算机，其特点：

1. 由高速寄存器组成的硬件堆栈。
2. 有丰富的堆栈操作指令，功能强大。
3. 支持高级语言编译、子程序的嵌套和递归调用。

数据表示的引入原则 * ^

1. 看系统的效率是否显著提高，包括实现时间和存储空间是否显著减少。
2. 看引入这种数据表示后，其通用性和利用率是否提高。

2、浮点数 ** *

• 📚 🇺🇸 兰德尔E.布莱恩特 深入理解计算机系统（第3版）ch2
• 📚 🇺🇸 贝赫鲁兹·佛罗赞 计算机科学导论（第4版） ch3
• 📚 🇺🇸 内尔·戴尔 计算机科学概论（第7版） ch3
• 📚 🇨🇳 李学干 计算机系统机构（12版） ch2

表示方式

IMG_8AA2772363DC-1 3

• 尾数：数制（小数或整数）和码制（原码或补码）
  • 尾数基值($r_m$)：2、4、、8、16和10进制。
  • 尾数位数($m$)：决定可表示数的精度
• 阶码（$2^p$）：整数，移码（偏码、增码、余码）或补码。
  • 阶码基值：通常为2进制。
  • 阶值位数($p$)：决定可表示数的范围

结论：尾数决定了浮点数的表示精度，阶值决定了浮点数的表示范围。 简记：尾数决定精度，阶值决定范围

什么是规格化正尾数？

正尾数小数点后的第1个r_m进制数位不是0的数。 ^

计算公式** ** ^ x3

规律：一般地，$r_m$都是2的整次幂，因此 $r_m^{m{\prime}}=2^m$

计算尾数最值及个数、阶的最值及个数、可表示数的最值及个数。

image-20230319144645762

浮点数计算

浮点数尾数基值大小分析（讨论 $r_m$ 取值）[**^]

尾数基值增大，会扩大浮点数表示范围，增加可表示数的个数，减少移位次数，降低右移造成的精度损失，提高运算速度，但也会降低数据的表示精度，数值的分布变稀疏。

• $r_m$ ↑ ，可表示数的范围 ↑

• $r_m$ ↑ ，可表示数的个数 ↑

• $r_m$ ↑ ，运算速度 ↑

• $r_m$ ↑ ，数在数轴上的（密度）分布 ↓

• $r_m$ ↑ ，可表示数的精度 ↓

• $r_m$ ↑ ，精度损失 ↓

因此，可简记：尾基与范个速成正相关，与密精损成负相关。 ^

选浮点数尾数基值大小分析

image-20230305154137350

尾数下溢处理方法 * **

处理办法：简记：截舍恒查

• 截断法。实现最简单。平均误差最大。
• 舍入法。最大误差小，平均误差趋于0。
• 恒置1法。最大误差最大，平均误差趋于0，下溢处理不耗时。
• 查表舍入法。实现最复杂

2210：平均误差最大的是？截断法。

1204#5A：实现最简单：截断法。

1404#3D：最大误差最大，平均误差趋于0，下溢处理不耗时：恒置1法。

查表舍入法 *

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

查表舍入法的优缺点：

• 优点：速度快，平均误差可调节到0；
• 缺点：硬件量大

查表舍入法填下溢处理表的规则，直接以真题为例 ^

image-20230305154700715

image-20230306212427696

3、寻址技术

1. 编址方式 ·
2. 寻址方式 *
3. 定位方式 *

编址方式

寻址方式^

寻址方式：指令寻找操作数或信息的方式。

寻址方式的三种面向

面向主存、寄存器、堆栈三种寻址方式。 简记：主寄堆

程序在主存中的定位技术

简简述程序的静态再定位和动态再定位的含义及实现方法 1204

• 静态再定位：程序执行时物理地址不改变。实现方法：在程序装入主存时，由装入程序用软件方法把程序的逻辑地址变换成物理地址。
• 动态再定位：在执行每条指令时才形成访存物理地址。实现方法：程序执行时，通过地址加法器将逻辑地址和程序基址相加后形成访存物理地址。
• 虚拟地址映像表。存储体系采用该技术实现定位程序在主存中的位置。

首先，弄清逻辑地址和主存物理地址：逻辑地址：程序员编程用的地址；主存物理地址：程序在主存中的实际地址；这两个术语适用于整个计算机体系。

4、指令系统*^

指令系统的组成

图指令系统的组成

image-20220803194605016

操作码由两部分组成：-

• 操作种类：加减乘除、移位、转移、输入输出等
• 操作数描述：定点数、浮点数等

地址码由三部分组成：-

• 地址：地址码、立即数、寄存器、变址寄存器。
• 地址的附加信息：偏移量、块长度、跳距。
• 寻址方式：直接寻址、间接寻址、变址寻址等

指令系统的设计

指令系统的设计包括指令功能和指令格式的设计。 ^

编译程序设计者要求指令系统应具有的特性：
简记：规整与对称、独立与全能、可扩与可组、还有正交性。

• 规整性。对相似操作做相同规定。
• 对称性。对称性操作的定义相同，便于编译。
• 独立性与全能性。有多种程序选择实现同一种功能，应限定只能有一种选择方式。
• 可扩充性。要留有一定数量的冗余操作码，以便新指令的扩充。
• 可组合性。所有操作对各种寻址方式和数据类型都适应。
• 正交性。指令中各个不同含义的字段，在编码时互不相关，相互独立。

指令系统的优化*

• 指令操作码的优化，比如有哈夫曼编码、扩展码。
• 指令字格式的优化。

👉🏻 指令格式优化

指令操作码的3种优化

1. 固定长度
2. 哈夫曼（Huffman）编码 *
3. 扩展编码

优化操作码编码的目的：节省程序存储空间。

image-20220807134512309

固定长度编码

码长公式：
$$
\left\lceil\log _2 n\right\rceil
$$

Huffman编码

哈夫曼压缩概念：当各种事件发生的概率不均等时，采用优化技术，对发生概率最高的事件用最短的位数（时间）来表示（处理），而对出现概率较低的事 件允许使用较长的位数（时间）来表示（处理），使表示（处理）的平均位数（时间）缩短。

如何构造哈夫曼树？

需要学会构造哈夫曼树，利用哈夫曼树进行操作码编码，如何构造哈夫曼树？可以参考《数据结构》笔记。

构造哈夫曼树口诀：

1. 构造森林全是根
2. 选用两小造新树
3. 删除两小添新人
4. 重复2、3剩单根

哈夫曼编码的相关公式：

• 操作码平均码长的公式 $H=log_2n$
• 操作码最短平均长度的公式 $H_opt$
• 信息冗余量的公式 $R$

以下面例题展示公式的具体应用：

重点关注： 使用频度（$p_i$）和 OP长度（$l_i$）

image-20220413225838893

image-20220413225920978

扩展编码

image-20221012125359565

扩展编码的思想：界于定长二进制编码和完全哈夫曼编码之间的一种编码方式，操作码的长度不是定长的，但是只有有限几种码长。仍然采用高概率指令用短码、低概率指令用长码的哈夫曼编码思想。该思想是为了解决解决哈夫曼编码造成的“编码种类多导致不便译码”的问题。

扩展编码法具体是怎么个扩展的？依据是什么？

指令格式的优化措施 **

从指令的组成和设计谈优化：

• ∵ 指令=操作码+地址码
• ∴ 从缩短码长的角度，可以用扩展码优化操作码；用多种寻址方式优化地址码。
• ∴ 从增强功能的角度，可以用多种地址制、地址形式以及指令字长度等方式增强指令功能。

指令系统的改进

• 面向 CISC
• 面向 RISC*

CISC 复杂指令系统

问题所在

1. 指令系统庞大、 操作繁杂
2. 指令执行速度低、使用频度低

优化途径^*

简记：操高目

• 面向目标程序
• 面向高级语言
• 面向操作系统

面向目标程序的优化实现改进

1. 增强使用频度高的指令
2. 增强运算型、传输型、程序控制型指令的功能

面向高级语言的优化实现改进

1. 根据高级语言语句的使用频率进行优化改进
2. 面向编译，优化代码生成
3. 改进指令系统，缩小语义差异
4. 采用面向问题动态自寻优的系统结构
5. 发展高级语言机器

面向操作系统的优化实现改进

RISC 精简指令系统

RISC 设计原则

1. 选择使用频率高的指令，
2. 让所有指令在一个机器周期内完成。
3. 减少指令系统的寻址方式
4. 精简指令、优化编译程序。
5. 扩大通用寄存器的数量。
6. 多数指令使用硬联控制实现。

RISC基本技术 * **

1. 按照RISC设计原则设计
2. 逻辑实现采用硬联与微程序相结合
3. 在CPU中设置工作寄存器并采用重叠寄存器窗口。
4. 指令采用流水和延迟转移
5. 指令和数据存放在Cache中
6. 优化编译程序设计

延迟转移技术 ** （借助慕课巩固下认知）

为了使指令流水线不断流，在转移指令之后插入一条没有数据相关和控制相关的有效指令，使转移指令被延迟执行。

重叠寄存器窗口技术：

在 RISC 中，因为子程序比 CISC 多，所以传送参数会大量地访问存储器信息。这时可通过重叠寄存器窗口技术来减少访存频率，提高系统效率，具体做法：每个过程都有寄存器窗口，各个过程的寄存器窗口部分重叠。

image-20230211125237456

RISC优缺点

• 优点：设计简单、速度快、成本低、
  • 简化指令系统和编译程序的设计。
  • 提高系统的执行速度和可靠性。
  • 降低设计成本，支持高级语言实现。
• 缺点：编程复杂度高
  • 加重汇编语言程序设计的负担。
  • 对浮点运算和虚拟存储器的支持还不够。