2020系统结构系列文章

指令是由操作码和地址码两部分组成的。

就指令格式的优化来说,是指如何用最短的位数来表示指令的操作信息和地址信息,使程序中指令的平均字长最短。 操作码的优化，也就是最短的位数来表示指令的操作信息。

固定位数：比如操作码固定为6位。 在指令字最高位部分分配固定的若干位用于表示操作码，有利于简化计算机硬件设计，提高指令译码和识别速度。 例如: 1BM360机、教学计算机

不固定位数：操作码可以是6位也可能是7位8位。 在指令字最高位部分用一固定长度的字段用于表示基本操作码，而对于部分操作数地址少的指令把它们的操作码扩充到该指令的操作数地址字段，即操作码可以变长。 这种方法在不增加指令字长度的情况下可表示更多的指令，但增加了译码和分析难度,需更多硬件支持

如何优化？ 首先我们要知道操作码部分的优化指的是变长操作码的优化。因为定长操作码没有优化空间。 优化的思路就是：想办法将指令的操作码的位数变短。

如何做？ 根据指令的使用频度，我们应该把最常用的指令尽可能用最短的位数来表示。这就涉及到了哈夫曼压缩概念。

哈夫曼压缩概念的基本思想是,当各种事件发生的概率不均等时,采用优化技术,对发生概率最高的事件用最短的位数(时间)来表示(处理),而对出现概率较低的事件允许用较长的位数(时间)来表示(处理),就会使表示"(处理)的平均位数(时间)缩短。 研究操作码的优化表示，主要是为了缩短指令字长,减少程序总位数及增加指令字能表示的操作信息和地址信息。要对操作码进行优化表示,就需要知道每种指令在程序中出现的概率(使用频度)，一般可通过对大量已有的典型程序进行统计求得。

前面我们已经知道了哈夫曼编码的概念。接下来根据例题来实际应用一下，题目如下： 结题思路：1、利用哈夫曼算法构造哈夫曼树。 构造哈夫曼树非常简单，将所有的节点放到一个队列中，用一个节点替换两个频率最低的节点，新节点的频率就是这两个节点的频率之和。这样，新节点就是两个被替换节点的父节点了。如此循环，直到队列中只剩下一个节点（树根）。 2、根据绘制出的哈夫曼树，从根节点开始，沿线到达各频度指令所经过的代码序列就构成该频度指令的哈夫曼码，如下表所示： 3、根据编码表计算平均码长。 如下图，计算出来的平均码长为2.2位，非常接近于题目中给出的H，且这种编码的信息冗余仅有1.36%，远远小于三位定长码的信息冗余（28%）。所以，完全的哈夫曼编码是最优化的编码。 但是这种编码的码长种类太多。如上表，7种指令就出现了4种码长，长度有1有2有3有5，不规整，不易于编码。为此，结合用一般的二进制编码，在哈夫曼编码的基础上进行扩展。

扩展操作码编码是介于定长二进制编码和完全的哈夫曼编码之间的一种编码方式，操作码不是定长的，但只有有限的几种码长。如上述题目，如果要求只能用固定两种码长，表示7条指令，应该使用什么编码方案？

最优的情况，肯定是尽可能用短的。所以我们先从最短码长开始考虑。

码长为1的情况，此时可以只能表示2条指令(2的1次方:0和1)，拿出1条用来扩展，扩展出几位呢？ 1位，又可以表示2条，（2-1）+2=3