系统结构讲义-2

第二章指令系统2.3指令格式的优化设计指令格式的优化是指如何用最短的二进制位数表示指令的操作码信息和地址码信息，使指令的平均字长最短，同时便于译码。指令的组成操作码地址码指令的操作种类。所用操作数数据类型。操作数地址。地址附加信息。寻址方式。指令格式的优化设计目标：使程序中指令的平均字长最短，节省程序的存储空间。指令格式要规整，减少硬件译码的复杂程度。操作码的优化表示操作码的表示方法：固定长度操作码。Huffman编码法。扩展编码法。一、固定长度操作码采用等长操作码。若指令系统共有N种不同功能的指令，则指令系统中的所有指令的操作码长度固定为[lbN]位。特点：长度规整，有利于硬件设计，减少指令译码时间。信息冗余。例：假设一台模型计算机共有7种不同的操作码，已知各种操作码在程序中出现的概率如下表，利用固定长度编码法进行操作码编码。指令I1概率0.45I20.30I30.15I40.05I50.03I60.01I70.01解：由于N=7

因此，指令操作码固定长度为[lbN]=[lb7]=3指令序号概率编码操作码长度I10.450003位I20.300013位I30.150103位I40.050113位I50.031003位I60.011013位I70.011103位编码结果：二、Huffman编码法（最小概率合并法）Huffman压缩概念（最佳编码定理）：当用n个长度不等的代码分别代表n种发生概率不等的事件时，按照短代码给高概率事件、把长代码给低概率事件的原则分配，可使平均码长达到最低。

Huffman编码方法

这种编码方法由两个过程组成。

频度合并：将全部n个事件（在此即为n条指令）的频度值排序，选取其中最小的2个频度合并，然后将剩下的n-1个频度再次排序，再合并最小的2个频度，如此重复，直至剩下1个频度为止。记录所有的合并关系，形成一棵二叉树──Huffman树，所有原始频度值充当树叶，而最后剩下的总频度1为树根；

码元分配：从树根开始，对每个中间结点的左右2个分支边各赋予一位代码“0”和“1”（“0”在哪一侧不限）。读出从根结点到任一片树叶的路径上依次出现的代码位就排成了这个事件（即指令）的完整编码。由于频度高的事件较晚被合并，它的编码位数也就较少，符合Huffman压缩原则。上面所说的频度值就是各事件实际出现次数的百分比，它是理论出现概率的近似值。

例：假设一台模型计算机共有7种不同的操作码，已知各种操作码在程序中出现的概率如下表，利用Huffman编码法进行操作码编码。指令I1概率0.45I20.30I30.15I40.05I50.03I60.01I70.01Huffman树生成步骤：把所有指令按照操作码在程序中出现的概率，自左向右从排列好。选取两个概率最小的结点合并成一个概率值是二者之和的新结点，并把这个新结点与其它还没有合并的结点一起形成新结点集合。在新结点集合中选取两个概率最小的结点进行合并，如此继续进行下去，直至全部结点合并完毕。最后得到的根结点的概率值为1。每个结点都有两个分支，分别用一位代码“0”和“1”表示。注意：对于同一个频度分布，应用哈夫曼算法可能生成不同的哈夫曼树，因此，得到的哈夫曼编码并不唯一，但平均码长唯一。0.450.300.150.050.030.010.011.000.550.02010101010101I1I2I3I4I5I6I7Huffman编码树生成过程指令序号概率Huffman编码法操作码长度I10.4501位I20.30102位I30.151103位I40.0511104位I50.03111105位I60.011111106位I70.011111116位编码结果：编码方法性能指标信息量：根据信息论的基本知识，在n种可能发生的事件集合中，报告第i种事件发生的消息中包含的信息量为：其中Pi是第i种事件发生的先验概率，a是编码基值。信息量的单位是表示位数（最少所需位数）。这个定义式表明事件的发生概率越低，关于它的消息中的信息量越大。熵（entropy）──平均信息量：一个消息源对n种事件发布的消息的信息量平均值，记为：平均码长：各事件编码长度的数学期望。信息冗余量：表明消息编码中“无用成分”所占的百分比。

从减少存储与传输量的角度看，编码方法的平均码长越短越好。但是平均码长不可能无限制缩短，它的下限就是熵（即R=0时）。如果短于熵就一定会丢失有用信息（即混淆不同指令），这是不允许的。例：假设一台模型计算机共有7种不同的操作码，如果采用固定长操作码需要3位。已知各种操作码在程序中出现的概率如下表，计算采用Huffman编码法的操作码平均长度，并计算固定长操作码和Huffman操作码的信息冗余量。解：Huffman编码结果如：指令序号概率Huffman编码法操作码长度I10.4501位I20.30102位I30.151103位I40.0511104位I50.03111105位I60.011111106位I70.011111116位采用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编码法的操作码平均长度为：0.45×1.152＋0.30×1.737＋0.15×2.737＋0.05×4.322＋0.03×5.059＋0.01×6.644＋0.01×6.644＝1.95（位）采用固定长度编码信息冗余量：采用Huffman编码法信息冗余量：与3位定长操作码的冗余量35％相比要小得多。Huffman操作码的主要缺点：操作码长度很不规整，硬件译码困难与地址码共同组成固定长的指令比较困难扩展编码方法（等长扩展法）由固定长操作码与Huffman编码法相结合形成。码长表示法：分等长扩展法和不等长扩展法。等长扩展法如4-8-12法，每次加长4位。但这并不能说明具体编码方法，例如下面两种编码方法都是4-8-12法。码点表示法：例如15/15/15法，8/64/512法15/15/15法，每一种码长都有4位可编码位（前头可以有相同的扩展标识前缀），可产生16个码点（即编码组合），但是至多只能使用其中15个来表示事件，留下1个或多个码点组合作为更长代码的扩展标识前缀。已经用来表示事件的码点组合不能再作为其它更长代码的前导部分，否则接收者会混淆。这就是“非前缀原则”。8/64/512法，每一种码长按4位分段，每一段中至少要留下1位或多位作为扩展标识。各段剩下的可编码位一起编码，所产生的码点用来对应被编码事件。每一段中的标识位指出后面还有没有后续段。00000001……11101111000011110001……11111110111111110000111111110001……1111111111104位长度的操作码共有15种8位长度的操作码共有15种12位长度的操作码共有15种操作码编码说明00000001……01111000000010000001……11110111100010000000100010000001……1111111101114位长度的操作码共有8种8位长度的操作码共有64种12位长度的操作码共有512种操作码编码说明等长15/15/15…扩展法等长8/64/512…扩展法例：假设一台模型计算机共有7种不同的操作码。已知各种操作码在程序中出现的概率如下表，如果采用1-2-3-5和2-4扩展编码法，计算操作码平均长度和信息冗余量。指令I1概率0.45I20.30I30.15I40.05I50.03I60.01I70.01解：采用1-2-3-5扩展编码法操作码平均长度：H=0.45×1＋0.30×2＋0.15×3＋（0.05＋0.03＋0.01＋0.01)×5

=2.00信息冗余量：采用2-4扩展编码法操作码平均长度：H=(0.45+0.30+0.15)×2+（0.05+0.03+0.01+0.01)×4

=2.20信息冗余量：序号概率1-2-3-5扩展编码I10.450I20.3010I30.15110I40.0511100I50.0311101I60.0111110I70.01111112-4等长扩展编码0001101100110111101111平均长度2.02.2信息冗余量2.5%11.4%7条指令的操作码扩展编码法指令I1I2I3I4I5I6I7I8I9I10概率50.100.080.080.050.040.030.02例：一台处理机有I1-I10共10条指令，经统计，各指令在程序中使用的频率如下：（1）计算这10条指令的操作码编码的最短平均码长。（2）写出这10条指令的操作码的哈夫曼编码，并计算编码的平均码长和信息冗余量。（3）采用3/7扩展编码和2/8扩展编码编写这10条指令的操作码，并分别计算平均码长和信息冗余量。哪种扩展编码比较好？说明理由。解:(1)最短平均码长：H=-∑pilog2pi=-(0.25×log20.25＋0.20×log20.20＋0.15×log20.15＋0.10×log20.10＋0.08×log20.08＋0.08×log20.08＋0.05×log20.05＋0.04×log20.04＋0.03×log20.03＋0.02×log20.02)＝2.96（位）(2)两种哈夫曼树0.020.030.040.050.080.000.250.050.030.320.430.5711011111111000000000.020.030.040.050.050.130.430.230.090.170.320.571101111111100000000IiPi哈夫曼1I1i哈夫曼2I2iI10.25102002I20.20002102I30.1511030103I40.1001031103I50.081110301104I60.080110411104I70.0501114011105I80.04111105011115I90.031111106111105I100.021111116111115可见，哈夫曼编码不唯一。哈夫曼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扩展编码如下表所示：IiPi3/7扩展I1i2/8扩展I2iI10.25002002I20.20012012I30.1510210004I40.1011000510014I50.0811001510104I60.0811010510114I70.0511011511004I80.0411100511014I90.0311101511104I100.02111105111143/7扩展平均码长：I3/7=∑Pi×I1i=(0.25+0.20+0.15)×2+(0.10+0.08+0.08+0.05+0.04+0.03+0.02)×5=3.2(位)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%地址码的优化表示地址码在指令中所占的长度最长。地址码长度=f（地址码个数，存储设备，寻址空间大小，编址方式，寻址方式）本节解决问题：地址个数的选择单个地址码长度如何优化。地址码个数选择：通常有3个、2个、1个及没有地址码等4种情况。评价指令中地址个数的标准：程序的存储量，即程序中所有指令的长度相加的总和最短。程序的执行速度，即程序在执行过程中访问主存储器的信息（包括指令和数据）量的总和最短。指令字格式优化设计的措施采用扩展操作码，以缩短操作码的平均码长。采用诸如基址、变址、相对寻址、寄存器寻址、寄存器间接寻址等多种寻址方式，以缩短需要在指令中表示的地址码长度，但不减少地址码寻址空间的大小。指令集采用零地址、一地址、二地址和三地址等多种地址制，且让常用的短操作码与多地址字段配合，长操作码与少地址字段配合。采用R-R、R-M、M-M等多种地址表示方式，让每种地址字段有多种长度，使长度不等的操作码与地址码配合成规整长度的指令字。在维持指令字在存储器中按整数边界存储的前提下，使用多种不同的指令字长度。要求指令字长应是主存存储字长的整数倍。表2.10各种不同地址数指令的特点及适用场合各种不同地址数指令的特点及适用场合地址数目指令码长度程序存储量程序执行速度使用场合三地址短最大一般向量，矩阵运算为主二地址一般很大很低一般不宜采用一地址较长较大较快连续运算，硬件结构简单0地址最长最小最低嵌套，递归，变量较多二地址R形一般最小最快多累加器，数据传送较多例：一台模型机共有7条指令，各指令的使用频率分别为35%，25%，20%，10%，5%，3%和2%，有8个通用数据寄存器，2个变址寄存器。（1）要求操作码的平均长度最短，请设计操作码的编码，并计算所设计操作码的平均长度。（2）设计8字长的寄存器-寄存器型指令3条，16位字长的寄存器-存储器型变址寻址方式指令4条，变址范围不小于±127。请设计指令格式，并给出各字段的长度和操作码的编码。解：（1）要使得到的操作码长度最短，应采用Huffman编码，构造Huffman树如下：0.300.050.030.020.000.601.00由此可以得到7条指令的编码分别如下：指令出现的频率编码135%00225%01320%10410%11055%111063%1111072%11111这样，采用Huffman编码法得到的操作码的平均长度为：H=2×(0.35+0.25+0.20)+3×0.10+4×0.05+5×(0.03+0.02)=1.6+0.3+0.2+0.25=2.35

三条指令的操作码分别为00，01，10设计16位字长的寄存器-存储器型变址寻址方式指令如下：4 3 1 8 （2）设计8位字长的寄存器-寄存器型变址寻址方式指令如下，因为只有8个通用寄存器，所以寄存器地址需3位，操作码只有两位，设计格式如下：2 33操作码OP源寄存器R1目的寄存器R2操作码OP通用寄存器变址寄存器偏移地址四条指令的操作码分别为1100，1101，1110，11112.4.3精简指令系统计算机RISC1.复杂指令系统计算机CISC

(ComplexInstructionSetComputer)

增强指令功能，设置功能复杂的指令。

面向目标代码、高级语言和操作系统。

用一条指令代替一串指令。

2.精简指令系统计算机RISC

(ReducedInstructionSetComputer)

只保留功能简单的指令。

功能较复杂的指令用子程序来实现。ISA(InstructionSetArchitecture)(IndustrialStandardArchitecture)CISC的特点庞大的指令系统原因：硬件成本下降、软件成本上升。系统向上兼容。微程序技术的发展。采用了可变长的指令格式为了缩短指令字长，同时增大存储器寻址范围，出现了多种寻址方式，出现了可变字长的指令格式。指令使用的寻址方式繁多指令系统中包括了一些用于特殊用途的指令复杂的指令系统，增加了微处理器的复杂性，使微处理器研制时间长、成本高，降低了机器的速度。从CISC到RISCCISC指令系统存在的问题：

1、20％与80％规律

CISC中，使用频度约20％的指令占据了80％的处理机时间，而使用频度80％的指令只占20％的处理机运行时间2、VLSI技术的发展引起的问题VLSI工艺要求规整性

RISC正好适应了VLSI工艺的要求主存与控存的速度相当

简单指令没有必要用微程序实现，复杂指令用微程序实现与用简单指令组成的子程序实现没有多大区别；由于VLSI的集成度迅速提高，使得生产单芯片处理机成为可能。3、软硬件的功能分配问题复杂的指令使指令的执行周期大大加长

一般CISC处理机的指令平均执行周期都在4以上，有些在10以上。CISC增强了指令系统功能，简化了软件，但硬件复杂了

1981年Patterson等人研制了32位RISCI微处理器，共31种指令，3种数据类型，2种寻址方式；研制周期10个月，比当时最先进的MC68000和Z8002快3至4倍；1983年又研制了RISCII，指令种类扩充到39种，使用单一的变址寻址方式，通用寄存器138个。RISC的定义与特点卡内基梅隆大学（CarnegieMellon）论述RISC的特点：大多数指令在单周期内完成LOAD/STORE结构硬布线控制逻辑减少指令和寻址方式的种类固定的指令格式注重编译优化技术90年代初，IEEE的MichaelSlater对RISC定义的描述：1、RISC为使流水线高效率执行，应具有：简单而统一格式的指令译码大部分指令可以单周期执行完成仅Load和Store指令可以访问存储器简单的寻址方式采用延迟转移技术采用LOAD延迟技术2、RISC为使优化编译器便于生成优化代码，应具有：三地址指令格式较多的寄存器对称的指令格式程序执行时间的计算公式：P=I·CPI·T其中：P是执行这个程序所使用的总的时间；I是这个程序所需执行的总的指令条数；CPI(CyclesPerInstruction)是每条指令执行的平均周期T是一个周期的时间长度。RISC的速度要比CISC快3倍左右，关键是RISC的CPI减小了。减少CPI是RISC思想的精华类型CISC指令条数

I指令平均周

期数CPI周期时间

T12～1533ns～5nsRISC1.3～1.41.1～1.410ns～2nsCISC与RISC的I、CPI和T的比较RISC的关键技术延时转移技术指令取消技术重叠寄存器窗口技术指令流调整技术以硬件为主固件为辅延时转移技术ADDR1,R2JMPNEXT2NEXT1：SUBR3,R4……NEXT2：MOVER4,A取指执行取指执行取指执行取指执行产生转移地址指令作废重新取指令a)因转移指令引起流水线断流产生转移地址

JMPNEXT2ADDR1,R2NEXT1：SUBR3,R4……NEXT2：MOVER4,A取指执行取指执行取指执行插入指令重新取指令b)采用延时转移技术的指令流水线指令取消技术LOOP：XXXYYY……ZZZCOMPR1,R2,LOOP

WWWa)调整前程序XXXLOOP：YYY……ZZZCOMPR1,R2,LOOPXXX

WWWb)调整后程序如果转移成功，则执行下面的XXX指令，然后返回LOOP；如果转移不成功，则取消下面的XXX指令，执行WWW指令。后取指执行取指执行取指执行取指执行产生转移地址指令作废重新取指令重叠寄存器窗口技术A局部寄存器A,B公用寄存器B局部寄存器B,C公用寄存器C局部寄存器C,D公用寄存器……全局寄存器137132131122121116115106105100999089841090A局部寄存器传送参数B局部寄存器传送参数传送参数C局部寄存器传送参数传送参数寄存器重叠寄存器重叠局部寄存器与下一个过程合用与上一个过程合用全局寄存器31262516151090A过程寄存器窗口指令流调整技术ADDR1,R2,R3;(R1)+(R2)→R3ADDR3,R4,R5;(R3)+(R4)→R5MULR6,R7,R3;(R6)×(R7)→R3MULR3,R8,R9;(R3)×(R8)→R9a)调整前的指令序列ADDR1,R2,R3MULR6,R7,R0ADDR3,R4,R5MULR0,R8,R9b)调整后的指令序列消除数据相关硬件为主固件为辅

RISC要求主要指令在单个周期内执行完成，因此，主要采用硬连线逻辑实现。对于少数复杂的指令，可以使用微程序（固件）实现，并且较多使用全水平型微指令。RISC优化编译技术RISC是硬件和软件相结合的产物。RISC硬件设计为优化编译程序设计带来如下方便：RISC指令系统比较简单，而且对称、均匀，简化了编译程序复杂指令选择工作。RISC寻址方式简单，指令大都在寄存