《系统结构讲义-2PPT课件》由会员分享，可在线阅读，更多相关《系统结构讲义-2PPT课件（53页珍藏版）》请在金锄头文库上搜索。
1、 第二章指令系统 2 3指令格式的优化设计 指令格式的优化是指如何用最短的二进制位数表示指令的操作码信息和地址码信息 使指令的平均字长最短 同时便于译码 指令的组成 操作码 地址码 指令的操作种类 所用操作数数据类型 操作数地址 地址附加信息 寻址方式 指令格式的优化设计目标 使程序中指令的平均字长最短 节省程序的存储空间 指令格式要规整 减少硬件译码的复杂程度 操作码的优化表示 操作码的表示方法 固定长度操作码 Huffman编码法 扩展编码法 一 固定长度操作码采用等长操作码 若指令系统共有N种不同功能的指令 则指令系统中的所有指令的操作码长度固定为 lbN 位 特点 长度规整 有利于硬件
2、设计 减少指令译码时间 信息冗余 例 假设一台模型计算机共有7种不同的操作码 已知各种操作码在程序中出现的概率如下表 利用固定长度编码法进行操作码编码 解 由于N 7因此 指令操作码固定长度为 lbN lb7 3 编码结果 二 Huffman编码法 最小概率合并法 Huffman压缩概念 最佳编码定理 当用n个长度不等的代码分别代表n种发生概率不等的事件时 按照短代码给高概率事件 把长代码给低概率事件的原则分配 可使平均码长达到最低 Huffman编码方法这种编码方法由两个过程组成 频度合并 将全部n个事件 在此即为n条指令 的频度值排序 选取其中最小的2个频度合并 然后将剩下的n 1个频度再
3、次排序 再合并最小的2个频度 如此重复 直至剩下1个频度为止 记录所有的合并关系 形成一棵二叉树 Huffman树 所有原始频度值充当树叶 而最后剩下的总频度1为树根 码元分配 从树根开始 对每个中间结点的左右2个分支边各赋予一位代码 0 和 1 0 在哪一侧不限 读出从根结点到任一片树叶的路径上依次出现的代码位就排成了这个事件 即指令 的完整编码 由于频度高的事件较晚被合并 它的编码位数也就较少 符合Huffman压缩原则 上面所说的频度值就是各事件实际出现次数的百分比 它是理论出现概率的近似值 例 假设一台模型计算机共有7种不同的操作码 已知各种操作码在程序中出现的概率如下表 利用Huff
4、man编码法进行操作码编码 Huffman树生成步骤 把所有指令按照操作码在程序中出现的概率 自左向右从排列好 选取两个概率最小的结点合并成一个概率值是二者之和的新结点 并把这个新结点与其它还没有合并的结点一起形成新结点集合 在新结点集合中选取两个概率最小的结点进行合并 如此继续进行下去 直至全部结点合并完毕 最后得到的根结点的概率值为1 每个结点都有两个分支 分别用一位代码 0 和 1 表示 注意 对于同一个频度分布 应用哈夫曼算法可能生成不同的哈夫曼树 因此 得到的哈夫曼编码并不唯一 但平均码长唯一 I1I2I3I4I5I6I7 Huffman编码树生成过程 编码结果 编码方法性能指标 信
5、息量 根据信息论的基本知识 在n种可能发生的事件集合中 报告第i种事件发生的消息中包含的信息量为 其中Pi是第i种事件发生的先验概率 a是编码基值 信息量的单位是表示位数 最少所需位数 这个定义式表明事件的发生概率越低 关于它的消息中的信息量越大 熵 entropy 平均信息量 一个消息源对n种事件发布的消息的信息量平均值 记为 平均码长 各事件编码长度的数学期望 信息冗余量 表明消息编码中 无用成分 所占的百分比 从减少存储与传输量的角度看 编码方法的平均码长越短越好 但是平均码长不可能无限制缩短 它的下限就是熵 即R 0时 如果短于熵就一定会丢失有用信息 即混淆不同指令 这是不允许的 例
6、假设一台模型计算机共有7种不同的操作码 如果采用固定长操作码需要3位 已知各种操作码在程序中出现的概率如下表 计算采用Huffman编码法的操作码平均长度 并计算固定长操作码和Huffman操作码的信息冗余量 解 Huffman编码结果如 采用Huffman编码法的操作码平均长度 0 45 1 0 30 2 0 15 3 0 05 4 0 03 5 0 01 6 0 01 6 1 97 位 最优Huffman编码法的操作码平均长度计算公式 所以 采用最优Huffman编码法的操作码平均长度为 0 45 1 152 0 30 1 737 0 15 2 737 0 05 4 322 0 03 5
7、059 0 01 6 644 0 01 6 644 1 95 位 采用固定长度编码信息冗余量 采用Huffman编码法信息冗余量 与3位定长操作码的冗余量35 相比要小得多 Huffman操作码的主要缺点 操作码长度很不规整 硬件译码困难与地址码共同组成固定长的指令比较困难 扩展编码方法 等长扩展法 由固定长操作码与Huffman编码法相结合形成 码长表示法 分等长扩展法和不等长扩展法 等长扩展法如4 8 12法 每次加长4位 但这并不能说明具体编码方法 例如下面两种编码方法都是4 8 12法 码点表示法 例如15 15 15法 8 64 512法15 15 15法 每一种码长都有4位可编码位
8、 前头可以有相同的扩展标识前缀 可产生16个码点 即编码组合 但是至多只能使用其中15个来表示事件 留下1个或多个码点组合作为更长代码的扩展标识前缀 已经用来表示事件的码点组合不能再作为其它更长代码的前导部分 否则接收者会混淆 这就是 非前缀原则 8 64 512法 每一种码长按4位分段 每一段中至少要留下1位或多位作为扩展标识 各段剩下的可编码位一起编码 所产生的码点用来对应被编码事件 每一段中的标识位指出后面还有没有后续段 00000001 1110 1111000011110001 11111110 111111110000111111110001 111111111110 4位长度的操
9、作码共有15种 8位长度的操作码共有15种 12位长度的操作码共有15种 操作码编码 说明 00000001 0111 1000000010000001 11110111 100010000000100010000001 111111110111 4位长度的操作码共有8种 8位长度的操作码共有64种 12位长度的操作码共有512种 操作码编码 说明 等长15 15 15 扩展法 等长8 64 512 扩展法 例 假设一台模型计算机共有7种不同的操作码 已知各种操作码在程序中出现的概率如下表 如果采用1 2 3 5和2 4扩展编码法 计算操作码平均长度和信息冗余量 解 采用1 2 3 5扩展编码
10、法操作码平均长度 H 0 45 1 0 30 2 0 15 3 0 05 0 03 0 01 0 01 5 2 00信息冗余量 采用2 4扩展编码法操作码平均长度 H 0 45 0 30 0 15 2 0 05 0 03 0 01 0 01 4 2 20信息冗余量 例 一台处理机有I1 I10共10条指令 经统计 各指令在程序中使用的频率如下 1 计算这10条指令的操作码编码的最短平均码长 2 写出这10条指令的操作码的哈夫曼编码 并计算编码的平均码长和信息冗余量 3 采用3 7扩展编码和2 8扩展编码编写这10条指令的操作码 并分别计算平均码长和信息冗余量 哪种扩展编码比较好 说明理由 解
11、1 最短平均码长 H pilog2pi 0 25 log20 25 0 20 log20 20 0 15 log20 15 0 10 log20 10 0 08 log20 08 0 08 log20 08 0 05 log20 05 0 04 log20 04 0 03 log20 03 0 02 log20 02 2 96 位 2 两种哈夫曼树 0 02 0 03 0 04 0 05 0 08 0 08 0 10 0 15 0 20 0 25 0 05 0 09 0 13 0 17 0 23 0 32 0 43 0 57 1 1 0 1 1 1 1 1 1 1 1 0 0 0 0 0 0
12、0 0 0 02 0 03 0 08 0 10 0 20 0 04 0 05 0 08 0 15 0 25 0 05 0 13 0 43 0 23 0 09 0 17 0 32 0 57 1 1 0 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 可见 哈夫曼编码不唯一 哈夫曼1平均码长 I1 Pi I1i 0 25 2 0 20 2 0 15 3 0 10 3 0 08 4 0 08 4 0 05 4 0 04 5 0 03 6 0 02 6 2 99 位 哈夫曼2平均码长 I2 Pi I2i 0 25 2 0 20 2 0 15 3 0 10 3 0 08 4 0 08 4
13、 0 05 5 0 04 5 0 03 5 0 02 5 2 99 位 可见 平均码长唯一 信息冗余量 Rn 1 H I1 1 2 96 2 99 1 0 3 7和2 8扩展编码如下表所示 3 7扩展平均码长 I3 7 Pi I1i 0 25 0 20 0 15 2 0 10 0 08 0 08 0 05 0 04 0 03 0 02 5 3 2 位 2 8扩展平均码长 I2 8 Pi I2i 0 25 0 20 2 0 15 0 10 0 08 0 08 0 05 0 04 0 03 0 02 4 3 1 位 可见 2 8扩展优于3 7扩展 两种编码的信息冗余量 Rn3 7 1 H I3 7
14、 1 2 96 3 2 7 5 Rn2 8 1 H I2 8 1 2 96 3 1 4 5 地址码的优化表示 地址码在指令中所占的长度最长 地址码长度 f 地址码个数 存储设备 寻址空间大小 编址方式 寻址方式 本节解决问题 地址个数的选择单个地址码长度如何优化 地址码个数选择 通常有3个 2个 1个及没有地址码等4种情况 评价指令中地址个数的标准 程序的存储量 即程序中所有指令的长度相加的总和最短 程序的执行速度 即程序在执行过程中访问主存储器的信息 包括指令和数据 量的总和最短 指令字格式优化设计的措施 采用扩展操作码 以缩短操作码的平均码长 采用诸如基址 变址 相对寻址 寄存器寻址 寄存
15、器间接寻址等多种寻址方式 以缩短需要在指令中表示的地址码长度 但不减少地址码寻址空间的大小 指令集采用零地址 一地址 二地址和三地址等多种地址制 且让常用的短操作码与多地址字段配合 长操作码与少地址字段配合 采用R R R M M M等多种地址表示方式 让每种地址字段有多种长度 使长度不等的操作码与地址码配合成规整长度的指令字 在维持指令字在存储器中按整数边界存储的前提下 使用多种不同的指令字长度 要求指令字长应是主存存储字长的整数倍 表2 10各种不同地址数指令的特点及适用场合 各种不同地址数指令的特点及适用场合 地址数目 指令码长度 程序存储量 程序执行速度 使用场合 三地址 短 最大 一
16、般 向量 矩阵运算为主 二地址 一般 很大 很低 一般不宜采用 一地址 较长 较大 较快 连续运算 硬件结构简单 0地址 最长 最小 最低 嵌套 递归 变量较多 二地址R形 一般 最小 最快 多累加器 数据传送较多 例 一台模型机共有7条指令 各指令的使用频率分别为35 25 20 10 5 3 和2 有8个通用数据寄存器 2个变址寄存器 1 要求操作码的平均长度最短 请设计操作码的编码 并计算所设计操作码的平均长度 2 设计8字长的寄存器 寄存器型指令3条 16位字长的寄存器 存储器型变址寻址方式指令4条 变址范围不小于 127 请设计指令格式 并给出各字段的长度和操作码的编码 解 1 要使得到的操作码长度最短 应采用Huffman编码 构造Huffman树如下 由此可以得到7条指令的编码分别如下 这样 采用Huffman编码法得到的操作码的平均长度为 H 2 0 35 0 25 0 20 3 0 10 4 0 05 5 0 03 0 02 1 6 0 3 0 2 0 25 2 35 三条指令的操作码分别为00 01 10设计16位字长的寄存器 存储器型变址寻址方式指令如下 4318
