数据表示与指令系统.pptx

《数据表示与指令系统.pptx》由会员分享，可在线阅读，更多相关《数据表示与指令系统.pptx（165页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、2.1 2.1 数据表示 2.1.1 数据类型、数据表示与数据结构整数、实数、布尔数、二进制位、字符、串、图、表、树、阵列、队列、链表、栈、向量等。数据类型定义了具有相同属性一组值的集合，还定义了这个集合上的操作集。数据数据 用户定义的数据用户定义的数据 用户程序中使用用户程序中使用 系统数据系统数据 执行程序时生成执行程序时生成 指令指令 数据的复合数据的复合第1页/共165页l 基本数据类型：二进制位、整数、十进制数、浮点数、字符、布尔数等。l结构数据类型：由一组相互有关的数据元素复合而成的数据类型数组、字符串、向量、堆栈、队列、记录、树等 计算机体系结构所要研究的一个内容是：在所有这些数

2、据类型中，哪些用硬件实现，哪些用软件实现，并研究它们的实现方法。所有系统结构都支持基本数据类型大多数系统结构只能部分地支持结构数据类型第2页/共165页数据表示：机器硬件能直接识别，并可以被指令调用的数据类型，由硬件实现的由硬件实现的数据类型。数据类型。数据结构：结构数据类型的组织方式。研究数据类型的逻辑结构和物理结构之研究数据类型的逻辑结构和物理结构之间的关系并给出算法，面向系统软件、面向应用领域所需处理的数据类型。间的关系并给出算法，面向系统软件、面向应用领域所需处理的数据类型。由由软件实现的数据类型。软件实现的数据类型。确定哪些数据类型用数据表示实现，哪些数据类型用数据结构实现，是软硬件

3、的主要分界面之一，本质上是一个软硬取舍问题。数据结构 基本数据类型映像存储器第3页/共165页缩短程序的运行时间占用存储空间少减少CPU和主存的通信量通用性和利用率确定哪些数据类型用数据表示实现的原则：例：实现A=A+B，A和B都是200200 的矩阵。标量机：6 6条指令,其中4 4条循环指令要执行200*200=40000200*200=40000次；因此CPUCPU与主存之间的通信量为：取指令 2 2440000440000条；读或写数据 340000340000个；共要访问主存 740000740000次以上。第4页/共165页通用性不好向量机：向量指令：1 1条指令,减少取指令操作4

4、*40000=1600004*40000=160000次，程序执行时间缩短了一半。对复杂的树数据结构的支持较好，高效；但对向量、数组、链表等其他数据结构支持不够，低效。举例1：引入树型数据表示可高效地对向量、数组、链表、树等多种数据结构提供支持。举例2：引入指针数据表示通用性好当选择产生冲突时，根据性能/价格衡量 从减少CPU和主存的通信量及缩短执行时间两方面看，对于处理矩阵运算，向量数据表示优越性要高。第5页/共165页实际系统设计 系统结构设计的任务：确定哪些数据类型用硬件即数据表示实现，哪些数据类型用软件实现，即数据结构，哪些数据类型由软件和硬件共同来实现。复杂的数据类型一般通过数据结构

5、或通过软硬件联合设计实现(如table、graph、record、tree等)简单的、常用的、通用的数据类型采用数据表示(如int、float、stack等)；第6页/共165页 数据表示是数据结构的一个子集，数据结构通过 一定的算法变成数据表示才能在系统中处理；数据表示是软、硬件界面的一部分；数据结构是软件和应用的一部分。l 数据结构与数据表示的关系数据结构数据表示软硬件的界面数据表示的确定实质上是软硬件的取舍问题第7页/共165页1.1.浮点数据表示的提出早期的计算机系统只有定点数据表示优点：硬件结构简单缺点：编程困难：先确定小数点位置，小数点对齐再运算表示数的范围小：如1616位字长表示

6、的整数范围为：-32768-327683276732767数据存储单元的利用率很低（大量的前置0 0）2.1.2 浮点数据表示第8页/共165页2.2.浮点数据表示的特点计算机中的浮点数来源于数学中的实数，但两者有很多本质的区别：实数：表示范围无限，表示精度连续。浮点数：表示范围有限，表示精度不连续。三大特点：表数范围、表数精度和表数效率关键问题：在数据字长确定的情况下，找到具有最大表数范围、最高表数精度和最大表数效率的浮点数表示方式。-Nmin 0 -NmaxNminNmax可表示的负数可表示的正数负下溢区负上溢区正下溢区正上溢区第9页/共165页3.3.浮点数据的表示方式浮点数的一般格式：

7、对任意浮点数N，可表示为：其中：其中：m：尾数，多采用规格化小数表示：尾数，多采用规格化小数表示e：阶码的值，一般采用整数、移码表示阶码的值，一般采用整数、移码表示rm：尾数的基，一般采用二进制、十六进制：尾数的基，一般采用二进制、十六进制re：阶码的基，一般采用二进制：阶码的基，一般采用二进制p：尾数长度（不包括符号位），当：尾数长度（不包括符号位），当rm 16时，每四个二进制位表示一位时，每四个二进制位表示一位尾数尾数q：阶码长度：阶码长度(不包括阶码的符号）不包括阶码的符号）第10页/共165页浮点数的表示需要六个基本参数：尾数m m、阶码e e的值；尾数的基r rm m、阶码的基r

8、re e、尾数长度p(p(不包括符号位)、阶码长度q(q(不包括符号位)一种浮点数的表示方式如下：一种浮点数的表示方式如下：mf ef e m 1 1 q p 在浮点表示方式中尾数采用规格化小数的目的是为了在尾数中表示最多的有效数据位及数据表示的惟一性。0.00345 0.34510-2尾数规格化数符阶符第11页/共165页 （1 1）表数范围：在尾数采用原码p p位、纯小数，阶码q q位采用移码的浮点数表示方式中，规格化浮点数N的表数范围如下：最大正数：最小正数：最大负数：最小负数：表数范围：第12页/共165页例如：尾数用原码，纯小数表示，阶码用移码整数表示，当p=23，q=7，rm=re

9、=2时，规格化数N在正数区间的表数范围是：在负数区间的表数范围是：表示数的个数是：规格化浮点数的个数应是可表示的阶码的个数与可表示的尾数的个数的乘积。第13页/共165页现以阶码为q=2，尾数p=4，正阶、正尾数为例，比较rm=2和rm=16时的不同情况。7 6 5 4 3 2 1 0阶符00尾符在尾数基值rm 2（二进制），p=4(即尾数bit3bit0，共4位）、做规格化表示（即此时bit3=1）的正阶、正尾的数的范围：在阶码相同的前提下，尾数采用不同基值时，表示的浮点数大小及个数均不相同。第14页/共165页 可表示的最大正浮点数为可表示规格化的最小正浮点数为可表示的正阶、正尾规格化数的

10、个数为最大尾数为 最小阶码为 最大阶码为阶码的个数为最小尾数为尾数的个数为第15页/共165页在尾数基值rm 16（十六进制）q2,p=4(尾数bit3bit0，4位二进制组成一个十六进制数）,做规格化表示（即此时bit3bit0 中必须有1位为“1”，不许出现全“0”，bit3bit0 为00011111）的正阶、正尾的数的范围：最小尾数为最大尾数为第16页/共165页最小阶码为 最大阶码为阶码的个数为可表示的最小正浮点数为尾数的个数为第17页/共165页可表示的正阶、正尾规格化数的个数为从上述例子，可得到下列两个结论：（1）当有相同阶码与尾数位数时，rm大，则表示数的范围也大，表示数的个数

11、增多。rm只能取2，4，8，16，。一般使用2，8，16三种。rm=2时，其个数是32。可表示的最大正浮点数为而rm=2时，其最大数是15/2。第18页/共165页（2）rm大时，虽然表示数的范围大，表示数的个数增加，但在数值的分布较稀疏。例如在数轴1/2-2之间，当rm 2时，有数15个；而当rm 16时，有数8个。原因有两点：一是因为采用规格化表示的缘故。如上例中rm 2时，规格化后，其尾数个数只为原来的1/2；二是因为在同长度阶码时，rm不同，每次小数点移动位置不同，如上例中rm 2时，1个阶码值移动小数点1bit，而rm 16时，则移动4bits。故：rm 增大，则表示数的个数增加，数

12、值上分布稀疏，从而计算误差增加。rm=2,20(0.10010.1111),21(0.10.1111)rm=16,160(0.10010.1111),161(0.0001）1/2 1 2第19页/共165页【例1】某计算机的浮点数采用1位符号位、6位阶码和9位尾数，基数为16，求规格化时它能表示数值的个数。解：此浮点数共有16位阶码为q=5，尾数位数p=9，re=2和rm=16。尾数用原码表示，阶码采用移码。可表示的正阶、正尾规格化数的个数为最大阶码为阶码的个数为最大尾数为(0.1FF)第20页/共165页l【例1】某计算机的浮点数采用1位符号位、7位阶码（移码）和8位尾数（原码规格化），基数

13、为2，数据1在这种浮点格式中的表示为 ，这种浮点表示的大于1的最小数是 。解：此浮点数共有16位，格式如下：10.1211:0 1000001,100000001最小数：0 1000001,10000001规格化表示的最小尾数 15 14 9 8 0数符尾数阶码第21页/共165页最小正尾数为：0.100000000可表示的正规格化浮点数的个数为可表示的负阶、正尾规格化数的个数为可表示的正、负规格化浮点数的个数为第22页/共165页 从上面的分析可以看到，规格化浮点数的表数范围主要与阶码的长度q和rm尾数基值有关，这时，能表示的绝对值最大的浮点数可近似为：表数范围随着q和rm的增大而扩大。当有

14、相同阶码与尾数位数时，rm大，则表示数的范围大。但rm大时，在数轴上的分布较稀疏。第23页/共165页 当浮点数的尾数长度相同时，尾基为2 2时具有最高的表数精度。（2 2）浮点数的表数精度浮点数的表数精度 表数精度也称为表数误差，浮点数存在表数精度的根本原因是由于浮点数的不连续性造成的。浮点数表示的仅仅是实数的一个子集。规格化浮点数的表数精度主要与尾数基值和尾数长度有关，一般认为尾数最后1位值的一半定义为表数精度第24页/共165页在尾数基值rm 16（十六进制）re 2,尾数4位（4位二进制组成一个十六进制数）、q=2时做规格化表示的最大正数、正规格化数的个数及一个数量单位的大小：rm 2

15、，正规格化尾数的个数8个，最大正数为 (124)22，一个数量单位=(24)221/4当表示的浮点数有相同的位数、尾数时，rm=2，有最大的表数精度。rm 16，正规格化尾数的个数15个，最大正数为 （1161）162，一个数量单位=(1/16)16216第25页/共165页 尾数基值rm2与rm16相比，显然基值越大浮点数的表数效率高。（3 3 3 3）浮点数的表数效率）浮点数的表数效率浮点数的表数效率定义为第26页/共165页浮点数的表数范围、表数精度和表数效率三个主要特征都与尾数基值rm有关。（4 4）浮点数尾数基值的选择rm 2 2，表数效率只有50%50%，为了提高表数效率，许多计算

16、机采用了隐藏位表示法，此时表数效率100%100%；当浮点数字长确定后，rm取2 2，具有最大的表数范围、表数效率和最高的表数精度。但rm 4时，就不能采用隐藏位表数法，因为尾数可以从00、01、10、11中取值，第27页/共165页IBM370系列机、IBM4300系列机等浮点数的尾数是16；Burroughs公司的B6700,B7700等大型计算机，浮点数尾数的基值是8；DEC公司的VAX-11、CDC公司CDC6600等大型机以及Intel公司的X86系列机等的浮点数均采用尾数基值为2。应用情况：第28页/共165页浮点数加法中的对阶、规格化右移操作以及乘法中结果取单倍长度会把有效位移掉

17、或截掉从而造成精度损失。（5 5）浮点数的下溢处理尾数下溢处理方式：（1）截断。也称为不舍入法。简单地将下溢部分截去。在整数运算中最大会接近于1；误差大都是负误差。（2）舍入法。被截尾数为1进1，运算中最大误差小于一半。（3）恒置1法。被截尾数无论是0是1，恒置1。最大误差比截断法大。（4）ROM或PLA法。也称查表舍入法，平均误差接近于零。第29页/共165页2.2 2.2 高级数据表示自定义数据表示（Self-definingSelf-defining）带标志符的数据表示数据描述符向量数据表示堆栈数据表示 内容：堆栈、向量、数组（队列）、记录、自定义等。目的：支持数据结构，提高系统效率和性

18、能/价格比。第30页/共165页 注意点：新数据表示引入的可行性（原则）；新数据表示的必要条件（指令系统和硬件器件）；新数据表示的存取方法（如稀疏向量表示）。第31页/共165页2.2.1 2.2.1 自定义数据表示引入思想：减小高级语言和机器语言的语义差距，减轻编译软件的工作量（减少指令种类）分类带标志符数据表示数据描述符第32页/共165页1.1.带标志符数据表示定义：用以定义某个数据的数据类型和数值的数据表示。格式如下：类型标志主要用于指明数据类型（如二进制整数、十进制整数等，也可用于指明机器内部所用信息的各种类型）。标志符由编译程序建立，对高级语言程序员来说是透明的。类型标志 数据第3

19、3页/共165页优点：简化指令系统和程序设计简化了系统程序和编译程序的设计便于一致性校验能由硬件自动完成数据类型的变换支持数据库系统的实现与数据类型无关的要求为软件调试和应用软件开发提供支持缺点：硬件设计的复杂度增加（数据类型转换、一致性检验等）降低指令的执行速度必须用专门的指令完成标志符的初始化第34页/共165页引入可行性分析存储空间是否减少？BA数据指令总数少总数多通常有面积B面积A采用标志符后 数据字增长不采用标志符采用标志符后 指令字缩短第35页/共165页例2.2 设处理机A的数据不带标志符，指令字长和数据字长都是32位，设处理机B的数据带3位标志符，使数据字长增至35位，但可使指

20、令字长减少至30位。现有1个程序正在处理机A和B上运行的目标程序都有IC条指令，平均每条指令访问2个操作数，每个操作数重复访问R次。（1）分别计算程序在处理机A和B上占用的存储空间大小。（2）在什么条件下，程序在处理机B上占用的存储空间才小于在处理机A上占用的存储空间？第36页/共165页l解 （1）程序在处理机A上占用的存储空间l程序在处理机B上占用的存储空间l（2）为实现MB3，即当操作数平均重复访问次数R3，在带标志符的数据表示的处理机上运行的程序占用的存储空间会减小。第37页/共165页实现时间是否减少？取出数据后转换，必须推迟到运行时间进行专门的指令用于标志符初始化，增加了辅助开销指

21、令执行过程中，对每个标志符进行逐个解释，并判断数据是否相容，因此单条指令的执行速度降低，但宏观执行时间减少宏观时间=设计时间+编译时间+调试时间第38页/共165页通用性和利用率这是一种理想的数据表示模式，通用性较好；只用一种存储器，利用率不高，采用指令和数据存储器后，利用率不会降低。结论运行时间增加，存储空间减少。减小高级语言和机器语言的语义差距通用机中不使用，专用机（支持动态数据类型如LISPLISP和PROLOGPROLOG）中使用第39页/共165页2.2.数据描述符目的：描述复杂和多维的结构类型，进一步减少标志符所占的存贮空间。举例：现以美国BurroughsBurroughs公司的

22、B6500B6500，75007500为例进行自定义数据表示的说明，格式如下：描述符标志位特征标记数据块长度数据块起始地址382020格式：第40页/共165页数据000数值描述符101P CISRTD长度地址3111120220111：不连续数据0：连续数据1：数据集中的一个0：数据集的全体只准读出的数据00：数据描述符写其他描述符0：不在主存中1：在主存中0：单精度数据1：双精度数据第41页/共165页优点:实现阵列数据的索引比变址方法实现的好，而且能检查程序设计中阵列越界错误为向量、数组数据结构的实现提供一定的支持，有利于简化编译中的代码生成引入可行性分析：同带标志符的数据表示描述符的工

23、作过程如下图第42页/共165页101000000101101101XY操作码指令描述符描述符地址生成逻辑（数据）（数据）数据块数据块主存储器第43页/共165页第44页/共165页3.3.两种自定义数据表示的区别标志符是和每一个数据相连的，合存在一个存储单元中，描述单个数据的类型特征。描述符是和数据分开存放的，专门用来描述所要访问的数据是整块数据还是单块数据，访问该数据块或数据元素所需要的地址以及其他特征信息等。第45页/共165页2.2.2 2.2.2 向量数据表示向量表示向量通常是指由标量的一组有序集合表示的量，类似于一维数组标量通常只是一个整数或实数数组 A=(aA=(a0 0,a,a

24、1 1,a,a2 2,a,an-1n-1)可看成向量Aa0a1a11l 向量在主存储器中的存放原则：规律性、地址计算简单、访存冲突小元素相邻存放元素等间距存放l向量计算机-处理向量数据的计算机第46页/共165页举例：计算 c ci i=a=ai i+b+bi i,I=10,11,1000,I=10,11,1000无向量数据表示(C(C语言)：for(i=10;i=1000;i+)for(i=10;i=1000;i+)ci=ai+bi;ci=ai+bi;向量数据表示：C(10:1000)=A(10:1000)+B(10:1000)C(10:1000)=A(10:1000)+B(10:1000)

25、向量加 X A Y B Z Cl向量指令及包含的参数基地址、位移量、向量长度格式如下：A,B,C:存放A,B,C的向量基址及长度X,Y,Z:寄存器号，存放A,B,C的位移量第47页/共165页注：向量起始地址=基址+位移量 向量有效长度=向量长度-位移量 向量的数据地址起始地址位移量a0an-1a10第48页/共165页举例：计算C(4C(4：11)=A(411)=A(4：11)+B(-411)+B(-4：3)3)A0A3A2A1A11A10A9A8A7A6A5A4C0C3C2C1C11C10C9C8C7C6C5C4B3B2B1B0B-1B-2B-3B-4源向量A结果向量C源向量B位移量Ad=

26、4基址Ab起始地址 As=4Ae=12-4=8Cd基址Cb起始地址 Cs=4Ce=12-4=8起始地址 Bs=4 Be=4(4)=8位移量 Bd=4基址Bb向量起始地址=基址+位移量向量有效长度=向量长度-位移量第49页/共165页稀疏向量的压缩采用隐蔽位向量法（压缩向量）存取过程如图示：A0A3A4A5(0)A6(0)A7A1(0)A2(0)012356471A00A10A20A61A31A41A70A5A0稀疏向量A3A4A7压缩向量Z向量（有序位向量）第50页/共165页描述符数据表示与向量数据表示对向量数据结构提供的支持有何不同？在描述符数据表示的机器中，只能提供描述符寄存器和简单的地

27、址形成逻辑等硬件，虽能支持向量数据结构的运算，但运行速度较慢。在向量数据表示的机器中，有丰富的向量运算指令，有大量的向量寄存器和并行、高速流水运算部件的支持，可以实现向量运算的高速执行。第51页/共165页2.2.32.2.3 堆栈数据表示 通用寄存器型机器对堆栈数据结构支持较差，表现为：-堆栈指令少，功能单一；-堆栈置于存储器内，访问堆栈速度慢以寄存器寻址方式指令为主通用寄存器型机器。高级语言机器：高级语言和机器语言合二为一，高级语言不用编译，直接由机器硬件解释执行。如LISP,PROLOG计算机等。第52页/共165页 堆栈机器：具有堆栈数据表示的机器,以堆栈寻址方式指令为主。主存寄存器控

28、制逻辑堆栈l 有若干高速寄存器组成的硬件堆栈，并附加控制电路让它与主存中的堆栈区在逻辑上组成一个整体，使堆栈的访问速度是寄存器的，堆栈的容量是主存的。第53页/共165页l有很丰富的堆栈操作类指令且功能很强，直接可对堆栈中的数据进行各种运算和处理l有力地支持高级语言程序的编译；逆波兰表达式如：F=A*B+C/(D-E)F=A*B+C/(D-E)逆波兰表达式：AB*CDE-/+AB*CDE-/+堆栈指令程序l有力地支持子程序的嵌套和递归调用第54页/共165页第55页/共165页数据表示小结：分类：基本数据表示 高级数据表示标志符描述符自定义数据表示向量数据表示堆栈数据表示引入数据表示的原则：（

29、1）系统效率高（2）通用性和利用率高第56页/共165页数据表示和数据结构的关系数据表示是数据结构的一个子集，面向硬件；数据结构是数据的组织方式，面向软件和应用由算法和软件实现两者的映射。数据结构数据表示软硬件界面数据结构和数据表示是软硬件的界面第57页/共165页结论：数据结构的发展总是优于机器的数据表示系统结构设计者的任务：从优化设计的角度，确定软硬件的分界面，哪些数据类型用数据表示来实现，哪些数据类型用数据结构来实现，应能对新型的数据结构提供更多更好的支持。第58页/共165页2.3 2.3 寻址方式与指令格式的优化设计寻址方式分析程序定位技术指令格式的优化设计第59页/共165页 寻址

30、方式：是指令按什么方式寻找（访问）到所 需的操作数或信息。指令所访问的数据 主存、寄存器、堆栈 寻址能力的要求 多样性、灵活性、寻址空间范围大小、地址变换速度 目标：以最短的位描述给定的寻址方式2.3.1 寻址方式分析1.1.设置寻址方式的目标设置寻址方式的目标第60页/共165页寻址方式在指令中的指明方式占用操作码位：DJS200DJS200系列指令系统中8 8位操作码最高两位：间接（1111）和直接（0101）地址码设置寻址方式字段：VAX-11VAX-11指令中源和目的各有4 4位寻址方式位字段第61页/共165页主存直接、间接、变址、基址、相对寻址 直接寻址使指令字变长 间接寻址使指令

31、执行速度变慢 相对寻址用于条件转移指令中定位转向后代码的位置 变址寻址支持向量、数组，实现循环，用寄存器做变址器，地址码部分不会很长，访问数据速度相当于一次访问内存的速度 基址寻址支持逻辑地址到物理地址的变换，用于程序的动态再定位；2.2.寻址方式第62页/共165页寄存器直接、间接寻址以寄存器寻址方式为主的计算机称为通用寄存器型计算机优点：-指令字长短 -执行速度快 -支持向量、矩阵运算缺点：-不利于编译程序的设计 -不利于中断和子程序的递归调用 -增加了硬件的复杂度第63页/共165页堆栈堆栈寻址（只对栈顶元素进行操作）特点：程序所占主存空间小，指令长度短 支持程序的嵌套和递归调用，支持中

32、断处理 支持高级语言编译第64页/共165页面向主存：主要访问内存，少量访问寄存器op m1 m2op m1 m2面向通用寄存器：多数在寄存器，少量在内存op r m op r m、op r1 r2op r1 r2面向堆栈：主要在堆栈，可减轻编译负担opop、op m op m、op rop r(2)(2)寻址方式分类 大多数采用分类编址，有三类：第65页/共165页 存储效率：堆栈型 通用寄存器型 程序占用空间小 利于减轻对高级语言编译的负担 支持子程序嵌套、递归调用 省去大量地址码字段，省空间 运算速度：堆栈型通用寄存器型 堆栈访存次数过多 面向寄存器方式支持向量、矩阵 一般在系统中三类寻

33、址方式都应当采用3.3.比较：第66页/共165页 寻址方式分析多种寻址方式可以显著减少程序的指令条数，但这同时也可能增加实现的复杂度和使用这些寻址方式的指令的执行时钟周期数(CPI)(CPI)，故需对多种寻址方式进行分析第67页/共165页2.3.2 2.3.2 程序定位技术逻辑地址：程序员编写程序时使用的地址物理地址：程序在主存中的实际地址一般来讲，逻辑地址的空间大于物理地址的空间。因此，映射实际上是压缩。l程序定位技术直接定位：程序装入前，编译时就已确定了程序中的指令和数据的主存物理地址静态再定位：程序装入时，由定位装入程序把程序的逻辑地址变换成物理地址，而在程序的执行过程中，物理地址不

34、再改变。第68页/共165页动态再定位：在执行每条指令时才形成访存物理地址的方法。通过基址寻址来实现基址寄存器内存逻辑地址用户程序第69页/共165页优点：提高了主存利用率主存中的同一个程序段可为多个程序共享支持虚拟存储器问题：需要硬件支持，虚拟存储器的软件管理算法也较复杂第70页/共165页2.3.3 指令格式的优化设计指令 =操作码 +地址码指令格式的优化：如何用最短的位数来表示指令的操作信息和地址信息，使程序中指令的平均字长最短主要目标节省程序的存储空间指令格式尽量规整，便于译码1.操作码的优化设计第71页/共165页操作码主要包括两部分内容操作种类：加减乘除、数据传送、移位、转移、I/

35、OI/O操作数描述：数据类型：定点、浮点、字符（串）、逻辑数、向量进位制：2 2、1010、1616进制数据字长：字、半字、双字、字节地址码通常包括三部分内容地址:直接、间接地址、立即数、寄存器编号、变址寄存器编号地址的附加信息:偏移量、块长度、间距寻址方式:直接、间接、立即数、变址、相对寄存器寻址第72页/共165页操作码的三种编码方法固定长度:规整性好,解码简单,占用空间大HuffmanHuffman编码:空间小,规整性不好,解码复杂扩展编码:折衷方案哈夫曼(Huffman)(Huffman)压缩概念当各种事件发生的概率不均等时,采用优化技术对发生概率较高的事件用较短的位数(时间)来表示(

36、处理),),而对出现概率较低的允许用较长的位数(时间)来表示(处理),),以达到平均位数最少的目的用于代码压缩、程序压缩、空间压缩和时间压缩用于代码压缩、程序压缩、空间压缩和时间压缩第73页/共165页操作码的优化表示信息源熵：信息源包含的平均信息量操作码的优化表示就是要使信息冗余量R最小H即为操作码可以达到的最短平均码长信息冗余量实际编码的操作码码长为：第74页/共165页例1.1.七条指令，频度如下 I1 I2 I3 I4 I5 I6 I7 I1 I2 I3 I4 I5 I6 I7 0.4 0.3 0.15 0.05 0.04 0.03 0.03 0.4 0.3 0.15 0.05 0.0

37、4 0.03 0.03信息源熵 H=2.17=2.17信息冗余量R=(3-2.17)/3=0.28=28%（1 1）等长编码 可用000000110110来分别表示7 7种不同的指令 I1:000I1:000 I2:001 I2:001 I3:010 I3:010 I4:011 I4:011 I5:100 I5:100 I6:101 I6:101 I7:110 I7:110第75页/共165页（2 2）哈夫曼编码（操作码设计）表示方法：哈夫曼树基本思想（频率相关思想）：当事件发生的概率不均等时，对概率高的事件用较短的位数（或时间）来表示，对概率低的事件用较长的位数（或时间）来表示，导致平均位数

38、（时间）最短。第76页/共165页(1)(1)将事件的使用频度值作为叶结点并按出现频率次序排列；（排序）(2)(2)将出现频率最小的两个事件合并（频率相加）形成一个新结点；（合并）(3)(3)在新组成的叶结点序列中继续做(2)(2)，直至到根结点（频率1 1，构成一棵树)；(4)(4)从树根起沿左和右子树分别分配其值为1 1和0 0，直至叶结点；（分配值）(5)(5)事件的使用频度值叶结点编码为从根结点到叶结点的编码组合。（得到编码）构建方法：第77页/共165页10000001110.090.300.601.000.1510.0610.030.03 0.040.050.150.300.40

39、I7 I6 I5 I4 I3 I2 I1I7 I6 I5 I4 I3 I2 I1I1 I2 I3 I4 I5 I6 I7 I1 I2 I3 I4 I5 I6 I7 I1 I2 I3 I4 I5 I6 I7 I1 I2 I3 I4 I5 I6 I7 0.4 0.3 0.15 0.05 0.04 0.03 0.03 0.4 0.3 0.15 0.05 0.04 0.03 0.03 0.4 0.3 0.15 0.05 0.04 0.03 0.03 0.4 0.3 0.15 0.05 0.04 0.03 0.030 10 110 11100 11101 11110 111110 10 110 1110

40、0 11101 11110 11111叶结点根结点合并结点第78页/共165页由此可得到哈夫曼编码如下：由此可得到哈夫曼编码如下：I1:0 I1:0 I2:10 I2:10 I3:110 I3:110 I4:11100 I4:11100 I5:11101 I5:11101 I6:11110 I6:11110 I7:11111I7: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位第79页/共165页HuffmanHuffman特点:-平均码长

41、最短 -代码不唯一 ：（0,1 0,1 可对换）（3 3）哈夫曼扩展编码（操作码优化）扩展编码法基本思想：对霍夫曼编码，根据使用频率宏观分布，将编码长度扩展成几种长度的编码。实现目标：平均码长接近全哈夫曼码的码长，同时又保持了定长码的规整性。lHuffmanHuffman操作码的主要缺点操作码长度很不规整,硬件译码困难与地址码共同组成固定长的指令比较困难第80页/共165页例1:Huffman1:Huffman用四种长度0,10,110,11100,11101,11110,111110,10,110,11100,11101,11110,111110.4,0.3,0.15,0.05,0.04,0

42、.03,0.030.4,0.3,0.15,0.05,0.04,0.03,0.03扩展哈夫曼编码如下：I1,I2,I3 I1,I2,I3 用两位:00,01,10:00,01,10I4,I5,I6,I7 I4,I5,I6,I7 用四位:1100,1101,1110,1111:1100,1101,1110,1111L L=(0.4+0.3+0.15)*2+(0.05+0.04+0.03+0.03)*4=(0.4+0.3+0.15)*2+(0.05+0.04+0.03+0.03)*4=2.30=2.30位信息冗余量=(2.30-2.20)/2.30=0.0565=5.65%第81页/共165页41

43、1 1 151 1 1 1 10.03I741 1 1 051 1 1 1 00.03I641 1 0 151 1 1 0 10.04I541 1 0 051 1 1 0 00.05I421 031 1 00.15I320 1 2 1 00.30I220 0100.40I1OP长度lihuffman扩展编码OP长度li操作码OP使用哈夫曼编码 频 度（Pi）指 令操作码的扩展（等长扩展）平均码长：2.2 2.3第82页/共165页扩展方法：等长扩展和不等长扩展两种。l等长扩展每次扩展相同的位数 如4-8-124-8-12等长扩展方法（每次扩展4 4位）l不等长扩展每次扩展不同的位数 如4-6-

44、104-6-10不等长扩展方法(美国的B-1700)B-1700)扩展标志：保留码点标志一组编码作为扩展标志 保留标志位一个标志位作为扩展标志扩展编码中选择某些特征位用于扩展。第83页/共165页0001000011101500000001.1110151111.11111111.000000011110151111.11111111.111111111111.80 0000 001.0 111641 0001 001.1 1115121 0001 001.1 1110 0000 0010 1111 0001 0011 1110 0000 0010 111.15/15/15扩展法8/64/51

45、2编码法码点标志码点标志保留标志位保留标志位4-8-12等长扩展编码第84页/共165页采用保留特征码（码点标志）方法编码简单，但表示的指令总数少。例如：4-8-12等长编码，15-15-15每种长度指令数为15，共可编码45种平均每条指令位数=(4812)15/45=8采用保留标志位方法编码较为复杂，但表示的指令总数多。例如：4-8-12等长编码，8-64-512共有指令数为584平均每条指令位数（8464851212）/584=11.45第85页/共165页 例2 2：指令系统共有4242种指令，前1515种使用频率平均为0.050.05，中间1313种使用频率平均为0.0150.015，

46、最后1414种使用频率平均为0.0040.004。如何编码？00000000 ：1515种111011101111 00001111 0000 ：1515种1111 11101111 11101111 1111 00001111 1111 0000 ：1515种1111 1111 11101111 1111 1110解：因频率分布有三种，故解：因频率分布有三种，故码长可有三种；码长可有三种；因每段指令数基本相同，故可采用等长扩展(4-8-12(4-8-12位)，保留特征码的每段指令数相同(15-15-15)(15-15-15)方法。结果如图所示；结果：采用15-15-1515-15-15扩展方

47、法，最后一种编码用于扩展，每段0000000011101110用于编码，11111111用于扩展。第86页/共165页 例3 3：指令系统共有7474种指令，前4 4种使用频率平均为0.120.12，中间1515种使用频率平均为0.020.02，最后5555种使用频率平均为0.0040.004。如何编码？解：同上例方法，码长可有三种；因每段指令数成比例(1(1：4)4)，故可采用等长扩展方法(3-6-9(3-6-9位)扩展，保留标志位方法，结果如图所示；结果：采用4-16-64扩展方法，编码第一位用于扩展，每段0XX用于编码，1XX用于扩展。0 xx 40 xx 4种1xx 0 xx 161x

48、x 0 xx 16种1xx 1xx 0 xx 641xx 1xx 0 xx 64种 4-16-64 4-16-64平均码长 =0.12*4*3+0.02*15*6+0.004*55*9=5.22=0.12*4*3+0.02*15*6+0.004*55*9=5.22；第87页/共165页 例4 4：指令系统共有7878种指令，前1010种使用频率平均为0.0490.049，中间1818种使用频率平均为0.020.02，最后5050种使用频率平均为0.0030.003。如何编码？解：同上例方法，码长可有三种；因每段指令数比例为1 1：2 2：5 5，故不可采用等长扩展，采用不等长编码(4-6-10

49、(4-6-10位)较能减少平均码长。00000000 ：1010种100110011010 001010 00 ：2020种1110 111110 111111 00 00001111 00 0000 ：6464种1111 11 11111111 11 1111 第一种采用4 4位编码中前1010种(0000-1001)(0000-1001)；第二种采用第一种频率编码中的后5 5种编码(1010-1110)(1010-1110)与扩展的2 2位共2020种编码；第三种采用第一种频率编码中的最后一种(1111)(1111)与扩展的6 6位共6464种编码。第88页/共165页 有了操作码的优化表

50、示之后，必须有地址码的相应配合，才能使整个指令字格式优化表示。操作数地址码长度和个数可在很宽的范围内变化，只要恰当安排就可与变长操作码很好合成定长指令。地址码的优化第89页/共165页整数边界存储保证访存速度造成浪费多种指令长度，有些指令出现跨越边界存储而需要两个主存周期的情况，会使机器速度明显下降。第90页/共165页(1)多种地址制：要使操作码的长度因优化而缩短的空位充分利用，通过改变指令字中地址码的个数，以使单地址、双地址、三地址和零地址都可以在指令中使用。操作码地址码地址码操作码操作码地址码 地址码一地址制三地址制二地址制地址码操作码零地址制地址码第91页/共165页(1)(1)多种寻