第二章 指令系統.pptVIP

第二章 指令系统 2.3 指令格式的优化设计 指令格式的优化是指如何用最短的二进制位数表示指令的操作码信息和地址码信息，使指令的平均字长最短，同时便于译码。 指令的组成 操作码 地址码 指令的操作种类。 所用操作数数据类型。 操作数地址。 地址附加信息。 寻址方式。 指令格式的优化设计目标： 使程序中指令的平均字长最短，节省程序的存储空间。 指令格式要规整，减少硬件译码的复杂程度。 操作码的优化表示 操作码的表示方法： 固定长度操作码。 Huffman编码法。 扩展编码法。 一、固定长度操作码 采用等长操作码。 若指令系统共有N种不同功能的指令，则指令系统中的所有指令的操作码长度固定为[lbN]位。 特点： 长度规整，有利于硬件设计，减少指令译码时间。 信息冗余。 例：假设一台模型计算机共有7种不同的操作码，已知各种操作码在程序中出现的概率如下表，利用固定长度编码法进行操作码编码。 解：由于N=7 因此，指令操作码固定长度为 [lbN]=[lb7]=3 编码结果： 二、Huffman编码法（最小概率合并法） Huffman压缩概念（最佳编码定理）：当用n个长度不等的代码分别代表n种发生概率不等的事件时，按照短代码给高概率事件、把长代码给低概率事件的原则分配，可使平均码长达到最低。 Huffman编码方法 这种编码方法由两个过程组成。 频度合并：将全部n个事件（在此即为n条指令）的频度值排序，选取其中最小的2个频度合并，然后将剩下的n-1个频度再次排序，再合并最小的2个频度，如此重复，直至剩下1个频度为止。记录所有的合并关系，形成一棵二叉树 ── Huffman树，所有原始频度值充当树叶，而最后剩下的总频度1为树根； 码元分配：从树根开始，对每个中间结点的左右2个分支边各赋予一位代码“0”和“1”（“0”在哪一侧不限）。读出从根结点到任一片树叶的路径上依次出现的代码位就排成了这个事件（即指令）的完整编码。由于频度高的事件较晚被合并，它的编码位数也就较少，符合Huffman压缩原则。 上面所说的频度值就是各事件实际出现次数的百分比，它是理论出现概率的近似值。 例：假设一台模型计算机共有7种不同的操作码，已知各种操作码在程序中出现的概率如下表，利用Huffman编码法进行操作码编码。 Huffman树生成步骤： 把所有指令按照操作码在程序中出现的概率，自左向右从排列好。 选取两个概率最小的结点合并成一个概率值是二者之和的新结点，并把这个新结点与其它还没有合并的结点一起形成新结点集合。 在新结点集合中选取两个概率最小的结点进行合并，如此继续进行下去，直至全部结点合并完毕。 最后得到的根结点的概率值为1。 每个结点都有两个分支，分别用一位代码“0” 和“1”表示。 注意： 对于同一个频度分布，应用哈夫曼算法可能生成不同的哈夫曼树，因此，得到的哈夫曼编码并不唯一，但平均码长唯一。 I1 I2 I3 I4 I5 I6 I7 Huffman编码树生成过程 编码结果： 编码方法性能指标 信息量：根据信息论的基本知识，在n种可能发生的事件集合中，报告第i种事件发生的消息中包含的信息量为： 其中Pi是第i种事件发生的先验概率，a是编码基值。信息量的单位是表示位数（最少所需位数）。 这个定义式表明事件的发生概率越低，关于它的消息中的信息量越大。 熵（entropy）── 平均信息量：一个消息源对n种事件发布的消息的信息量平均值，记为： 平均码长：各事件编码长度的数学期望。 信息冗余量：表明消息编码中“无用成分”所占的百分比。 从减少存储与传输量的角度看，编码方法的平均码长越短越好。但是平均码长不可能无限制缩短，它的下限就是熵（即R=0时）。如果短于熵就一定会丢失有用信息（即混淆不同指令），这是不允许的。 例：假设一台模型计算机共有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.059＋0.01×6.644＋