第二章 数据表示与指令系统

习题2.10

2.1 数据表示

基本概念

• 数据类型：计算机系统使用和处理的数据类型，整数、布尔数、字符、文件、图、表、树、阵列、队列、链表、栈、向量、串
• 数据表示：硬件直接识别和引用，有相应运算指令和硬件支持，定点数据表示、逻辑数据表示、浮点数据表示
• 数据结构：带有结构的数据元素的集合，串、队列、栈、向量、阵列、链表、树、图
• 关系
  • $数据表示\subseteq 数据类型$ $数据结构\subseteq 数据类型$
  • 数据表示：硬件容易实现的简单数据类型
  • 数据结构：软件实现，转换为数据表示

基本数据表示

• 内容：定点数、浮点数、十进制数、逻辑数、字符等
• 目的：支持数据结构，提高系统性能
• 设计：根据应用需求，设计参数指标

浮点数数据表示

• 浮点数格式
  • N=m⋅rmeN = m \\cdot r_m^eN=m⋅rme​ 其中 e=rege = r_e^ge=reg​
    • 两数：$m$ 尾数，$e$ 阶码
    • 两基：rmr_mrm​ 尾数基，rer_ere​ 阶码基
  • 1 位 mfm_fmf​ | 1 位 efe_fef​ | q 位 $e$ | p 位 $m$
    • 两符号：mfm_fmf​ 尾数符号，efe_fef​ 阶码符号
    • 两字长：$p$ 尾数字长，$q$ 阶码字长
• rmr_mrm​ 尾数基值选择
  • rmr_mrm​ 加大，表数范围加大。表数个数增多。表数精度变低。运算精度损失变小。运算速度变快
  • 巨/大/中型机 rmr_mrm​ 宜取大，尾数字长较长弥补精度损失
  • 小/微型机 rmr_mrm​ 宜取小，提高精度弥补尾数字长较短
• 尾数下溢处理方法（$p+g$ 位尾数）
  • 截断法（恒舍法）：舍去 g 位
  • 恒置法：p 的最低一位置为 rm/2r_m/2rm​/2
  • 下舍上入法：g 位中间值为界，小于舍去，大于等于则入
  • R*舍入法：判断 g 位代码是否为 10…00，再用下舍上入法或恒置法
  • 查表法：见下图
• 警戒位
  • 作用：
    • 左规格化时移入尾数有效字长内
    • 舍入
  • 来源
    • 做加、减法时，因对阶从有效字长内移出去的部分。
    • 做乘法时，双倍字长乘积的低字长部分。
    • 做除法时，因没有除尽而多上商的几位。
    • 右规格化时移出有效字长的那部分。
    • 从十进制实数转换成二进制浮点数时，尾数超出有效字长的那部分。
• 浮点数格式设计
  • 多数机器
    • 尾数：原码、小数、尾数基 rm−2r_m - 2rm​−2
    • 阶码：移码、整数、阶数基 re−2r_e - 2re​−2
  • 规格化浮点数的表数精度最高

高级数据表示

• 内容：堆栈、向量、数组（队列）、记录、自定义数据表示等
• 目的：支持数据结构，提高系统性能
• 问题：高级语言与机器语言存在语义差距
• 解决方法
  • 带标志符的数据表示法
    • 数据格式：标志符+数值
    • 标识符：编译器或其他软件设置，对程序员和用户透明
    • 存储空间分析：数据字长加长，指令字长缩短
    • 优缺点
      • 优点
        • 简化指令系统和程序设计
        • 简化编译程序
        • 便于硬件实现一致性校验
        • 能由硬件自动完成数据类型的变换
        • 为软件调试和应用软件开发提供支持
      • 缺点
        • 数据和指令的长度可能不一致
        • 指令执行速度降低
        • 硬件复杂度增加
  • 数据描述符表示法

2.2 指令集结构的分类

分类依据

• CPU中操作数存储方法（主要准则）
  • 堆栈型指令系统
    • 优点：指令长度短，代码密度高，占用存储空间小
    • 缺点：代码效率低，执行效率不高
  • 累加器型指令系统
    • 优点：指令长度短，代码密度高，代码效率高
    • 缺点：执行效率不高
  • 寄存器型指令系统（主流结构：通用寄存器型）
    • 优点：指令简单，执行效率高，对编译程序支持好
    • 缺点：指令长度长
• 指令中显式操作数个数
• 寻址方式
• 操作类型
• 操作数类型和大小

通用寄存器型指令系统

指令系统选择

• 指令执行效率
• 寄存器个数，操作数个数
• OS 对编译程序的支持

2.3 寻址技术

常用寻址方式

寻址方式选择：频度分析法

寻址方式参数选择：频度分析法

定位方式

• 直接定位方式
  • 在程序装入主存储器之前，程序中的指令和数据的主存物理地址就已经确定
• 静态定位方式
  • 在程序装入主存储器的过程中随即进行地址变换，确定指令和数据的主存物理地址
• 动态定位方式
  • 在程序执行过程中，当访问到相应的指令或数据时才进行地址变换，确定指令和数据的主存物理地址

2.4 指令格式的优化设计

指令的组成

• 指令：操作码+地址码
  • 操作码：操作种类、操作数类型
  • 地址码：操作数地址、地址附加信息、寻址方式

优化目标

• 节省存储空间
• 指令格式规整，减少硬件译码复杂度

操作码优化

• 评价方法
  • 平均码长：l=∑i=1npi⋅lil = \\sum_{i=1}^{n}p_i \\cdot l_il=∑i=1n​pi​⋅li​
    • pip_ipi​ 第 i 种操作码在程序中出现的概率
    • lil_ili​ 第 i 种操作码的编码长度
    • $n$ 操作码的总数
  • 信息冗余量：R=1−HlR = 1-\\frac{H}{l}R=1−lH​
    • H=−∑i=1npi⋅log⁡2piH = -\\sum_{i=1}^{n}p_i \\cdot \\log_{2}{p_i}H=−∑i=1n​pi​⋅log2​pi​ 信息熵，理论最短平均码长
• 编码方法
  • 固定长度操作码
    • $n$ 种操作码 $\\left \\lceil \\log_{2}{n} \\right \\rceil $ 位操作码
    • 特点：规整，硬件译码简单，浪费严重
  • 哈夫曼编码
    • 特点：最优化编码，平均码长最短，信息冗余量最小，不规整
    • 编码方法
      • 从小到大排列概率
      • 最小两个合并，节点值为概率和
      • 最后得到一个概率为 1 的节点
      • 每个节点两个分支，左 0 右 1
      • 从 1 节点到指令节点的路径代码为指令编码
  • 扩展编码法
    • 对哈夫曼编码，根据频率分布，将编码长度扩展成有限几种长度
    • 等长扩展
      • 4-8-12（15/15/15）
      • 4-8-12（8/64/512）
    • 不等长扩展
      • 4-6-10（15/3/16，8/31/16，8/30/32，8/16/256，4/32/256）

地址码优化

• 地址个数
• 优化单个地址码
  • 目的：较短地址码表示较大逻辑地址空间
  • 方法
    • 寄存器间接地址（最有效）
    • 间址寻址
    • 变址寻址

指令字格式优化

• 问题：操作码和地址码优化使得指令字不定长
• 合理结合，长操作码 + 短地址码

2.5 指令集结构的功能设计

性能

• 完整性：通用计算机应具备的基本指令种类
• 高效率：执行速度快，使用频度高
• 兼容性：计算机系统的生命力之所在
• 规整性：硬件和软件设计需要
  • 对称性：数据存储设备的使用、操作码的设置要对称
  • 均匀性：不同数据类型、字长、操作种类和数据存储设备，指令同等对待

基本指令系统

• 数据传送类指令
• 运算类指令
• 程序控制指令
• 输入输出指令
• 处理机控制和调试指令

复杂指令系统（CISC）

• 思想：增强原有指令功能，设置复杂指令取代软件子程序的功能，实现软件功能硬化
• 面向目标程序优化
  • 目的：减少程序时空复杂度
  • 指令使用频度
    • 静态使用频度：源代码统计，减少空间复杂度
    • 动态使用频度：运行时统计，减少时间复杂度
    • $指令动态使用频度\approx 指令静态使用频度$
  • 优化方法
    • 高频率指令：增强功能，加快速度，缩短字长
    • 高频率指令串：新指令替代
    • 低频率指令：取消或合并，考虑兼容性
• 面向高级语言优化
  • 目的：减小高级语言和机器语言的语义差距，精简编译器，缩短编译时间
  • 优化方法
    • 增强对高级语言支持的指令的功能：优化高级语言
    • 增强对编译程序支持的指令的功能
      • 同时面向各种高级语言优化：使指令系统与各高级语言的语义差距共同缩小
      • 动态自适应指令系统：面向各高级语言的多种指令系统和系统结构，动态切换
    • 高级语言计算机：高级语言和机器语言无语义差距
      • 间接执行高级语言机器：高级语言 = 汇编语言 -> 机器语言
      • 直接执行高级语言机器：高级语言 = 机器语言
• 面向操作系统优化
  • 目的：减少操作系统辅助操作时间和存贮空间
  • 优化方法
    • 操作系统常用指令（串）频率统计，分析改造
    • 增设 OS 专用指令
    • 软件子程序改用硬件/固件实现

精简指令系统（RISC）

• CISC 问题
  • 指令系统复杂
  • 执行速度慢
  • 编译程序难优化
  • 80% 指令只在 20% 运行时间用到
• RISC 定义
  • Carnegie -Mellon大学：大多数指令为单周期，LOAD/STORE结构，硬布线控制逻辑，减少指令和寻址方式的种类，固定的指令格式，注重编译优化技术
  • IEEE的Michael Slater：使流水线处理高效率执行，优化编译器并生成优化代码
• RISC 思想：减少 CPI
• RISC 关键技术
  • 硬件为主固件为辅
  • 在CPU中设置数量较大的寄存器组
    • 重叠寄存器窗口技术
      • 目标：缩短 CALL、RETURN 操作时间
      • 方法：设置大量寄存器，分多组和一个全局区，每组分高、本、低三区，相邻组的高、低区重叠，不同过程使用不同组和共享全局区
      • 寄存器设置：嵌套调用不超过 8 层，每层 24 个寄存器（每个区8个寄存器）可基本满足要求，不满足概率为 1% 左右（可使用主存缓冲）
  • 指令流水执行
    • 延时转移技术
      • 两个限制条件
        • 被移动指令移动过程中与所经过的指令无数据相关
        • 被移动指令不破坏条件码，至少不影响后续指令使用条件码
      • 找不到符合条件的指令：转移指令后面插入空操作，分多个流水段则插入多条指令
    • 指令取消技术：找不到适合转移的指令时使用，尽量少取消指令
      • 向后转移：loop结构
        • 能够使指令流水线在绝大多数情况下不断流，因为绝大多数情况下，转移是成功的
      • 向前转移：if-then-else结构
        • 成功与不成功的概率通常各为50%，效果就不明显。用于转移不成功为主的场合
      • 隐含转移：if-then结构
        • 用于转移成功为主的场合
  • 设计和优化编译系统
    • 指令流调整技术
      • 通过调整指令序列，变量重新命名消除数据相关
• RISC 特点
  • 优点
    • 简化指令系统设计，适合VLSI实现
    • 提高执行速度和效率
    • 降低设计成本，提高了系统的可靠性
    • 可以提供直接支持高级语言的能力，简化编译程序的设计
  • 缺点
    • 加重了汇编语言程序员的负担
    • 对浮点运算和虚拟存储器的支持不够理想
    • 相对来说，RISC机器上的编译程序要比CISC机器上的难写

综合实例 MIPS 指令集

概述

• MIPS计算机：简单 64bit load-store 系统结构的 RISC 计算机
• 寄存器
  • 整数寄存器：32 个 64bit 通用寄存器（GPR），R0 永远为零
  • 浮点寄存器：32 个 64bit 浮点数寄存器（FPR），F0~F31
  • 特殊寄存器：浮点状态寄存器等
• 数据表示
  • 整数：字节（8bit）半字（16bit）字（32bit）双字（64bit）
  • 浮点数：单精度（32bit）双精度（64bit）
• 寻址方式：字段长度都为 16bit
  • 只有：立即数、偏移寻址
  • 注意：寄存器间接寻址、16bit绝对寻址
• 指令格式
  • 固定长度：32bit
  • 6bit 操作码，包含寻址方式
• 操作
  • ALU 操作
  • 分支与跳转
  • load/store 操作
  • 浮点数操作：加、减、乘、除，后缀S为单精度，后缀D为双精度