《《计算机系统结构》电子教案(清华2版).ppt》由会员分享，可在线阅读，更多相关《《计算机系统结构》电子教案(清华2版).ppt（170页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、计算机系统结构主讲：华中科技大学计算机学院林安主讲：华中科技大学计算机学院林安教学计划教学计划 教材：教材：计算机系统结构（第二版）计算机系统结构（第二版）郑纬民等郑纬民等清华大学出版社清华大学出版社 参考书：参考书：计算机系统结构复习与考试指导计算机系统结构复习与考试指导郑纬民等郑纬民等高等教育出版社高等教育出版社总学时：总学时：4040第第1 1章：章：2 2第第2 2章：章：4 4第第3 3章：章：6 6第第4 4章：章：4 4第第5 5章：章：6 6第第6 6章：章：2 2第第7 7章：章：6 6第第8 8章：章：2 2第第9 9、1010章：章：2 2习题课：习题课：4 4复习课：复
2、习课：2 22006.3.202计算机系统结构第一章第一章 基本概念（基本概念（P1P1）本章介绍计算机系统结构的一些基本知识。包括定性知识和定量知本章介绍计算机系统结构的一些基本知识。包括定性知识和定量知识两大组内容。为了便于学习，本章各节重新编号，与教材编号不同。识两大组内容。为了便于学习，本章各节重新编号，与教材编号不同。定性知识定性知识：本课程经常使用的一些名词概念，以及对计算机的定性：本课程经常使用的一些名词概念，以及对计算机的定性认识、分析方法。认识、分析方法。定量知识定量知识：对计算机性能进行定量评价的几个重要公式。：对计算机性能进行定量评价的几个重要公式。2006.3.203计
3、算机系统结构 1.1.1 1.1.1 什么是计算机系统结构？（什么是计算机系统结构？（P4P4）别名：计算机体系结构，英文名：别名：计算机体系结构，英文名：Computer ArchitectureComputer Architecture（其中其中 Architecture Architecture 的原义是的原义是“建筑学建筑学”）学科定义学科定义：提高计算机性能的系统理论：提高计算机性能的系统理论特点：特点：综合性：将硬、软件统一考虑，整体优化，强调功能效果（因为计算机是一种工具），偏综合性：将硬、软件统一考虑，整体优化，强调功能效果（因为计算机是一种工具），偏重于硬件；重于硬件；结构性
4、：与微电子学扮演的角色不同，它不研究器件性能，而研究系统的结构，特别是并结构性：与微电子学扮演的角色不同，它不研究器件性能，而研究系统的结构，特别是并行处理结构，即通过时间重叠分配来缩短程序执行时间；行处理结构，即通过时间重叠分配来缩短程序执行时间；定量性：用数学建模方法，尽可能精确地计算各种技术的性能高低。定量性：用数学建模方法，尽可能精确地计算各种技术的性能高低。1.1 1.1 定性知识定性知识几个基本概念几个基本概念2006.3.204计算机系统结构实体定义实体定义：广义定义：使用者必须了解的机器外部特性知识广义定义：使用者必须了解的机器外部特性知识 狭义定义：低级语言程序员必须了解的机
5、器外部特性知识。狭义定义：低级语言程序员必须了解的机器外部特性知识。（这里的（这里的“外部外部特性特性”特指整个硬件的外部特性）特指整个硬件的外部特性）（注：速度（注：速度/运行时间不属于系统结构，因为只看最终运算结果）运行时间不属于系统结构，因为只看最终运算结果）透明性概念透明性概念：使用者可以不了解的知识。使用者可以不了解的知识。（意义：让一部分技术透明，可使同一种功能容纳多种实现方法）（意义：让一部分技术透明，可使同一种功能容纳多种实现方法）附：附：“计算机系统结构计算机系统结构”学科定义的学科定义的3个版本个版本 版本版本1：合理分配硬软件分工的方法；：合理分配硬软件分工的方法；版本版
6、本2：程序员必须了解的硬件知识；：程序员必须了解的硬件知识；版本版本3：提高计算机性能的理论。：提高计算机性能的理论。（意义：目前流行的主要技术，都属于并行处理类型，即通过时间重叠分布来缩短总执行时间。（意义：目前流行的主要技术，都属于并行处理类型，即通过时间重叠分布来缩短总执行时间。课文各章都体现了这一点）课文各章都体现了这一点）计算机系统结构的广义、狭义定义计算机系统结构的广义、狭义定义2006.3.205计算机系统结构“计算机系统结构计算机系统结构”狭义定义包含的内容（狭义定义包含的内容（P4）1.1.数据表示（硬件能够直接识别和处理的数据类型和格式等）；数据表示（硬件能够直接识别和处理
7、的数据类型和格式等）；2.2.寻址方式（包括最小寻址单位、寻址方式的种类、表示和地址计算等）；寻址方式（包括最小寻址单位、寻址方式的种类、表示和地址计算等）；3.3.寄存器组织（包括各种寄存器的配置数目和功能定义）；寄存器组织（包括各种寄存器的配置数目和功能定义）；4.4.指令系统（包括机器指令的操作类型和格式、指令间的排序方式和控制机指令系统（包括机器指令的操作类型和格式、指令间的排序方式和控制机构等）；构等）；5.5.存储系统（包括编址方式、存储容量、最大编址空间等）；存储系统（包括编址方式、存储容量、最大编址空间等）；6.6.中断机构（中断源的分类管理和中断服务功能设计）；中断机构（中断
8、源的分类管理和中断服务功能设计）；7.7.机器工作状态（如管态、目态等）的定义和切换；机器工作状态（如管态、目态等）的定义和切换；8.8.输入输入/输出子系统结构与管理；输出子系统结构与管理；9.9.信息保护手段及其实现。信息保护手段及其实现。2006.3.206计算机系统结构第第5级级 专用应用语言机器专用应用语言机器 特定应用用户特定应用用户 （使用特定应用语言）（使用特定应用语言）（经应用程序翻译成高级语言）（经应用程序翻译成高级语言）第第4级级 通用高级语言机器通用高级语言机器 高级语言程序员（使用通用高级语言）高级语言程序员（使用通用高级语言）（经编译程序翻译成汇编语言）（经编译程序
9、翻译成汇编语言）第第3级级 汇编语言机器汇编语言机器 汇编语言程序员（使用汇编语言）汇编语言程序员（使用汇编语言）（经汇编程序翻译成机器语言、操作系统原语）（经汇编程序翻译成机器语言、操作系统原语）第第2级级 操作系统语言机器操作系统语言机器 操作系统用户操作系统用户 （使用操作系统原语）（使用操作系统原语）（经原语解释子程序翻译成机器语言）（经原语解释子程序翻译成机器语言）第第1级级 传统机器语言机器传统机器语言机器 传统机器程序员（使用二进制机器语言）传统机器程序员（使用二进制机器语言）（由微程序解释成微指令序列）（由微程序解释成微指令序列）第第0级级 微指令语言机器微指令语言机器 微指令
10、程序员微指令程序员 （使用微指令语言）（使用微指令语言）（由硬件译码器解释成控制信号序列）（由硬件译码器解释成控制信号序列）图图1.1 计算机系统的多级层次模型计算机系统的多级层次模型1.1.2 1.1.2 计算机系统的多级层次模型（计算机系统的多级层次模型（P3）2006.3.207计算机系统结构1.1.3 1.1.3 其他重要名词概念（自学）其他重要名词概念（自学）计算机组成计算机组成 计算机系统结构的逻辑实现。（计算机系统结构的逻辑实现。（P5P5）计算机实现计算机实现 计算机组成的物理实现。计算机组成的物理实现。（P5P5）计算机系统设计的计算机系统设计的3 3种主要方法种主要方法：“
11、由下往上由下往上”、“由上往下由上往下”、“由中由中间开始间开始”。（。（P14P14）系列机系列机 （P23P23）兼容性兼容性 （P24P24）模拟模拟 （P24P24）仿真仿真 （P24P24）虚拟机虚拟机 （P24P24）宿主机宿主机 （P24P24）并行性并行性 求解一个问题的若干操作在时间安排上的可重叠性。求解一个问题的若干操作在时间安排上的可重叠性。2006.3.208计算机系统结构1.1.4 1.1.4 冯冯.诺依曼（诺依曼（Von NeumannVon Neumann）型机器的特点（型机器的特点（P22P22）传统计算机又称为冯传统计算机又称为冯.诺依曼型机器，它由运算器、控
12、制器、存储器、输诺依曼型机器，它由运算器、控制器、存储器、输入设备和输出设备入设备和输出设备5 5部分组成，并具有如下特点：部分组成，并具有如下特点：1.1.以运算器为数据流动中枢，以控制器为控制命令中枢；以运算器为数据流动中枢，以控制器为控制命令中枢；2.2.存储程序并且执行，程序象数据一样可以修改；存储程序并且执行，程序象数据一样可以修改；3.3.存储器按地址访问，线性顺序编址；存储器按地址访问，线性顺序编址；4.4.程序顺序执行；程序顺序执行；5.5.指令由操作码与操作数两部分组成；指令由操作码与操作数两部分组成；6.6.数据用二进制编码；数据用二进制编码；7.7.机器由硬件与软件组成，
13、硬件功能不能改变。机器由硬件与软件组成，硬件功能不能改变。2006.3.209计算机系统结构1.1.5 1.1.5 现代计算机系统的分类（现代计算机系统的分类（FlynnFlynn分类法，分类法，P6P6）按照指令流和数据流的多倍性状况把计算机分为：按照指令流和数据流的多倍性状况把计算机分为：1.1.单指令流单数据流（单指令流单数据流（SISD-Single Instruction Stream Single Data SISD-Single Instruction Stream Single Data StreamStream）2.2.单指令流多数据流（单指令流多数据流（SIMD-Singl
14、e Instruction Stream Multiple SIMD-Single Instruction Stream Multiple Data StreamData Stream）3.3.多指令流单数据流（多指令流单数据流（MISD-Multiple Instruction Stream Single MISD-Multiple Instruction Stream Single Data StreamData Stream）4.4.多指令流多数据流（多指令流多数据流（MIMD-Multiple Instruction Stream Multiple MIMD-Multiple Inst
15、ruction Stream Multiple Data StreamData Stream）思考题（不交）：思考题（不交）：P32，题题7，题，题8，题，题9。2006.3.2010计算机系统结构1.2 1.2 定量知识定量知识33个性能公式个性能公式1.2.1 1.2.1 AmdahlAmdahl定律（加快经常性事件原理，定律（加快经常性事件原理，P9P9）其中：其中：S Sn n 全局加速比；全局加速比；T To o 原执行时间（原执行时间（oldold）；）；T Tn n 新执行时间（新执行时间（newnew）；）；S Se e 被改进部分的局部加速比；被改进部分的局部加速比；F Fe
16、 e 被改进部分原执行时间占原来总时间的百分比。被改进部分原执行时间占原来总时间的百分比。2006.3.2011计算机系统结构AmdahlAmdahl定律的推导定律的推导2006.3.2012计算机系统结构AmdahlAmdahl定律的图形定律的图形 从从图图1.21.2可可以以看看出出，增增大大SeSe和和FeFe对对SnSn都都有有提提升升作作用用；但但当当FeFe固固定定时时，一味增大一味增大SeSe对对SnSn的作用会越来越不显著。的作用会越来越不显著。2006.3.2013计算机系统结构AmdahlAmdahl定律的意义定律的意义 Amdahl定律指出，在局部改进力度定律指出，在局部
17、改进力度Se相同的情况下，选择原来最费时间相同的情况下，选择原来最费时间（即（即Fe最大）的工作内容作为改进对象，可以获得最大的全局改进效果最大）的工作内容作为改进对象，可以获得最大的全局改进效果Sn。所以可以认为，所以可以认为，Amdahl定律（加快最费时间的事件）是经济学的定律（加快最费时间的事件）是经济学的“烂桶烂桶板原理板原理”（木桶的最大盛水量由最短的桶板决定，要增加木桶盛水量，必（木桶的最大盛水量由最短的桶板决定，要增加木桶盛水量，必须将短木板加长）的一个定量化诠释。须将短木板加长）的一个定量化诠释。2006.3.2014计算机系统结构1.2.2 1.2.2 CPICPI与程序执行
18、时间与程序执行时间TeTe（P11P11）CPI是衡量是衡量CPU执行指令效率的重要指标。让我们先考虑一个标准测执行指令效率的重要指标。让我们先考虑一个标准测速程序的全部执行时间速程序的全部执行时间Te和其中所有第和其中所有第i种指令的累计时间种指令的累计时间Ti，易知易知2006.3.2015计算机系统结构1.2.3 1.2.3 每秒百万指令数每秒百万指令数MIPSMIPS与每秒百万浮点数与每秒百万浮点数MFLOPSMFLOPS（P11P11）2006.3.2016计算机系统结构本章小结本章小结 本章从定性知识和定量知识两个方面介绍计算机系统结构的基本概本章从定性知识和定量知识两个方面介绍计
19、算机系统结构的基本概念。有关重点如下：念。有关重点如下：(1)计算机系统结构的广义定义与狭义定义（计算机系统结构的广义定义与狭义定义（9项内容），计算机系统项内容），计算机系统结构与计算机组成的主要分工；结构与计算机组成的主要分工；(2)计算机系统的多级层次模型（计算机系统的多级层次模型（6级），以及基于该模型的透明性判级），以及基于该模型的透明性判断方法；断方法；(3)计算机实现、计算机系统设计的主要思路、模拟、仿真、虚拟机、计算机实现、计算机系统设计的主要思路、模拟、仿真、虚拟机、宿主机、系列机、兼容性、并行性等重要名词的含义；宿主机、系列机、兼容性、并行性等重要名词的含义；(4)冯冯.诺
20、依曼型机器的诺依曼型机器的7个特点；个特点；(5)现代计算机系统分类的现代计算机系统分类的Flynn法（法（4类）；类）；(6)Amdahl定律；定律；(7)平均周期数平均周期数CPI公式，程序执行时间公式，程序执行时间Te公式；公式；(8)每秒百万指令数每秒百万指令数MIPS公式，每秒百万浮点数公式，每秒百万浮点数MFLOPS公式。公式。习题：习题：P33，题题12（快（快2020倍就是倍就是Se=20Se=20），题题15，题，题19。2006.3.2017计算机系统结构第二章第二章 指令系统（指令系统（P36P36）本章介绍指令系统设计中本章介绍指令系统设计中2 2个最基本的内容：个最基
21、本的内容：数据表示数据表示、操作码优操作码优化化。2.1 2.1 数据表示数据表示 数据表示数据表示 就是计算机硬件能够直接辨认与处理的数据类型。就是计算机硬件能够直接辨认与处理的数据类型。人们通常使用的数据类型有整数、实数、逻辑数（布尔数）、字符串、人们通常使用的数据类型有整数、实数、逻辑数（布尔数）、字符串、队列、堆栈、链表、文件等，它们的运算方法各不相同。队列、堆栈、链表、文件等，它们的运算方法各不相同。所谓所谓“硬件能够直接辨认与处理硬件能够直接辨认与处理”，指的是对该数据类型的各种运，指的是对该数据类型的各种运算操作都有相应的实现硬件电路。算操作都有相应的实现硬件电路。硬件不能直接辨
22、认与处理的数据类型就要根据数据结构的知识编制硬件不能直接辨认与处理的数据类型就要根据数据结构的知识编制软件转化为硬件能处理的数据类型。软件转化为硬件能处理的数据类型。下面介绍通用型计算机数据表示集合中的一个基本成员下面介绍通用型计算机数据表示集合中的一个基本成员 浮点浮点数据的分析与设计。数据的分析与设计。2006.3.2018计算机系统结构2.1.1 2.1.1 浮点数据表示（浮点数据表示（P38P38，P39P39）浮点数据就是高级语言课程中所说的浮点数据就是高级语言课程中所说的“实型数实型数”。2.1.1.1 2.1.1.1 浮点数的组成浮点数的组成 浮点数的组成与人们通常所说的浮点数的
23、组成与人们通常所说的“科学记数法科学记数法”非常相似，唯一不同的是各部分非常相似，唯一不同的是各部分均为有限位数，如下所示均为有限位数，如下所示它的主要参数有它的主要参数有8 8个：个：m m 尾数，一般为纯小数，符合规格化原则（即最高位的绝对值不为尾数，一般为纯小数，符合规格化原则（即最高位的绝对值不为0 0），），用原码或补码表示；用原码或补码表示；e e 阶码，整数，常用移码表示（见下文解释）；阶码，整数，常用移码表示（见下文解释）；r rm m 尾数的基值，简称尾基，常见的有尾数的基值，简称尾基，常见的有2 2进制、进制、8 8进制、进制、1616进制、进制、1010进制等，进制等，选
24、定以后不变；选定以后不变；r re e 阶码的基值，简称阶基，目前都采用阶码的基值，简称阶基，目前都采用2 2，也是选定以后不变；，也是选定以后不变；p p 尾数的位数，未将符号位计入；尾数的位数，未将符号位计入；q q 阶码的位数，未将符号位计入。阶码的位数，未将符号位计入。m mf f 尾数的符号，表示数的正负，简称数符；尾数的符号，表示数的正负，简称数符；e ef f 阶码的符号，表示阶码的正负，简称阶符。但对移码表示来说，这仅仅阶码的符号，表示阶码的正负，简称阶符。但对移码表示来说，这仅仅是额外的是额外的1 1位位2 2进制数，不决定正负。进制数，不决定正负。2006.3.2019计算
25、机系统结构移码（移码（P41P41）移移码码是是一一种种2 2进进制制记记数数方方法法，它它的的真真值值等等于于相相同同编编码码的的无无符符号号数数加加上上一一个个指指定定的的偏偏移移量量d d。例例如如，同同样样是是2 2进进制制编编码码000000 000000 111111111111，看看作作6 6位位无无符符号号数数时时的的取取值值范范围围是是0 0 63 63，而看作，而看作6 6位移位移-10-10码的取值范围就是码的取值范围就是 10 10 53 53。如下图所示。如下图所示。移移码码是是一一种种有有符符号号数数，但但它它的的最最高高位位通通常常不不决决定定数数的的正正负负，不
26、不应应称称为为符符号号位位。它它的的独独特特之之处处在在于于其其最最小小取取值值的的2 2进进制制编编码码是是全全0 0，这这给给机机器器零零的的判判断断和和处处理理电电路路设设计计带带来来很大方便。很大方便。2006.3.2020计算机系统结构2.1.1.2 2.1.1.2 浮点数的机内格式（浮点数的机内格式（P39P39）一一种种浮浮点点数数中中每每个个数数据据的的尾尾基基r rm m、阶阶基基r re e都都是是相相同同的的，在在设设计计运运算算电电路路已已经经作作为为默默认认值值来来使使用用，各各个个具具体体数数据据在在存存储储时时只只需需要要存存入入如下参数即可：如下参数即可：200
27、6.3.2021计算机系统结构2.1.1.3 2.1.1.3 浮点数的性能（浮点数的性能（P38P38）浮点数的性能主要用浮点数的性能主要用表数范围表数范围、表数精度表数精度和和表数效率表数效率来刻画，下面分别进行分析。来刻画，下面分别进行分析。(1)(1)表数范围（表数范围（P39P39）表表数数范范围围由由这这样样一一些些参参数数构构成成：最最小小负负数数、最最大大负负数数、最最小小正正数数、最最大大正正数数、最小绝对值最小绝对值|N|N|minmin、最大绝对值最大绝对值|N|N|maxmax。它们几何意义可以在数轴上表示，如下图。它们几何意义可以在数轴上表示，如下图。图中阴影部分为浮点
28、数的表数范围。图中阴影部分为浮点数的表数范围。根根据据浮浮点点数数的的组组成成表表达达式式可可知知，图图2.32.3中中4 4个个边边界界值值分分别别由由尾尾数数m m、阶阶码码e e各各自自的的边界值两两组合而成，如下所示。边界值两两组合而成，如下所示。最大正数最大正数 最大正尾数最大正尾数/最大阶码；最大阶码；最小正数最小正数 最小正尾数最小正尾数/最小阶码；最小阶码；最大负数最大负数 最大负尾数最大负尾数/最小阶码；最小阶码；最小负数最小负数 最小负尾数最小负尾数/最大阶码。最大阶码。2006.3.2022计算机系统结构对规格化浮点数，尾数为原码，阶码为移对规格化浮点数，尾数为原码，阶码
29、为移 码，写出表数范围。（码，写出表数范围。（P40）解：由于原码在数轴的零点两边对称分布，即最大正数与最小负数的绝对值相解：由于原码在数轴的零点两边对称分布，即最大正数与最小负数的绝对值相等、最小正数与最大负数的绝对值相等，所以可以用最小、最大绝对值来描述等、最小正数与最大负数的绝对值相等，所以可以用最小、最大绝对值来描述它的分布。它的分布。首先根据图首先根据图2.22.2和式和式2.12.1以及移码的基本定义，可以确定绝对值的极值表达式：以及移码的基本定义，可以确定绝对值的极值表达式：例例2.12.1写在一起就是：写在一起就是：再用阶码的偏移量代换式中的再用阶码的偏移量代换式中的-d d得
30、：得：2006.3.2023计算机系统结构可以代入具体数字来帮助理解：可以代入具体数字来帮助理解：2006.3.2024计算机系统结构 显然它随着阶码显然它随着阶码e ek k增大而增大而迅速增大，即在不同区间里迅速增大，即在不同区间里 会有不同的值会有不同的值。表数精度表数精度用最大表数误差表示（指相对误差用最大表数误差表示（指相对误差）。而计算相对误差之前先要计算绝对误差。）。而计算相对误差之前先要计算绝对误差。最大绝对误差最大绝对误差是是真实值与可表示值之间的可真实值与可表示值之间的可能最大距离，按能最大距离，按“舍入法舍入法”它等于相邻两个可表它等于相邻两个可表示值间距的示值间距的1/
31、2，如图，如图2.4所示。所示。根据浮点数的组根据浮点数的组成式成式，可以写出任一对邻点，可以写出任一对邻点Nk与与Nk+1之间的区间之间的区间内内最最大大绝绝对对误误差差为为（为为了了简简便便，可可先先假假设设Nk与与Nk+1的的阶阶码码相相同同来来推推导导，其其实实阶码不同的结果也一样）阶码不同的结果也一样）(2)(2)表数精度（表数精度（P42P42）2006.3.2025计算机系统结构最大相对误差最大相对误差与阶码与阶码e e无关，但与尾数无关，但与尾数m m的值有关。的值有关。按相对误差基本定义，上述区间内的最大相对误差为按相对误差基本定义，上述区间内的最大相对误差为 同样同样 也不
32、是常数，各区间内并不一致，只是它受的是尾数也不是常数，各区间内并不一致，只是它受的是尾数 的影响。的影响。为了找到所有区间中最大的为了找到所有区间中最大的 （即全局最大相对误差（即全局最大相对误差 ），我们应取分），我们应取分母母 的最小值。从上文已知尾数取值范围的最小值。从上文已知尾数取值范围 ，这样就能得到，这样就能得到2006.3.2026计算机系统结构(3)(3)表数效率（表数效率（P45P45）定义：定义：此此式式说说明明效效率率之之所所以以低低于于100%100%，是是因因为为规规格格化化的的尾尾数数最最高高位位m m1 1只只能能有有r rm m-1-1种取值的缘故。可以看出，种
33、取值的缘故。可以看出，的极小值与极大值分别是的极小值与极大值分别是 隐藏位技术隐藏位技术 是一种提高表数效率的方法，但仅适用于是一种提高表数效率的方法，但仅适用于r rm m=2=2的情况：的情况：尾数最高位尾数最高位m m1 1 在二进制条件下只有在二进制条件下只有0 0和和1 1两种可能，按照规格化要求，两种可能，按照规格化要求，m m1 1 可由其它位推出，。可由其它位推出，。“隐藏隐藏”了了m m1 1之后，尾数只存储后面之后，尾数只存储后面p-1p-1位，位，它们中的任一位都有它们中的任一位都有r rm m种取值，所以表数效率种取值，所以表数效率=100%。2006.3.2027计算
34、机系统结构2.3 2.3 指令格式的优化（指令格式的优化（P90P90）2.3.2 2.3.2 操作码优化操作码优化 目前常用的编码方法有目前常用的编码方法有3 3种：定长编码，种：定长编码，HuffmanHuffman编码，扩展编码。编码，扩展编码。2.3.2.1 2.3.2.1 定长编码定长编码 就是所有指令使用相同的代码位数，其最小码长等于就是所有指令使用相同的代码位数，其最小码长等于式中式中 是平均码长，是平均码长，是第是第i i种指令的码长，种指令的码长，n n是指令总数。是指令总数。例例2.22.2 已知已知 n=15n=15，求定长编码的最小平均码长。求定长编码的最小平均码长。解
35、：解：2006.3.2028计算机系统结构2.3.2.2 2.3.2.2 HuffmanHuffman压缩编码（压缩编码（P91P91）(1)(1)HuffmanHuffman压压缩缩概概念念（最最佳佳编编码码定定理理）：当当用用n n个个长长度度不不等等的的代代码码分分别别代代表表n n种种发发生生概概率率不不等等的的事事件件时时，按按照照短短代代码码给给高高概概率率事事件件、把把长长代代码码给给低低概概率率事件的原则分配，可使平均码长达到最低。事件的原则分配，可使平均码长达到最低。(2)(2)HuffmanHuffman编码方法编码方法 这种编码方法由两个过程组成。这种编码方法由两个过程组
36、成。频频度度合合并并：将将全全部部n n个个事事件件（在在此此即即为为n n条条指指令令）的的频频度度值值排排序序，选选取取其其中中最最小小的的2 2个个频频度度合合并并，然然后后将将剩剩下下的的n-1n-1个个频频度度再再次次排排序序，再再合合并并最最小小的的2 2个个频频度度，如如此此重重复复，直直至至剩剩下下1 1个个频频度度为为止止。记记录录所所有有的的合合并并关关系系，形形成成一一棵棵二二叉叉树树 HuffmanHuffman树树，所所有有原原始始频频度度值值充充当当树树叶叶，而而最最后后剩剩下下的的总频度总频度1 1为树根；为树根；码码元元分分配配：从从树树根根开开始始，对对每每个
37、个中中间间结结点点的的左左右右2 2个个分分支支边边各各赋赋予予一一位位代代码码“0”“0”和和“1”“1”（“0”“0”在在哪哪一一侧侧不不限限）。读读出出从从根根结结点点到到任任一一片片树树叶叶的的路路径径上上依依次次出出现现的的代代码码位位就就排排成成了了这这个个事事件件（即即指指令令）的的完完整整编编码码。由由于于频频度度高高的的事事件件较较晚晚被被合合并并，它它的的编编码码位位数数也也就就较较少少，符符合合HuffmanHuffman压压缩缩原原则。则。上上面面所所说说的的频频度度值值就就是是各各事事件件实实际际出出现现次次数数的的百百分分比比，它它是是理理论论出出现现概概率率的近似
38、值。的近似值。2006.3.2029计算机系统结构2.3.2.3 2.3.2.3 扩展编码方法（等长扩展法，扩展编码方法（等长扩展法，P93P93）用码长表示：例如用码长表示：例如4-8-124-8-12法。这并不能说明具体编码方法，例如法。这并不能说明具体编码方法，例如下面两种编码方法都是下面两种编码方法都是4-8-124-8-12法。法。用码点数表示：例如用码点数表示：例如15/15/1515/15/15法，法，8/64/5128/64/512法法15/15/1515/15/15法，每一种码长都有法，每一种码长都有4 4位可编码位（前头可以有相同位可编码位（前头可以有相同的扩展标识前缀），
39、可产生的扩展标识前缀），可产生1616个码点（即编码组合），但是个码点（即编码组合），但是至多只能使用其中至多只能使用其中1515个来表示事件，留下个来表示事件，留下1 1个或多个码点组合个或多个码点组合作为更长代码的扩展标识前缀。已经用来表示事件的码点组作为更长代码的扩展标识前缀。已经用来表示事件的码点组合不能再作为其它更长代码的前导部分，否则接收者会混淆。合不能再作为其它更长代码的前导部分，否则接收者会混淆。这就是这就是“非前缀原则非前缀原则”。8/64/5128/64/512法，每一种码长按法，每一种码长按4 4位分段，每一段中至少要留下位分段，每一段中至少要留下1 1位或多位作为扩展标
40、识。各段剩下的可编码位一起编码，所位或多位作为扩展标识。各段剩下的可编码位一起编码，所产生的码点用来对应被编码事件。每一段中的标识位指出后产生的码点用来对应被编码事件。每一段中的标识位指出后面还有没有后续段。面还有没有后续段。2006.3.2030计算机系统结构以3-6-9位为例 36bit目标：平均码长最小化 33bit平均码长=P1l1+P2l2+P84l84 30bit 27bit 24bit 21bit 18bit 15bit 12bit 9bit 6bit 3bit7/7/7法码长分布 7条 7条 7条 7条 7条 7条 7条 7条 7条 7条 7条 7条 9bit 6bit 3bi
41、t4/16/64法码长分布 4条 16条 64条指令频度分布悬殊 P1 P84指令频度分布均匀 P1 P84两种等长扩展码适用性比较两种等长扩展码适用性比较2006.3.2031计算机系统结构2.3.2.4 2.3.2.4 编码方法性能指标（编码方法性能指标（P91-P93P91-P93）信息量：根据信息论的基本知识，在信息量：根据信息论的基本知识，在n n种可能发生的事件集合中，报告第种可能发生的事件集合中，报告第i i种事件发生的消息中包含的信息量为种事件发生的消息中包含的信息量为 其其中中P Pi i是是第第i i种种事事件件发发生生的的先先验验概概率率，a a是是编编码码基基值值。信信
42、息息量量的的单单位位是是表表示示位位数（最少所需位数）。数（最少所需位数）。这个定义式表明事件的发生概率越低，关于它的消息中的信息量越大。这个定义式表明事件的发生概率越低，关于它的消息中的信息量越大。熵熵（entropyentropy）平平均均信信息息量量：一一个个消消息息源源对对n n种种事事件件发发布布的的消消息息的的信信息息量平均值，记为量平均值，记为2006.3.2032计算机系统结构 平均码长：各事件编码长度的数学期望。平均码长：各事件编码长度的数学期望。信息冗余量：它表明消息编码中信息冗余量：它表明消息编码中“无用成分无用成分”所占的百分比。所占的百分比。从从减减少少存存储储与与传
43、传输输量量的的角角度度看看，编编码码方方法法的的平平均均码码长长越越短短越越好好。但但是是平平均均码码长长不不可可能能无无限限制制缩缩短短，它它的的下下限限就就是是熵熵（即即R=0R=0时时）。如如果果短短于于熵熵就就一一定会丢失有用信息（即混淆不同指令），这是不允许的。定会丢失有用信息（即混淆不同指令），这是不允许的。2006.3.2033计算机系统结构 例例2.32.3 已知频度序列为已知频度序列为0.10.1，0.10.1，0.150.15，0.150.15，0.20.2，0.30.3，求，求HuffmanHuffman编码、等编码、等长扩展长扩展3/3/33/3/3码、定长编码、三者的
44、平均码长、信息冗余量以及熵。码、定长编码、三者的平均码长、信息冗余量以及熵。解：解：熵熵 H=(20.1log20.1+20.15log20.15+0.2log20.2+0.3log20.3)2.47 根据根据Huffman编码方法作编码方法作Huffman树如图树如图2.5所示，三种编码方法的结果列所示，三种编码方法的结果列于表于表2.1中。中。2006.3.2034计算机系统结构表表2.1 Huffman编码、等长扩展编码、等长扩展3/3/3码及定长编码码及定长编码2006.3.2035计算机系统结构 2.3.3 2.3.3 操作数优化操作数优化寻址方式比较（寻址方式比较（P95P95）指
45、令中操作数占用的位数由操作数的个数与寻址方式决定。指令中操作数占用的位数由操作数的个数与寻址方式决定。按按操操作作数数的的个个数数划划分分，有有零零操操作作数数指指令令、一一操操作作数数指指令令、二二操操作作数数指指令令、三三操操作作数数指指令令共共四四种种形形式式。应应该该按按机机器器用用途途来来选选择择（P99P99，表表2.202.20）。）。缩短操作数长度的常用方法是间址和变址（缩短操作数长度的常用方法是间址和变址（P99P99页末页末）。）。2006.3.2036计算机系统结构 本章主要内容有数据表示和操作码优化两个部分。具体细节如下：本章主要内容有数据表示和操作码优化两个部分。具体
46、细节如下：(1)浮点数的表数范围（在数轴上的浮点数的表数范围（在数轴上的4个端点）、表数精度个端点）、表数精度、表数效率、表数效率；(2)Huffman编码方法；编码方法；(3)等长扩展编码方法（等长扩展编码方法（15/15/15法，法，8/64/512法）；法）；(4)编码方法性能指标（熵编码方法性能指标（熵H，平均码长平均码长L，信息冗余量信息冗余量R）。）。习题：习题：P124，题题3（忽略（忽略P124倒倒1行行 P125第第8行文字），题行文字），题13。本章小结本章小结2006.3.2037计算机系统结构第三章第三章 存储系统（存储系统（P130P130）Memory Memory
47、 HirarchyHirarchy 长期存在的问题：在合理的总价格限制下，单纯性主存设备的速长期存在的问题：在合理的总价格限制下，单纯性主存设备的速度跟不上度跟不上CPUCPU的发展，容量不能满足软件尺寸扩大。的发展，容量不能满足软件尺寸扩大。本章学习两种提高主存系统性能本章学习两种提高主存系统性能/价格比的结构化方法：并行存储价格比的结构化方法：并行存储器与存储层次技术。后者为主。器与存储层次技术。后者为主。2006.3.2038计算机系统结构3.1 3.1 并行存储器（并行存储器（P136P136）并并行行存存储储器器技技术术可可以以提提高高主主存存系系统统的的整整体体等等效效速速度度，实
48、实际际应应用用中中，常将它与存储层次技术组合使用，可以互为补充，获得很高的性能。常将它与存储层次技术组合使用，可以互为补充，获得很高的性能。并并行行存存储储器器技技术术的的基基本本思思想想是是用用多多个个独独立立的的存存储储部部件件组组成成主主存存系系统统，让让它它们们并并行行工工作作，在在一一个个存存储储周周期期内内可可以以访访问问到到多多个个数数据据，从从而实现较高的存取流量。而实现较高的存取流量。并并行行存存储储器器包包括括多多种种类类型型，我我们们仅仅介介绍绍提提高高访访问问速速度度效效果果最最显显著著的的低位交叉访问低位交叉访问这一种。这一种。2006.3.2039计算机系统结构低位
49、交叉访问并行存储器的结构：低位交叉访问并行存储器的结构：它由它由n n个存储体组成（一般个存储体组成（一般n n为为2 2的整次幂），每个体均有独立的地址译的整次幂），每个体均有独立的地址译码器和数据缓冲器，以主存地址低位字段（最低的码器和数据缓冲器，以主存地址低位字段（最低的loglog2 2n n位）作为体选译位）作为体选译码信号，而剩下的高位字段则是体内地址。如图所示（设码信号，而剩下的高位字段则是体内地址。如图所示（设 n=n=4 4）。）。2006.3.2040计算机系统结构主存地址与结构参数的换算（主存地址与结构参数的换算（P139P139）：）：其中：其中：n n 存储体个数，存
50、储体个数，A A 主存地址，主存地址，j j 体内地址，体内地址，k k 体序号（体序号（k=0k=0，1 1，2 2，n-1 n-1）例例3.13.1 已知已知 n=4n=4，问主存地址问主存地址1313是在几号体的几号单元？是在几号体的几号单元？解：解：由由于于 n n=4 4，体体选选译译码码信信号号使使用用主主存存地地址址的的最最低低 loglog2 2n n=2 2位位，所所以以地地址址1313（其其二二进进制制为为11011101B B）对对应应的的体体号号k k=1 1（即即0101B B）、体体内内地地址址j j=3 3（即即1111B B），），也就是说，地址也就是说，地址1