指令格式的优化设计

指令格式的优化设计

指令格式的优化设计的目的是用最短的二进制位数表示指令的操作信息和地址信息，使指令的平均字长最短。指令格式的优化设计，首先根据指令集各指令的使用频度的分布{Pi}对操作码进行优化设计，然后对地址码和寻址方式的表示采取优化措施，使指令格式达到优化。经过优化设计的指令集减少了程序的总位数，减少了程序运行的时空开销，从而提高了系统的性能。

我们首先讨论操作码的优化编码方法，然后讨论寻址技术，最后，在操作码和地址码优化表示的基础上，说明指令格式的优化设计。

一、操作码的优化设计 1、操作码优化编码的方法

操作码优化编码的方法有三种：定长编码、哈夫曼编码和扩展编码。

定长编码：是指所有指令的操作码长度都是相等的。如果有n个需要编码的操作码，定长操作码的位数最少需要log2n位。

哈夫曼编码：用哈夫曼方法构造哈夫曼树进行编码。构造哈夫曼树的方法是：每次从指令集中选出两个使用频度最小的指令，将其频度相加，形成一个节点，称为父节点，将新生成的父节点放到结点集中，从新的节点集中再选两个使用频度最少的节点生成一个新的父节点，直至节点集成为空集，就生成了一棵哈夫曼树。每个节点的两个分支节点，称为节点，用0和1标识，上面的节点称根节点，下面的节点称为叶节点。从最上面的根节点到一个叶节点的路径(由0和1组成的序列)就是这个叶节点的哈夫曼编码。

由于哈夫曼编码的码长种类较多。既不利于硬件对操作码的译码，也很难与地址码配合形成长度规整的指令格式。因此，实用的操作码编码一般不采用哈夫曼编码而采用扩展编码的方法。

扩展编码：限定使用少数几种长度码长，使用频度高的码点用短码表示，使用频度低的码点用长码表示。特别需要指出的是，不是所有的短码都可以作为长码的前缀，即不是任何短码都可以是任何长码的若干位。否则，编码将会不唯一。所以，要留下若干个短码作为长码的扩展标志，以便长码在扩展编码时使用。这是扩展编码“扩展”一词的含义。

扩展编码的两种表示方法。

1）码长表示法，用短横线前后的数字分别表示短码码长和长码码长，例如，

2-4-6表示指令操作码的长度有三种，分别是2位、4位、6位。（没有表示三种长度的编码各有多少个码点）。

2）码点数表示法，用斜线前后的数字分别表示短码码点的个数和长码码点的

个数，例如，3/4/6表示有三种码长，最短码长的码点个数是3，最长码长的码点个数是4，三种码点的总数是13。（没有表示各个码点数的码长是多少）。 2、操作码优化编码的评价方法

(1)用平均码长评价编码优化的程度，平均码长为：

l??pili

i?1n其中pi是第i种码点的使用频度，li是第i种码点的编码长度。 (2)用位冗余量衡量编码优化的程度，位冗余量为

R?l?HH?1? ll其中，H称为信息熵(Entropy)

H???pilog2pi

i?1n表示用二进制编码表示n个码点时理论上最短平均编码长度。因此对于任何实际编码得出的平均码长l，都有l>H，故有0

3、对于同一个频度分布{pi}，应用哈夫曼法有可能生成不同的哈夫曼树。因此，由不同的哈夫曼树得出的各码点的编码不相同。也就是说，从频度分布{pi}得出的哈夫曼编码并不唯一。但，计算得到的平均码长l肯定是唯一的。

根据实现编码的码点个数的要求，在采用扩展编码方法进行优化编码时，选用几个短码作为长码扩展码标志的原则：一是根据需要编码的短码的码点个数和长码码点个数进行选择，二是尽量减少编码可表示的冗余码点的个数。总之，应尽可能达到平均码长l最短的优化要求。

2

例1：一个处理机共有I1～I10共10条指令，经统计各指令在程序中的使用频率分别为：

p1=0.25 p2=0.20 p3=0.15 p4=0.10 p5=0.08 p6=0.08 p7=0.05 p8=0.04 p9=0.03 p10=0.02

(1)计算该10条指令的操作码编码的最短平均码长；

(2)写出该10条指令的操作码的哈夫曼编码，并计算该种编码的平均码长和位冗余量；

(3)采用3/7扩展编码和2/8扩展编码编写该10条指令的操作码，并分别计算平均码长和位冗余量。问哪一种扩展编码较好？说明其理由。 解：

(1)由给出的使用频率p1～p10，计算I1～I10的操作码编码的最短平均码长：

H???pilog2pi

i?110=-(0.25log20.25+0.20log20.20+0.15log20.15+0.10log20.10

+0.08log20.08+0.08log20.08+0.05log20.05+0.04log20.04+ 0.03log20.03+0.02log20.02) =2.96位

所以，这十条指令的操作码编码的最短平均码长为2.96位。

(2)根据给出的使用频度，在用哈夫曼编码算法构造哈夫曼树的过程中，在选两个频度最小的节点合并时，有时有两个以上的节点可供选择，因此就会生成结构不同的哈夫曼树。这里给出了两个哈夫曼树。如下图：

3

1100.431010.5700.230.200.3210I2100.130.100.170.1510I410I30.050.080.090.0810I610I50.020.030.040.05I10I9I8I7

4

0.25I1

1100.571010.4300.32100.25I10.23100.20I20.17100.15I310.1300.10I40.09100.08I50.05I70.08I60.05100.04I80.02I100.03I9

由哈夫曼树得到的两种哈夫曼编码如下表：

Ii I1 I2 I3 I4 I5 I6 I7 I8 I9 I10 pi 哈夫曼编码(a) 码长Iai 2 2 3 3 4 4 5 5 5 5 哈夫曼编码(b) 码长Ibi 10 00 110 010 1110 0110 0111 11110 111110 111111 2 2 3 3 4 4 4 5 6 6 0.25 00 0.20 10 0.15 010 0.10 110 0.08 0110 0.08 1110 0.05 01110 0.04 01111 0.03 11110 0.02 11111 可见哈夫曼编码是不唯一的。 两种哈夫曼编码的平均码长为：

5