【教学课件】第二章数据表示与指令系统.ppt

第二章 数据表示与指令系统,2.1 数据表示2.2 浮点数据表示2.3 高级数据表示2.4 指令系统的优化设计2.5 指令系统设计的两种风格,2.1 数据表示,2.1.1 数据类型、数据表示与数据结构,整数、实数、布尔数、二进制位、字符、串、图、表、树、阵列、队列、链表、栈、向量等。,数据类型定义了具有相同属性一组值的集合，还定义了这个集合上的操作集。,基本数据类型：二进制位、整数、十进制数、浮点数、字符、布尔数等。,结构数据类型：由一组相互有关的数据元素复合而成的数据类型数组、字符串、向量、堆栈、队列、记录、树等,计算机体系结构所要研究的一个内容是：在所有这些数据类型中，哪些用硬件实现，哪些用软件实现，并研究它们的实现方法。,所有系统结构都支持基本数据类型,大多数系统结构只能部分地支持结构数据类型,数据表示：机器硬件能直接识别，并可以被指令调用的数据类型，由硬件实现的数据类型。,数据结构：结构数据类型的组织方式。研究数据类型的逻辑结构和物理结构之间的关系并给出算法，面向系统软件、面向应用领域所需处理的数据类型。由软件实现的数据类型。,确定哪些数据类型用数据表示实现，哪些数据类型用数据结构实现，是软硬件的主要分界面之一，本质上是一个软硬取舍问题。,缩短程序的运行时间占用存储空间少减少CPU和主存的通信量通用性和利用率,确定哪些数据类型用数据表示实现的原则：,例：实现A=A+B，A和B都是200200 的矩阵。标量机：6条指令,其中4条循环指令要执行200*200=40000次；因此CPU与主存之间的通信量为：取指令 2440000条；读或写数据 340000个；共要访问主存 740000次以上。,通用性不好,向量机：向量指令：1条指令,减少取指令操作4*40000=160000次，程序执行时间缩短了一半。,对复杂的树数据结构的支持较好，高效；但对向量、数组、链表等其他数据结构支持不够，低效。,举例1：引入树型数据表示,可高效地对向量、数组、链表、树等多种数据结构提供支持。,举例2：引入指针数据表示,通用性好,当选择产生冲突时，根据性能/价格衡量,从减少CPU和主存的通信量及缩短执行时间两方面看，对于处理矩阵运算，向量数据表示优越性要高。,实际系统设计,系统结构设计的任务：确定哪些数据类型用硬件即数据表示实现，哪些数据类型用软件实现，即数据结构，哪些数据类型由软件和硬件共同来实现。,复杂的数据类型一般通过数据结构或通过软硬件联合设计实现(如table、graph、record、tree等),简单的、常用的、通用的数据类型采用数据表示(如int、float、stack等)；,数据表示是数据结构的一个子集，数据结构通过 一定的算法变成数据表示才能在系统中处理；数据表示是软、硬件界面的一部分；数据结构是软件和应用的一部分。,数据结构与数据表示的关系,数据表示的确定实质上是软硬件的取舍问题,1.浮点数据表示的提出,早期的计算机系统只有定点数据表示优点：硬件结构简单缺点：编程困难：先确定小数点位置，小数点对齐再运算表示数的范围小：如16位字长表示的整数范围为：-3276832767数据存储单元的利用率很低（大量的前置0）,2.1.2 浮点数据表示,2.浮点数据表示的特点,计算机中的浮点数来源于数学中的实数，但两者有很多本质的区别：实数：表示范围无限，表示精度连续。浮点数：表示范围有限，表示精度不连续。,三大特点：表数范围、表数精度和表数效率关键问题：在数据字长确定的情况下，找到具有最大表数范围、最高表数精度和最大表数效率的浮点数表示方式。,3.浮点数据的表示方式,浮点数的一般格式：对任意浮点数N，可表示为：,其中：,m：尾数，多采用规格化小数表示e：阶码的值，一般采用整数、移码表示rm：尾数的基，一般采用二进制、十六进制re：阶码的基，一般采用二进制p：尾数长度（不包括符号位），当rm 16时，每四个二进制位表示一位尾数q：阶码长度(不包括阶码的符号）,浮点数的表示需要六个基本参数：尾数m、阶码e的值；尾数的基rm、阶码的基re、尾数长度p(不包括符号位)、阶码长度q(不包括符号位),一种浮点数的表示方式如下：,在浮点表示方式中尾数采用规格化小数的目的是为了在尾数中表示最多的有效数据位及数据表示的惟一性。0.00345 0.34510-2,尾数规格化,数符,阶符,（1）表数范围：在尾数采用原码p位、纯小数，阶码q位采用移码的浮点数表示方式中，规格化浮点数N的表数范围如下：,最大正数：最小正数：最大负数：最小负数：表数范围：,例如：尾数用原码，纯小数表示，阶码用移码整数表示，当p=23，q=7，rm=re=2时，规格化数N在正数区间的表数范围是：,在负数区间的表数范围是：,表示数的个数是：,规格化浮点数的个数应是可表示的阶码的个数与可表示的尾数的个数的乘积。,现以阶码为q=2，尾数p=4，正阶、正尾数为例，比较rm=2和rm=16时的不同情况。,在尾数基值rm 2（二进制），p=4(即尾数bit3bit0，共4位）、做规格化表示（即此时bit3=1）的正阶、正尾的数的范围：,在阶码相同的前提下，尾数采用不同基值时，表示的浮点数大小及个数均不相同。,可表示的最大正浮点数为,可表示规格化的最小正浮点数为,可表示的正阶、正尾规格化数的个数为,最大尾数为,最小阶码为,最大阶码为,阶码的个数为,最小尾数为,尾数的个数为,在尾数基值rm 16（十六进制）q2,p=4(尾数bit3bit0，4位二进制组成一个十六进制数）,做规格化表示（即此时bit3bit0 中必须有1位为“1”，不许出现全“0”，bit3bit0 为00011111）的正阶、正尾的数的范围：,最小尾数为,最大尾数为,最小阶码为,最大阶码为,阶码的个数为,可表示的最小正浮点数为,尾数的个数为,可表示的正阶、正尾规格化数的个数为,从上述例子，可得到下列两个结论：（1）当有相同阶码与尾数位数时，rm大，则表示数的范围也大，表示数的个数增多。rm只能取2，4，8，16，。一般使用2，8，16三种。,rm=2时，其个数是32。,可表示的最大正浮点数为,而rm=2时，其最大数是15/2。,（2）rm大时，虽然表示数的范围大，表示数的个数增加，但在数值的分布较稀疏。例如在数轴1/2-2之间，当rm 2时，有数15个；而当rm 16时，有数8个。,原因有两点：一是因为采用规格化表示的缘故。如上例中rm 2时，规格化后，其尾数个数只为原来的1/2；二是因为在同长度阶码时，rm不同，每次小数点移动位置不同，如上例中rm 2时，1个阶码值移动小数点1bit，而rm 16时，则移动4bits。故：rm 增大，则表示数的个数增加，数值上分布稀疏，从而计算误差增加。,rm=2,20(0.10010.1111),21(0.10.1111),rm=16,160(0.10010.1111),161(0.0001）,【例1】某计算机的浮点数采用1位符号位、6位阶码和9位尾数，基数为16，求规格化时它能表示数值的个数。,解：此浮点数共有16位,阶码为q=5，尾数位数p=9，re=2和rm=16。尾数用原码表示，阶码采用移码。,【例1】某计算机的浮点数采用1位符号位、7位阶码（移码）和8位尾数（原码规格化），基数为2，数据1在这种浮点格式中的表示为，这种浮点表示的大于1的最小数是。,解：此浮点数共有16位，格式如下：10.1211:0 1000001,100000001最小数：0 1000001,10000001,规格化表示的最小尾数,最小正尾数为：0.100000000,可表示的正规格化浮点数的个数为,可表示的负阶、正尾规格化数的个数为,可表示的正、负规格化浮点数的个数为,从上面的分析可以看到，规格化浮点数的表数范围主要与阶码的长度q和rm尾数基值有关，这时，能表示的绝对值最大的浮点数可近似为：,表数范围随着q和rm的增大而扩大。当有相同阶码与尾数位数时，rm大，则表示数的范围大。但rm大时，在数轴上的分布较稀疏。,当浮点数的尾数长度相同时，尾基为2时具有最高的表数精度。,（2）浮点数的表数精度,表数精度也称为表数误差，浮点数存在表数精度的根本原因是由于浮点数的不连续性造成的。浮点数表示的仅仅是实数的一个子集。,规格化浮点数的表数精度主要与尾数基值和尾数长度有关，一般认为尾数最后1位值的一半定义为表数精度,在尾数基值rm 16（十六进制）re 2,尾数4位（4位二进制组成一个十六进制数）、q=2时做规格化表示的最大正数、正规格化数的个数及一个数量单位的大小：,rm 2，正规格化尾数的个数8个，最大正数为(124)22，一个数量单位=(24)221/4,当表示的浮点数有相同的位数、尾数时，rm=2，有最大的表数精度。,rm 16，正规格化尾数的个数15个，最大正数为（1161）162，一个数量单位=(1/16)16216,尾数基值rm2与rm16相比，显然基值越大浮点数的表数效率高。,（3）浮点数的表数效率,浮点数的表数效率定义为,浮点数的表数范围、表数精度和表数效率三个主要特征都与尾数基值rm有关。,（4）浮点数尾数基值的选择,rm 2，表数效率只有50%，为了提高表数效率，许多计算机采用了隐藏位表示法，此时表数效率100%；,当浮点数字长确定后，rm取2，具有最大的表数范围、表数效率和最高的表数精度。,但rm 4时，就不能采用隐藏位表数法，因为尾数可以从00、01、10、11中取值，,IBM370系列机、IBM4300系列机等浮点数的尾数是16；Burroughs公司的B6700,B7700等大型计算机，浮点数尾数的基值是8；DEC公司的VAX-11、CDC公司CDC6600等大型机以及Intel公司的X86系列机等的浮点数均采用尾数基值为2。,应用情况：,浮点数加法中的对阶、规格化右移操作以及乘法中结果取单倍长度会把有效位移掉或截掉从而造成精度损失。,（5）浮点数的下溢处理,尾数下溢处理方式：,（1）截断。也称为不舍入法。简单地将下溢部分截去。在整数运算中最大会接近于1；误差大都是负误差。,（2）舍入法。被截尾数为1进1，运算中最大误差小于一半。,（3）恒置1法。被截尾数无论是0是1，恒置1。最大误差比截断法大。,（4）ROM或PLA法。也称查表舍入法，平均误差接近于零。,2.2 高级数据表示,自定义数据表示（Self-defining）带标志符的数据表示数据描述符向量数据表示堆栈数据表示,内容：堆栈、向量、数组（队列）、记录、自定义等。,目的：支持数据结构，提高系统效率和性能/价格比。,注意点：,新数据表示引入的可行性（原则）；新数据表示的必要条件（指令系统和硬件器件）；新数据表示的存取方法（如稀疏向量表示）。,2.2.1 自定义数据表示,引入思想：减小高级语言和机器语言的语义差距，减轻编译软件的工作量（减少指令种类）分类带标志符数据表示数据描述符,1.带标志符数据表示,定义：用以定义某个数据的数据类型和数值的数据表示。格式如下：,类型标志主要用于指明数据类型（如二进制整数、十进制整数等，也可用于指明机器内部所用信息的各种类型）。标志符由编译程序建立，对高级语言程序员来说是透明的。,优点：简化指令系统和程序设计简化了系统程序和编译程序的设计便于一致性校验能由硬件自动完成数据类型的变换支持数据库系统的实现与数据类型无关的要求为软件调试和应用软件开发提供支持缺点：硬件设计的复杂度增加（数据类型转换、一致性检验等）降低指令的执行速度必须用专门的指令完成标志符的初始化,引入可行性分析存储空间是否减少？,例2.2 设处理机A的数据不带标志符，指令字长和数据字长都是32位，设处理机B的数据带3位标志符，使数据字长增至35位，但可使指令字长减少至30位。现有1个程序正在处理机A和B上运行的目标程序都有IC条指令，平均每条指令访问2个操作数，每个操作数重复访问R次。（1）分别计算程序在处理机A和B上占用的存储空间大小。（2）在什么条件下，程序在处理机B上占用的存储空间才小于在处理机A上占用的存储空间？,解（1）程序在处理机A上占用的存储空间,程序在处理机B上占用的存储空间,（2）为实现MBMA即有程序在处理机A上占用的存储空间,由此可得R3，即当操作数平均重复访问次数R3，在带标志符的数据表示的处理机上运行的程序占用的存储空间会减小。,实现时间是否减少？取出数据后转换，必须推迟到运行时间进行专门的指令用于标志符初始化，增加了辅助开销指令执行过程中，对每个标志符进行逐个解释，并判断数据是否相容，因此单条指令的执行速度降低，但宏观执行时间减少宏观时间=设计时间+编译时间+调试时间,通用性和利用率这是一种理想的数据表示模式，通用性较好；只用一种存储器，利用率不高，采用指令和数据存储器后，利用率不会降低。,结论运行时间增加，存储空间减少。减小高级语言和机器语言的语义差距通用机中不使用，专用机（支持动态数据类型如LISP和PROLOG）中使用,2.数据描述符,目的：描述复杂和多维的结构类型，进一步减少标志符所占的存贮空间。,举例：现以美国Burroughs公司的B6500，7500为例进行自定义数据表示的说明，格式如下：,描述符,1：不连续数据,0：连续数据,1：数据集中的一个,0：数据集的全体,只准读出的数据,00：数据描述符,写其他描述符,0：不在主存中,1：在主存中,0：单精度数据,1：双精度数据,优点:实现阵列数据的索引比变址方法实现的好，而且能检查程序设计中阵列越界错误为向量、数组数据结构的实现提供一定的支持，有利于简化编译中的代码生成引入可行性分析：同带标志符的数据表示描述符的工作过程如下图,3.两种自定义数据表示的区别,标志符是和每一个数据相连的，合存在一个存储单元中，描述单个数据的类型特征。描述符是和数据分开存放的，专门用来描述所要访问的数据是整块数据还是单块数据，访问该数据块或数据元素所需要的地址以及其他特征信息等。,2.2.2 向量数据表示,向量表示向量通常是指由标量的一组有序集合表示的量，类似于一维数组标量通常只是一个整数或实数数组 A=(a0,a1,a2,an-1)可看成向量,向量在主存储器中的存放原则：规律性、地址计算简单、访存冲突小元素相邻存放元素等间距存放向量计算机-处理向量数据的计算机,举例：计算 ci=ai+bi,I=10,11,1000无向量数据表示(C语言)：for(i=10;i=1000;i+)ci=ai+bi;向量数据表示：C(10:1000)=A(10:1000)+B(10:1000),向量指令及包含的参数基地址、位移量、向量长度格式如下：,A,B,C:存放A,B,C的向量基址及长度,X,Y,Z:寄存器号，存放A,B,C的位移量,注：向量起始地址=基址+位移量 向量有效长度=向量长度-位移量 向量的数据地址起始地址位移量,a0,an-1,a10,举例：计算C(4：11)=A(4：11)+B(-4：3),向量起始地址=基址+位移量向量有效长度=向量长度-位移量,稀疏向量的压缩采用隐蔽位向量法（压缩向量）存取过程如图示：,描述符数据表示与向量数据表示对向量数据结构提供的支持有何不同？,在描述符数据表示的机器中，只能提供描述符寄存器和简单的地址形成逻辑等硬件，虽能支持向量数据结构的运算，但运行速度较慢。在向量数据表示的机器中，有丰富的向量运算指令，有大量的向量寄存器和并行、高速流水运算部件的支持，可以实现向量运算的高速执行。,堆栈数据表示,通用寄存器型机器对堆栈数据结构支持较差，表现为：-堆栈指令少，功能单一；-堆栈置于存储器内，访问堆栈速度慢,以寄存器寻址方式指令为主通用寄存器型机器。高级语言机器：高级语言和机器语言合二为一，高级语言不用编译，直接由机器硬件解释执行。如LISP,PROLOG计算机等。,堆栈机器：具有堆栈数据表示的机器,以堆栈寻址方式指令为主。,有若干高速寄存器组成的硬件堆栈，并附加控制电路让它与主存中的堆栈区在逻辑上组成一个整体，使堆栈的访问速度是寄存器的，堆栈的容量是主存的。,有很丰富的堆栈操作类指令且功能很强，直接可对堆栈中的数据进行各种运算和处理有力地支持高级语言程序的编译；逆波兰表达式如：F=A*B+C/(D-E)逆波兰表达式：AB*CDE-/+堆栈指令程序有力地支持子程序的嵌套和递归调用,数据表示小结：分类：基本数据表示 高级数据表示,标志符描述符,自定义数据表示向量数据表示堆栈数据表示,引入数据表示的原则：（1）系统效率高（2）通用性和利用率高,数据表示和数据结构的关系数据表示是数据结构的一个子集，面向硬件；数据结构是数据的组织方式，面向软件和应用由算法和软件实现两者的映射。,数据结构和数据表示是软硬件的界面,结论：数据结构的发展总是优于机器的数据表示,系统结构设计者的任务：从优化设计的角度，确定软硬件的分界面，哪些数据类型用数据表示来实现，哪些数据类型用数据结构来实现，应能对新型的数据结构提供更多更好的支持。,2.3 寻址方式与指令格式的优化设计,寻址方式分析程序定位技术指令格式的优化设计,寻址方式：是指令按什么方式寻找（访问）到所 需的操作数或信息。指令所访问的数据 主存、寄存器、堆栈 寻址能力的要求 多样性、灵活性、寻址空间范围大小、地址变换速度 目标：以最短的位描述给定的寻址方式,2.3.1 寻址方式分析,设置寻址方式的目标,寻址方式在指令中的指明方式占用操作码位：DJS200系列指令系统中8位操作码最高两位：间接（11）和直接（01）地址码设置寻址方式字段：VAX-11指令中源和目的各有4位寻址方式位字段,主存直接、间接、变址、基址、相对寻址 直接寻址使指令字变长 间接寻址使指令执行速度变慢 相对寻址用于条件转移指令中定位转向后代码的位置 变址寻址支持向量、数组，实现循环，用寄存器做变址器，地址码部分不会很长，访问数据速度相当于一次访问内存的速度 基址寻址支持逻辑地址到物理地址的变换，用于程序的动态再定位；,2.寻址方式,寄存器直接、间接寻址以寄存器寻址方式为主的计算机称为通用寄存器型计算机优点：-指令字长短-执行速度快-支持向量、矩阵运算缺点：-不利于编译程序的设计-不利于中断和子程序的递归调用-增加了硬件的复杂度,堆栈堆栈寻址（只对栈顶元素进行操作）特点：程序所占主存空间小，指令长度短 支持程序的嵌套和递归调用，支持中断处理 支持高级语言编译,面向主存：主要访问内存，少量访问寄存器op m1 m2面向通用寄存器：多数在寄存器，少量在内存op r m、op r1 r2面向堆栈：主要在堆栈，可减轻编译负担op、op m、op r,(2)寻址方式分类 大多数采用分类编址，有三类：,存储效率：堆栈型 通用寄存器型 程序占用空间小 利于减轻对高级语言编译的负担 支持子程序嵌套、递归调用 省去大量地址码字段，省空间 运算速度：堆栈型通用寄存器型 堆栈访存次数过多 面向寄存器方式支持向量、矩阵 一般在系统中三类寻址方式都应当采用,3.比较：,寻址方式分析多种寻址方式可以显著减少程序的指令条数，但这同时也可能增加实现的复杂度和使用这些寻址方式的指令的执行时钟周期数(CPI)，故需对多种寻址方式进行分析,2.3.2 程序定位技术,逻辑地址：程序员编写程序时使用的地址物理地址：程序在主存中的实际地址一般来讲，逻辑地址的空间大于物理地址的空间。因此，映射实际上是压缩。,程序定位技术直接定位：程序装入前，编译时就已确定了程序中的指令和数据的主存物理地址静态再定位：程序装入时，由定位装入程序把程序的逻辑地址变换成物理地址，而在程序的执行过程中，物理地址不再改变。,动态再定位：在执行每条指令时才形成访存物理地址的方法。通过基址寻址来实现,优点：提高了主存利用率主存中的同一个程序段可为多个程序共享支持虚拟存储器问题：需要硬件支持，虚拟存储器的软件管理算法也较复杂,2.3.3 指令格式的优化设计,指令=操作码+地址码指令格式的优化：如何用最短的位数来表示指令的操作信息和地址信息，使程序中指令的平均字长最短主要目标节省程序的存储空间指令格式尽量规整，便于译码,1.操作码的优化设计,操作码主要包括两部分内容操作种类：加减乘除、数据传送、移位、转移、I/O操作数描述：数据类型：定点、浮点、字符（串）、逻辑数、向量进位制：2、10、16进制数据字长：字、半字、双字、字节地址码通常包括三部分内容地址:直接、间接地址、立即数、寄存器编号、变址寄存器编号地址的附加信息:偏移量、块长度、间距寻址方式:直接、间接、立即数、变址、相对寄存器寻址,操作码的三种编码方法固定长度:规整性好,解码简单,占用空间大Huffman编码:空间小,规整性不好,解码复杂扩展编码:折衷方案哈夫曼(Huffman)压缩概念当各种事件发生的概率不均等时,采用优化技术对发生概率较高的事件用较短的位数(时间)来表示(处理),而对出现概率较低的允许用较长的位数(时间)来表示(处理),以达到平均位数最少的目的,用于代码压缩、程序压缩、空间压缩和时间压缩,操作码的优化表示信息源熵：信息源包含的平均信息量,操作码的优化表示就是要使信息冗余量R最小,H即为操作码可以达到的最短平均码长,信息冗余量,实际编码的操作码码长为：,例1.七条指令，频度如下 I1 I2 I3 I4 I5 I6 I7 0.4 0.3 0.15 0.05 0.04 0.03 0.03信息源熵 H=2.17,信息冗余量R=(3-2.17)/3=0.28=28%,（1）等长编码 可用000110来分别表示7种不同的指令 I1:000 I2:001 I3:010 I4:011 I5:100 I6:101 I7:110,（2）哈夫曼编码（操作码设计）,表示方法：哈夫曼树,基本思想（频率相关思想）：当事件发生的概率不均等时，对概率高的事件用较短的位数（或时间）来表示，对概率低的事件用较长的位数（或时间）来表示，导致平均位数（时间）最短。,(1)将事件的使用频度值作为叶结点并按出现频率次序排列；（排序）(2)将出现频率最小的两个事件合并（频率相加）形成一个新结点；（合并）(3)在新组成的叶结点序列中继续做(2)，直至到根结点（频率1，构成一棵树)；(4)从树根起沿左和右子树分别分配其值为1和0，直至叶结点；（分配值）(5)事件的使用频度值叶结点编码为从根结点到叶结点的编码组合。（得到编码）,构建方法：,1,0,0,0,0,0,0,1,1,1,0.09,0.15,1,0.06,1,I1 I2 I3 I4 I5 I6 I7 0.4 0.3 0.15 0.05 0.04 0.03 0.03,0 10 110 11100 11101 11110 11111,叶结点,根结点,合并结点,由此可得到哈夫曼编码如下：I1:0 I2:10 I3:110 I4:11100 I5:11101 I6:11110 I7:11111,信息冗余量R=(2.20-2.17)/2.20=1.36%指令长度个数=4,平均码长L=0.4*1+0.3*2+0.15*3+0.05*5+0.04*5+0.03*5+0.03*5=2.20位,Huffman特点:-平均码长最短-代码不唯一：（0,1 可对换）,（3）哈夫曼扩展编码（操作码优化）扩展编码法,基本思想：对霍夫曼编码，根据使用频率宏观分布，将编码长度扩展成几种长度的编码。,实现目标：平均码长接近全哈夫曼码的码长，同时又保持了定长码的规整性。,Huffman操作码的主要缺点操作码长度很不规整,硬件译码困难与地址码共同组成固定长的指令比较困难,例1:Huffman用四种长度0,10,110,11100,11101,11110,111110.4,0.3,0.15,0.05,0.04,0.03,0.03扩展哈夫曼编码如下：I1,I2,I3 用两位:00,01,10I4,I5,I6,I7 用四位:1100,1101,1110,1111L=(0.4+0.3+0.15)*2+(0.05+0.04+0.03+0.03)*4=2.30位,信息冗余量=(2.30-2.20)/2.30=0.0565=5.65%,操作码的扩展（等长扩展）,平均码长：2.2 2.3,扩展方法：等长扩展和不等长扩展两种。,等长扩展每次扩展相同的位数 如4-8-12等长扩展方法（每次扩展4位）不等长扩展每次扩展不同的位数 如4-6-10不等长扩展方法(美国的B-1700),扩展标志：保留码点标志一组编码作为扩展标志 保留标志位一个标志位作为扩展标志,扩展编码中选择某些特征位用于扩展。,0001,0000,1110,15,0000,0001,.,.,.,1110,15,1111,.,.,.,1111,1111,.,.,.,0000,0001,1110,15,1111,.,.,.,1111,1111,.,.,.,1111,1111,1111,.,.,.,15/15/15扩展法,8/64/512编码法,码点标志,码点标志,保留标志位,保留标志位,4-8-12等长扩展编码,采用保留特征码（码点标志）方法编码简单，但表示的指令总数少。例如：4-8-12等长编码，15-15-15每种长度指令数为15，共可编码45种平均每条指令位数=(4812)15/45=8采用保留标志位方法编码较为复杂，但表示的指令总数多。例如：4-8-12等长编码，8-64-512共有指令数为584平均每条指令位数（8464851212）/584=11.45,例2：指令系统共有42种指令，前15种使用频率平均为0.05，中间13种使用频率平均为0.015，最后14种使用频率平均为0.004。如何编码？,解：因频率分布有三种，故码长可有三种；,因每段指令数基本相同，故可采用等长扩展(4-8-12位)，保留特征码的每段指令数相同(15-15-15)方法。结果如图所示；,结果：采用15-15-15扩展方法，最后一种编码用于扩展，每段00001110用于编码，1111用于扩展。,例3：指令系统共有74种指令，前4种使用频率平均为0.12，中间15种使用频率平均为0.02，最后55种使用频率平均为0.004。如何编码？,解：同上例方法，码长可有三种；,因每段指令数成比例(1：4)，故可采用等长扩展方法(3-6-9位)扩展，保留标志位方法，结果如图所示；,结果：采用4-16-64扩展方法，编码第一位用于扩展，每段0XX用于编码，1XX用于扩展。,0 xx 4种1xx 0 xx 16种1xx 1xx 0 xx 64种,4-16-64平均码长=0.12*4*3+0.02*15*6+0.004*55*9=5.22；,例4：指令系统共有78种指令，前10种使用频率平均为0.049，中间18种使用频率平均为0.02，最后50种使用频率平均为0.003。如何编码？,解：同上例方法，码长可有三种；因每段指令数比例为1：2：5，故不可采用等长扩展，采用不等长编码(4-6-10位)较能减少平均码长。,第一种采用4位编码中前10种(0000-1001)；第二种采用第一种频率编码中的后5种编码(1010-1110)与扩展的2位共20种编码；第三种采用第一种频率编码中的最后一种(1111)与扩展的6位共64种编码。,有了操作码的优化表示之后，必须有地址码的相应配合，才能使整个指令字格式优化表示。操作数地址码长度和个数可在很宽的范围内变化，只要恰当安排就可与变长操作码很好合成定长指令。,地址码的优化,整数边界存储保证访存速度造成浪费,多种指令长度，有些指令出现跨越边界存储而需要两个主存周期的情况，会使机器速度明显下降。,(1)多种地址制：要使操作码的长度因优化而缩短的空位充分利用，通过改变指令字中地址码的个数，以使单地址、双地址、三地址和零地址都可以在指令中使用。,(1)多种寻址方式：采取多种灵活的寻址方式，或在指令空白处存放立即操作数或常数，提高地址码段的利用率。,5.IBM370指令格式举例,IBM370系列计算机的指令长度有16位、32位和48位3种，所有指令的操作码都是8位固定长度，操作码的最高两位用来指明指令的长度和格式。具体如下：00为RR格式，指令字长16位01为RX格式，指令字长32位10为RS或SI格式，指令字长32位11为SS格式，指令字长48位这里R代表寄存器，S代表存贮器，X代表变址，I代表立即操作数。,RR型,(R1)OP(R2)R1,RX型,(R1)OP M(X2)+(B2)+D2 R1,RS型,(R3)OP M(B2)+D2 R1,SI型,I OP M(B1)+D1 M(B1)+D1,SS型,L：M2(B2)+D2 M1(B1)+D1,多种指令字长：16位（RR型）、32位、48位（SS型）,多种地址码长：8位（RR型）、24位、40位（SS型）,多种寻址方式：R寻址、变址寻址、偏移寻址,多种操作数地址制：双操作数地址、三操作数地址,例题,1.若某机要求有：三地址指令4条，单地址指令192条，零地址指令16条。设指令字长为12位，每个地址码长3位。问能否以扩展操作码为其编码？,1.解：三种指令格式字如下：,OPC,000 xxx xxx xxx 011 xxx xxx xxx 000 000 xxx 111 101 xxx111 111 110 000 111 111 111 111,三地址4条,一地址192条,零地址16条,3,3,3,3,三地址指令4条,单地址指令192条,零地址指令16条,2.某机指令字长16位。设有单地址指令和双地址指令两类。若每个地址字段为6位，且双地址指令有X条。问单地址指令最多可有多少条？解：二种指令格式字如下：,由于双地址指令有X条，单地址指令最多可有：,指令系统性能分析,为了评价各种指令系统的性能，分别在下列5种不同指令系统的处理机上计算算术表达式：,处理机1：三地址指令系统；处理机2：二地址指令系统（无通用寄存器）；处理机3：一地址指令系统：(通用寄存器）处理机4：零地址指令系统（堆栈型处理机）；处理机5：二地址多累加器(通用寄存器)指令系统。,（1）用5种不同类型的指令系统分别编写5个程序计算表达式X的值，所有程序都用直接寻址方式编写，并假设数据ag已经存放在相应的AG存储单元中。最终运算结果存入主存X单元中。,（2）对5个程序分别统计出指令条数、访存次数、程序存储量和访存信息量。访存次数包括访取指令、到存储器读操作数和将结果写入存储器的访存操作次数。程序存储量是指所有指令占用的存储空间，不包括数据占用空间，因为数据占用空间对所有处理机是相同的。,访存信息量是指所有取指令访存和读写操作数访存信息的和。并假设一个操作码为1B，一个地址码为2B，一个数据为4B，一个通用寄存器地址为0.5B。统计的程序存储量和访存信息量以字节为单位。,（3）根据（2）统计的结果，分别对程序存储量和访存信息量进行排序。,（1）用三地址指令编写的程序如下：ADD X，A，B；X单元暂时用来存放中间结果 MUL X，X，C MUL Y，D，E；Y单元暂存中间结果 ADD X，X，Y SUB Y，F，G DIV X，X，Y共6条指令。每条指令需3次访存读/写操作数（二次读数，一次写运算结果）。访问主存读/写操作数的总次数为：63=18。程序占用量：6（1+32）42B访存总量：421844272112B,一个操作码为1B，一个地址码为2B，一个数据为4B，一个通用寄存器地址为0.5B。,用二地址指令(无累加器）编写的程序如下：MOV X，A；复制一个变量到X单元 ADD X，B MUL X，C MOV Y，D MUL Y，E ADD X，Y MOV Y，F SUB Y，G DIV X，Y；最后结果存放在X单元共9条指令，其中三条传送指令每条执行时2次访问主存，其他6条指令每条执行时3次访问主存。访问主存读/写操作数的总次数为：32+63=24程序占用量：9（1+22）45B访存总量：452444596141B,一个操作码为1B，一个地址码为2B，一个数据为4B，一个通用寄存器地址为0.5B。,用一地址指令（隐含累加器）编写程序如下：LOAD F；先做分母（取F单元的数据送累加器）SUB G；累加器累加器GSTORE X；暂存f-g于X单元LOAD AADD BMUL CSTORE Y；暂存(a+b)cLOAD DMUL EADD YDIV XSTORE X共12条指令，每条指令只需一次访存取得操作数（12）。,访问主存读/写操作数的总次数为：12程序占用量：12（1+2）36B访存总量：36124364884B,用零地址指令编写程序时，首先要将这个算术表达式转换成波兰表达式。编写程序如下：PUSH A；将操作数a压入堆栈 PUSH B；将操作数b压入堆栈 ADD；从栈顶弹出两个操作数，结果压入堆栈 PUSH C MUL PUSH D PUSH E MUL ADD PUSH F PUSH G,SUB DIV POP X；从堆栈栈顶弹出结果送主存X单元在以上14条指令中，8条一地址指令，每条指令执行时需2次访问主存；6条零地址指令，每条指令执行时3次访问主存。,访问主存读/写操作数的总次数为：82+63=34程序占用量：8（1+2）630B访存总量：3034430136166B,用二地址多累加器（设有通用寄存器R1、R2）程序：MOVE R1，A；复制一个变量到通用寄存器R1 ADD R1，B MUL R1，C MOVE R2，D MUL R2，E ADD R1，R2 MOVE R2，F SUB R2，G DIV R1，R2 MOVE X，R1；将通用寄存器的结果存放到X单元在以上10条指令中，有4条传送指令和4条运算指令，每条指令执行时一次访问主存，另外二条寄存器操作指令无须访问主存。该程序执行时由于读写操作数访问主存总次数为8次。,（2）根据以上5种程序，统计有关信息量如下表,（3）根据（2）统计的结果，对程序存量的排序为：,对程序执行时的访存信息量的排序为：,分析结果表明：二地址R-S型指令程序存储量、访存信息量最少。,2.4 指令系统的发展方向,增强指令功能，实现软件功能向硬件转移复杂指令系统计算机(CISC)尽可能降低指令功能及结构的复杂程度，以达到简化实现，提高性能的目的精简指令指令系统计算机(RISC),复杂指令系统计算机(CISC),CISC(Complex Instruction Set Computer)复杂指令集计算机（硬件比例增大）进一步增强原有指令的功能，设置复杂的功能更强的新指令代替原先由软件子程序实现的功能，进行软件功能的硬化，以达到减少程序的指令条数，提高性能的目的。,按CISC方向改进指令系统 1.面向目标程序增强指令功能的优化与改进2.面向高级语言及编译程序的指令功能的优化与改进 3.面向操作系统的指令功能的优化与改进,基本操作采用一条指令还是多条指令？,静态使用频度：对程序中出现的各种指令以及指令串进行统计得出的百分比。动态使用频度：在目标程序执行过程中对出现的各种指令和指令串进行统计得出的百分比。,静态使用频度改进指令功能：侧重减少占用空间 动态使用频度改进指令功能：侧重减少运行时间,方法：统计使用频度,依据效率是否提高缩短目标程序长度、减少指令执行时间、减少程序执行期间CPU与主存的通信量。,1.面向目标程序指令功能的改进,基于哈夫曼思想：对于那些频度高的常用指令，可以考虑增强其功能，加快其执行速度，缩短其指令字长；而对于那些使用频度很低的指令就可以考虑将其取消，或将其功能合并到某些频度较高的指令中去。,例：Z80微型计算机的自增循环指令LDIR长度为2个字节，传送一个数椐为5个或4个时钟周期。因此，当传送100个数时，需499个周期。,优化传送类指令：如成组传送指令、自增循环（LDIR）、自减循环（LDDR）等 优化转移类指令：多种转移指令等 优化运算类指令：如多项式运算指令POLY,（1）数据传送类 设置成组传送类指令。（2）程序控制类 设置多种程序控制指令，可通过相对寻址或常规的寻址方式把新地址送入程序计数器来实现转移，以达到缩小程序空间和提高软件运行效率的目的。（3）运算型 增设复合指令取代原宏指令或子程序实现的功能。如：开平方、求三角函数、对数函数、指数函数等。,根据统计分析，需增强下面几类指令的功能：,目