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

第二章数据表示与指令系统内容摘要：

址方式： 是指令按什么方式寻找（访问）到所 需的操作数或信息。 • 指令所访问的数据 主存、寄存器、堆栈 • 寻址能力的要求 多样性、灵活性、寻址空间范围大小、地址变换速度 • 目标： 以最短的位描述给定的寻址方式 寻址方式分析  寻址方式在指令中的指明方式 – 占用操作码位： DJS200系列指令系统中 8位操作码最高两位：间接（ 11）和直接（ 01） – 地址码设置寻址方式字段： VAX11指令中源和目的各有 4位寻址方式位字段 主存 —— 直接 、 间接 、 变址 、 基址 、 相对寻址 直接寻址 使指令字变长 间接寻址 使指令执行速度变慢 相对寻址 用于条件转移指令中定位转向后代码的位置 变址寻址 支持向量、数组，实现循环 ，用寄存器做变址器，地址码部分不会很长，访问数据速度相当于一次访问内存的速度 基址寻址 支持逻辑地址到物理地址的变换， 用于程序的动态再定位； 寄存器 —— 直接、间接寻址 以寄存器寻址方式为主的计算机称为通用寄存器型计算机 优点： 指令字长短 执行速度快 支持向量、矩阵运算 缺点： 不利于编译程序的设计 不利于中断和子程序的递归调用 增加了硬件的复杂度  堆栈 —— 堆栈寻址（只对栈顶元素进行操作） 特点： 程序所占主存空间小，指令长度短 支持程序的嵌套和递归调用，支持中断处理 支持高级语言编译  面向主存：主要访问内存，少量访问寄存器 – op m1 m2  面向通用寄存器：多数在寄存器，少量在内存 – op r m 、 op r1 r2  面向堆栈：主要在堆栈，可减轻编译负担 – op、 op m 、 op r (2)寻址方式分类 大多数采用分类编址，有三类： ① 存储效率 ： 堆栈型 〉 通用寄存器型 程序占用空间小 利于减轻对高级语言编译的负担 支持子程序嵌套 、 递归调用 省去大量地址码字段 ， 省空间 ② 运算速度 ：堆栈型 〈 通用寄存器型 堆栈访存次数过多 面向寄存器方式支持向量 、 矩阵 一般在系统中三类寻址方式都应当采用 3. 比较：  寻址方式分析 – 多种寻址方式可以显著减少程序的指令条数，但这同时也可能增加实现的复杂度和使用这些寻址方式的指令的执行时钟周期数 (CPI)，故需对多种寻址方式进行分析 程序定位技术  逻辑地址：程序员编写程序时使用的地址  物理地址：程序在主存中的实际地址  一般来讲，逻辑地址的空间大于物理地址的空间。 因此，映射实际上是压缩。 程序定位技术 – 直接定位 ：程序装入前，编译时就已确定了程序中的指令和数据的主存物理地址 – 静态再定位 ：程序装入时，由定位装入程序把程序的逻辑地址变换成物理地址，而在程序的执行过程中，物理地址不再改变。 – 动态再定位 ：在执行每条指令时才形成访存物理地址的方法。 通过基址寻址来实现 基址寄存器 ＋ 内存 逻辑地址 用户程序 优点：  提高了主存利用率  主存中的同一个程序段可为多个程序共享  支持虚拟存储器 问题：  需要硬件支持，虚拟存储器的软件管理算法也较复杂 指令格式的优化设计  指令 = 操作码 + 地址码  指令格式的优化：如何用最短的位数来表示指令的操作信息和地址信息，使程序中指令的平均字长最短  主要目标 – 节省程序的存储空间 – 指令格式尽量规整，便于译码 1. 操作码的优化设计  操作码主要包括两部分内容 – 操作种类：加减乘除、数据传送、移位、转移、I/O – 操作数描述： 数据类型：定点、浮点、字符（串）、逻辑数、向量 进位制： 16进制 数据字长：字、半字、双字、字节  地址码通常包括三部分内容 – 地址 : 直接、间接地址、立即数、寄存器编号、变址寄存器编号 – 地址的附加信息 : 偏移量、块长度、间距 – 寻址方式 : 直接、间接、立即数、变址、相对寄存器寻址  操作码的三种编码方法 – 固定长度 : 规整性好 , 解码简单 , 占用空间大 – Huffman编码 : 空间小 , 规整性不好 , 解码复杂 – 扩展编码 : 折衷方案  哈夫曼 (Huffman)压缩概念 – 当各种事件发生的概率不均等时 , 采用优化技术对发生 概率较高 的事件用 较短 的位数 (时间 )来表示 (处理 ), 而对出现概率较低的允许用较长的位数 (时间 )来表示 (处理 ), 以达到平均位数最少的目的 用于代码压缩、程序压缩、空间压缩和时间压缩  操作码的优化表示 – 信息源熵 ：信息源包含的平均信息量 – 操作码的优化表示就是要使信息冗余量 R最小 H即为操作码可以达到的最短平均码长 – 信息冗余量 – 实际编码的操作码码长为： 例 ，频度如下 I1 I2 I3 I4 I5 I6 I7 信息源熵 H= 信息冗余量 R=()/3==28% （ 1）等长编码 可用 000～ 110来分别表示 7种不同的指令 I1: 000 I2: 001 I3: 010 I4: 011 I5: 100 I6: 101 I7: 110 （ 2）哈夫曼编码（操作码设计） •表示方法：哈夫曼树 •基本思想 （频率相关思想）： 当事件发生的概率不均等时，对概率高的事件用较短的位数（或时间）来表示，对概率低的事件用较长的位数（或时间）来表示，导致平均位数（时间）最短。 • (1)将事件的使用频度值作为叶结点并按出现频率次序排列； （排序） (2)将出现频率最小的两个事件合并（频率相加）形成一个新结点； （合并） (3)在新组成的叶结点序列中继续做 (2)，直至到根结点（频率＝ 1，构成一棵树 )； (4)从树根起沿左和右子树分别分配其值为 1和 0，直至叶结点； （分配值 ） (5)事件的使用频度值叶结点编码为从根结点到叶结点的编码组合。 （得到编码） 构建方法： 1 0 0 0 0 0 0 1 1 1 1 1 I7 I6 I5 I4 I3 I2 I1 I1 I2 I3 I4 I5 I6 I7 0 10 110 11100 11101 11110 11111 叶结点 根结点 合并结点 由此可得到哈夫曼编码如下： I1: 0 I2: 10 I3: 110 I4: 11100 I5: 11101 I6: 11110 I7: 11111 信息冗余量 R=()/=% 指令长度个数 =4 平均码长 L=*1+*2+*3+*5 +*5+*5+*5 =  Huffman特点 : 平均码长最短 代码不唯一 ：（ 0, 1 可对换） （ 3）哈夫曼扩展编码 （操作码优化） —— 扩展编码法 基本思想：对霍夫曼编码，根据使用频率宏观分布，将编码长度扩展成几种长度的编码。 实现目标：平均码长接近全哈夫曼码的码长， 同时又保持了 定长码的规整性。 Huffman操作码的主要缺点 – 操作码长度很不规整 , 硬件译码困难 – 与地址码共同组成固定长的指令比较困难  例 1: Huffman用四种长度 0, 10, 110, 11100, 11101, 11110, 11111 , , ,  扩展哈夫曼编码如下： I1, I2, I3 用两位 : 00, 01, 10 I4, I5, I6, I7 用四位 : 1100,1101,1110,1111 L=(++)*2+(+++)*4 = 信息冗余量 =()/==% 4 1 1 1 1 5 1 1 1 1 1 I7 4 1 1 1 0 5 1 1 1 1 0 I6 4 1 1 0 1 5 1 1 1 0 1 I5 4 1 1 0 0 5 1 1 1 0 0 I4 2 1 0 3 1 1 0 I3 2 0 1 2 1 0 I2 2 0 0 1 0 I1 OP长度 li huffman扩展编码 OP长度 li 操作码 OP 使用哈夫曼编码 频 度 （ Pi） 指 令 操作码的扩展（等长扩展） 平均码长： 2. 2 扩展方法： 等长扩展 和 不等长扩展 两种。 等长扩展 —— 每次扩展相同的位数 如 4812等长扩展方法（ 每次扩展 4位 ） 不等长扩展 —— 每次扩展不同的位数 如 4610不等长扩展方法 (美国的 B1700) 扩展标志： 保留 码点标志 —— 一组编码作为扩展标志 保留 标志位 —— 一个标志位作为扩展标志 扩展编码中选择某些特征位用于扩展。 0001 0000 1110 15 0000 0001 . . . 1110 15 1111 . . . 1111 1111 . . . 0000 0001 1110 15 1111 . . . 1111 1111 . . . 1111 1111 1111 . . . 8 0 000 0 001 . . . 0 111 64 1 000 1 001 . . . 1 111 512 1 000 1 001 . . . 1 111 0 000 0 001 0 111 1 000 1 001 1 111 0 000 0 001 0 111 . . . . . . 15/15/15扩展法 8/64/512编码法 码点标志 码点标志 保留标志位 保留标志位 4812等长扩展编码  采用保留特征码（码点标志）方法编码简单，但表示的指令总数少。 例如： 4812等长编码， 151515每种长度指令数为15，共可编码 45种 平均每条指令位数 =(4＋ 8＋ 12) 15/45=8  采用保留标志位方法编码较为复杂，但表示的指令总数多。 例如： 4812等长编码， 864512共有指令数为 584 平均每条指令位数＝ （ 8 4＋ 64 8＋ 512 12） /584= 例 2：指令系统共有 42种指令，前 15种使用频率平均为 ，中间 13种使用频率平均为 ，最后 14种使用频率平均为。 如何编码。 0000 ： 15种 1110 1111 0000 ： ： 15种 1111 1110 1111 1111 0000 ： ： ： 15种 1111 1111 1110 解：因频率分布有三种，故码长可有三种； 因每段指令数基本相同，故可采用 等长扩展 (4812位)， 保留特征码的每段指令数相同 (151515)方法。 结果如图所示； 结果：采用 151515扩展方法，最后一种编码用于扩展，每段 0000～ 1110用于编码， 1111用于扩展。 例 3：指令系统共有 74种指令，前 4种使用频率平均为 ，中间 15种使用频率平均为 ，最后 55种使用频率平均为。 如何编码。 解：同上例方法， 码长可有三种； 因每段指令数成比例(1： 4)，故可采用 等长扩展方法 (369位 )扩展 ，保留标志位方法，结果如图所示； 结果：采用 41664扩展方法，编码第一位用于扩展，每段 0XX用于编码， 1XX用于扩展。 0xx。