《系统结构讲义》PPT课件.ppt

第二章 指令系统,2.3 指令格式的优化设计,指令格式的优化是指如何用最短的二进制位数表示指令的操作码信息和地址码信息，使指令的平均字长最短，同时便于译码。指令的组成,操作码,地址码,指令的操作种类。所用操作数数据类型。,操作数地址。地址附加信息。寻址方式。,指令格式的优化设计目标：使程序中指令的平均字长最短，节省程序的存储空间。指令格式要规整，减少硬件译码的复杂程度。,操作码的优化表示,操作码的表示方法：固定长度操作码。Huffman编码法。扩展编码法。,一、固定长度操作码采用等长操作码。若指令系统共有N种不同功能的指令，则指令系统中的所有指令的操作码长度固定为lbN位。特点：长度规整，有利于硬件设计，减少指令译码时间。信息冗余。,例：假设一台模型计算机共有7种不同的操作码，已知各种操作码在程序中出现的概率如下表，利用固定长度编码法进行操作码编码。,解：由于N=7 因此，指令操作码固定长度为lbN=lb7=3,编码结果：,二、Huffman编码法（最小概率合并法）Huffman压缩概念（最佳编码定理）：当用n个长度不等的代码分别代表n种发生概率不等的事件时，按照短代码给高概率事件、把长代码给低概率事件的原则分配，可使平均码长达到最低。Huffman编码方法 这种编码方法由两个过程组成。频度合并：将全部n个事件（在此即为n条指令）的频度值排序，选取其中最小的2个频度合并，然后将剩下的n-1个频度再次排序，再合并最小的2个频度，如此重复，直至剩下1个频度为止。记录所有的合并关系，形成一棵二叉树 Huffman树，所有原始频度值充当树叶，而最后剩下的总频度1为树根；码元分配：从树根开始，对每个中间结点的左右2个分支边各赋予一位代码“0”和“1”（“0”在哪一侧不限）。读出从根结点到任一片树叶的路径上依次出现的代码位就排成了这个事件（即指令）的完整编码。由于频度高的事件较晚被合并，它的编码位数也就较少，符合Huffman压缩原则。,上面所说的频度值就是各事件实际出现次数的百分比，它是理论出现概率的近似值。例：假设一台模型计算机共有7种不同的操作码，已知各种操作码在程序中出现的概率如下表，利用Huffman编码法进行操作码编码。,Huffman树生成步骤：把所有指令按照操作码在程序中出现的概率，自左向右从排列好。选取两个概率最小的结点合并成一个概率值是二者之和的新结点，并把这个新结点与其它还没有合并的结点一起形成新结点集合。在新结点集合中选取两个概率最小的结点进行合并，如此继续进行下去，直至全部结点合并完毕。最后得到的根结点的概率值为1。每个结点都有两个分支，分别用一位代码“0”和“1”表示。注意：对于同一个频度分布，应用哈夫曼算法可能生成不同的哈夫曼树，因此，得到的哈夫曼编码并不唯一，但平均码长唯一。,I1 I2 I3 I4 I5 I6 I7,Huffman编码树生成过程,编码结果：,编码方法性能指标,信息量：根据信息论的基本知识，在n种可能发生的事件集合中，报告第i种事件发生的消息中包含的信息量为：,其中Pi是第i种事件发生的先验概率，a是编码基值。信息量的单位是表示位数（最少所需位数）。这个定义式表明事件的发生概率越低，关于它的消息中的信息量越大。熵（entropy）平均信息量：一个消息源对n种事件发布的消息的信息量平均值，记为：,平均码长：各事件编码长度的数学期望。,信息冗余量：表明消息编码中“无用成分”所占的百分比。,从减少存储与传输量的角度看，编码方法的平均码长越短越好。但是平均码长不可能无限制缩短，它的下限就是熵（即R=0时）。如果短于熵就一定会丢失有用信息（即混淆不同指令），这是不允许的。,例：假设一台模型计算机共有7种不同的操作码，如果采用固定长操作码需要3位。已知各种操作码在程序中出现的概率如下表，计算采用Huffman编码法的操作码平均长度，并计算固定长操作码和Huffman操作码的信息冗余量。,解：Huffman编码结果如：,采用Huffman编码法的操作码平均长度：0.4510.3020.1530.0540.0350.0160.0161.97（位）最优Huffman编码法的操作码平均长度计算公式：,所以，采用最优Huffman编码法的操作码平均长度为：0.451.1520.301.7370.152.7370.054.3220.035.0590.016.6440.016.6441.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位或多位作为扩展标识。各段剩下的可编码位一起编码，所产生的码点用来对应被编码事件。每一段中的标识位指出后面还有没有后续段。,000000011110,1111 00001111 00011111 1110,1111 1111 00001111 1111 00011111 1111 1110,4位长度的操作码共有15种,8位长度的操作码共有15种,12位长度的操作码共有15种,操作码编码,说明,000000010111,1000 00001000 00011111 0111,1000 1000 00001000 1000 00011111 1111 0111,4位长度的操作码共有8种,8位长度的操作码共有64种,12位长度的操作码共有512种,操作码编码,说明,等长15/15/15扩展法,等长8/64/512扩展法,例：假设一台模型计算机共有7种不同的操作码。已知各种操作码在程序中出现的概率如下表，如果采用1-2-3-5和2-4扩展编码法，计算操作码平均长度和信息冗余量。,解：采用1-2-3-5扩展编码法操作码平均长度：H=0.4510.3020.153（0.050.030.010.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信息冗余量：,例：一台处理机有I1-I10共10条指令，经统计，各指令在程序中使用的频率如下：,（1）计算这10条指令的操作码编码的最短平均码长。（2）写出这10条指令的操作码的哈夫曼编码，并计算编码的平均码长和信息冗余量。（3）采用3/7扩展编码和2/8扩展编码编写这10条指令的操作码，并分别计算平均码长和信息冗余量。哪种扩展编码比较好？说明理由。,解:(1)最短平均码长：H=-pilog2pi=-(0.25log20.250.20log20.200.15log20.15 0.10log20.100.08log20.080.08log20.080.05log20.050.04log20.040.03log20.030.02log20.02)2.96（位）(2)两种哈夫曼树,0.02,0.03,0.04,0.05,0.08,0.08,0.10,0.15,0.20,0.25,0.05,0.09,0.13,0.17,0.23,0.32,0.43,0.57,1,1,0,1,1,1,1,1,1,1,1,0,0,0,0,0,0,0,0,0.02,0.03,0.08,0.10,0.20,0.04,0.05,0.08,0.15,0.25,0.05,0.13,0.43,0.23,0.09,0.17,0.32,0.57,1,1,0,1,1,1,1,1,1,1,1,0,0,0,0,0,0,0,0,可见，哈夫曼编码不唯一。,哈夫曼1平均码长：I1=PiI1i=0.252+0.202+0.153+0.103+0.084+0.084+0.054+0.045+0.036+0.026=2.99(位)哈夫曼2平均码长：I2=PiI2i=0.252+0.202+0.153+0.103+0.084+0.084+0.055+0.045+0.035+0.025=2.99(位)可见，平均码长唯一。信息冗余量：Rn=(1-H/I1)=1-2.96/2.99=1.0%3/7和2/8扩展编码如下表所示：,3/7扩展平均码长：I3/7=PiI1i=(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=PiI2i=(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树如下：,由此可以得到7条指令的编码分别如下：,这样，采用Huffman编码法得到的操作码的平均长度为：H=2(0.35+0.25+0.20)+30.10+4 0.05+5(0.03+0.02)=1.6+0.3+0.2+0.25=2.35,三条指令的操作码分别为00，01，10设计16位字长的寄存器-存储器型变址寻址方式指令如下：43 18,（2）设计8位字长的寄存器-寄存器型变址寻址方式指令如下，因为只有8个通用寄存器，所以寄存器地址需3位，操作码只有两位，设计格式如下：2 3 3,四条指令的操作码分别为1100，1101，1110，1111,2.4.3 精简指令系统计算机RISC,1.复杂指令系统计算机CISC(Complex Instruction Set Computer)增强指令功能，设置功能复杂的指令。面向目标代码、高级语言和操作系统。用一条指令代替一串指令。2.精简指令系统计算机RISC(Reduced Instruction Set Computer)只保留功能简单的指令。功能较复杂的指令用子程序来实现。ISA(Instruction Set Architecture)(Industrial Standard Architecture),CISC的特点,庞大的指令系统原因：硬件成本下降、软件成本上升。系统向上兼容。微程序技术的发展。采用了可变长的指令格式 为了缩短指令字长，同时增大存储器寻址范围，出现了多种寻址方式，出现了可变字长的指令格式。指令使用的寻址方式繁多指令系统中包括了一些用于特殊用途的指令 复杂的指令系统，增加了微处理器的复杂性，使微处理器研制时间长、成本高，降低了机器的速度。,从CISC到RISC,CISC指令系统存在的问题：1、20与80规律 CISC中，使用频度约20的指令占据了80的处理机时间，而使用频度80的指令只占20的处理机运行时间2、VLSI技术的发展引起的问题VLSI工艺要求规整性RISC正好适应了VLSI工艺的要求主存与控存的速度相当简单指令没有必要用微程序实现，复杂指令用微程序实现与用简单指令组成的子程序实现没有多大区别；由于VLSI的集成度迅速提高，使得生产单芯片处理机成为可能。,3、软硬件的功能分配问题复杂的指令使指令的执行周期大大加长 一般CISC处理机的指令平均执行周期都在4以上，有些在10以上。CISC增强了指令系统功能，简化了软件，但硬件复杂了 1981年Patterson等人研制了32位RISC I微处理器，共31种指令，3种数据类型，2种寻址方式；研制周期10个月，比当时最先进的MC68000和Z8002快3至4倍；1983年又研制了RISC II，指令种类扩充到39种，使用单一的变址寻址方式，通用寄存器138个。,RISC的定义与特点,卡内基梅隆大学（Carnegie Mellon）论述RISC的特点：大多数指令在单周期内完成LOAD/STORE结构硬布线控制逻辑减少指令和寻址方式的种类固定的指令格式注重编译优化技术,90年代初，IEEE的Michael Slater对RISC定义的描述：1、RISC为使流水线高效率执行，应具有：简单而统一格式的指令译码大部分指令可以单周期执行完成仅Load和Store指令可以访问存储器简单的寻址方式采用延迟转移技术采用LOAD延迟技术2、RISC为使优化编译器便于生成优化代码，应具有：三地址指令格式较多的寄存器对称的指令格式,程序执行时间的计算公式：P=I CPI T其中：P是执行这个程序所使用的总的时间；I是这个程序所需执行的总的指令条数；CPI(Cycles Per Instruction)是每条指令执行的平均周期T是一个周期的时间长度。RISC的速度要比CISC快3倍左右，关键是RISC的CPI减小了。,减少CPI是RISC思想的精华,CISC与RISC的I、CPI和T的比较,RISC的关键技术,延时转移技术指令取消技术重叠寄存器窗口技术指令流调整技术以硬件为主固件为辅,延时转移技术,ADD R1,R2 JMP NEXT2NEXT1：SUB R3,R4NEXT2：MOVE R4,A,取指,执行,取指,执行,取指,执行,取指,执行,产生转移地址,指令作废,重新取指令,a)因转移指令引起流水线断流,指令取消技术,LOOP：XXX YYY ZZZ COMP R1,R2,LOOP WWW,a)调整前程序,取指,执行,取指,执行,取指,执行,取指,执行,产生转移地址,指令作废,重新取指令,重叠寄存器窗口技术,A局部寄存器,A,B公用寄存器,B局部寄存器,B,C公用寄存器,C局部寄存器,C,D公用寄存器,全局寄存器,137132131122121116115106105100999089841090,A局部寄存器,传送参数,B局部寄存器,传送参数,传送参数,C局部寄存器,传送参数,传送参数,寄存器重叠,寄存器重叠,局部寄存器,与下一个过程合用,与上一个过程合用,全局寄存器,31262516151090,A过程寄存器窗口,指令流调整技术,ADD R1,R2,R3;(R1)+(R2)R3ADD R3,R4,R5;(R3)+(R4)R5MUL R6,R7,R3;(R6)(R7)R3MUL R3,R8,R9;(R3)(R8)R9,a)调整前的指令序列,硬件为主固件为辅,RISC要求主要指令在单个周期内执行完成，因此，主要采用硬连线逻辑实现。对于少数复杂的指令，可以使用微程序（固件）实现，并且较多使用全水平型微指令。,RISC优化编译技术,RISC是硬件和软件相结合的产物。RISC硬件设计为优化编译程序设计带来如下方便：RISC指令系统比较简单，而且对称、均匀，简化了编译程序复杂指令选择工作。RISC寻址方式简单，指令大都在寄存器之间进行操作，因此省却了存储器地址计算、访问工作。RISC大多数指令在一个周期完成，方便编译器调整指令序列。RISC给编译器造成的困难：编译器需要使用大量的寄存器，因此，必须精心安排寄存器的用法，发挥寄存器的效率。编译器要做数据和控制相关分析，要调整指令序列，并与硬件相配合实现指令延迟技术和指令取消技术。程序量较大，需要建立复杂的子程序库。,CISC和RISC体系结构比较,CISC和RISC体系结构到底谁更好？RISC支持者：廉价、速度快。RISC反对者：软件开发复杂。眼下事实：75%的PC、工作站和服务器基于CISC体系结构。背后原因：CISC和RISC体系结构越来越接近。许多RISC芯片仍然支持更多过去的CISC芯片，今天CISC芯片也运用了很多与RISC体系结构相关技术，因此，CISC和RISC共同发展。,主存储器,合一高速缓存,指令/数据通路,控制部件,控制存储器,（指令）主存储器（数据）,数据高速缓存,数据通路,硬连线控制部件,数据高速缓存,（a）经典CISC处理器,（b）纯RISC处理器,小规模寄存器堆,大型寄存器堆,经典CISC和纯RISC处理器的体系结构区别,经典CISC和纯RISC体系结构的特征,特性,经典CISC体系结构,纯RISC体系结构,指令格式,可变格式：1632和64位,固定32位指令,时钟频率,随技术发展而变化,随技术发展而变化,寄存器堆,824个通用寄存器,32192个分离的整数和浮点寄存器堆,指令系统规模和类型,约300条，多于48种指令类型,约100条，除取/存外，大都基于寄存器,寻址方式,约12种,包含间接/变址寻址,35种,只有取/存寻址存储器,高速缓存设计,较早使用合一高速缓存，有些使用分离高速缓存,大多数使用分离的数据和指令高速缓存,CPI及平均CPI,120个周期,平均4个,简单操作1个周期,平均约1.5个,CPU控制,大多数用微程序控制，有些使用硬连线控制,大多数用硬连线控制，没有控制存储器,代表性商品化处理器,Intel x86,Vax8600,IBM390,MC68040,Intel Pentium,AMD486和Cyrix686,SunUltraSparc,MIPS R10000Power PC-604,HP PA-8000,Digital Alpha 21164,混合CISC/RISC体系结构,Pentium Pro处理器的CISC/RISC体系结构,前端部分,基于RISC核心,DB,AB,将X86代码转化为RISC指令,