第二章 指令优化

计算机系统结构-指令系统优化指令结构分类寻址方式分类寻址方式的使用频度指令操作分类控制流指令的使用频度指令编码格式数据结构与数据表示-1计算机常用的各种数据结构有串、堆栈、队列、向量、阵列、矩阵、链表、图等。实现这些数据结构的各种算法，几乎都立足于计算机系统结构只提供按地址访问的一维线形存储器以及最基本、最简单的数据表示。数据结构与数据表示-2数据表示指的是能由硬件直接辨认的数据类型。这样，这些数据结构要经过软件映象，变换成按地址访问一维存储器内的各种数据表示。如何用最少的存储空间存储这些数据结构，以及用什么样的算法能最快、最简地存储则是数据结构的研究课题。数据结构与数据表示-3计算机的基本数据类型有逻辑（布尔）数、定点数（整数）、浮点数（实数）、十进制数、字符串、数组等。对这些数据的运算可以设置专门指令，也可以仅设置最简单的算术逻辑运算指令。而通过编制程序执行实现之，但后者速度下降很多。在机器中若设置能直接对矩阵向量数据（数组）进行运算的指令及硬件，可以大大提高对向量、数组的处理速度，这一般在巨型机中才使用。数据结构与数据表示-4目前计算机所用数据字长有8位、16位、32位等。在存储器中每个单元的容量为8位，即一个字节，故存储器单元地址按字节编址。计算机的指令系统可支持对字节（8位）、半字（16位）、字（32位）、双字（64位）的运算。数据结构与数据表示-5计算机的数据表示如何确定，是一个复杂的问题。除了必不可少的基本数据表示之外，数据表示的确是一个软、硬件分配的问题。这是因为各种数据结构本来是能够实现于只有最简单、最基本数据表示的机器中，只是在有了更好的数据表示之后，实现的效率可以更高罢了。数据结构与数据表示-6衡量某种数据表示是否合适的标准，首先要看这能使实行时间以及所需存储容量减少了多少。而衡量实行时间是否减少，一个重要的指标是看主存与处理机间所需传送的信息量是否减少。数据结构与数据表示-7例如，有两个200×200元素（定点数）的阵列A与B进行相加运算，若用PL/1语言仅需一条语句，经优化编译形成6条机器指令的目标程序，其中有4条需循环执行40，000次。但若机器有阵列型数据表示，则只需一条机器指令就能执行两个阵列相加的运算，所以只需一次访问存储器操作，处理机与主存间取指操作减少了4×40000次，故实现时间大大减少。数据结构与数据表示-8衡量某种数据表示的确是否合适的另一个标准，是看这个数据表示的通用性如何，利用率如何。对于基本的数据表示，其通用性和利用率当然不构成如何问题，而对于如上述阵列机的数据表示（指阵列数据表示），则其通用性、利用率就不理想了。而且，阵列数据表示还有能表达多大阵列的问题；阵列过大，硬件投资增加，机器性能价格比下降，利用率可能不高；阵列过小，阵列运算要拆成多块，分批进入阵列运算部件，使编译困难。所以，机器的数据表示的选择应该综合平衡上述的各种因素后才确定。指令优化指令系统是计算机所有指令的集合，程序员用各种语言编写的程序都要翻译成（编译或解释）以指令形式表示的机器语言后才能运行，所以它反映了计算机的基本功能，是硬件设计人员和程序员都能见到的机器的主要属性，早期计算机的指令系统很简单，一些比较复杂的操作由子程序实现，因此计算机的处理速度比较慢。指令优化随着硬件价格的下降，指令系统逐步扩充，指令的功能也逐步增强。指令系统的改进是围绕着缩小与高级语言的语义差异以及有利于操作系统的优化而进行的。例如，高级语言中的实数计算是通过浮点运算进行的，对应在指令系统中设置浮点运算指令能明显地提高速度指令优化例如，在高级语言程序中经常用到IF语句、DO语句等，为此在指令系统中设置功能较强的“条件转移”指令是有益的。例如，为了便于实现程序嵌套，设置了Call及Ret指令……上述这些措施都是针对高级语言的优化进行的，使生成的目标程序短而且运行速度快，同时也便于编译。指令优化例如，为操作系统的实现或优化而设置的特殊指令，除了各种控制系统状态的指令外，还有为多道程序公用数据管理和多处理机系统信息管理用的“测试与置定”、“比较与交换”等指令。指令格式优化指令由操作码和地址码两部分组成，上述各种寻址方式主要反映在指令的地址码部分。随着指令类型不同，对地址码的长度要求变化很大，例如操作数据在内部通用寄存器内比之在存储器内，其地址码长度要短得多。为缩小程序代码所占的存储容量，各类指令的长度可以不一致，例如在同一个计算机中可以有1字节、2字节、3字节、4字节等多种长度的指令。指令格式优化从压缩代码的观点出发，希望常用的指令的操作码短些，这样最后使程序的长度也短些。运用哈夫曼（Huffman）码制压缩的基本概念，可以达到操作码优化的目的。指令格式优化哈夫曼压缩的基本概念是：出现概率最大的事件用最少的位（或最短的时间）来表示（或处理），而概率较小的事件用较多的位（或较长的时间）来表示（或处理），达到导致平均位数（或时间）缩短的目的。在使用哈氏压缩之前，必须先了解每一种指令使用中的概率——使用频率Pi。举例-使用频度设某计算机有7条指令（I1—I7），经过典型程序的统计，其使用频度Pi为（使用频度表）I10.40000I20.30001I30.15010I40.05011I50.04100I60.03101I70.03110举例-最少使用位数按信息论中的哈氏信息源熵（即平均信息量）H公式计算H=-∑Pi×log2Pi本例H=0.40×1.32+0.30×1.74+0.15×2.74+0.05×4.32+0.04×4.64+0.03×5.06+0.03×5.06=2.17表示只需2.17位（平均码长，又名最少使用位数）举例-冗余度操作码的实际平均长度为∑Pi*Ii（Ii：操作码位数）。本例=3信息冗余量表示使用n位后，与最少使用位数的冗余程度。冗余度=1-H/∑Pi*Ii本例7条指令用3位二进制表示，则信息冗余度为1-2.17/3=28%。举例-HaffmanTree压缩步骤按使用频度排列，由小到大；选最小二结点合并成一个结点，写入“和”；不断合并，最终有“根结点”；从“根结点”向下二叉用“1”、“0”表示；得到Haffmancode举例-HaffmanTree0.030.030.040.050.150.300.400.060.090.150.300.601.00101010101010举例-HaffmancodeI10.400000I20.3000110I30.15010110I40.0501111100I50.0410011101I60.0310111110I70.0311011111举例-Haffmancode最少使用位数最小使用位数H=0.40×1+0.30×2+0.15×3+0.05×5+0.04×5+0.03×5+0.03×5=2.20信息冗余度1-2.17/2.20=1.36%举例-Haffmancode缺点Haffman编码的最大缺点是不规整。不利于存储器存储；不利于指令译码网络的执行。改进的方法“扩展编码”举例-扩展编码原理只有两种码长的扩展操作码编码，是需要对指令使用频度进行按大小分“群”。将高频的指令分在同一群中，对其用短的操作码编码，而将低频的指令分在另一群中，使用长操作码编码。每一群都各自用等长操作码编码。注意，为了能唯一解码和立即解码，在短操作码中还要使用某些码来作为扩展成长操作码的扩展标志码。经过综合权衡，使平均码长尽可能短，来定好长、短码的码长组配关系。举例-扩展编码I10.40000000I20.300011001I30.1501011010I40.05011111001100I50.04100111011101I60.03101111101110I70.03110111111111举例-扩展编码最少使用位数最小使用位数H=0.40×2+0.30×2+0.15×2+0.05×4+0.04×4+0.03×4+0.03×4=2.30信息冗余度1-2.17/2.30=5.65%举例-小结等长Haffman扩展Haffman3位2.2位2.3位28%1.36%5.65%习题一假设系统某一部件的处理速度加快9倍，但该部件的原处理时间仅为整个运行时间的45%，则采用加快措施后能使整个系统的性能提高多少？如果部件改进后获得的加速比变为SP=5.5，问改进前的执行时间占改进后的百分比是多少？习题二经统计，某计算机的14条指令的使用频度分别为0.01，0.15，0.12，0.03，0.02，0.04，0.02，0.04，0.01，0.13，0.15，0.14，0.11，0.03。分别求出用等长码、Huffman码、只有两种码长的扩展操作码等3种编码方式的操作码平均码长。举例经统计，某计算机的14条指令的使用频度分别为0.01，0.15，0.12，0.03，0.02，0.04，0.02，0.04，0.01，0.13，0.15，0.14，0.11，0.03。分别求出用等长码、Huffman码、只有两种码长的扩展操作码等3种编码方式的操作码平均码长。[分析]等长操作码的意思是不管其指令的使用频度如何，都用同样长度的二进制码位数来对指令操作码编码。显然，当指令系统中的指令条数为n时，等长操作码位数应当是「log2n」。Huffman编码是用Huffman算法构造出Huffman树而得到的。它的平均码长是用i=1,nΣPili求得的。只有两种码长的扩展操作码编码，是需要对指令使用频度进行按大小分群。将高频的指令分在同一群中，对其用短的操作码编码，而将低频的指令分在另一群中，使用长操作码编码。每一群都各自用等长操作码编码。注意，为了能唯一解码和立即解码，在短操作码中还要使用某些码来作为扩展成长操作码的扩展标志码。经过综合权衡，使平均码长尽可能短，来定好长、短码的码长组配关系。从而，再用i=1,nΣPili求得其平均码长。[解答]14条指令的等长操作码的平均码长是「log214」，即4位。Huffman编码可先用Huffman算法构造出Huffman树，见图。它的平均码长是用i=1,14ΣPili=3.38位。采用只有两种码长的扩展操作码编码，可根据14条指令所给出的使用频度值分成两群。让使用频度较高的6种指令用3位操作码表示。留下110和111两个3位码作为长码的扩展标志，扩展出2位码。从而用5位码就可以各扩展出4条使用频度较低的指令，这样，共有8条使用频度较低的指令。由此可求得操作码的平均码长为i=1,14ΣPili=3X0.80+5X0.20=3.4位。参考中文书pp.34～36：指令优化课堂举例习题一、习题二