系统结构讲义2.ppt

第二章 指令系统;2.3 指令格式的优化设计;操作码的优化表示;例：假设一台模型计算机共有7种不同的操作码，已知各种操作码在程序中出现的概率如下表，利用固定长度编码法进行操作码编码。;指令序号;二、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”表示。 注意： 对于同一个频度分布，应用哈夫曼算法可能生成不同的哈夫曼树，因此，得到的哈夫曼编码并不唯一，但平均码长唯一。;0.45;指令序号;编码方法性能指标;平均码长：各事件编码长度的数学期望。;例：假设一台模型计算机共有7种不同的操作码，如果采用固定长操作码需要3位。已知各种操作码在程序中出现的概率如下表，计算采用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编码法信息冗余量： 与3位定长操作码的冗余量35％相比要小得多。 Huffman操作码的主要缺点： 操作码长度很不规整，硬件译码困难 与地址码共同组成固定长的指令比较困难;扩展编码方法（等长扩展法）;0000 0001 …… 1110;例：假设一台模型计算机共有7种不同的操作码。已知各种操作码在程序中出现的概率如下表，如果采用1-2-3-5和2-4扩展编码法，计算操作码平均长度和信息冗余量。;序号;指令;0.02;0.02;Ii;哈夫曼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/8扩展编码如下表所示：;Ii;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)=1-2.96/3.2=7.5% Rn2/8=(1-H/I2/8)=1-2.96/3.1=4.5%;地址码的优化表示;指令字格式优化设计的措施;表2.10 各种不同地址数指令的特点及适用场合 ; 例：一台模型机共有7条指令，各指令的使用频率分别为35%，25%，20%，10%，5%，3%和2%，有8个通用数据寄存器，2个变址寄存器。 （1）要求操作码的平均长度最短，请设计操作码的编码，并计算所设计操作码的平均长度。 （2）设计8