《《系统结构讲义》PPT课件.ppt》由会员分享，可在线阅读，更多相关《《系统结构讲义》PPT课件.ppt（53页珍藏版）》请在金锄头文库上搜索。
1、第二章第二章 指令系统指令系统 2 3 2 3 指令格式的优化设计指令格式的优化设计 指令格式的优化是指如何用最短的二进制位数表示指令的操作码信息和地 址码信息 使指令的平均字长最短 同时便于译码 指令的组成 操作码地址码 1 指令的操作种类 所用操作数数据 类型 1 操作数地址 2 地址附加信息 3 寻址方式 指令格式的优化设计目标 指令格式的优化设计目标 1 使程序中指令的平均字长最短 节省程序的存储空间 2 指令格式要规整 减少硬件译码的复杂程度 操作码的优化表示操作码的优化表示 操作码的表示方法 操作码的表示方法 1 固定长度操作码 2 Huffman编码法 3 扩展编码法 一 一 固
2、定长度操作码 采用等长操作码 若指令系统共有N种不同功能的指令 则指令系统中的 所有指令的操作码长度固定为 lbN 位 特点 特点 1 1 长度规整 有利于硬件设计 减少指令译码时间 长度规整 有利于硬件设计 减少指令译码时间 2 2 信息冗余 信息冗余 例 假设一台模型计算机共有7种不同的操作码 已知各 种操作码在程序中出现的概率如下表 利用固定长度编码 法进行操作码编码 指令I1 概率0 45 I2 0 30 I3 0 15 I4 0 05 I5 0 03 I6 0 01 I7 0 01 解 由于N 7 因此 指令操作码固定长度为 lbN lb7 3 指令序号概率编码操作码长度 I10 4
3、50003位 I20 300013位 I30 150103位 I40 050113位 I50 031003位 I60 011013位 I70 011103位 编码结果 编码结果 二 二 Huffman编码法 最小概率合并法 Huffman压缩概念 最佳编码定理 当用n个长度不等的代码分别 代表n种发生概率不等的事件时 按照短代码给高概率事件 把长代码给 低概率事件的原则分配 可使平均码长达到最低 Huffman编码方法 这种编码方法由两个过程组成 频度合并 将全部n个事件 在此即为n条指令 的频度值排序 选 取其中最小的2个频度合并 然后将剩下的n 1个频度再次排序 再合并 最小的2个频度 如
4、此重复 直至剩下1个频度为止 记录所有的合并关 系 形成一棵二叉树 Huffman树 所有原始频度值充当树叶 而最后 剩下的总频度1为树根 码元分配 从树根开始 对每个中间结点的左右2个分支边各赋予 一位代码 0 和 1 0 在哪一侧不限 读出从根结点到任一片树叶的路 径上依次出现的代码位就排成了这个事件 即指令 的完整编码 由于 频度高的事件较晚被合并 它的编码位数也就较少 符合Huffman压缩原 则 上面所说的频度值就是各事件实际出现次数的百分比 它是理论出现概率的近似值 例 假设一台模型计算机共有7种不同的操作码 已 知各种操作码在程序中出现的概率如下表 利用Huffman 编码法进行
5、操作码编码 指令I1 概率0 45 I2 0 30 I3 0 15 I4 0 05 I5 0 03 I6 0 01 I7 0 01 Huffman树生成步骤 q 把所有指令按照操作码在程序中出现的概率 自左向右 从排列好 q 选取两个概率最小的结点合并成一个概率值是二者之和 的新结点 并把这个新结点与其它还没有合并的结点一 起形成新结点集合 q 在新结点集合中选取两个概率最小的结点进行合并 如 此继续进行下去 直至全部结点合并完毕 q 最后得到的根结点的概率值为1 q 每个结点都有两个分支 分别用一位代码 0 和 1 表示 注意 对于同一个频度分布 应用哈夫曼算法可能生成不同的哈夫曼树 因此
6、得到的哈夫曼编码并不唯一 但平均码长唯一 0 450 300 150 050 030 010 01 1 00 0 55 0 25 0 10 0 05 0 02 01 0 1 0 1 0 1 0 1 0 1 I1 I2 I3 I4 I5 I6 I7 Huffman编码树生成过程 指令序号概率Huffman编码法操作码长度 I10 4501位 I20 30102位 I30 151103位 I40 0511104位 I50 03111105位 I60 011111106位 I70 011111116位 编码结果 编码结果 编码方法性能指标编码方法性能指标 信息量 信息量 根据信息论的基本知识 在n种
7、可能发生的事件集合中 报告第i 种事件发生的消息中包含的信息量为 其中Pi是第i种事件发生的先验概率 a是编码基值 信息量的单位是表 示位数 最少所需位数 这个定义式表明事件的发生概率越低 关于它的消息中的信息量越大 熵 熵 entropyentropy 平均信息量 平均信息量 一个消息源对n种事件发布的消息的 信息量平均值 记为 平均码长 平均码长 各事件编码长度的数学期望 信息冗余量 信息冗余量 表明消息编码中 无用成分 所占的百分比 从减少存储与传输量的角度看 编码方法的平均码长越短越 好 但是平均码长不可能无限制缩短 它的下限就是熵 即R 0 时 如果短于熵就一定会丢失有用信息 即混淆
8、不同指令 这是不允许的 例 假设一台模型计算机共有7种不同的操作码 如果采用固定 长操作码需要3位 已知各种操作码在程序中出现的概率如下表 计算采用Huffman编码法的操作码平均长度 并计算固定长 操作码和Huffman操作码的信息冗余量 解 Huffman编码结果如 指令序号概率Huffman编码法操作码长度 I10 4501位 I20 30102位 I30 151103位 I40 0511104位 I50 03111105位 I60 011111106位 I70 011111116位 采用Huffman编码法的操作码平均长度 0 45 1 0 30 2 0 15 3 0 05 4 0 0
9、3 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 059 0 01 6 644 0 01 6 644 1 95 位 采用固定长度编码信息冗余量 采用Huffman编码法信息冗余量 与3位定长操作码的冗余量35 相比要小得多 HuffmanHuffman操作码的主要缺点 操作码的主要缺点 1 操作码长度很不规整 硬件译码困难 2 与地址码共同组成固定长的指令比较困难 扩展编码方法 等长扩展法扩
10、展编码方法 等长扩展法 由固定长操作码与Huffman编码法相结合形成 码长表示法 分等长扩展法和不等长扩展法 等长扩展法如4 8 12法 每次加长4位 但这并不能说明具体编码方法 例如下面两种编码 方法都是4 8 12法 码点表示法 例如15 15 15法 8 64 512法 15 15 15法 每一种码长都有4位可编码位 前头可以有相同的扩 展标识前缀 可产生16个码点 即编码组合 但是至多只能 使用其中15个来表示事件 留下1个或多个码点组合作为更长代码 的扩展标识前缀 已经用来表示事件的码点组合不能再作为其它 更长代码的前导部分 否则接收者会混淆 这就是 非前缀原则 8 64 512法
11、 每一种码长按4位分段 每一段中至少要留下1位或 多位作为扩展标识 各段剩下的可编码位一起编码 所产生的码 点用来对应被编码事件 每一段中的标识位指出后面还有没有后 续段 0000 0001 1110 1111 0000 1111 0001 1111 1110 1111 1111 0000 1111 1111 0001 1111 1111 1110 4位长度 的操作码 共有15种 8位长度 的操作码 共有15种 12位长度 的操作码 共有15种 操作码编码说明 0000 0001 0111 1000 0000 1000 0001 1111 0111 1000 1000 0000 1000 10
12、00 0001 1111 1111 0111 4位长度 的操作码 共有8种 8位长度 的操作码 共有64种 12位长度 的操作码 共有512种 操作码编码说明 等长等长15 15 15 15 15 15 扩展法扩展法等长等长8 64 512 8 64 512 扩展法扩展法 例 假设一台模型计算机共有7种不同的操作码 已知各种操作 码在程序中出现的概率如下表 如果采用1 2 3 5和2 4扩展编 码法 计算操作码平均长度和信息冗余量 指令I1 概率0 45 I2 0 30 I3 0 15 I4 0 05 I5 0 03 I6 0 01 I7 0 01 解 采用1 2 3 5扩展编码法操作码平均长
13、度 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 信息冗余量 序号概率1 2 3 5扩展编码 I10 450 I20 3010 I30 15110 I40 0511100 I50 0311101 I60 0111110 I70 0111111 2 4等长扩展编码 00 01 10 1100 1101 1110 1111 平均长度2 02 2 信息冗余量2 5 11 4 7 7条指令的操作码扩展编码法条指
14、令的操作码扩展编码法 指令I1I2I3I4I5I6I7I8I9I10 概率0 250 200 150 100 080 080 050 040 030 02 例 一台处理机有I1 I10共10条指令 经统计 各指令在程序中使用的频率 如下 1 计算这10条指令的操作码编码的最短平均码长 2 写出这10条指令的操作码的哈夫曼编码 并计算编码的平均码长和信 息冗余量 3 采用3 7扩展编码和2 8扩展编码编写这10条指令的操作码 并分别计 算平均码长和信息冗余量 哪种扩展编码比较好 说明理由 解 1 最短平均码长 H pilog2pi 0 25 log20 25 0 20 log20 20 0 15
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 020 030 040 050 080 080 100 150 200 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 0 0 0 020 030 080 100 200 040 050 080 150 25 0 05 0 13 0 43 0
16、 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 IiPi哈夫曼1I1i哈夫曼2I2i I10 25102002 I20 20002102 I30 1511030103 I40 1001031103 I50 081110301104 I60 080110411104 I70 0501114011105 I80 04111105011115 I90 031111106111105 I100 021111116111115 可见 哈夫曼编码不唯一 哈夫曼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 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
