计算机指令格式的优化-课件（PPT·精·选）.ppt

指令的组成
一般的指令主要由两部分组成:
 
操作码通常包括两部分内容:
操作种类:加、减、乘、除、数据传送、移位、转移、输入输出
操作码(OPC)
地址码(A)
指令格式的优化(P90)
主要目标:节省程序的存储空间,指令格式尽量规整
研究内容:操作码优化表示, 地址码优化表示
操作数描述
数据的类型:定点数、浮点数、复数、字符、字符串、逻辑数、向量
进位制:2进制、10进制、16进制
数据字长:字、半字、双字、字节
地址码通常包括三部分内容:
地址:还包括间接地址、立即数、寄存器编号、变址寄存器
地址的附加信息:偏移量、块长度、跳距
寻址方式:直接寻址、间接寻址、立即数寻址、变址寻址、相对寻址、寄存器寻址
操作码优化
目前常用编码方法有3种:定长编码,Huffman编码,扩展编码。
编码方法性能指标(P91-P93)
信息量:根据信息论的基本知识,在n种可能发生的事件集合中,报告第i种事件发生的消息中包含的信息量为
其中Pi是第i种事件发生的先验概率,a是编码基值。信息量的单位是表示位数(最少所需位数)。
这个定义式表明事件的发生概率越低,关于它的消息中的信息量越大。
熵(entropy)──平均信息量:一个消息源对n种事件发布的消息的信息量平均值,记为
平均码长:各事件编码长度的数学期望。
信息冗余量:它表明消息编码中“无用成分”所占的百分比。
从减少存储与传输量的角度看,编码方法的平均码长越短越好。但是平均码长不可能无限制缩短,它的下限就是熵(即R=0时)。如果短于熵就一定会丢失有用信息(即混淆不同指令),这是不允许的。
定长编码就是所有指令使用相同代码位数,其最小码长等于
式中是平均码长, 是第i种指令的码长,n是指令总数。
已知 n = 15,求定长编码的最小平均码长。
解:
主要优点:规整,译码简单
主要缺点:浪费信息量(操作码的总长位数增加)
Huffman压缩编码(P91)
(1)Huffman压缩概念(最佳编码定理):当用n个长度不等的代码分别代表n种发生概率不等的事件时,按照短代码给高概率事件、长代码给低概率事件的原则分配,可使平均码长达到最低。
(2)Huffman编码方法(最小概率合并法)
频度合并:将全部n个事件(在此即为n条指令)频度值排序,选取其中最小2个频度合并,然后将剩下n-1个频度再次排序,再合并最小2个频度,如此重复,直至剩下1个频度为止。记录所有合并关系,形成二叉树─Huffman树,所有原始频度值当树叶,最后剩下总频度1为树根;
码元分配:从树根开始,对每个中间结点2分支边各赋予一位代码“0”和“1”。读出从根结点到树叶路径上依次出现的代码位,其排列即为此事件(即指令)完整编码。由于频度高事件较晚被合并,其编码位数也就较少,符合Huffman压缩原则。
上面所说频度值就是各事件实际出现次数百分比,它是理论出现概率近似值。
指令序号
出现的概率
I1

I2

I3

I4

I5

I6

I7














1
0
0
0
0
0
0
1
1
1
1
1
模型机的操作码Huffman编码法
指令序号
出现的概率
Huffman编码法
操作码长度
I1

0
1位
I2

1 0
2位
I3

1 1 0
3位
I4

1 1 1 0
4位
I5

1 1 1 1 0
5位
I6

1 1 1 1 1 0
6位
I7

1 1 1 1 1 1
6位
采用Huffman编码法所得到的操作码的平均长度为:
=×1+×2+×3+×4
+×5+×6+×6
= (位)
采用最优Huffman编码法,操作码的平均长度为:

=×+×+
×+×+×+×+× =